■

[集合論] Jech本二章章末問題から

　
＜問題2.7＞
任意のnormal sequence < \gamma_\alpha:\alpha \in Ord > (i.e. Ord \to Ordの対応で，増加かつ連続 \forall \alpha:limit \Rightarrow \gamma_\alpha = lim_{\xi \to \alpha} \gamma_\xi)に対して，いくらでも大きな 固定点 (i.e. \gamma_\alpha=\alpha)が存在する．

＜解＞ ヒントにあるように適当なa_0 \in Ordから始めて，a_{n+1}:=\gamma_{a_n}と定義し，\alpha:=lim_{n\to \omega} a_{n}とすればよいが，初期値に応じてすこし丁寧にやるのが吉である．

(i) a_0 < \gamma_{a_0}のとき：
　この場合はnormal sequenceの増加性より，a_nは単調に増加している（もっとも普通に想定しているケースである）．\cup_{n < \omega} a_n = \cup_{n < \omega} \gamma_{a_n}が成立するが，左辺は \alpha，右辺は連続性より \gamma_\alphaであり，\alphaが固定点となる．また a_0 \le \alphaである.
(ii) a_0 = \gamma_{a_0}のとき：
　この場合は a_0が固定点なのでこれ以上何もやることがない．
(iii) a_0 > \gamma_{a_0} のとき：
　今度はa_nは単調減少列である．しかし，この場合a_nの集合は最小元を持たないが，これはOrdの整列性に反するので実はこのケースはもともとありえないことになる．
よって，固定点が存在することが証明された．a_0はなんでもよかったので，結局
『いくらでも大きな固定点』が存在することも同時に証明されている□

＜問題2.11＞

次を満たすような \alpha,\beta,\gammaを見つけよ．
(i) \alpha < \betaかつ\alpha+\gamma=\beta+\gamma
(ii)\alpha < \betaかつ\alpha \cdot \gamma=\beta \cdot \gamma
(iii)\alpha < \betaかつ\alpha^\gamma=\beta^\gamma

＜解＞実は問題を誤解して，任意の\alpha < \betaに対して，それぞれの等号が成り立つような\gammaを見つけよというより難しい問題を解いてしまっていた．せっかくなのでそっちの解答を紹介しよう．
(i) \beta=\alpha+\deltaと書けるので，\gamma = \delta+\gammaとなるような\gammaを見つければよい．これは簡単で \gamma=\delta\cdot\omegaとすればよい．要するに\deltaを右から無限に足してやれば，左辺で一つぐらい余分に多いのは吸収されてしまうという理屈である．フォーマルには \delta+\delta\cdot\omega=\delta\cdot(1+\omega)=\delta\cdot\omegaとなる．

(ii) 実は\gamma=0というトンチ解がある．ただ，0 < 1というケースではトンチ解しか解が無いので無意味というわけではない．しかし，ここでは 0 < \alpha < \beta としてトンチ解でないものを見つけてみよう．(i)の類推から \gamma=\beta^\omegaでいけそうである．\beta\cdot \beta^\omega=\beta^{1+\omega}=\beta^\omegaなので，1 \le \alpha < \betaに右から\gamma=\beta^\omegaを掛けると \gamma \le \alpha\cdot \gamma \le \gammaとなるので，\alpha\cdot \gamma=\gammaと全部\gammaに潰れていることがわかる．

(iii) トンチ解\gamma=0でないものを，1 < \alpha < \betaという条件で求めてみる．今回の類推はちょっと悩んだが，\gamma=\beta^{\beta^{\beta^{\cdot^{\cdot^\cdot}}}}=\beta \uparrow \uparrow \omegaである．\beta^\gamma = \gammaになっているわけである．一方，\alpha^\gamma=\gammaになっていてやはり全部\gammaに潰れているのだが，この証明にはちょっと工夫がいる．

＜補題＞　任意の順序数 \alphaに対して， \alpha \le 2^\alpha
＜証明＞　超限帰納法による．\alpha=0のとき，0 \le 2^0=1で成立している．\alpha+1に対して，\alpha+1 \le \alpha+\alpha \le \alpha\cdot 2=2^\alpha \cdot 2=2^{\alpha+1}でよい．\alpha=lim_{\xi\to \alpha}\xiのとき，\xi < \alphaと帰納法の仮定より \xi < 2^\xi < 2^\alphaで，極限操作により \alpha \le 2^\alpha □

　2 \le \alpha < \betaの肩に \beta \uparrow \uparrow nを乗せると，2^{\beta\uparrow \uparrow n} \le \alpha^{\beta\uparrow \uparrow n} \le \beta{\uparrow \uparrow (n+1)}. 補題より \beta\uparrow \uparrow n \le 2^{\beta\uparrow \uparrow n}が得られるので，n\to \omegaとすれば \alpha^\gamma = \gammaが得られる．□

＜問題2.15＞(Well-Founded Recursion)

Eを集合P上のwell-founded relationとし，Gを関数とする（P \times \{Pの部分集合上で定義され，集合に値を取る関数\}上で定義され，集合に値を取る関数）とき，P上で定義され，集合に値を取る関数 Fが存在して，
F(x)=G(x,F\upharpoonright \{y\in P:yEx\})

＜解＞本文での一般化された超限再帰法に比べると，この問題ではなんだか一つ前のデータだけで再帰するケースのようである．ちなみにGの引数にxがあるのは，順序数の場合と異なり，\{y\in P:yEx\}という集合から逆にxをユニークに決めることができないからである．

　まず，Fの唯一性から．条件を満たす関数F'がもう一つあるとして，\{x:F(x)\neq F'(x)\}という集合のE-極小元のひとつをx_0としよう．極小性から，\{y\in P:yEx_0\}という集合上ではFとF'は一致しているので，F(x_0)=G(x_0,F\upharpoonright \{y\in P:yEx_0\})=G(x_0,F'\upharpoonright \{y\in P:yEx_0\})=F'(x_0)となるが，これはx_0の取り方に矛盾する．

　Fの存在を示す．ところでよくよく見るとJech本では関数といったときは関数クラスを意味している（p.11）．しかしながら，定義域が集合上の関数クラスは自動的に集合としての関数になる（∵置換公理により値域が集合となり，分出公理より集合となる）．とはいえ，今回は定理2.27のP_\alphaを使うのが早そうである．
　FをP_\alpha上に順に定義して，\alphaに対する超限帰納法を使う．P_0=\emptysetなので証明することは何もない．\alpha+1の場合，x\in P_{\alpha+1}ならば\{y\in P:yEx\}\subset P_{\alpha}なので，F(x):=G(x,F\upharpoonright \{y\in P:yEx\})で定義すればよい．\alpha=lim_{\xi\to \alpha}\xiの場合，x\in P_{\alpha}\Rightarrow \exists \xi < \alpha(x\in P_\xi)なので，\{y\in P:yEx_0\}\subset P_{\xi}で（∵ x\in P_\xi \subset P_{\xi+1}と考えればよい），同様にF(x):=G(x,F\upharpoonright \{y\in P:yEx\})で定義すればよい．\xiの選び方に依らないのは一意性からFの部分的な定義はすべて共通の定義域で一致しているからである□

