どうも仮面の数学者です.
気が付いたら一か月以上このBlogを放置していました. ずぼらで申し訳ない......
今回は数学基礎論サマースクール2015にて, 教えてもらった「(命題論理の)コンパクト性定理」を「Tychonoffの定理」から証明する話です. 部屋の大掃除をしていたら, 数学基礎論サマースクール(以下基礎論SS)のときのノートが出てきたので, 自分用のまとめも兼ねて書くことを思い立ちました.
コンパクト性定理とは以下のようなLogicの定理である(この定理に含まれる用語などは後で解説, 定義する).
[コンパクト性定理]
理論$T$に対して次の(1), (2)は同値である.
(1)「$T$はモデルを持つ」
(2)「どんな$T$の有限部分集合もモデルを持つ」
対して, Tychonoffの定理は次のような位相空間についての定理である.
[Tyconoffの定理]
位相空間の族$\left\{S_{\lambda}\right\}_{\lambda\in\Lambda}$の直積空間を$S=\prod_{\lambda\in\Lambda}S_{\lambda}$とするとき, $S$がコンパクトであるためには, すべての$\lambda\in{\Lambda}$に対して$S_{\lambda}$がコンパクトであることが必要十分.
この二つは一見つながりがあるように見えないが, Tychonoffの定理を使うとコンパクト性定理を示すことができる. どうもこの辺りの関係が「コンパクト性」と言われる由縁のようである.
今回は人口的になじみの薄い人が多いであろうLogic側の定理であるコンパクト性定理の主張を理解するために必要な言葉の定義をして, Thyconoffの定理からコンパクト性定理を証明してみよう*1.
「Logicとはどのような学問であるか」と問われると, どのように答えても炎上するような気がするが, ある一面の捉え方(これなら燃え上がらないと思いたい)としては「記号列とその意味世界についての数学」と言えると思う.
今回扱う「記号列」は「命題論理」と呼ばれる人工的な「言語」である. この「言語」は「命題同士の関係」について記述ができる世界(体系)ではあるが, 逆にそれ以上のことは表現できない体系である*2.
まずこの「言語」で使われる「記号」の集合を定義しよう.
[定義:記号]
「命題論理」の記号の集合
は以下の記号の集まりである.
・命題記号
\begin{align*}&{A, B, C, D, }\dots;\\&{X, Y, Z, }\dots;\\&{A_1, A_2, A_3, }\dots.\end{align*}
・論理記号
\[\lnot, \land, \lor, \to. \]
論理記号についてはLogicになじみのない人々でも見たことがある人が多いように思われる.
一応なじみのない人のために少しだけ解説すると$\lnot$は「否定」, $\lor$は「または」, $\land$は「かつ」, $\to$は「ならば」などと呼ばれることが多いと思う. ここではただの記号でしかないので「意味」というものを考えてはならないが, 気持ちとしてはそういったものを含んでおり, 実際, 後でそういったものを意味するように「記号」の意味を定義する.
これらの記号をある一定のルールに並べると論理式という「文」にあたるものができる. ラフに言えば「文法」にあたるものである.
[定義:命題記号の論理式]
命題記号の論理式とは次の2つの規則によって帰納的に得られる記号の有限列のことである.
(1) 命題記号は論理式である.
(2) $\phi, \psi$が論理式の時, 以下も論理式である.
\begin{align*}&\lnot\phi, &\land\phi\psi, \\&\lor\phi\psi, &\to\phi\psi. \end{align*}
ここでいう「帰納的」とは, 「有限回これらの規則を適用して」という意味である*3 .
一応, 例を挙げておく.
[例:論理式]
以下の記号列は論理式である.
\begin{align*}&\lnot {A}\\&\to {A}\\&\lor \lnot {A}\land {BC}\end{align*}
以下の記号列は論理式ではない.
\begin{align*}&\lnot {A}\lor\\&{A}\lnot \mathbf{B}\\&{A}\lor {B}\end{align*}
最後の${A}\lor {B}$が論理式でないことに違和感を覚える方もいるかもしれない. 確かに, 数学徒が"ラフ"に使っている論理式などでは, ${A}\lor {B}$普通に使っている*4.
しかし, 今回の体系では${A}\lor {B}$というのは「文法違反」なのである. 今回の体系では「かっこ」を排除したかったのでそのような記法を採用した. しかし, $\phi\lor \psi$なども扱えるようにしておいた方が後で便利そうである. そこでこれらの記号列は「略記」として扱うことにしよう.
[定義:論理式の略記]
$\phi, \psi, \rho$を論理式とする.
i) $\phi\land\psi$は$\land\phi\psi$の略記である.
ii) $\phi\lor\psi$は$\lor\phi\psi$の略記である.
iii) $\phi\to\psi$は$\to\phi\psi$の略記である.
iv) $\%, *$を$\lor, \land, \to$のいずれかの記号とする.
このとき$\left(\phi \% \psi\right)*\rho$を$* \% \phi\psi\rho$の略記とする.
また, $\phi \%\left(\psi*\rho\right)$を$\%\phi*\psi\rho$の略記とする.
$\lnot \left(\phi\%\psi\right)$は$\lnot\%\phi\psi$の略記とする.
以上のように定義しておけば, 数学徒が普段使っている"ラフ"な論理式を我々の体系でも略記として扱えそうである*5.
次にこれらの論理式に「意味」を与えることを考えよう. 命題${A, B, \ldots}$がどのような「意味」「ニュアンス」を持っているかは今回は興味の対象としない. 今回は「命題同士の関係」にのみフォーカスをあてるので, せいぜい${A, B, \ldots}$の真, 偽がわかればよい. そのため以下のような定義になる.
[定義: 論理式への真理値割り当て]
I) 命題記号全体から2値集合$\left\{\mathrm{T, F}\right\}$への関数$M$を真理値割り当てという.
II) $M $を真理値の割り当てとする. 以下i)-iii)を帰納的に満たす命題論理の論理式全体から2値集合$\left\{\mathrm{T, F}\right\}$への関数$S$を$M $による解釈という.
i) 任意の命題記号$\mathbf{X}$に対して, $S\left(\mathbf{X}\right)=M\left(\mathbf{X}\right)$
ii) 任意の論理式$\phi$に対して
\[S\left(\lnot\phi\right)=\begin{cases}\mathrm{F} &\text{if $S\left( \phi\right)=\mathrm{T}$};\\ \mathrm{T} &\text{Otherwise}. \end{cases}\]
iii)任意の論理式$\phi, \psi$に対して
\begin{align*}S\left(\lor\phi\psi\right)&=\begin{cases}\mathrm{F} &\text{if only $S\left(\phi\right)=\mathrm{F}, S\left(\psi\right)=\mathrm{F}$};\\ \mathrm{T} &\text{Otherwise}. \end{cases} \\ S\left(\land\phi\psi\right)&=\begin{cases}\mathrm{T} &\text{if only $S\left(\phi\right)=\mathrm{T}, S\left(\psi\right)=\mathrm{T}$};\\ \mathrm{F} &\text{Otherwise}. \end{cases}\\ S\left(\to\phi\psi\right)&=\begin{cases}\mathrm{F} &\text{if only $S\left(\phi\right)=\mathrm{T}, S\left(\psi\right)=\mathrm{F}$};\\ \mathrm{T} &\text{Otherwise}. \end{cases}\end{align*}
この定義の後半の気持ちは以下のようなものである.
Tはtrue, Fはfalseの頭文字である. それぞれの意味するところは良かろう. 日本語ではTは「真」, Fは「偽」などと呼ばれることもある.
$\phi\land\psi$が真になるのは, $\phi, \psi$が同時に真になる時であり, $\phi\lor\psi$が真になるのは, $\phi, \psi$のどちらか少なくとも一方が真になる時である*6. これらに異論はないであろう.
$\phi\to\psi$については事情は複雑である. 4つのケースに分けて考えてみる.
i) $\phi$が真で, $\psi$が真の時
ii) $\phi$が真で, $\psi$が偽の時
iii) $\phi$が偽で, $\psi$が真の時
iv) $\phi$が偽で, $\psi$が偽の時
i)の時に真でii)の時に偽なのは異論がないと思われる.
iii), iv)のときにどちらも真になるのは「前提が間違っているときには結論が真だろうが偽だろうが, その文章全体としては真」というものである*7. 開き直って, この体系での$\phi\to\psi$は$\lnot\phi\lor\psi$と同じ意味と思ってもよいかもしれない.
さて, 以上のような準備の下で「理論」と「モデル」を定義しよう.
[定義: 理論, モデル]
i) 命題論理の論理式の集合(有限でも無限でもよい)を理論(theory)という.
ii) 理論$T$を解釈によって, すべて真にするような真理値割り当てを$T$のモデルという.
iii) 理論$T$と論理式$\phi$に対して\[T\models\phi\]とはどんな$T$のモデルに対しても$\phi$を真とする時をいう.
iv) $T$が空集合の時, 単に$\models\phi$と書き, このような$\phi$をトートロジーという*8.
論理式の集合を理論と呼ぶのは不思議に思うかもしれないが, これは気持ちとしては「公理」を意味しているのである. ホントはここから「推論」を定義し, 「公理」から「定理」を証明するという風に話(構文論)を持っていくのが普通であるが, (長くなるので)今回は割愛することにする.
例だけは出しておく.
[例:理論, モデル]
$T=\left\{{A}, \land{A}\lnot{B}\right\}$のモデルは
\begin{align*}M\left( {A} \right)&=\mathrm{T}\\ M\left( {B} \right)&=\mathrm{F}\end{align*}
というものを満たす真理値割り当てである.
さあ, これでコンパクト性定理に出現する用語の定義はすべて出そろった.
Thyconoffの定理からコンパクト性定理を証明しよう.
[証明]
(1)$\Rightarrow$(2)は自明.
(2)$\Rightarrow$(1) を示す.
真理値の集合$I=\left\{\mathrm{T}, \mathrm{F}\right\}$に離散位相が入っているものとして扱うこととする.
$P$を
に含まれる命題記号すべての集合とする.
$P$を添え字集合として$I^P$という積位相空間を考える.
$I$がコンパクトであるから, Thyconoffの定理よりこの空間はコンパクトである.
$S$を理論$T$の有限部分集合として,
\[C_S:=\left\{v\in I^P\left|\text{$v$は$S$のモデル}\right.\right\}\]
を考えると, この$C_S$は$T$の有限部分集合にはモデルが存在することから空ではない. また明らかに閉集合である.
このとき, $\left\{C_S\left|S\text{は$T$の有限部分集合}\right.\right\}$は有限交差性を持つ.
実際$S_1, S_2$を$T$の有限部分集合とすると, $C_{S_1}\cap C_{S_2}$は$S_1\cup S_2$のモデル全体の集合になっているが, $S_1\cup S_2$もまた有限集合であるから$C_{S_1}\cap C_{S_2}$は仮定より空でない.
$I^P$がコンパクトであることから$I^P$の閉集合の族が有限交叉性を持つとき, その族すべての共通部分は空でない.
すなわち, \[\bigcap_{S\subset T:\text{有限}}C_S\neq\emptyset\]
このとき, $\bigcap_{S\subset T:\text{有限}}C_S$の元が$T$のモデルとなっている. $\blacksquare$
ふぅ, 疲れた.
自分の知らない分野同士のつながりが見えた時の感動は素晴らしいですね. 逆にコンパクト性定理からTyconoffの定理が証明されるかとても気になりますが, まだ考え中です.
このあたりの対応関係についてはもっと掘り下げると面白そうですが疲れたのでまた今度......
Tyconoffの定理周辺については気が向いたらまた取り上げます.
参考文献
今回詳しく取り上げたLogic側の参考文献は以下の通り.
[1] 基礎論夏の学校2015チュートリアルのノート
http://www2.kobe-u.ac.jp/~mkikuchi/ss2015.html
[2]
[3]
[4]
特に論理式の定義は[4]を主に参考にしました. 証明の部分は[1]のまんまです.
次に位相空間についての参考文献. 最初にこの記事の話を聞いたとき, 自分が位相空間弱者なことを思い知らされました. まぁ, 数学全般弱者ですが......
[5]
[6]
[5]は定評のある教科書ですが, 回りくどい記述が多いかも. [6]は位相空間論に入ってからが本領発揮です.
