2018-07-15

命題論理の完全性定理について

数学

今回は趣味でやってる基礎論の話題について書こうと思います。

といってもそんな大した話ではなく，古典一階命題論理の完全性定理について自分の覚え書きのためも兼ねてつらつらと書いていきます。

数理論理学pdf
モデル存在定理
完全性定理
おわりに

数理論理学pdf

まず、以前に基礎論布教用に命題論理について基本を一通りまとめたpdfを書きました。

論理式の定義から完全性定理までをカバーしています。

この完全性定理の証明なのですが、できるだけ直接に完全性定理を示そうとしたところなんか微妙な証明になった気がするのでここでは別の証明をざっくり追ってみようと思います。

以下、ノーテーションはpdfに従うものとします。

モデル存在定理

pdfの最後の方でも触れた通りモデル存在定理という定理があります。

　モデル存在定理

　　論理式の集合 $\Gamma$ について $\Gamma$ が無矛盾ならば $\Gamma$ はモデルをもつ．

今回はこの定理を証明し、これを用いて完全性定理を示していきます。

モデル存在定理を示すためにpdfと同様に2つの補題を用います。

　Zornの補題

　　空でない帰納的順序集合 $X$ には極大元が存在する．

　　特に任意の $x\in X$ について $x\leq x^\ast$ となる極大元 $x^\ast\in X$ が存在する．

　演繹定理

　　論理式の集合 $\Gamma$ ，論理式 $\varphi,\psi$ について

$\Gamma\cup\{\varphi\}\vdash\psi\ \Leftrightarrow\ \Gamma\vdash\varphi\to\psi$

これらの補題についてはpdfを参照とします。ただし演繹定理の方は今回は明示的には用いません。

以上の準備の下にモデル存在定理を証明していきます。

（証明） $\Gamma$ を無矛盾な論理式の集合とする．

論理式全体の集合を $\Phi$ とおく． $\mathcal{A}$ を無矛盾な $\Phi$ の部分集合全体の集合とする．

このとき $\mathcal{A}$ は包含関係について帰納的順序集合となることがわかる． $\Gamma\in\mathcal{A}$ なのでZornの補題より $\Gamma\subset\Gamma^\ast$ となる極大元 $\Gamma^\ast\in\mathcal{A}$ がとれる．

$\Gamma^\ast$ は次の性質を持っている．（ここで演繹定理を用いる）

$\mbox{任意の論理式}\varphi\mbox{について}\ \varphi\in\Gamma^\ast\mbox{または}\neg\varphi\in\Gamma^\ast$

またこの性質から $\Gamma^\ast$ について次の性質が従う．

　　 $\psi\wedge\chi\in\Gamma^\ast \ \Leftrightarrow\ \psi\in\Gamma^\ast\mbox{かつ}\chi\in\Gamma^\ast$

　　　 $\psi\vee\chi\in\Gamma^\ast \ \Leftrightarrow\ \psi\in\Gamma^\ast\mbox{または}\chi\in\Gamma^\ast$

　　　 $\ \psi\to\chi\in\Gamma^\ast \ \Leftrightarrow\ \psi\notin\in\Gamma^\ast\mbox{または}\chi\in\Gamma^\ast$

$\neg\psi\in\Gamma^\ast \ \Leftrightarrow\ \psi\notin\Gamma^\ast\hspace{0.9cm}$

そこで写像 $\mathcal{M}\colon\Omega\to\{0,1\}$ を次のように定義する．

$\mathcal{M}(X)=1\hspace{1.0em}(X\in\Gamma^\ast\mbox{のとき})$

$\ \mathcal{M}(X)=0\hspace{1.0em}(X\notin\Gamma^\ast\mbox{のとき})$

このとき前述の $\Gamma^\ast$ の性質より

$\mbox{任意の論理式}\varphi\mbox{について}\ \mathcal{M}\models\varphi\ \Leftrightarrow\ \varphi\in\Gamma^\ast$

が成り立つ．

よって $\Gamma\subset\Gamma^\ast$ であることより $\mathcal{M}$ は $\Gamma$ のモデルである． $\rule{4mm}{4mm}$

この証明では極大無矛盾集合とよばれる $\Gamma^\ast$ がキーになっています。pdfでの完全性定理の証明も本質的にはこれと同じ方法をとっています。

