■

[集合論] Jech本三章章末問題その１（Jech本p.34）

　やってみて気になった問題を解説する．

＜問題3.5＞　\Gamma(\alpha\times\alpha) \le \omega^\alpha

　左辺で\alphaがAlephのたびに\Gamma(\alpha\times\alpha)=\alphaに戻るのに対して右辺のベキは単調増加だから評価ガバガバやんと思っていたのだが，\alpha=\omega^\alphaみたいな不動点は\epsilon_0を含め無限に存在するので逆にイケてる不等式なんじゃないかと，証明した後で気が付いた．

＜証明＞
\alphaに対する超限帰納法．\alpha=0のときは成立している．\alpha+1のとき，(\alpha+1)\times(\alpha+1)の順序がどうなっているかを見てみると

\alpha\times\alpha\mbox{ の元} < \{(x,\alpha):x\in \alpha\} < \{(\alpha,y):y\in \alpha\} < (\alpha,\alpha) ( < (0,\alpha+1) )

(最後の(0,\alpha+1)は(\alpha+1)\times(\alpha+1)の元ではないが，始切片であることを表した)．これを順序数の和で表現すると，

\Gamma( (\alpha+1)\times(\alpha+1) )=\Gamma(\alpha\times\alpha)+\alpha+\alpha+1

となる．帰納法の仮定と\alpha \le \omega^\alphaを使うと，

\Gamma( (\alpha+1)\times(\alpha+1) )=\omega^\alpha+\omega^\alpha+\omega^\alpha+1 \le \omega^\alpha\cdot\omega=\omega^{\alpha+1}

となりOKである．\alpha=lim_{\xi\to \alpha}\xiであるとき，\xi\times \xiが始切片W( (0,\xi) )であることから，\Gamma(\alpha\times\alpha)=lim_{\xi\to\alpha}\Gamma(\xi\times\xi)．一方，帰納法の仮定から\Gamma(\xi\times\xi) \le \omega^\xi \le \omega^\alphaで左辺の極限を取れば，\Gamma(\alpha\times\alpha) \le \omega^\alphaが成立する □


＜問題3.6＞　Ordのすべての有限列のクラスに整列順序を入れて，すべての順序数\alphaに対して，\omega_\alphaの中の全ての有限列の集合が，始切片となりかつその順序タイプが\omega_\alphaになるものがある．

　どうせならその整列順序の定義も書いておいてよ，と思うのだが．\omegaでの経験から，有限列のmax値でまず順序を付けて，その中では辞書式順序でいけるだろうか．整列性については，それぞれの有限列のmax値の最小値が存在するので，その最小値を取る有限列の集合を辞書式順序でみたとき，列の1番目の最小値を与える列の中から，二番目の最小値を与える列の中から...と調べていくが...あーこれはだめだ．0がn個続いて，1で終わる有限列のnを全て動かして集めた集合には最小元がない．そこでちょっと修正して，max値の小さいもの，列の短いもの，最後は辞書式に並べよう．これならば，整列順序である．