■

[集合論] 無限公理が無い時に... (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である．□

■

[集合論] Well-Founded Relations (Jech本 p.25)

　
　例によって、テキストで引っかかったところをネタにするノート記事である．

＜well-founded relation＞

集合 P上の二項関係 Eが次の性質を持つとき、Eを well-foundedという．
Pの任意の部分集合 X \subset Pに対して、Pの元 aで
\forall x \in X : \neg x E a
なるものが存在する（これを E-minimal な元と呼ぶ）．

well-founded な二項関係Eと集合Pを合わせて、well-founded setと呼ぶ．


Eをあたかも大小関係'<'のように見たときに、任意の部分集合に最小元が存在するという well-orderd set の一般化になっているというわけである．もちろん一般的には Eは順序関係ですらない．とはいえ、このままではつまらない一般化に見えるが、次の定理がなんともすごい．Pを関係Eでの極小元から数え上げて階層づけできるというイメージである．

＜定理＞（Jech本 Theorem 2.27）

Eを集合 P上のwell-foundedな二項関係とする．このとき Pから順序数のクラスOrdへの関数で次の式を満たす\rho : P \to Ordが唯一存在する．
\forall x\in P:\rho(x)=sup_y\{\rho(y)+1:y E x\}
また、このとき値域 ran\ \rhoは一つの順序数となる（これをEのheightと呼ぶ）．

＜証明＞
対応を逆にして、順序数に対して Pの部分集合を超限再帰的に定義する．
P_0:=\emptyset, P_{\alpha+1}:=\{x\in P:\forall y(yEx \to y\in P_{\alpha}\},
P_{\alpha}:=\cup_{\xi < \alpha}P_{\xi}　　 \alphaが極限順序数のとき.

\alpha+1の定義の心は、xの下があるならそれは P_{\alpha}の元に限るというような意味合いである．ただし、x\in P_0のとき、yExなるyが存在しないので、条件式の前提が常にfalseとなるため P_0 \subset P_1であることを注意すれば、\alpha < \betaならば P_\alpha \subset P_\betaであることが超限帰納法で示せる（∵ \betaが極限順序数なら定義から自明．\beta=\beta'+1の時は、さらに

(i) \beta'が後続順序数の場合：
\beta'=\beta''+1とすれば、定義より x\in P_{\beta'}=\{x\in P:\forall y(yEx \to y\in P_{\beta''}\}であるが、超限帰納法の仮定から P_{\beta''} \subset P_{\beta'}であるため、後続順序数に対するPの定義から包含関係を＋１進めたP_{\beta''+1} \subset P_{\beta'+1} すなわち P_{\beta'} \subset P_{\beta}が成立する．
(ii)\beta'が後続順序数の場合：
定義より x\in P_{\beta'}\Rightarrow \exists \beta'' < \beta' (x \in P_{\beta''})で、超限帰納法の仮定から P_{\beta''} \subset P_{\beta'}なので P_{\beta''+1} \subset P_{\beta'+1}=P_{\beta}．\beta'' < \beta''+1 < \betaなので再び超限帰納法の仮定から P_{\beta'} \subset P_{\beta''+1}．これらより、x \in P_{\beta}．よって、P_{\beta'} \subset P_{\beta}．
より、超限帰納法が完成する．）


さて、ここでJech本では P_\theta = P_{\theta+1}なるような、\thetaが置換公理により存在するとさらっと主張している．StackExchangeでもこの点の質問があったが、その解答を紹介しよう．もしこのような\thetaが存在しないとすると \phi(\theta):= P_{\theta+1}\setminus P_\thetaの値は空集合でなく、順序数全体のクラスからPのベキ集合への単射になっている（∵ 単射であるのは \theta+1より小さい順序数\theta'に対する P_{\theta'}がすべて \phi(\theta)から除かれてしまっているため）．そして\phiの像に対しては、この\phiの逆写像を考え、\phiの像に入っていないPの部分集合に対しては 0を対応させれば、Pのベキ集合から、順序数全体のクラスへの全射が得られることになる（これらの対応はすべて関数クラスである．念のため）．しかし、これは置換公理により順序数全体のクラスが集合であることになるので、不合理である．
　さて， P_\theta = P_{\theta+1}となったとしよう．このとき，\theta < \theta'に対しても，P_{\theta'}=P_\thetaとなる．その証明は\theta' > \thetaをP_{\theta'}\neq P_\thetaなる最小の順序数とする：

((i) \theta'=\theta''+1 のとき：
　仮定より，\theta \le \theta''でP_{\theta''} = P_{\theta}. これよりP_{\theta''+1} = P_{\theta+1}=P_{\theta}であるから，\theta'の定義に反する．
(ii) \theta'が極限順序数のとき：
　定義より P_{\theta'}=\cup_{\xi < \theta'}P_{\xi}=\cup_{\theta \le \xi < \theta'}P_{\xi}=\cup_{\theta \le \xi < \theta'}P_{\theta}=P_{\theta}は\theta'の定義に反する．

続いて，P=P_{\theta}を証明する．もしそうでないとすると P\setminus P_{\theta}にE-minimalな元 aが存在する．E-minimal の定義より \forall y( yEa \to y\in P_{\theta})となるが，これは a\in P_{\theta+1}そのもので，P_{\theta+1}=P_{\theta}なのでaの決め方に矛盾する．

P_\alphaの準備ができたので，\rhoを次のように定義する．

x \in Pに対して，\rho(x):= min\{\xi:x\in P_{\xi+1}\}

このとき xEyならば，\rho(x) < \rho(y)である（∵ y\in P_{\rho(y)+1}なので，定義から x\in P_{\rho(y)}でなければならない．\rho(y)が後続順序数なら \xi+1=\rho(y)で x\in P_{\xi+1}だから \rho(x) \le \xi < \rho(y). \rho(y)が極限順序数なら \exists \xi < \rho(y)(x\in P_{\xi})．x\in P_{\xi} \subset P_{\xi+1}なので \rho(x) \le \xi < \rho(y) □）

定理の等式を証明しよう．yExより\rho(y) < \rho(x)なので\rho(y)+1 \le \rho(x)．よって、\rho(x) \ge sup_y\{\rho(y)+1:yEx\}は直ちに出る．ここでさらに > が成立しないことを見る．
まず，x\in P_{\rho(x)+1} \wedge x \notin P_{\rho(x)}である（∵もしx\in P_{\rho(x)}なら，\rho(x)が後続順序数なら直ちに矛盾だし，極限順序数なら \exists \xi < \rho(x) (x \in P_{\xi})だが，\xi+1 < \rho(x) かつ x \in P_{\xi}\subset P_{\xi+1}なのでこれも\rho(x)の定義に矛盾する）．さて，\exists \xi < \rho(x)で，\forall y (yEx \to y\in P_{\xi})となってしまうと，x \in P_{\xi+1}より，\rho(x) \le \xiで矛盾する．よって yExなるyの中に y \notin P{\xi} \wedge y\in P_{\rho(x)}なるものがあるが，もし\rho(y) < \xi ならば \rho(y)+1 \le \xi より y\in P_{\rho(y)+1} \subset P_{\xi}は矛盾なので， \xi \le \rho(y). よって，\xi < \rho(y)+1 \le \rho(x)かつ yExなるyが存在する．さて，もし\rho(x) > sup_y\{\rho(y)+1:yEx\}ならば \xi=sup_y\{\rho(y)+1:yEx\}に対して，\xi < \rho(y)+1 かつ yExなるyが存在するが，\rho(y)+1 \in sup_y\{\rho(y)+1:yEx\}=\xiより \rho(y)+1 < \xiは矛盾である□

　最後に heightが \thetaに等しいことを証明する．ここでひとつ重要な注意を．私も一時ハマって『気づいてしまったシリーズ』のネタに入りかけたのだが，定理のステートメント ran\ \rho=\theta は集合としての一致であり，左辺はそもそも順序数であるかどうかは自明ではない．この左辺はsup\{ran\ \rho\} の意味では決してない．なぜなら\thetaが極限順序数でないときは，sup\{ran\ \rho\} \neq \thetaである．例えば１点 xしかない集合で，E=\emptysetとするとトリビアルに well-founded だが，P_0=\emptyset,\ P_1={x}であり，\theta=1．一方 \rho(x)=0となっている．sup\{lo(x)\}=0 \neq 1=\thetaである．しかし，集合としては \{0\}=1で確かに成立している．
　さて， ran\ \rho=\thetaを示そう．

\thetaが後続順序数のとき：
\theta=\theta'+1として，P=P_{\theta}=P_{\theta'+1}なので \forall x \in P \Rightarrow \rho(x) \le \theta'． よって，ran \rho \subset \theta．逆向きは \forall \xi \le \theta'に対して，\xi+1 \le \theta'+1=\thetaだから P_{\xi} \subsetneq P_{\xi+1}なので x \in P_{\xi+1} \wedge x \notin P_{\xi}なるxが存在するが，このとき\rho(x)=\xiである（∵ \rho(x) < \xiだとすると \rho(x)+1 \le \xiより x\in P_{\rho(x)+1} \subset P_{\xi}は xの取り方に矛盾）□
\thetaが極限順序数のとき：
x\in P=P_{\theta}=\cup_{\xi < \theta}P_{\xi}より \exists \xi(x \in P_{\xi})．\xi+1 < \thetaなので \rho(x) < \theta. よって，ran\ \rho \subset \theta．逆向きは \forall \xi < \thetaに対して，\xi < \xi+1 < \thetaなので P_{\xi} \subsetneq P_{\xi+1}．x \in P_{\xi+1} \wedge x \notin P_{\xi}なるxが存在するが，このとき\rho(x)=\xiであるのは先と同じ理由である □

というわけで，特に\rho(x) < \thetaなのであり，等号は成立していない．

■

[集合論]気づいてしまったシリーズ － 順序数の減算編

　いままでさらっと理解したつもりが、ある時気づいてウッとなってしまったことを紹介するコーナーである．今回は、順序数の減算編．

さて、順序数\alpha,\betaの和 \alpha+\beta は順序数で、次のような再帰的な定義である．

(i) \alpha+0 := \alpha
(ii) \alpha+(\beta+1) := (\alpha+\beta)+1
(iii) \betaが極限順序数のとき、\alpha+\beta:=Sup\{ \alpha+\xi : \xi < \beta\}

この定義で(iii)だけが、ちょっとわかりにくいが Sup\{ \alpha+\xi : \xi < \beta\}=\cup_{\xi < \beta} (\alpha+\xi) と書き直しておけば、右辺が『順序数の集合の和集合は順序数になる』ことから順序数であることがわかるし、計算も便利である．ここまでは曖昧なところはどこにもない．

次に順序数の減算に相当する次のような定理がある．

定理： \alpha < \betaならば \alpha+\delta = \betaなる順序数\deltaが唯一存在する．

＜証明＞
　加法の性質 『\beta < \gamma\ \Rightarrow \ \alpha+\beta < \alpha+\gamma』を既知とすれば、唯一性はこれからでるので存在のみを示す．\betaに関する超限帰納法を使おう．\beta=0のとき、\alphaが存在しないのでこの場合は自動的に命題は成立する．気持ち悪いなら、0 < 1から始めてもよい．次に\beta=\gamma+1の場合、\alpha=\gammaか\alpha < \gammaだが、前者なら\delta=1でよい．後者なら、超限帰納法の仮定より \alpha+\delta=\gammaなる\deltaが存在するが、\alpha+(\delta+1)=(\alpha+\delta)+1=\gamma+1=\betaより、OK．\betaが極限順序数のとき、超限帰納法の仮定から \forall \xi < \betaに対して、\alpha+\delta_{\xi}=\xiなるような\delta_\xiが存在する．\delta:=Sup\{\delta_\xi\}は順序数で、\alpha+\delta = Sup\{ \alpha+\delta_{\xi} : \xi < \beta \}=Sup\{ \xi : \xi < \beta\}=\beta となり、\betaに対しても成立するため、超限帰納法より定理が成立する．□


　自作の証明だが、何も悪くなさそうである．しかし、一点だけ穴があることに気づいてしまった．それは\alpha+\delta = Sup\{ \alpha+\delta_{\xi} : \xi < \beta \}である．何がいけないのか．\delta:=Sup\{\delta_\xi\}は順序数で、\alpha+\deltaは確定している．一方、右辺は順序数の集合のSupなので、これも確定した順序数を与える．しかし、これが一致するかどうかは自明でないのである．一見すると順序数の和の定義の(iii)がよく似ているので、納得しそうになってしまうが、① \deltaが極限順序数かどうか明らかでない、② Supを取る集合が定義とはそもそも似て非なるものである、といろいろマズい．


　これからこれらの点を解消するための冒険にでるわけだが、結論を先に言っておこう．①は\betaが極限順序数ならば、\deltaも極限順序数．②、①とは無関係に一般的に任意の順序数の集合\{\beta_\mu\}_\muに対して、\alpha+Sup_\mu(\beta_\mu)=Sup_\mu(\alpha+\beta_\mu)．なので一応、証明は正しいことがわかる．

　まずは①を示そう．ちなみに『\alphaが極限順序数 \Leftrightarrow　(\forall\beta < \alpha \Rightarrow \beta+1 < \alpha)』を使う．これの証明は、\alpha=\beta+1と書けると右辺に反するので、（\Leftarrow)はよい．\alphaが極限順序数（後続順序数でない）かつ、右辺の否定 \beta < \alpha \le \beta+1 が成立すると\beta \in \alphaかつ \alpha \in \beta \cup \{\beta \}から \beta \in \betaまたは \alpha=\betaが出て矛盾である（\Rightarrow)．
　さて、\gamma < \delta=\cup_{\xi} \delta_\xi としよう．\exists \xi: \gamma \in \delta_\xi ．一方、\alpha+\delta_\xi=\xiで、これに右から 1 を加えると、\alpha+\delta_\xi+1=\xi+1 < \beta （∵最後の不等式は\betaが極限順序数であるから）．よって、\delta_{\xi+1}=\delta_\xi+1 \subset \delta．同じことをもう一度やれば、\delta_{\xi+2}=\delta_\xi+2 \subset \delta が得られるが、\delta_\xi+1 \in \delta_\xi+2 \subset \deltaから、\deltaが極限順序数であることがわかる．

