■

[集合論] 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の部分的な定義はすべて共通の定義域で一致しているからである□