2011-09-01

タイプとStone空間メモ

第５章

$S_{n}^{M}(A)$ 　：　Mを言語Lのモデル、A⊂M として、
　　　公理系　 $Th_{A}(M)$ 　＝｛φ ： M |= φ，φはAをパラメタとしたL-閉論理式｝
　　　に関する完全ｎ-タイプ全体の集合。

$S_{n}^{M}(A)$ は、位相の基底を各論理式φに対して
　　　 $\left \langle \varphi \right \rangle_{T}\: =\left \{ p\in S^{M}_{n} :\varphi \in p \right \}$
とすることで、位相空間（Stone空間）になる。
ここで、 $T=Th_{A}(M)$ とおいた。

Stone空間は、完全不連結なコンパクトハウスドルフ空間になっている。

2011-07-28

レーヴェンハイム・スコーレムの定理をちょっと使うと、

第５章

　「可算モデルだけが持つような特徴」を一階論理で公理化することは不可能であることがわかります。

最も単純な例では、公理系Ｔが「モデルＭが有限集合である」ということを表す論理式の集合であるようにしたいとしましょう。しかもモデルＭは有限集合でありさえすればよく、どんなにも大きい有限でもかまわない。つまり、任意のモデルＭについて、

$M\models T\; \Leftrightarrow \; card\left ( \left | M \right | \right )< \omega$

となるようにしたいとします。
ところが、上方のレーヴェンハイム・スコーレムの定理により、Ｔがどんなにも大きな有限モデルを持つので、好きな大きさの基数濃度のモデルを持つことが判明してしまいます。よって、「有限集合である」という特徴は１階論理で公理化可能ではありません。

この例は新井本ではp.55演習問題１１に載っています。ちなみに、「元の個数がｎ以下の有限」というふうに制限すれば、公理化可能です。

　他の例では、「Ｍは有限生成アーベル群」という特徴も１階論理で公理化不可能です。すなわち、

$M\models T\; \Leftrightarrow \;$ 　　「Ｍは有限生成アーベル群である」

となるような１階閉論理式の集合Ｔは存在しません。
　なぜなら、有限生成アーベル群の濃度は高々可算ですが、これまた上向きのレーヴェンハイム・スコーレムの定理から、可算無限濃度のモデルを持つ公理系Ｔは不可算濃度のモデルをも持つのでアウト！になります。

2011-07-21

レーヴェンハイム・スコーレムの定理！！

第５章

公理系Ｔが無限モデルを持てば、可算モデルも不可算モデルも持ちますよ！それどころかどんな大きな濃度のモデルも持ちますよ！っていう定理です。ちょっとテンションが上がってきますねー(∩´∀｀)∩

まずは定理の引用から。（新井敏康「数学基礎論」より）

定理５.１.７（上方(Upward)Löwenheim-Skolem 定理）
１．言語Ｌでの公理系Ｔがどんなにも大きい有限モデルをもてばあるいは無限モデルをもてば
　　（つまり $\forall n\exists M\left [ M\models T\& card\left ( \left | M \right | \right ) \geq n \right ]$ ），
　　どんな無限基数 $\kappa \geq card\left ( L \right )$ についても
　　Ｔのモデル $N$ で濃度κのものが存在する．
２．無限モデル $M$ についてその初等拡大 $N\prec M$ で
　　与えられた無限濃度 $card\left ( \left | N \right | \right )=\kappa \geq card\left ( \left | M \right | \right )+card\left ( L \right )$
　　となるものが存在する．
　　　　（p.183）

定理５.１.１３（下方(Downward)Löwenheim-Skolem の定理）
１．Ｌ-無限モデル $M$ と集合 $X\subset \left | M \right |$ について，
　　初等部分モデル $H\left ( X \right )\prec M$ で
　　 $X\subset \left | H\left ( X \right ) \right |$ かつ
　　 $card\left ( \left | H\left ( X \right ) \right | \right )\leq card\left ( L \right )+card\left ( X \right )+\aleph _{0}$
　　となるものが作れる．
　　　　（p.185）

　上方のほうのスコーレム・レーヴェンハイムの定理は、ある公理系が無限モデルをもてば、どんなにも大きい無限モデルをも持つことを主張しています。なので、たとえば自然数の公理系ＰＡのモデルで、不可算濃度のものが作れます。

