【Wathematicaアドベントカレンダー企画2022】命題論理のコンパクト性と完全性

はじめに
- 導入
定義など
- 文記号、文結合記号
- 真理値割り当て
健全性、完全性
おわりに
おまけ
参考文献

はじめに

こんにちは、かまあげです。うだるような暑さですね。私も茹ってしまいそうです。かまあげだけに。

数学基礎論についてはどのようなイメージをお持ちでしょうか。なんか「不完全性定理」がどうとか、「メタ数学」がどうとか、なんか断片的に聞いたことがあるのではないでしょうか。

「不完全性定理に矛盾するので神は存在しない！！！！！！！」とかいうよくわからない主張(？)を見たことがある人もいるかもしれません。これについては諸般の事情によって触れないことにします。なんか怖いし...

あと、一応この記事に関しては数学の前提知識とかはありません。「いやタイトルからして意味不明だけど」となっているかもしれませんが、説明するので大丈夫です。

加えて、後半に集合論の知識を仮定するパートが存在していますが、まあ別に知らなくても「コンパクト性」って何？「完全性」って何？くらいは理解できるようにしたつもりです。ちゃんと頭からつま先まで知りたいのであれば集合論の本を買いましょう。松坂集合位相とか。買って衝撃の稲妻を走らせましょう。

ちなみに、緩い議論が散見されると思いますが、一応「数学基礎論入門」みたいなノリで書いたので、軽いノリで読んでくれると嬉しいです。興味を持ったら、キューネンとか最近出たエンダートンの訳書とか買って読みましょう。もっとこう、ちゃんと書いてあるので...。

導入

数学基礎論ってなんでしょうか。

いや、私もよく知っているわけではないですが、少なくとも一側面として「証明って何？」ということを掘り下げて考えている、というのがあります。

そしてこの記事では主にその側面について触れます。

一応いうと数学基礎論の守備範囲って結構広いです。まあ公理的集合論と密接にかかわっている部分があるので、そりゃそう、って感じですが...

さて、私たちが数学のいわゆる問題を解くとき、「Aという仮定からBが導けて、BからCが導けるから、Cと仮定Dを合わせてEという結論が...」みたいなことをやっていますね。

他方、「Aでないと仮定すると矛盾するからAは正しくて...」とか、「BでないならばAでないから、AならばBで...」とかもやりますよね。

この前者をいわゆる「モーダス・ポネンス」な推論と言います。ちゃんと書くなら、

P ならば Q である。

P である。

従って、Q である。

という感じ。「導けてるな～」という感じがしますね。

後者はいわゆる「トートロジー的言い換え」とか、まあ単に「トートロジー」とかと言いますね。この用語は後でちゃんと定義しますが、まあ要するに「おんなじこと言ってる」ってことです。「言い換え」です。そしてこの推論そのものはA,Bの内容に関わらず常に正しいですよね。

こういうのを記号列とかを用いて定式化しよう、というのが「数学基礎論」の一側面です。「BならばA」であるというときに「Aである」ことから「Bである」ことを導いたら誤りですよね。数学的に「正しい」推論ってなんだろう、ということを定義してみたいわけです。

定義など

以下、青字の定義は参考文献[1]に基づきます。

文記号、文結合記号

では、様々な用語の解説をしていきましょう。

まず、 $A_1,A_2,\cdots,A_n,\cdots$ を文記号と呼びます。

これには、「リンゴは赤い」とか、「塩化ナトリウムの固体は白い」とか、そういう真偽を判定できる文が入ります。「すべてのリンゴは赤い」とか、そういうことを言っているわけではないことに注意してください。

そして、 $\neg,\land,\lor,\rightarrow,\leftrightarrow$ を文結合記号と呼びます。

順番に、否定、かつ、または、ならば、同値(英語でいうiff)を意味します。

これらは文記号と組み合わせて使います。

たとえば、 $A_1$ に「リンゴは赤い」 $A_2$ に「梨は美味しい」という文が入っているとしましょう。

$A_1\rightarrow A_2$ は「リンゴが赤いなら、梨は美味しい」と翻訳できます。

同様に、 $\neg A_1$ は「リンゴは赤くない」と翻訳できますね。

さらに、区切りとして括弧を導入します。例えば

$\neg A_1\rightarrow A_2$

という記号列を考えてみると、これは

「「 $A_1$ でない」ならば $A_2$ である」

「「 $A_1$ ならば $A_2$ 」でない」

の二つのどちらであるのかよくわかりません。翻訳文で「」を導入しているように、