完全性定理

では実際にモデル存在定理を用いて完全性定理を証明しましょう。

　完全性定理

　　 $\Gamma$ を論理式の集合， $\varphi$ を論理式とするとき

$\Gamma\models\varphi\Rightarrow\Gamma\vdash\varphi$

（証明）対偶を示す．つまり $\Gamma\vdash\hspace{-0.8em}\backslash \varphi$ を仮定して $\Gamma\models\hspace{-1.0em}\backslash\ \varphi$ を示す．ここで $\Gamma\models\varphi$ とは $\Gamma$ の任意のモデルで $\varphi$ が真であることだったので $\Gamma\models\hspace{-1.0em}\backslash\ \varphi$ を示すには $\varphi$ が偽となる $\Gamma$ のモデルが存在することを言えばよい．

$\Gamma\vdash\hspace{-0.8em}\backslash \varphi$ のとき， $\Gamma\cup\{\neg\varphi\}$ が無矛盾であることがわかる．よってモデル存在定理より $\Gamma\cup\{\neg\varphi\}$ のモデル $\mathcal{M}$ が存在するが，この $\mathcal{M}$ は $\varphi$ が偽となる $\Gamma$ のモデルである． $\rule{4mm}{4mm}$

見る人が見ればすぐにわかるかと思いますがこの証明は鹿島先生の『数理論理学』を参考にしたもの（というかこの部分に関してはまるっきりそのもの）です。

完全性定理の証明は数理論理学の中でも最初に悩むことになる非自明なところなのですが、このように対偶をとることでモデル存在定理に帰着しモデル存在定理はZornの補題から無矛盾極大集合をとることで示されると思えば理解しやすいのではないかと思います。

ただしこの方法は命題論理だから通用するもので、述語論理では存在量化記号に対してデリケートな問題が残るので言語の拡大などの方法でもう少し調整をする必要があります。このあたりがまた悩むところですね…

おわりに

以上で命題論理の完全性定理が証明できました。本当はもう少し、完全性定理とモデル存在定理とコンパクト性定理の同値性辺りまで書こうかと思ったのですが疲れたのでまたいつか気が向いたときに書くことにします。

参考文献はpdfに載せてあります。数理論理学の入門としてオススメの順番に並べてあるので興味のある人は上の方にあるタイトルを適当に開いてみるといいかと思います。

2018-06-09

位相空間上のフィルターの収束

数学

先日位相空間論におけるフィルターの話をpdfにまとめてTwitterに投稿しました

詳しい証明などは上のpdf（以下上の記事）に書いたのでここでは簡単な紹介だけしようかと思います。

フィルターとは位相空間論における「点列」を（ある意味で）一般化した概念で題にあるとおりフィルターの収束というものが位相空間において定義できます。

一般の位相空間では点列収束の一意性とハウスドルフ性や点列コンパクト性とコンパクト性などの条件は微妙に差がありますが、これの点列のところをフィルターに変えるとなんとこれらは同値になります！フィルターすげえ！！というのが上の記事の主題になります。

また上の記事ではその応用としてフィルターを用いてチコノフの定理を証明しています。この証明もフィルターを使えばずいぶんシンプルになるのでフィルター強ええ！！！というのがわかります。

もう少し具体的な話をしましょう。位相空間 ${ X }$ 上の点列 ${ \{x_n\} }$ が点 ${ x\in X }$ に収束することの定義は以下の通りでした。

$\forall U \in\mathfrak{N}(x)\ \exists N\in\mathbb{N}\ \forall n\in\mathbb{N}\ \ n\geq N \Rightarrow x_n\in U$

ただし $\mathfrak{N}(x)$ は $x$ の近傍系です。

ここで $F_N=\{x_n\mid n\geq N\}$ とおいてみましょう。すると上の収束の定義は次のように書き換えられます。

$\forall U\in\mathfrak{N}(x)\ \exists N\in\mathbb{N}\ \ F_N\subset U$

これがフィルターで書いた場合の収束であり、上の記事の中でいう命題2.3です。つまりフィルター基底 $\mathfrak{B}=\{F_N\mid N\in\mathbb{N}\}$ の収束をみているわけです。