　つぎに②を示そう．Sup_\mu(\beta_\mu)は極限順序数とは限らないので次の２つの場合に分ける．

(i)\beta:=Sup_\mu(\beta_\mu)が後続順序数のとき:
\beta=\xi+1と書けるが、\xi \in \beta=\cup_{\mu}{\beta_\mu}なので\exists \gamma ;\ \xi \in \beta_\gamma．このときtransitivityから \xi \subset \beta_\gammaでもあるので、\beta=\xi+1=\xi \cap \{\xi\} \subset \beta_\gammaなので、\beta \subset \beta_\gamma \subset \betaより \beta = \beta_\gamma．そこで証明したい式の右辺について Sup_\mu(\alpha+\beta_\mu) \ge \alpha+\beta_\gamma=\alpha+\beta．一方、\beta_\mu \le \betaより \alpha+\beta_\mu \le \alpha+\betaなので、\alpha+Sup_\mu(\beta_\mu)=Sup_\mu(\alpha+\beta_\mu)は成立している．

(ii) \beta:=Sup_\mu(\beta_\mu)が極限順序数のとき:
この場合でも、\beta=\beta_\muなるものが存在していると、(i)の後半と同じく、簡単に\alpha+Sup_\mu(\beta_\mu)=Sup_\mu(\alpha+\beta_\mu)が成立することがわかるので、\beta_\mu < \betaと仮定しておこう．\alpha+\betaは和の定義の(iii)から、Sup_{\xi < \beta}(\alpha+\xi)に等しいが、これより直ちに②の右辺=Sup_\mu(\alpha+\beta_\mu) \le Sup_{\xi < \beta}(\alpha+\xi)=\alpha+\betaがわかる．もし、この最初の不等号で=が成り立たないとすると、
Sup_\mu(\alpha+\beta_\mu) \in Sup_{\xi < \beta}(\alpha+\xi)=\cup_{\xi < \beta}(\alpha+\xi)なので、Sup_\mu(\alpha+\beta_\mu) \in \alpha+\xiが成立するような \xiが存在する．よって \forall\mu:\beta_\mu < \xiでなければならないが、これより \beta=Sup_\mu(\beta_\mu) \le \xi < \betaは矛盾である．□