＜証明＞
まず，一般的に\alphaの中に値を取る有限列\{\alpha_i:0 \le i < n\}が上の順序で，\{\alpha_i\} < \{\alpha\}となっているのはほぼ自明であろう（∵最初にmax値で大小が決まるため）．よって問題の始切片の部分は示された．
　後半部だが，\psi:\omega_\alpha \to W(\{\omega_\alpha\})を\psi(\xi):=\{\xi\}と定めれば，\psiは順序を保つ写像なので，\omega_\alpha \le \Gamma(W(\{\omega_\alpha\}))であることは分かる．\alpha=0のときは有限順序数の有限列の全体は\omegaに順序同型になるとほぼ同じ論法で，\omega = \Gamma(W(\{\omega\}))は成立している．この等号が成立しないつまり，\omega_\alpha < \Gamma(W(\{\omega_\alpha\}))となっている最小の順序数を\alphaとしておく（ただ，以下の証明では最小性は微妙に使っていない）．上の不等号から，\omega_\alphaは\Gamma(W(\{\omega_\alpha\}))の始切片なので，それはW(\{\omega_\alpha\})のある始切片に対応する．その始切片を定義する有限列を\{\alpha_i:0 \le i < n,\ \alpha_i < \omega_\alpha\}としよう．すなわち\omega_\alpha = \Gamma(W(\{\alpha_i:0 \le i < n\})．この右辺の集合濃度を評価する．\beta:=max\{\alpha_i:0 \le i < n\}+1とすると\beta < \omega_\alphaで|\beta| \le \omega_{\alpha'} < \omega_\alphaなるような無限基数\omega_{\alpha'}があるとしてよい．一方，W(\{\alpha_i:0 \le i < n\})\subset W(\{\beta\})．右辺は集合としては A:=\cup_{n=0}^{\infty} \beta^nに等しく，その濃度は|A|=\sum_{n=0}^{\infty}|\beta|^n=\sum_{n=0}^{\infty}|\omega_{\alpha'}|^n．ところが定理3.5から，\forall n > 0\ (|\omega_{\alpha'}|^n=|\omega_{\alpha'}|)なので |A|=\sum_{n=0}^{\infty}|\omega_{\alpha'}|=|\omega_{\alpha'}|\cdot |\omega| \le |\omega_{\alpha'}|\cdot |\omega_{\alpha'}|=|\omega_{\alpha'}| < |\omega_\alpha|．しかし，これは\omega_\alpha=\Gamma(W(\{\alpha_i:0 \le i < n\}) に矛盾する □


以下の問題で次の用語を使う：

集合Bが集合Aのprojection \overset{\text{def}}{\Longleftrightarrow} 全射：A\to Bが存在する

ここでさらっと選択公理を仮定すると

集合Bが集合Aのprojection \Leftrightarrow |A| \ge |B|

と述べられている．逆像から選択公理で一つ元を選べば，B\to Aなる単射が得られるのでこれは正しい．テキストではこれに続いて，選択公理なしにはこのことは証明できないと述べている．これは選択公理を仮定しないZF公理系で上のステートメントが成立しないモデルが作れるという意味だが，今は深追いは避けておこう．

＜問題3.7＞　Bが\omega_\alphaのprojection ならば |B| \le \aleph_\alpha

＜証明＞
なんだかすでに上で証明してしまった感はあるが，選択公理の仮定が無くても projection \omega_\alpha \to Bの逆像から最小元を選べばよい □

＜問題3.8＞　\omega_\alphaの有限部分集合の全体の集合濃度は\aleph_\alpha

＜証明＞
問題3.6から\omega_\alphaの有限部分列の集合の全体(Sと書く）の集合濃度は\aleph_\alphaとわかっている．任意の有限列から要素を集めて有限集合を作れば，有限列全体の集合(Fと書く）から有限部分集合全体の集合への全射が得られる．つまり，\aleph_\alphaから全射が入るので 問題3.7から|F| \le |S|=\aleph_\alpha. 一方，\omega_\alphaの元を一つの元からなら部分集合だと思えば，単射 \omega_\alpha \to Fが存在するので，\aleph_\alpha \le |F| □

＜問題3.9＞　Bが\omega_\alphaのprojection ならば |P(B)| \le |P(A)|

＜証明＞
f:A\to Bを全射とする．X\in P(B)に対して，f^{-1}(X)\in P(A)を対応させる写像は単射である（∵fが全射なので f\circ f^{-1}=id_{P(B)}） □

＜問題3.10＞　\omega_{\alpha+1}はP(\omega_\alpha)のprojectionである．

＜証明＞
ヒントがなかなか難しい．定理3.5から|\omega_\alpha \times \omega_\alpha|=\omega_\alphaなので，P(\omega_\alpha)の代わりにP(\omega_\alpha \times \omega_\alpha)を考慮する．写像 f:P(\omega_\alpha \times \omega_\alpha)\to Ordを構成するのだが，R\in P(\omega_\alpha \times \omega_\alpha)でRが整列順序関係を与えるものに対しては，そのorder-typeをf(R)とし，そうでないようなRには（なんでもいいので）f(R):=0としておく．
　さて，この像が\omega_{\alpha+1}に一致することを示したい．まず，作り方から像になっているorder-typeの順序数\betaの濃度は高々\aleph_\alphaである．なので，\beta < \omega_{\alpha+1}でなければならず ran\ f \subset \omega_{\alpha+1}は明らか．逆に任意の\beta < \omega_{\alpha+1}なる順序数 \betaの濃度は基数の定義から |\beta| \le \aleph_\alphaなので，単射\psi:\beta \to \omega_\alphaが存在する．\alphaの整列順序の構造をran\ \psiに入れれば，\omega_\alpha（の部分集合）上に整列順序関係Rが定義されるが，作り方から f(R)=\betaなので題意が証明された □

＜問題3.11＞　\aleph_{\alpha+1} < 2^{2^{\aleph_\alpha}}．

＜証明＞　問題3.10と問題3.9から P(\aleph_{\alpha+1}) \le P(P(\aleph_\alpha))．一方，\aleph_{\alpha+1} < P(\aleph_{\alpha+1})なので題意の不等式が成立する □


＜問題3.12＞　\aleph_{\alpha}を非加算な極限基数とすると，cf\ \omega_\alpha=cf\ \alpha．

＜証明＞　\gamma := cf\ \omega_\alphaと書いて，\omega_\alpha=lim_{\xi < \gamma}\beta_\xiとする．\beta_\xiは必ずしも基数とは限らないので，\omega_\alpha(\xi)=|\beta_\xi|が成立するように \alpha(\xi)を定めると \alpha(\xi) < \alphaかつ \alpha=lim_{\xi < \gamma}\alpha(\xi)となっている（∵後半は\omega_\alphaが極限順序数であることを使った）．\gamma-列\{\alpha(\xi)\}は非減少列で，Lemma3.7 (ii)より，cf\ \gamma=cf\ \alpha．左辺は cf\ (cf\ \omega_\alpha)=cf\ \omega_\alphaなので題意が証明された □

＜問題3.12＞（ZF） \omega_2は可算個の可算集合族の和集合ではない．

　本文で示唆されていたが，これと同じステートメントを\omega_1で主張するには選択公理が必要ということである．

＜証明＞ ヒントに従う．\omega_2=\cup_{n < \omega}S_nで，各 S_nが高々可算集合としよう．\alpha_nをS_nのorder-typeとする．\alpha:=sup_n\ \alpha_nとすると \alpha \le \omega_1である（∵もし \omega_1 < \alphaなら \exists n\ (\omega_1 \le \alpha_n)だが，\alpha_nは高々可算な順序数なので無論これは成立しない）．ここで \omega\times \alphaから\omega_2の写像\psiを(n,\xi)\in \omega\times \alphaに対して，もし\xi \in \alpha_nならば\psi(n,\xi):=\xiに対応するS_nの元，そうでないときは\psi(n,\xi):=0とすれば，条件\omega_2=\cup_{n < \omega}S_nから\psi:\omega\times \alpha \to \omega_2が全射であることがわかる．一方で，\omega\times \alphaは\omega_1\times \omega_1の部分集合で |\omega_1\times \omega_1|=\omega_1(定理3.5)であるから結局（対応していない元は適当に0に写像すれば）\omega_1から\omega_2への全射が得られる．問題3.7より \aleph_2 \le \aleph_1が得られるがこれは矛盾である □