このように点列の収束は集合の包含関係で書き換えられます。さらにこの形で書けば $F_N$ が点列である必要すらなくね？という発想に至りこれを一般の集合で書き直すことでフィルターの定義にたどり着きます。

（この辺りの「具体的な抽象化の過程」は上の記事では触れなかったのでここで書いておくことにしました。）

フィルターの感覚はだいたいそんな感じです。こうして定義されたフィルターを用いると最初に書いたような強い結果が色々得られるのですがその辺の詳しいところは上の記事を見てください。

今回なぜ自分が上の記事を書いたかというとフィルターについての初等的な文献があまりないような気がしたからです。それでTwitterで「フィルターのpdf書いたら需要ある？」みたいなツイートをしてみたら思ったより反応があったので書くことにしました。

実際、自分がフィルターについて勉強したいと思ったときもどの本に載っているのかわからず、適当な位相空間の本を開いてみるも見つからず、結局大学の本棚にあったブルバキを読んで勉強しました。

記事内では参考文献を6冊ほど挙げていますがそのうちフィルターについてまともに載っている本は2冊だけです。

森田先生の位相空間と内田位相は位相空間論の参考にしただけでフィルターは出てきませんし、松坂位相でも演習問題で一瞬でてくるだけでしたし、位相のこころでは説明がされてますがこれは読み物なので証明などは詳しくされていません。また論理と位相ではフィルターについて扱われていますがこれは順序集合におけるフィルターの話（束論での扱い）なので位相空間上での収束などは書かれていませんでした。

要するに上の記事はほとんどブルバキを参考に書かれています。「クセがある」と名高いブルバキの内容を現代的な記法で書き直し、チコノフの定理を焦点にまとめ直しました。

解析系や幾何系に進んでいるとフィルターはメジャーな道具のように思う（？）のですがどうも文献が少ないです。もしフィルターの平易な文献があれば教えてもらえると嬉しいです。

2018-06-05

初投稿

初投稿です。最初なので自己紹介でもします。

ハンドルネームはちょーさん、TwitterIDは@cho_san111000です。現在は関西の某ロケット団大学で数学を専攻しています。趣味はアニメで主にきらら系作品から活力をもらいながら生きてます。

とまあだいたいそんな感じの人間です。以下もう少し詳しく自己を紹介していきます。

大学で専攻している数学についてですが専門は位相幾何学です。学部中にド・ラーム理論くらい終わらせたい…

ちなみにTwitterで数学垢もやっていて、先に載せた垢のbioにも書いてますが@kyo_math1729というIDでこちらのハンネはε（イプシロン）といいます。数学の会合などではこっちを名乗ることにしてるのですがだんだん住み分けが曖昧になってきております。

このアカウントを覗いてもらえばわかるかもしれませんが、実は専門の位相幾何学以外にも趣味で数学基礎論をやっていたりします。最近は自主ゼミで公理的集合論を勉強中です。

基礎論を専門にしようかと考えた時期もありましたが色々あって専門は位相幾何学、基礎論は趣味という形に収まりました。

続いてアニメの方の話題も触れておきます。まず最初にはっきり明記しておきますがちょーさんは普通にアニオタです。μ'sでは海未推しです。どのくらい海未推しかというとTwitterでハッシュタグ #ちょーさん海未ちゃん勧誘祭りで検索してみてください。

きらら系作品と冒頭に書きましたが美少女系ばかり観てるというわけでもなくジャンルは広く色々観ます。今期の目玉はヒロアカ3期です。

ちなみにきらら作品にハマったきっかけはきんいろモザイクです。ごちうさも好きですが個人的にはきんモザ派です。

声優も好きでエンドテロップは必ず見るのですが最近は若手の勢いが凄いですね。新人の登場ペースが早くて追いつくのが大変です。

とまあ色々語りましたがおそらくこのブログで語ることになるのは数学の話が多くなるかと思います。数学をしていて気になったことや学んだことを気まぐれでまとめていこうかと思います。アニメやその他についてもまあ何かあれば書くかもしれません。

そんな感じでゆる～くやっていきますのでよろしくお願いします。

ちょーさんメモ出張版気まぐれブログ

ちょーさん（@cho_san111000）のブログです。数学やその他のことを書きます。更新頻度はちょーさんの気分次第です。