■

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

　後半戦はDedekind有限性に関してだが，あまり面白い問題はなかったのでまとめ風にしてみた．

まず定義：
集合SがDedekind有限
　　\overset{\text{def}}{\Longleftrightarrow} \forall S'\subsetneqq Sに対して，上へのone-to-one写像 \psi:S\to S'が存在しない.

集合SがDedekind無限
　　\overset{\text{def}}{\Longleftrightarrow} \exists S'\subsetneqq Sに対して，上へのone-to-one写像 \psi:S\to S'が存在する.

ある集合の真部分集合に対して，元の集合と一対一対応があるという直観的に正しそうな無限の定義である．Jech本での有限順序数へone-to-one写像が存在しないという（Dedekindと断らない）無限性の定義との関係を以前から知りたいと思っていたが今回の章末問題で解消できた．

まず，『有限　⇒ Dedekind有限』（対偶は『Dedekind無限 ⇒ 無限』）である（∵証明は普通の数学的帰納法を使えばよい）．この逆，『Dedekind有限 ⇒ 有限』あるいは『無限 ⇒ Dedekind無限』はどうかというと，選択公理を仮定するとこれは正しい（証明はすぐ後で）．というわけで選択公理があると，Dedekindの有限・無限性は本書の有限・無限性と一致してしまう．一方，選択公理がないとこの逆向きは証明できないとのコメントがある．


＜(AC)『無限 ⇒ Dedekind無限』の証明＞
選択公理を仮定すると任意の集合Sは整列可能で，ある基数\alphaが存在して，|S|=\alpha. Sが無限なら \omega \le \alphaで特に \omega \subset \alphaなので，Sは可算無限集合を含む．この可算無限集合に対しては一つずつずらし，それ以外は同じ要素を対応させる写像はSから0に対応する元を除いた真部分集合への上へのone-to-one写像になっている（問題3.14の左向き）．つまり，SはDedekind無限である □

実際のところ，選択公理を仮定せずに 『S:Dedekind無限 ⇔ Sが可算無限部分集合を含む』（問題3.14）となっている．この右辺の『Sが可算無限部分集合を含む』については以前にネタに取り上げたことがあるが，
(https://kazu-fgf.hatenablog.com/entry/2022/08/04/011920)
選択公理を仮定しない場合に無限集合なのに可算無限部分集合が存在しないという奇妙なことが起こるというのを覚えておられるだろうか？ それはまさに『無限 ⇒ Dedekind無限』の反例になっているというわけである．

右向き（⇒）については，テキストのヒント通り，Dedekind無限の定義を与える上へのone-to-one写像 f:S\to X \subsetneqq Sを使って，x_0 \in S-Xから始めて，x_{n+1}:=f(x_n)と作ればよい．以前のネタでも指摘したように，この無限操作には問題は無く，写像fがあれば可算無限部分集合は再帰的に定義可能なのである．

さて，選択公理を仮定しないときにはこの2つの有限・無限性の定義は異なることが分かったとして，その優劣はあるだろうか？ そもそも優劣を決める基準などは無いが，有限集合から構成されたいろいろな集合が再び有限集合であるかどうかという基準を採用してみよう．つまり集合を作り出す操作で閉じているかどうかである．

＜問題3.15＞

(i) A,B:Dedekind有限 なら A\cup B, A\times BもDedekind有限
(ii) S:Dedekind有限ならば， Sの値の重ならない有限列の全ての集合も Dedekind有限
(iii) 互いに素な Dedekind有限集合のDedekind有限個の族の和集合も Dedekind有限

＜解＞ 問題3.14のDedekind無限と同値な条件『可算無限部分集合を含む』を使えば大体解決する．
(i)はできたものが可算無限集合を含むとすると，AまたはBがそうなるので矛盾する．
(ii)は異なる有限列が可算無限個あるとしよう．それらの有限列からを順に今まで選んでこなかった元を選んでいく．ある有限列でいままで選んだ元しかないときはスキップして次の有限列に行く．この再帰的な作業が止まらなければ，Sの可算無限部分集合が作れるので矛盾．もし途中でN番目以降で元が増えなくなったとすると，すでに集めたN個の元からなる値の重ならない有限列は有限個しかないので可算無限列は途切れるはずなので矛盾である．
(iii)は和集合が可算無限集合を含むとする．族は互いに素なので可算無限集合の元それぞれにそれが属する族のインデックスが対応付けできる．ところがインデックスはDedekind有限なので，すくなくともどれか一つのインデックスに対して，可算無限回この対応が被ることになる．しかし，このことはそのインデックスに対応するDedekind有限集合が可算無限部分集合を含むことになるので矛盾である □


その直後のテキストのコメントによると，projection, ベキ集合，Dedekind有限集合の部分有限集合全体，そして （互いに素を仮定しない）Dedekind有限集合のDedekind有限個の族の和集合 はDedekind有限集合になることが選択公理なしでは証明できないとのことで，Dedekind有限集合の概念は単純な集合演算に対しても閉じていないということになる．テキストでの有限集合の定義ではこれらはすべてふたたび有限集合なので，こちらに軍配が...とはいえ有限順序数がガチガチに構成されている（ので数学的納法が使える）のが効いているでなんとも．

さて最後の問題：
＜問題3.16＞　Aが無限集合なら，P(P(A))はDedekind無限集合

この問題が興味深いのは，『Dedekind無限 ⇒ 無限』なので，AがDedekind無限集合のとき，P(A)はDedekind無限集合にならないことがあると先に述べたが，P(P(A))は再びDedekind無限集合になるということを含意している．

＜証明＞ ヒントにより S:=\{\{X\subset A:|X|=n\}:n < \omega\}を考えてみる．カッコの内側はnを固定するとP(P(A))の元（かつAが無限集合なので空ではない）なので，SはP(P(A))の可算無限部分集合を定義している．よってP(P(A))はDedekind無限集合 □