　さらにすごいのは、この定理から導かれる系５.１.１０。この系によれば、公理系Ｔが無限モデルをもてば、Ｔの濃度κのモデルＭで、Ｍで定義できる無限集合の濃度がすべてＭと同じκになるようなものが作れます。すると、たとえばＺＦＣの(有限部分の)モデルで、モデル内で定義できる無限集合がすべて可算濃度ωになるものが存在します。ＺＦＣといえば、順序数のクラスを定義できるので、基数もどんどん大きくできるように思えます。が、そのモデルの中では、すべての順序数が可算、実数の集合も可算、実数のべき集合も可算です。ｵｲｵｲヾ(ﾟДﾟ )これどうなってんのよ？不可算基数はどこ行ったァァァっ！って感じのモデルです。ＺＦＣのすべての無限集合が不可算になるモデルもあります。ωが不可算とかね。もうね。何が起きているのやら。

　下方のほうのスコーレム・レーヴェンハイムの定理からは、言語が可算であれば、どんな大きな無限モデルにもその初等部分モデルになるような可算モデルを持つことが言えます。（X＝∅とすればよい。）

　こっちのほうは、素朴に考えたらたとえば実数の集合Ｒとかは可算な初等部分モデルを持たなそうですけど、それが作れてしまいます^^;
　可算な実数のモデルというのは実数の集合 $\mathbb{R}$ に対して、
　　 $M\subset \mathbb{R}$ かつ
　　 $M\models \varphi \Leftrightarrow \mathbb{R}\models \varphi$ 　（φはＬ(M)-論理式）
なる可算集合Ｍのことですから、かなり奇妙な感じがしますね。

2011-07-19

モデル理論の最初　モデルの拡大

第５章

第５章モデル理論に入りました。

部分モデルと初等部分モデルについて。
この辺は具体例と一緒に考えたいと思います。

部分モデル

ＭがＮの部分モデルであることをＭ⊂Ｎと書きます。集合の包含関係と同じ記号。

部分モデルの定義はp.179で与えられていますが、
言語Ｌ＝｛R，…，f，…，c，…｝の二つモデルＭとＮが、
・集合としてＭ⊂Ｎであり、
・各定数記号の解釈 $c^{M}$ がすべてＭに入っており、
・関数 $f^{M}$ についてＭは閉じている
ことを確認すれば十分です。

同値な言い換え。

集合としてＭ⊂Ｎであれば、
　　 $M\subset N\; \; \Leftrightarrow \; \; N\models Diag(M)$
ただし、ＭのダイアグラムDiag(Ｍ)とは、言語Ｌ(Ｍ)において、Ｍが充たす閉リテラル全体の集合のこと。

このことから、Ｍの拡大モデルで、いくつか公理を付け加えたモノを作りたいときには、まずDiag(Ｍ)を考え、付け加えたい公理達をＴとすると、Ｔ∪Diag(Ｍ)が充足可能であることを示してモデルを作ればよいことがわかかります。

例：
言語Ｌ＝｛０,１,＋,・｝のモデルである整数全体の集合Ｚと有理数全体の集合Ｑは、モデルとして、
　　 $\mathbb{Z}\subset \mathbb{Q}$
となっています。
あと、群の部分群は部分モデルでもあります。
要するに関数記号について閉じていることをチェックすればいいので、部分モデルを見つけるのは難しくなさそうです。

初等部分モデル

定義

ＭがＮの初等部分モデルである（ＮがＭの初等拡大モデルである）
　　 $M\prec N$
とは、
・ＭがＮの部分モデルである。
・任意のＬ(Ｍ)論理式φについて
　　　 $M\models \varphi \; \Leftrightarrow \; N\models \varphi$
となること。

Ｍの元をパラメタとした論理式の真偽がＭとＮで一致するということですね。

こちらの同値な言い換えは、

集合としてＭ⊂Ｎであれば、
　　 $M\prec N\; \Leftrightarrow \; N\models Diag_{el}(M)$
ただし、
　　 $Diag_{el}(M)$ とは、Ｍの初等ダイアグラム：Ｍで真であるＬ(Ｍ)閉論理式全体の集合のことである。

で、具体例が割と難しいです(+ω+)
さきほどの整数と有理数は部分モデルにはなっても初等的部分モデルにはなりません。なぜなら、論理式
　∃ｘ(ｘ＋ｘ＝１)
は、有理数では真ですが、整数では偽であるので、各モデルで真なる論理式が一致しません。