　さて、Jech本にはこの定理の証明はヒントしかなくて『\{\xi:\alpha \le \xi < \beta\}の順序型を\deltaとせよ』とある．これ結構、謎のヒントである．私が困ったときによく参考にしている StackExchangeでもこのヒントをコピペしただけの解答に『その証明が知りたいんだよ！』と怒っている人がいるぐらいで役に立たなかった．それでも超限帰納法でできるとのヒントもあったので先の証明をひねり出してみたわけである．とはいえJech本のヒントに沿った証明も考えてみたが、順序同型 h:\delta \to \{\xi:\alpha \le \xi < \beta\}が存在してもいまひとつこの仮定が使いにくいのである．しかし、よくよく考えるとこのhは\alpha+\delta=\betaならばg_\alpha: x \mapsto \alpha+xに一致しなければならないはずである．ただ、現時点ではg_\alpha: \delta \to I:=\{\xi:\alpha \le \xi < \beta\}が全射かどうか（そもそも値域からはみ出ていないかすら）分かっていないわけである．

＜別証明＞
　まず、 hとg_\alphaが\deltaから順序数のクラスへの写像として等しいことを\deltaまでの超限帰納法で証明しよう．まず、h(0)=\alpha=g_\alpha(0)である．\xi < \gamma < \deltaなる \xiについて h(\xi)=g_\alpha(\xi)が成立したとする．\gammaが後続順序数で \gamma=\zeta + 1とすると、h(\zeta)=g_\alpha(\zeta)．h(\zeta) < h(\zeta+1)だが、\zeta < \zeta' < \zeta+1なるような \zeta'は存在しない（∵ \zeta' \in \zeta \cup \{\zeta\}から \zeta' \in \zetaまたは \zeta' = \zetaはいずれも矛盾）ので hが順序同型であることから h(\zeta) < h(\zeta+1)の間には順序数は存在せず、h(\zeta) < h(\zeta+1) \le h(\zeta)+1．もし、この後ろの等号が成立しないとすると h(\zeta) < h(\zeta+1) < h(\zeta)+1となるが、これが成り立たないことは先にみたので、h(\zeta+1)=h(\zeta)+1=g_\alpha(\zeta)+1=g_\alpha(\zeta+1) で h(\gamma)=g_\alpha(\gamma)が成立する．最後に\gammaが極限順序数のとき、\gamma = \cup_{\xi < \gamma}\xiで g_\alpha(\gamma)=\cup_{\xi < \gamma}(\alpha+\xi)は加法の定義．一方、\alpha+\xi=g_\alpha(\xi)=h(\xi) < h(\gamma)より、\alpha+\xi \subset h(\gamma)（∵推移性）．よって、\alpha+\gamma \subset h(\gamma)．ここで等号が成立しない場合は、\alpha+\gamma \in h(\gamma)となるが、\gamma':=h^{-1}(\alpha+\gamma) < \gammaとしたとき、\gammaが極限順序数だったので、\gamma' < \gamma'' < \gammaなる順序数 \gamma''が存在する．hを掛けると h(\gamma') < h(\gamma'')だが、h(\gamma')=\alpha+\gamma < h(\gamma'')=\alpha+\gamma''は加法の単調性に矛盾する．よって、\alpha+\gamma = h(\gamma)となって超限帰納法が完成する．
　さて、\alpha+\delta=\betaを証明しよう．もし、\alpha+\delta < \betaなら、\alpha+\delta \in Iなので h^{-1}(\alpha+\delta)=\delta' < \deltaとすると、\alpha+\delta'=h(\delta')=\alpha+\deltaは矛盾である．\beta < \alpha+\deltaとしよう．すなわち \beta \in \alpha+\deltaだが、\deltaが後続順序数でも極限順序数でも、\xi < \deltaで\beta \le \alpha+\xiなるものが存在する(∵ \delta=\delta'+1 なら \beta \in (\alpha+\delta') \cup \{\alpha+\delta'\}．\delta=\cup_{\xi < \delta} \xiなら \beta \in \cup_{\xi < \delta} (\alpha+\xi))．これは hの像がIに入っていないことになり矛盾である．よって、\alpha+\delta=\beta　□


確かにこれは長い．．．

■

[集合論]InductionとRecursion

　タイトルは和訳では、『帰納と再帰』となるだろうか。最近読んでいたどれかの本で（Jech本ではなかった気がする）数学書でもこの２つの用語がごっちゃになってることがあるとの指摘があった。前回の私の記事でも、『関数を帰納的に定義する』というようなことをいっちゃってたような気がするが、正しくは『関数を再帰的に定義する』である。ややこしいのは『帰納的定義』というのもあって、単純なオブジェクトから複雑なオブジェクト作る手順が
① なんちゃらはオブジェクトである。
② オブジェクトとオブジェクトを一定の手順で組み合わせるとオブジェクトができる。
③ オブジェクトはすべてこれらの操作のみで作られる。
というやつである。帰納的に定義されたオブジェクトの集まり（クラス）に対しては、オブジェクトのある性質について、その帰納的定義の構造に基づく帰納法により全てのオブジェクトでその性質が成り立つといった証明ができる。しかし、一旦、帰納的定義を忘れて、考えているオブジェクトのクラスが先に存在したとしよう。

帰納法：
オブジェクトのある性質Rについて、

① なんちゃらは性質Rを持つ。
② 性質Rを持つオブジェクトを一定の手順で組み合わせると性質Rを持つオブジェクトができる。
ならば、すべてのオブジェクトが性質Rを持つ。

といった形の論法が帰納法である。次に見る順序数のように帰納法は成り立つが、オブジェクトが必ずしも帰納的に定義されているわけではない場合がある。

定理（超限帰納法 Transfinite Induction; たとえば Jech本p.21のTheorem 2.14）
　Cを順序数のクラスとする。Cが次の3つの条件を満たすと、それは順序数全体と一致する。

(i) 0\in C
(ii) \alpha \in C\ \Rightarrow \ \alpha+1 \in C
(iii) \alphaが0でない極限順序数であるとき、\forall\beta < \alpha;\ \beta \in C \Rightarrow \alpha \in C

ちなみにこの手順を逆にして、順序数を帰納的に定義したようなテキストは見たことない。順序数の定義としては、推移的かつ\inに関する整列集合という定義以外は知らない（このフォン・ノイマン流定義を最初見たときは、なんじゃこれはと思ったが、今となっては良くできた定義であると思う。フォン・ノイマンすげえ）。手順が逆にできない理由は、(iii)で極限順序数\alphaなるものの存在が先にある点で、\alpha=\cup_{\beta < \alpha}\betaを知っているとしても、この右辺の和集合の条件に\alphaが出てきてしまっている。ここを仮に『これまでの過程で作ったすべての順序数』としてみても、『これまでの過程で作ったすべての順序数』の集まりが集合になっている保証がなければその和も集合になっている保証はない。恐らくそれをいちいち確かめなければならない点で帰納的定義が躓くのだろうと思う。

ところで、上の定理の証明はJech本ではまさかの一行証明である。

＜証明＞ そうでなければ、\alphaを\alpha \notin Cなる最小の順序数として、(i),(ii),(iii)を適用せよ。

まあ、無論、Jech本では証明の前に準備はあるのだが、\alphaは0か\alpha=\beta+1となる\betaがあるか、極限順序数なので(i),(ii),(iii)を適用すると\alpha\in Cとなって矛盾するという論法である。任意の順序数のクラスCに最小元があるというのがミソで、実際 \alpha=\cap Cとなっていて、それはいつでも集合（かつ順序数）であるということが事前に証明されているので抜かりはない。


さて、前回に関数の再帰的定義は集合論としても正しいという一例を証明してみたが、実は今回の記事はその続きでもある。底本はJech本だが、テキストではTransfinite Recursion の証明は 1/3ページぐらいしか証明がなく、ギャップを埋めてみようという魂胆である。それに Transfinite Recursion の定式の意味の理解にかなり苦しんだのでそのノートという意図もある。

さて、記号の準備から始める。集合に値を取るOrd上の関数クラスを考えたいので、それを

< a_\alpha\ :\ \alpha \in Ord >

と書こう。これを列(sequence)と呼ぶ。無論これの実体は \{(\alpha, a_\alpha) | \alpha \in Ord \}というペアのクラスだが、Ordがもともと集合でないので、これも真のクラスである。ただ、ある順序数\thetaでちょんぎった
< a_\alpha\ :\ \alpha < \theta >

なるものは集合になっていて、これを \theta-列と呼ぼう。\theta-列が集合になるのは、\{\alpha | \alpha \in \theta\}は集合なので、置換公理からその像 \{a_\alpha | \alpha \in \theta \}も集合で、
< a_\alpha\ :\ \alpha < \theta >=\{ (\alpha,y) \in \theta \times \{a_\alpha | \alpha \in \theta \}| \alpha \in \theta \wedge y=a_\alpha \}
から分出公理により集合となる。ただし、『集合に値を取る』というのが特定の集合内に値を取るということではなくて、集合全部を動く可能性も含むので \thetaを固定したとしても、\theta-列の全体は真のクラスとなってしまう。ちょっと風呂敷広げすぎとは思う。さて、ここでGを、\thetaがすべてのOrgを動くときの全ての\theta-列のクラス上で定義された、集合に値を取る任意の関数クラスとしよう（さらに風呂敷が広がったわけである）。


定理 (超限再帰法 Transfinite Recursion)
　(先に述べたような)任意のGに対して、Org上の関数クラス Fで、任意の順序数 \alphaに対して、

F(\alpha)=G(F \upharpoonright \alpha)

が成立するものが唯一存在する。

（Fは列であり、F \upharpoonright \alphaは列Fを\alphaでちょん切った \alpha-列を指す記号である。）

風呂敷を広げまくった割にはこじんまりとした定理であるが、これのどこがRecursionなのか最初はピンとはこなかった。しかし、ちょっと最初の方を具体的に計算してみるとその意味がわかってくる。F=< a_\alpha\ :\ \alpha \in Ord > として、F(\alpha)=a_\alphaという列としての表記も併用しよう。

・まず、\alpha=0からスタートである。Fがなんであれ F \upharpoonright 0 = 0なので、結局 a_0=F(0)=G(0)である。

・\alpha=1のとき、もうa_0は決まってしまっているので、a_1=F(1)=G( < a_0 > )。

・\alpha=2のとき、もうa_0,a_1は決まってしまっていて、a_2=F(2)=G( < a_0,a_1 > )。

とまあ、以下FがGで決まってしまうのが見て取れるだろう。しかもすべての\alpha-列の上での関数クラスとしているため、引数の数でG_nと分けて書けば、F(n)=G_n(G_0,G_1(G_0),G_2(G_0,G_1(G_0)),\cdots ),\cdots,G_{n-1}(G_0,\cdots)) といったようにその時点より前に計算したすべての値をパラメータに使う最も一般的な再帰的定義を表現していることがわかるだろう（しかもそのTransfinite版である）。