$(\neg A_1)\rightarrow A_2$

$\neg (A_1\rightarrow A_2)$

とすれば見分けがつきますね。そういうわけで、「()」を区切りとして導入します。

ところで、 $\neg \rightarrow A_1$ を翻訳することはできるでしょうか？

うーん、ちょっと難しいですね。 $\rightarrow$ の両隣には文記号が欲しいです。

つまり、「翻訳できる記号列」「翻訳できない記号列」が存在するわけです。

これを踏まえて、「翻訳できる記号列」として整式を定義します。具体的には、

(a) 個々の文記号は整式である。

(b) $\alpha$ と $\beta$ が整式なら、 $(\neg \alpha), (\alpha\land\beta),(\alpha\lor\beta),(\alpha\rightarrow\beta),(\alpha\leftrightarrow\beta)$ も整式である。

とします。

真理値割り当て

文記号や整式が与えられたとき、それが「正しい」「正しくない」ということをそれぞれに対して返す写像を考えてみましょう。

以下、文記号の集合は $\mathcal{S}$ とし、 $\{F,T\}$ を真理値の集合とします。

真理値は、ここでは要するに個々の文記号に対して「True」「False」を返すものです。

その頭文字をとっているわけですね。そして、 $\mathcal{S}$ の各要素に対して「正しい」「正しくない」を返す写像を以下のように定義しましょう。

$v:\mathcal{S}\rightarrow\{F,T\}$

$A\mapsto T(\text{Aが正しい})$

$A\mapsto F(\text{Aが正しくない})$

これを真理値割り当てと言います。ただ、これだけだと整式に真理値が定まらなくて微妙ですね。でも、でたらめに拡張するとまずそうです。 $v(A_1)=T,v(A_2)=F$ で $v(A_1\rightarrow A_2)=T$ になったら困りますね。というわけで、良い感じのルールを満たした拡張を考えたいわけです。

以下、 $\overline{\mathcal{S}}$ を、 $\mathcal{S}$ から5種類の文記号操作を有限回行って作れるような整式全体の集合とします。硬い言葉(？)を使えば、 $\mathcal{S}$ が5種類の文記号操作によって生成する集合が $\overline{\mathcal{S}}$ です。

$\overline{v}:\overline{\mathcal{S}}\rightarrow\{F,T\}$

を、以下のルールを満たすように定めます。

0. どの $A\in \mathcal{S}$ についても、 $\overline{v}(A)=v(A)$ である。

以下では(任意に) $\alpha,\beta\in\overline{\mathcal{S}}$ とします.

1. $\overline{v}(\neg \alpha)=T$ ( $\overline{v}(\alpha)=T$ のとき)

$\overline{v}(\neg \alpha)=F$ (それ以外の時)

2. $\overline{v}(\alpha\land\beta)=T$ ( $\overline{v}(\alpha)=T$ かつ $\overline{v}(\beta)=T$ のとき)

$\overline{v}(\alpha\land\beta)=F$ (それ以外の時)

3. $\overline{v}(\alpha\lor\beta)=T$ ( $\overline{v}(\alpha)=T$ または $\overline{v}(\beta)=T$ (両方でもよい)のとき)

$\overline{v}(\alpha\lor\beta)=F$ (それ以外の時)

4. $\overline{v}(\alpha\rightarrow\beta)=F$ ( $\overline{v}(\alpha)=T$ かつ $\overline{v}(\beta)=F$ のとき)

$\overline{v}(\alpha\rightarrow\beta)=T$ (それ以外の時)

5. $\overline{v}(\alpha\leftrightarrow\beta)=T$ ( $\overline{v}(\alpha)=\overline{v}(\beta)$ のとき)

$\overline{v}(\alpha\leftrightarrow\beta)=F$ (それ以外の時)

とすればよいです。真理値表を書いてみれば(つまり、T,Fの可能性をすべて書き出して表にまとめてみれば)この定義の妥当性がわかると思います。

そして、もちろんこの真理値割り当ては各 $v$ に対して一意です。直感的にはそれはそう、という感じですが、これをちゃんと証明することはここではしません。実のところ、それだけで一つ記事が書けてしまいますので...

気になる人は再帰定理、などで調べてみるとよいです。一応、定理として書いておきます。

定理１

集合 $\mathcal{S}$ へのどんな真理値割り当て $v$ に対しても、前述の条件 $0~5$ に合致する写像 $\overline{v}:\overline{\mathcal{S}}\rightarrow\{F,T\}$ が存在する。