整数の初等拡大モデルを考えるには、
　　 $Diag_{el}(\mathbb{Z})$
に公理を矛盾しないように付け加えて、そのモデルをつくればいいのですが、
たとえばＺに無限大を付け加えた整数の超準モデルを考えていけばいいと思います。

2011-07-13

第２不完全性定理

第３章

新井先生の本p.110によれば、第２不完全性定理を証明するために使う事実は、
・不動点定理
・標準的な証明可能性述語
だけで、第１不完全性定理に比べると、そんなに多くない。
この二つが成り立つ任意の公理系で第２不完全性定理は成り立つので、ＺＦやＺＦＣでも成り立つ。

公理系Ｔを与えておく。

不動点定理

任意の一変数論理式φ[v]に対して、閉論理式Ｆが存在して、
　　　 $T\vdash F\leftrightarrow \phi \left [ \left \lceil F \right \rceil \right ]$

ただし、φの中身はＦのゲーデル数（のＴにおける数項）を表している。

不動点定理はどんな公理系でも成り立つわけではなく、教科書ではＰＡにおける不動点定理を扱っている。原始再帰的関数とそのコードの関係を使った証明。

証明可能性述語Ｐｒ

φ，ψを任意の論理式とする
（Ｄ１）
　　 $T\vdash \varphi \; \Rightarrow \; T\vdash Pr(\varphi )$
（Ｄ２）
　　 $T\vdash Pr(\varphi \rightarrow \psi )\; \rightarrow \; \left ( Pr(\varphi )\rightarrow Pr(\psi) \right )$
（Ｄ３）
　　 $T\vdash Pr(\varphi )\rightarrow Pr(Pr(\varphi ))$

　公理系Ｔで「φはＴで証明可能である」を意味する証明可能性述語Pr(φ)が上の三条件を満たしている時、Prは標準的な証明可能述語といい、これらから第二不完全性定理を証明できる。

第２不完全性定理の証明

では、証明の中で実際にどのようにして不動点定理と証明可能述語が使われているかをp.109に従ってまとめます。

　　　第２不完全性定理
証明体系Ｈを含む公理系Ｔで、不動点定理と(Ｄ１)、(Ｄ２)、(Ｄ３)が成立するとする。
Ｔが無矛盾ならば、
　　　　　　　　　　 $T\vdash \hspace{-.80em}/$ Con(T)$
ただし、Con(T)はＴの無矛盾性を意味する論理式で、Fmlを論理式の集合とすると、
　　　　 $\forall x\in Fml \left [ \neg Pr(x) \wedge Pr(Not(x)) \right ]$

（証明）
はじめに不動点定理により、ゲーデル文Ｇをつくる。
閉論理式Ｇを、
　　　 $T\vdash G\leftrightarrow \neg Pr(G)$ 　　…（１）
により定義する。

このとき、Ｔが無矛盾であれば、
　　　 $T\vdash \hspace{-.80em}/$ G$ 　　…(２)
となる。

このことは背理法により示せる。使う性質は（Ｄ１）。
　　 $T\vdash G\Rightarrow T\vdash Pr(G)$ 　　（Ｄ１）
　　 $T\vdash Pr(G) \Rightarrow T\vdash \neg G$ 　　（Ｇの定義より）
上の二つから、
　　 $T\vdash G \Rightarrow T\vdash \neg G$ 　　…（３）
であるので、ＧがＴで証明可能であるとするとＴは矛盾してしまう。
以上で（１）の証明終わり。

ところで、（３）をＴの中に形式化したものは、
　　 $T\vdash Pr(G) \rightarrow Pr(\neg G)$ 　　…（４）
であるが、これは（１）の証明に（Ｄ３）をはさむと導出できる。

さらに、
　　 $T\vdash Pr(G) \rightarrow \neg Pr(\neg G)$ 　　…（５）
が、どんな論理式についても成り立つことが、（Ｄ１）と（Ｄ２）とＴ|- Con(Ｔ)を使って導ける。