＜証明＞
　任意の順序数 \alphaに対して、F(\alpha)を定義したい。\xi < \alphaなるすべての順序数 \xiに対して、F(\xi)が定義されていて、F(\xi)=G(F\upharpoonright \xi)が成立しているとしよう。このとき、F(\alpha)=G(F\upharpoonright \alpha)と定義すればよいだろう。しかし、この定義のありようはTransfinite Recursionそのものなので、これを素直に認めてしまったら証明にならない。アヤシイのは『F(\xi)が定義されていて』の部分である。Jech本の証明ではこれを\alphaごとにつどつど、つぎの条件を満たす\alpha-列の存在に置き換える。

条件：(\forall \xi < \alpha)a_\xi=G( < a_\eta:\eta < \xi \ > )

この条件を満たす\alpha-列sが唯一存在する（証明はのちほど）が、このとき、F(\alpha)=G(s)と定義するのである。この構成だとF:=\{(\alpha,F(\alpha))| \alpha \in Ord\}が論理式で閉じた形で表現できるため、Fは関数クラスとなる。また、\alphaに対して、\alpha-列 < F(\xi):\xi < \alpha > = F \upharpoonright \alphaが、(\forall \xi < \alpha)F(\xi)=G( < F(\eta):\eta < \xi \ > )を満たすつまり、先の条件を満たす\alpha-列になっていることが証明できるので、Fが定理の条件を満たしていることがわかる。
(この最後のステートメントを念のため証明しておこう。超限帰納法と同じ論法である。\xi=0の時は F(0)=G(0)なので成立している。先の条件を満たさない最小の順序数を\xi_0 < \alphaとしよう。\xi < \xi_0に対しては、\xi_0-列 F\upharpoonright \xiが先の条件を満たすため、F(\xi_0)の定義に使う唯一の\xi_0-列に一致するので、 F(\xi_0)=G(F\upharpoonright \xi_0)となるが、これは\xi_0が条件をみたすことになり、矛盾である。)
　残した\alpha-列の存在と唯一性を証明しよう。ただ、唯一性については上の証明とほぼ同じなので、存在だけを示そう。\alphaに対する超限帰納法を使う。条件をみたす\alpha-列が存在する順序数の全体のクラスをCとしよう。
(i) \alpha=0の時、a_0:=G(0)とすればよいので 0 \in C。
(ii) \alpha \in Cのとき、\xi < \alpha+1とは、\xi < \alphaか\xi = \alphaなので、\xi < \alphaの時は条件は仮定\alpha \in Cから成立しており、a_{\alpha}:=G( < a_\eta:\eta < \alpha \ > )とすれば\xi = \alphaでも条件が成立するので、 \alpha+1 \in C。
(iii)\alpha \in Cが0でない極限順序数のとき、\forall\beta < \alphaに対して \beta \in Cとしよう。各々の\betaに対する条件は (\forall \xi < \beta)a_\xi=G( < a_\eta:\eta < \xi \ > )となる。右辺の数列は\betaごとに違ってもいいのだが、実際は定義されているところではすべて一致している（これも超限帰納法による）。そこで F_\beta := \{(\xi,a_\xi) | \xi < \beta \}と書いて、F_\alpha := \cup_{\beta < \alpha} F_\beta を作ると F_\alphaは\alpha-列を定義することがわかる（Jech本では、この和を作るときのインデックスが順序数\alphaなので、和は集合になるとの注意がある）。しかも、 \forall\xi < \alphaに対して、\beta := \xi+1 < \alpha なので(∵ \alphaが極限順序数だったから)、\betaに対する超限帰納法の仮定から、a_\xi=G( < a_\eta:\eta < \xi \ > )が成立しているが、右辺のGの中は < F_\alpha(\eta):\eta < \xi \ > に等しいので、条件が成立している。よって \alpha \in C
よって、超限帰納法より C=Ordとなる。□


