■

[集合論] 無限公理が無い時に... (Jech本 p.26)

　
　今回の話題は無限公理が無い時にどういうことが言えるかというケッタイなJech本の2章末問題がネタである．

＜問題2.4（無限公理が無いとき）＞

0でない最小の極限順序数が存在するときそれを\omegaとする．それが存在しないとき \omega:=Ordとする．このとき次は同値である．
(i)　inductive set が存在する．
(ii)　無限集合が存在する．
(iii)　\omegaは set である．

　注意としては(ii)の無限集合の定義は通常は，『いかなるn \in \mathbb{N}に対しても，上への one-to-one 写像が存在しない』であるが，集合としての\mathbb{N}の存在が保証されていないので，

Xが無限集合 ⇔ \forall n \in N \neg(n \sim X)

というようには簡単にできない．集合論で使用する論理式の変数・定項はすべて集合でなければならないからである．一方で集合Xが順序数であることは，transitive かつ \inでwell-orderd であるという条件を真っ正直に並べれば論理式で記述できる．問題は\mathbb{N}=\{0,1,2,\cdots \}の元を論理式\phi(x)で書けるか？ということであるが，意外にこれはうまくいかないのである．ところで問題の『0でない最小の極限順序数\omegaが存在するとき』は常にそれは\omega=\mathbb{N}なのであろうか？ もし，x\in Nが論理式で記述できるなら，\{x:x\in \omega \wedge \phi(x)\}は選出公理より集合であり，また極限順序数である．よって\omegaの最小性から\omega=\mathbb{N}とならざるを得ないのだが本当だろうか？　これに深入りするとZFで無限集合の存在公理をその否定に置き換えた遺伝的有限集合論の非標準モデルというアヤシイ方向に行くようなのでここで立ち止まっておこう．
　順序数Xが極限順序数であることは論理式で表現できる:\forall x(x\in X \Rightarrow x+1 \in Xため，ここでは有限集合の定義として，『自分自身とその要素が全て極限順序数でない』という定義を採用しよう．この定義は，もし最小な極限順序数\omegaが存在すれば X < \omegaと同値であり，最小な極限順序数が存在しない場合は単にX \in Ordである．この問題のケッタイな\omegaの定義はこの有限集合の定義に適合しており，恐らくもともとそういう意図であったのかもしれない．また有限集合をこの定義にしておくと，\omegaの定義とは独立にできるので(ii)のステートメントの意味が明確であるという利点もある．

　極限順序数が存在しない一番簡単な例は通常の集合論での有限集合だけを集めた（無限公理を抜いたZFC）集合論で，0でない極限順序数は存在せず，この世界での Ordは\omega:=有限集合の全ての集まりと一致し，それは集合ではない．ところで，無限公理が在ろうが無かろうがOrdは集合では無い（つまり真のクラスになる）ので，上の問題で\omega=Ordの場合，(iii)が成立しないため，0でない極限順序数が存在しないし inductive setも無限集合も存在しない集合論となっていることがわかる．ちなみに完全に蛇足だが，調べたところNFと呼ばれる集合論の公理系ではそもそも順序数の定義がフォンノイマン流ではなくて，順序数全体のクラスは必ずしも真のクラスではない（モデル依存）そうである．さらに困ったことにNFでは選択公理が否定されるらしいが，キューネン本によると『NFは数学の基礎として一般的には受け入れられていない』とのことでマニア以外の人はまあ安心である．

＜問題の証明＞
(i) ⇒ (ii)
　inductive set の一つをXとする．\alpha := X \cap Ordは inductiveな順序数なので極限順序数である．なので \omega \le \alphaなのはわかるが，かといって \forall x < \omegaなるxに対して 上への one-to-one が存在しないかどうかはそんなに自明ではない．ちなみに２つの順序数に対して \alpha < \beta \Rightarrow |\alpha| < |\beta|は正しくなくて（∵たとえば \omega < \omega+1だが，|\omega|=|\omega+1|. 最後の等式のone-to-one写像としては \phi(n):=n-1 \ ;\ n>0，\phi(0):=\omegaという例がある．）

　さて，もしあるx < \omegaに対して，one-to-one写像 \phi:\alpha \to xが存在すると \omega \subset \alphaに制限すれば \phiは\omegaからxの中へのone-to-one写像となる．一方，もとより x \subset \omegaなので，次のセクションのCantor-Bernsteinの定理より，|x|=|\omega|となる．結局，x < \omegaなら|x|=|\omega|が不可能であることを示せばよいことになる．　S:\omega \to \omegaをS(x):=x+1と定義する．まずSは単射である（∵ \alpha < \beta \Rightarrow \alpha+1 < \beta+1より）．また ran\ S=\omega\setminus 0である（∵ 0以外のx\in \omegaは\omegaの定義より後続順序数でなければならない）．さて次に0 < x < \omegaとして，任意のy \in xに対して，上への one-to-one写像 \rho:x-1 \to x \setminus yを構成しよう．大仰だが超限帰納法を使う．x=1の時はx\setminus yは空集合なのでよい．x=x-1\cup {x-1}で，y=x-1の時はx-1 \subset xでよい．y \in x-1のときは帰納法の仮定から，上へのone-to-one写像 \rho':x-2 \to x-1\setminus yが存在するので，\rho'(x-1):=x-1と定義を拡張すれば，\rho':x-1 \to x\setminus yが上へのone-to-one写像を与える．
　さて，順序数xをx < \omegaで|x|=|\omega|なるような最小のものとしよう．x=0は明らかに条件を満たさないのでx > 0．\phi:\omega \to xを上へのone-to-one写像とする．y:=\phi(0)として，\rho:x-1 \to x\setminus yを上へのone-to-one写像としよう．ここで \rho^{-1}\circ\phi\circ S:\omega \to x-1 が定義されて 上へのone-to-one写像となるが，これはxの最小性に反する □

(ii) ⇒ (iii) (Jech本のヒントに従う)
　このステートメントは結局，無限集合の存在が極限順序数の存在を導くということである．Xを無限集合とする．Xに含まれる有限集合を全て集めたものは集合である（∵ Xのベキ集合について，有限順序数が存在してその上へのone-to-oneが存在するという論理式による分出公理から集合となる）．各々の有限集合に対して，そのone-to-oneが存在する順序数を対応させる関数クラスが定義されるが，置換公理によりその像は集合である．よってこの像の和集合\alphaは順序数となるが，これがすべての有限順序数を含むことを証明しよう．そうなれば，\omega \subset \alphaなので\omega=Ordのケースではないことがわかる．
　\alphaに含まれない有限順序数の最小のものをxとしよう．0は明らかに\alphaの元なので，0 < xとしてよい．有限順序数の定義からxは後続順序数で x=x'+1と書けるが，x'自身も有限順序数の定義を満たし，xの最小性からx' \in Aとなる．そこで部分集合Y \subset Xでx'に上へのone-to-one写像が存在するものがある．また，Xは無限集合なのでYに含まれないXの元yが存在する．そこで Y\cup\{y\}に対して，y以外は元のone-to-one写像，yに対してはx'を対応させれば，x=x'\cup\{x'\}の上へのone-to-one写像が作れ，x\in Aとなるがこれは矛盾である．□

(iii)⇒(i)
\omegaはinductive setである．□