あと少し、定義を書いておきましょう。

真理値割り当て $\overline{v}$ と整式 $\varphi$ について $\overline{v}(\varphi)=T$ が成り立つとき、 $\varphi$ は $\overline{v}$ を充足すると言います。

$\Sigma$ をとある整式の集合、 $\tau$ を整式とします。 $\Sigma$ が $\tau$ をトートロジー的に含意するとは、 $\Sigma$ と $\tau$ に現れる文記号への真理値割り当てについて、それが $\Sigma$ のすべての要素を充足するなら、 $\tau$ をも充足することを言います。 $\Sigma\vDash\tau$ と書きます。

また、ある整式 $\tau$ が、 $\tau$ に現れる文記号へのどんな真理値割り当てについても $\overline{v}(\tau)=T$ を満たしているとき、 $\tau$ はトートロジーであると言います。 $\varnothing \vDash \tau$ ですね。

健全性、完全性

...さて、ここまで長々と用語の定義をしてきたわけですが、これらを用いて示したいのは「命題論理の完全性」でした。では、健全性と完全性ってそもそも何でしょうか。ここでは一般的な定義を扱うことはしませんが、大雑把に言えば、健全性は「証明できる式は正しい式である」こと、そして完全性は「正しい式は証明できること」となります。ここではこの「証明できる」ことを以下のように定義しましょう。

$\Sigma$ を整式の集合とする。 $\Sigma$ からの演繹とは、

整式の有限列 $\lt\alpha_0,\cdots,\alpha_n\gt$ であって、全ての $k\leq n$ について

(a) $\alpha_k$ はトートロジーである

(b) $\alpha_k\in\Sigma$

( (c)が成立しているとき、 $\alpha_k$ は $\alpha_i$ と $\alpha_k$ からモダス・ポネンスで得られているという)

ある整式 $\tau$ について、 $\Sigma$ からの演繹でその末尾が $\tau$ になるようなものが存在するとき、 $\tau$ は $\Sigma$ の下で証明可能と呼ぶことにする。

一つ例を挙げておきましょう。

問2

$S,P,R$ を文記号とする。

$\Sigma = \{\neg S\lor R, R\rightarrow P, S\}$

からPが証明可能であることを示せ。

答

Pを末尾とする演繹を作ればよい。実際、

$\lt S, (\neg S\lor R), ( (\neg S\lor R)\rightarrow(S\rightarrow R) ),(S\rightarrow R),R,(R\rightarrow P),P\gt$

とすると、各要素は整式であって、

$S \in \Sigma$

$(\neg S\lor R)\in\Sigma$

$( (\neg S\lor R)\rightarrow(S\rightarrow R) )$ : トートロジー

$(S\rightarrow R):\alpha_2:\alpha_1\rightarrow \alpha_3$

$R: \alpha_3:\alpha_0\rightarrow\alpha_4$

$(R\rightarrow P)\in\Sigma$

$P:\alpha_5:\alpha_4\rightarrow\alpha_6$

なので、確かに上記は $\Sigma$ からの演繹となっている。□

次に、以下の命題を示します。

トートロジー的含意が「結論を導いている」ことに対応していることがわかれば、この命題はいわば健全性を示していると言えるでしょう。

命題3

$\lt\alpha_0,\cdots,\alpha_n\gt$ を整式の集合 $\Sigma$ からの演繹とする。

このとき、すべての $k\leq n$ について $\Sigma\vDash\alpha_k$ である。

証明

kについての数学的帰納法によって示す.

$(i)\ k=0$ のとき

$\alpha_0$ は(c)を満たしえないので、 $\alpha_0$ はトートロジーであるか、 $\alpha_0 \in \Sigma$ である。

トートロジーならその真理値は常に $T$ で、 $\alpha_0\in\Sigma$ ならトートロジー的含意の定義から $\Sigma\vDash\alpha_0$

$(ii)$ すべての $k\leq m-1\ (m\in\mathbb{N})$ について $\Sigma\vDash$ を仮定する。

このとき、 $\Sigma\vDash\alpha_m$ を示す。

$\alpha_m$ が(a)か(b)を満たしているときは上記同様にして成立。

$\alpha_m$ が(c)を満たすとき、 $i,j\lt m$ を満たす等式で $\alpha_i:\alpha_j\rightarrow \alpha_m$ となっている。 $i,j\lt m$ より $\Sigma\vDash\alpha_i$ かつ $\Sigma\vDash\alpha_j$ なので、このとき $v(\alpha_m)=T$ である.よって $\Sigma\vDash\alpha_m$ .　□