　前回の記事で気にしていたのは、再帰的に定義された関数は本当に（集合としての）関数か？という点にあったのだが、今回の超限再帰法の定理では、Ord上の関数クラスの存在しか主張してない点で、もう一押しが必要である。とはいえ、\omegaまでの話を考えればいいだろう。Gが、\omega-列上にしか定義されていないとき、\omegaに等しいか大きい順序数\alphaに対する\alpha-列には、 0と拡張しておけば、今回の超限再帰法の定理が使えて、それに対応する関数クラスFが存在する。そこで F \upharpoonright \omegaが関数か？が問題となるが、これは置換公理からほぼ自明となっている...のでまあ、Fが関数クラスとして定義されうるという点が本質ということなのだろうが、なんか肩透かし感はある。

（蛇足編）
　本記事を書くにあたって、何か証明のヒントは無いかとKunen本（集合論 独立性証明への案内 日本評論社）も調べてみたところ、Jech本の証明と同じ筋でした。こっちのがもう少し筋を明確に書いてますね。Kunen本の原著の初版が1983年なのでこっちのが断然前ですな。しかし、そこの続きにも超限帰納法を使えとだけ...

■

[集合論]任意の無限集合は可算無限集合を含む（のか？）

　タイトルの『任意の無限集合は可算無限集合を含む』は選択公理の話題には必ず出てくる有名な命題である。まずダメだとされる証明をあげよう。

＜証明 Ver.0＞
　無限集合をAとする。

① Aは空集合でないので、何か元 a_1が存在する。
② Aから、a_1を除いた集合は空でない。なぜならこれが空になることはAが無限集合であることに反するから。そこで何か元 a_2 \in A-\{a_1\}が存在する。
③ 同様に②の手続き"a_{n+1}をA-\{a_1,a_2,\cdots,a_n\}から取り出す"を繰り返すと、加算無限集合 C＝\{a_1,a_2,a_3,\cdots\}\subset Aが得られる。□

この証明がダメだと言われるのは、選択公理が必要なことが明示的になっていないからだとされる。ちなみに②で『空でない集合から元を選んでくる』というところに選択公理が必要なのではないので要注意。この点については後でも触れる。
　本当にダメなのは③である。無限に続く手続きが何かを定義しているかどうかアヤシイし、そもそも元を列挙しても、それが集合を定義しているという保証はない。ZFC公理系にそのような集合の定義はないからである。もし、この列挙する条件が論理式\phiで閉じた形で記述できるのなら、 C=\{x\in A| \phi(x) \}は分出公理から集合となる。

次によくある選択公理を明示的に用いた証明を見よう。