（５）の証明：
　　 $T\vdash \perp \rightarrow \perp$ 　　（トートロジー）
　　 $T\vdash \neg \perp$ 　　（¬記号で書き換えた）
　　 $T\vdash Pr(\neg \perp )$ 　　（Ｄ１）
と、Ｔ|- Con(Ｔ)の仮定から
　　 $T\vdash \neg (Pr(\perp ) \wedge Pr(\neg \perp ))$
を合わせて、
　　 $T\vdash \neg Pr(\perp )$
あとは、（Ｄ２）から
　　 $T\vdash Pr(G) \wedge Pr(\neg G) \rightarrow Pr(\perp )$
が任意の論理式に対して言えるので、その対偶を考えることで、
　　 $T\vdash \neg (Pr(G) \wedge Pr(\neg G))$
よって、
　　 $T\vdash Pr(G) \rightarrow \neg Pr(\neg G)$
(５)が導かれた。

（４）と（５）から、
　　 $T\vdash Pr(G) \rightarrow \; \perp$
であり、
否定記号¬は、¬φ:≡φ→⊥の略記であったので、
　　 $T\vdash \neg Pr(G)$
となる。

したがってＧの定義より、
　　 $T\vdash G$
となり、（２）に反する！！！

と、証明を書き下してみたものの

ちょっとアヤシイな。
この証明では、Ｔ|- Con(Ｔ)の仮定が、論理式に⊥を入れたものしか使っていない。
つまりCon(Ｔ)としては、
　　¬Pr(⊥)
を準備すれば十分だったことになります。
まぁ実際、Ｔの無矛盾性を意味する論理式は、述語Ｐｒさえしっかりと定義できていれば、「無矛盾ならば少なくとも一つ証明できいない論理式がある」ので、たとえば「⊥」を使っちゃえばいい。ということなんでしょうかね。

上で定義したCon(Ｔ)は教科書通り書き写したものです。
しかし、これは正式には論理式ではなく、第一不完全性定理からの流れで、原始再帰的述語から写された論理式の省略形でした。第一不完全性定理にこだわらなければ、Con(Ｔ)はけっこう簡単に書いてしまってかまわない、ということなのかもしれませんね。

2011-07-05

第１不完全性定理　公理系ＰＡ

第３章

　不完全性定理を始めて勉強するなら、「数学ガール」第３巻がおすすめです。ミルカさんがやさしく指導してくれて、テトラちゃんが一緒に悩んでくれて、ユーリちゃんが鋭い直観的指摘をしてくれます。

数学ガール/ゲーデルの不完全性定理 (数学ガールシリーズ 3)

作者: 結城浩
出版社/メーカー: SBクリエイティブ
発売日: 2009/10/24
メディア: 単行本
購入: 37人クリック: 930回
この商品を含むブログ (149件) を見る

さて新井先生の「数学基礎論」は第３章、不完全性定理です。

不完全性定理は算術を含む公理系についての定理です。
本で紹介されているのは、

第１不完全性定理
公理系ＰＡが無矛盾であるならば、ＰＡは不完全：
φのＰＡでの証明も、¬φのＰＡでの証明も存在しないような閉論理式φがつくれる。

ＰＡは自然数の算術を含む公理系なのですが、このＰＡとは何なのかをまとめてみます。

公理系とは、関数記号や関係記号の集合である言語Ｌがまず定義されたときに、Ｌ-閉論理式の集合のことでした。簡単に言うと「文」の集合なのですけど、「文」とは何かについて形式的に定義したのでした。

公理系ＰＡは、
・証明体系Ｈ
・原始再帰的関数の関数記号たち
・数学的帰納法の公理
からなります。

公理系ＰＡを決めるための言語は、
・証明体系Ｈで出てきた→,⊥,∃,＝,あと無限個の変数記号 $v_{1},v_{2},v_{3},\cdots$
・原始再帰的関数全体と１対１で対応している関数記号の皆さん
ですが、関数記号の皆さんを決めるためには、原始再帰的関数たちをコード化していかなくてはなりません。
どういう方法でもいいのですが、要点は原始再帰的関数がコード（つまり自然数）eによって[e]と書かれ、異なる関数には異なるコードが割り当てられていればとりあえずオッケー。
原始再帰的関数全体の集合をＰＲとすると、関数記号の皆さんは
$\left \{ f_{e}:[e]\epsilon PR \right \}$
と書けます。
言語に定数記号を特別に入れる必要はありません。自然数０、１、２、…は、ゼロ関数0と後者関数Scによって、0、Sc(0)、Sc(Sc(0))、…と表せるので、それらに対応するコードによって、自然数の関数記号が与えられます。