次に完全性を示すことにしましょう。その前に、少しだけ用語と、定理を紹介しておきます。

整式の集合 $\Sigma$ の要素すべてを充足するような真理値割り当てが存在するとき、 $\Sigma$ は充足可能であると言います。

また、 $\Sigma$ のすべての有限部分集合が充足可能であるとき、 $\Sigma$ は有限充足可能であると言います。

このとき、一見非自明な次の定理が成り立ちます。

定理4　(コンパクト性定理)

整式の集合が充足可能であることと、その整式の集合が有限充足可能であることは同値。

系5 $\Sigma\vDash\tau$ ならば、有限集合 $\Sigma_0\subset\Sigma$ で、 $\Sigma_0\vDash\tau$ を満たすものが存在する。

そして、これらの証明はおまけに回すことにします。(すこし難しいので)

というわけで、これを用いると完全性が次のように示せます。

定理6

$\Sigma\vDash\tau$ であるときは必ず、 $\Sigma$ からの演繹で、その末端が $\tau$ であるものが存在する。

証明

コンパクト性定理の系から、 $\Sigma '=\{\alpha_0,\cdots,\alpha_n\}\subset\Sigma$ であり $\Sigma '\vDash\tau$ となる有限集合 $\Sigma '$ が存在する。

いま整式 $\beta,\gamma$ が演繹の列に存在するとすると、 $(\beta\rightarrow(\gamma\rightarrow(\beta\land\gamma) ) )$ はトートロジーなので、(c)を繰り返し用いると、演繹の列に $(\beta\land\gamma)$ を置くことができる。

つまり $( ( (\alpha_0\land\alpha_1)\land\cdots)\land\alpha_n)$ という整式を演繹の列に置くことができて、ここから $( ( ( (\alpha_0\land\alpha_1)\land\cdots)\land\alpha_n)\rightarrow\tau)$ も置けるので、従う。□

おわりに

なんか最後の証明が短すぎて、「コンパクト性定理が偉いだけでは？」となってしまいそうな気がしています。実際偉いんですが...。

ちなみにこの名前の通り、位相空間論のコンパクト性とのアナロジーがあって、実際位相の言葉を用いてコンパクト性定理を示すことができたりします。(参考文献[4]を参照.)

あとはどんな疑問が残るでしょうか...。「文記号って可算無限個しかないの？」とかでしょうか。これは僕もよくわかってないのですが、そう言える分野とそういえない分野があるような気がしています。そしてこの記事でそれが問題になるのはコンパクト性定理のところでしょうから、一応おまけの証明は可算無限個でなくても対応できるものにしておきました。しかし実際どうなんでしょう。わかる人いたら教えてください。

それともう一つ、これは半分宣伝なんですが、量子論理ってものがあります。

私たちは真理値の集合としてFとTの二元集合を採用したわけですが、これを三つとか、128個とか、可算無限個とか、の集合に拡張したりするらしく、その中の分野の一つに量子論理があるらしいです。誰かがそれで記事を書くというのを風の噂で耳にしたので、書いておきます。

おまけ

コンパクト性定理と、その系を示します。Zornの補題を用います。

定理4(再掲)　(コンパクト性定理)

整式の集合が充足可能であることと、その整式の集合が有限充足可能であることは同値。

証明

$\Rightarrow$ は明らか。 $\Leftarrow$ を示す。

$\Sigma$ を整式の集合として、 $\Sigma$ の任意の有限部分集合が充足可能であるとする。

ここで必ずしも有限でない $\Gamma\subset\Sigma$ をとる。 $\Gamma$ を含み、かつそのすべての有限部分集合が充足可能であるような集合全体の集合に包含によって順序を導入する。これを $\Phi$ とする。 $\Phi$ の任意の全順序部分集合 $\delta$ に対して、 $\Delta=\cup\delta$ としてその要素の和集合を定める。このとき、 $\Delta$ は有限充足可能である。

実際、 $\Delta$ が有限充足可能でない、つまり、ある有限集合 $A=\{A_0,\cdots,A_n\}\subset\Delta$ が存在してAが充足不能なら、各 $A_i$ に対して、 $A_i\in\theta_i$ を満たす $\theta\in\delta$ が存在する。 $\delta$ は全順序部分集合だったので、 $\theta_i$ のうち最大のものを $\theta$ とすると $\Delta\subset\theta$ が成立するが、 $\theta\in\delta$ より $\theta$ は有限充足可能である。よって矛盾。