＜証明 Ver.1＞
　無限集合をAとする。Aから任意の有限集合\mu（0個のときの\phiも含む）を抜き去った集合をA_\mu:=A-\muと書く。\muがAのすべての有限集合の族Gを動くときの集合族を \{A_\mu \}_{\mu\in G}とする。Aが無限集合なのでどのA_\muも空ではない。そこで選択公理から選択函数 fが存在して、f(\mu)\in A_\muとできる。

① a_1=f(A)とする。
② a_{n+1}:=f(A-\{a_1,a_2,\cdots,a_n\})と定義する。
③ これを繰り返すことで C＝\{a_1,a_2,a_3,\cdots\}\subset Aが得られる。□

うおおおおおい。③がおんなじやがな。無限操作と列挙という Ver.0と同じ欠点を持つこの証明を見て、何が違うのかと私は頭を抱えていたのである。しかし、お手元の関連書籍の証明を調べていただくと分かるがこれ以上の説明は無いことが多い。てか、この先を見たことない。
　しかし、Ver.1のいいところは証明中に出てくる概念がすべて集合論の言葉で書かれており、『選択する』というVer.0の操作が、Ver.1では関数fを適用するに置き換えられている点にある。そう、Ver.1 では関数 n \mapsto a_nが帰納的に定義されていると言えるのである。すると問題はえらく一般的になって、集合論において関数の帰納的定義の正当性を明らかにすればよいことになる。もう、この時点では選択公理の出番は終わっている。ちなみに関数（関数クラスでもよい） n \mapsto a_nが集合論的に正しく定義されていれば、その像であるCが集合であることは置換公理から出る。

　実は、数学的帰納法を公理に含む整数論（ペアノの公理系とか）を集合論から組み立てる際に必要となる、帰納的に定義された関数の集合論的な存在の証明を彌永昌吉『数の体系　上』（岩波新書）の付録で最近たまたま見たときにやっと腑に落ちた次第である（購入したのは高校生だったときのような気がする。当時はまったく読んでませんが）。

　そこでの論法をここで真似てみよう。ただ、ちょっとだけ手抜きしたいのは、先に『Aのすべての有限集合の族G』なるものを考えたが、これが集合になっているというのはそもそも有限集合とはなんぞやという話になるので、ここでは一旦Gは集合であることは認めていただきたい。集合論での自然数の定義を認めるなら、自然数のどれかと全単射があるとか、デデキントの無限の定義の否定であるところの真の部分集合に対して、全単射が存在しないとかそんな有限集合の定義のどれかを採用していると考えて欲しい。

すると \mu \mapsto A_\muは関数なので、置換公理から \{A_\mu \}_{\mu\in G}も集合である。

まず、\mathbb{N}\times \{A_\mu \}_{\mu\in G}は集合で、そのベキ\mathcal{P}(\mathbb{N}\times \{A_\mu \}_{\mu\in G})も集合で、その元は二項関係である。さらにそのベキ集合F:=\mathcal{P}(\mathcal{P}(\mathbb{N}\times \{A_\mu \}_{\mu\in G}))の元とは、二項関係を集めた集合族である。この二項関係の集合族のうち次のような論理式を満たすものを分出公理で選ぶとそれもまた集合である。
G:=\{X \in F |\ (0,A)\in X \ かつ \ (n,B)\in X \Rightarrow (n+1,B-f(B)) \in X\}

積集合の全体X=\mathbb{N}\times \{A_\mu \}_{\mu\in G}はこの条件を満たすため、Gは空ではない。そこで \cap G \in \mathcal{P}(\mathbb{N}\times \{A_\mu \}_{\mu \in G})を考えるとこの共通集合は先の条件を満たす最小の二項関係ということになる。(0,A)\in \cap Gより、この共通集合は空ではない。さらにこの二項関係が関数かつ単射であることを示そう。(0,B)\in \cap Gなる元で、A\neq Bなるものがあったとする。そこで\cap G-\{(0,B)\}を考えるとこれ自身が Gの元となる条件を満たしていることがわかるので、\cap Gの最小性に反する。同様な方法で、n=Nまで単射なら、n=N+1でも単射であることが示せる。要するにこれが欲しかった単射 \mathbb{N}\to \{A_\mu \}_{\mu\in G}である。この関数にfを合成してやれば、単射 \mathbb{N}\to Aが得られる。□

　まあ、七面倒な手順を踏んでいるが『関数を帰納的に定義してよろしい、ただしその定義中に使う道具は集合であること』となる。なので、選択公理で関数fの存在が本質的というのはまあ、今となっては首肯できるところである。

　さて、ちょっと話題はもどるが、選択公理の定義で集合族\{X_\mu\}_{\mu \in I}の元の各々は空でないから、x_\mu \in X_\muなるようなx_\muの存在が保証されている。この点は不思議はないのだが、それを集めて関数 \{(\mu,x_\mu)\}_{\mu \in I} \subset I\times \cup X_\mu を定義しようとしても、この時点でこれが集合である保証がないのである（列挙による集合の定義は認められていない）。分出公理を使おうにももし、\{(\mu,x)|x\in X_\mu \wedge \phi(\mu,x)\}のように書けたなら、そもそも\phi(\mu,x)が選出函数である。


　さて、実は今までの話は全て前置きである。ここで最近知った衝撃的な事実を述べよう。ソースは田中尚夫『選択公理と数学』（遊星社）である（例によって、Amazon価格は定価の倍以上なので購入はお勧めしない。私はたまたま持ってましたが、無論ちゃんとは読めてません）。

『ZF公理系と命題「任意の無限集合は可算無限集合を含む」は独立である』

これはつまりは、

『ZF公理系のモデルで可算無限集合を含まない無限集合が存在するものがある』

となる。なかなか直観に反するトンデモないモデルであるが、どうやらZFと選択公理の独立性を示すモデルがそれになっているらしい。選択公理についてはとやかく言われることがあるが、選択公理が無いなら無いでこんな変なことが起こるというのが面白い。

Jech本のPart IIのforcingのあたりをざくっと調べてみたが、ぴったり同じ記述は見つからなかった（そもそも書いてあることはさっぱりわからないわけですが）。いやまあ、こんなところまでたどり着けるかどうかこれはこれで楽しみですねぇ。

■

[数論]高木貞治『初等整数論講義 第二版』第五章ノート その15

　最近はめっきり更新間隔がでたらめだが、これは実は次に読もうと思う数学書を物色しているうちにそっちに読み始めてしまっているという単純な理由である。二次体という具体的なものを一生懸命やった反動で反対方向に振れてしまって JechのSet Theoryという太い本に手をだしている。公理論的集合論はいままで何度かトライしてみたことがあるのだが、あまり先に進めないまま挫折してきた。途中で証明のロジックのツボがわからなくなってしまうのである（そういうときはだいたい定義や公理の意味をきちんと理解できていないときが多い）。しかし、今回は何かが臨界に達したのか、『読める、読めるぞ！』という感じである。この調子でPart I Basic Set Theory ぐらいまではいければいいな。しかし、この分野にはちょこっと計算の出番がないという欠点があってブログのネタになかなかならないんだよねぇ...

さて、§52の最後の問題５である。合わせて§53で５章は終わりとなる。

[問題５]　x^2-5y^2=k　D=20,\ f=2: K(\sqrt{5})
　N(x+\sqrt{5}y)=k. A=[1,\sqrt{5}]=(1),\ N(A)=1なのでN(J)=|k|なるような単項イデアル Jを探すことになる。ただ、テキストにあるようにK(\sqrt{5})ではh=1なので、単項イデアルという条件はいつでも成り立っており、ノルムだけの問題となる。まず例によってK(\sqrt{5})における有理素数の分解状況を確認しよう。d=5なので、分岐するのは 5のみ。(\frac{5}{p})=(\frac{p}{5})より p\equiv \pm 1 \pmod{5}の時、完全分解。p\equiv \pm 2 \pmod{5}の時、惰性。そこで Jが原始イデアル条件は、完全分解される有理素数(p=5n\pm 1)あるいは、p=5を高々一回のみ含む場合となる。ただ、テキストには J=(\rho)であっても一般には\rho=\frac{a+b\sqrt{5}}{2}なので、有理整数解を得るにはa,bともに偶数である必要があるとかいまさら指摘があるが、これはイデアルの問題Cの言い換えに過ぎないので何も新しい問題ではない。
　さて、\epsilon_0:=\frac{1+\sqrt{5}}{2}のノルムは-1なので、\rhoに\epsilon_0を掛ければ符号を変えられるので、kが正でも負でも N(\alpha)=kなる整数 \alphaが存在する。\epsilon:={\epsilon_0}^2=\frac{3+\sqrt{5}}{2}がN(\epsilon)=1なる基本単数である。
\epsilon^2=(\frac{3+\sqrt{5}}{2})^2=\frac{7+3\sqrt{5}}{2},\ \epsilon^3=\frac{7+3\sqrt{5}}{2}\frac{3+\sqrt{5}}{2}=9+4\sqrt{5}なので、\epsilon^3が判別式20に対する基本単数である。よって、\alpha,\ \alpha\epsilon,\ \alpha\epsilon^{-1}のどれかがx+y\sqrt{5}という形をしているものがあればそれが解であり、なければ解は無い。
　テキストでは続けて、解があるなら \alpha,\ \alpha\epsilon,\ \alpha\epsilon^{-1}の中の一つだけに限るという考察を続けているが、まあ、具体的な問題だと３回やるだけなので、あまり重要性を感じないが、いつものように整理してみよう。

　\alpha=\frac{a+b\sqrt{5}}{2}としたとき、b,\ \frac{a+3b}{2},\ \frac{-a+3b}{2}のうち一つだけが偶数になるというのが同値な主張である。
ここでノルムの条件 \frac{a^2-5b^2}{4}=kが成立している。また、原始解の場合、先の考察からkは奇数である。

ア）bが奇数の場合：
\alphaが整数なので、aも奇数。一方、\frac{a+3b}{2}-\frac{-a+3b}{2}=aなので、\frac{a+3b}{2},\ \frac{-a+3b}{2}の片方だけが偶数となる。よってこの場合はOKである。

イ）bが偶数の場合：
\alphaが整数なので、aも偶数。一方、ア）と同様の考察により、\frac{a+3b}{2},\ \frac{-a+3b}{2}は同時に奇数（この場合は証明完了）か偶数となる。偶数の場合、(a/2+3b/2)(-a/2+3b/2)\equiv 0 \pmod{4}となるが、一方、k=(a/2)^2-5(b/2)^2\equiv (a/2)^2-(b/2)^2\equiv (a/2-b/2)(a/2+b/2)
\equiv -(a/2-b/2)(a/2+b/2) \equiv 0 \pmod{4}より、kが奇数であることに矛盾する。□


例１）　x^2-5y^2=11:
11は(\frac{11}{5})=(\frac{1}{5})=1なので完全分解する有理素数である。ちょこっと計算すると P=[11,4+\sqrt{5}])となるが、これは実は単項イデアル(4+\sqrt{5})になっているのはすぐにわかる。で、この場合はもうこれで終わりで、一般解は x+y\sqrt{5}=\pm (4+\sqrt{5})(9\pm 4\sqrt{5})^n\ (n=0,1,2,\cdots)となる。

例２） 　x^2-5y^2=19:
19は(\frac{19}{5})=(\frac{-1}{5})=1なのでこれも完全分解する有理素数である。素イデアルを求める計算をきちんとやると、r^2\equiv 5 \pmod{19}を総当たりで解いて r=9. 2b+1\equiv 9 \pmod{19}は さくっと b=4で解けるので、P=[19,4+\omega]=[19,\frac{9+\sqrt{5}}{2}]. これも単項イデアル (\frac{9+\sqrt{5}}{2})となっている。すなわち、\alpha=\frac{9+\sqrt{5}}{2}で、\alpha \epsilon=\frac{9+\sqrt{5}}{2}\cdot \frac{3+\sqrt{5}}{2}=8+3\sqrt{5} からOKでこれから一般解が作れる。念のため、\alpha \epsilon^{-1}=\frac{9+\sqrt{5}}{2}\cdot \frac{3-\sqrt{5}}{2}=8+3\sqrt{5}=\frac{11-3\sqrt{5}}{2}で、これは解にならない。


ラストの§53は一般の二次二元不定方程式を扱っている。結局、斉次式に変形できて、いままでのイデアルによる解法が使える。ただし、元の不定方程式の整数解があれば変形後の方程式の整数解が存在するが、逆の変形が整数解を整数解に対応させないこともあるので、変形後の整数解が元の不定方程式の整数解になっているかは個別に検討する必要があるようだ。計算そのものはそう面白いものではないので、テキストの『次の例はGaussが取り扱ったものである』の部分にこだわってみた。その例とは

x^2+8xy+y^2+2x-4y+1=0

だが、Gaussの『 Disquisitiones Arithmeticae』のラテン語原書のpp.307-308にある。左ページの中央やや下あたりである。

一般解がさらっと記載されているが、原書の第5章で140ページぐらい一般論で費やした結果の例の一つのようだ。式の形は微妙に違って見えるが、具体的な解はテキストと一致している。変形後の不定方程式の定数項をわざわざ3^2倍してあるのはp,qが3で割れるのにいまひとつ理由はわからない。Gaussの一般論からの都合なのかもしれないが、衒学的考察はこれぐらいにしておこう。

　2節の判別式が0になるときは、まあ大体問題は簡単に解けるようになるのだが、モ変形を使うのがふーんという感じである。ちなみに天下りのY=-x+yの方は、X=3x-2yの3と2が互いに素なので、そこから出してきている。

さて、長々と続いた『第五章ノート』も今回でいったん終了である。んー次のネタなにするかなぁ...実は『初等整数論講義 第2版』は附録が最も面白いという評判ががが...