■

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

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

＜証明 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のあたりをざくっと調べてみたが、ぴったり同じ記述は見つからなかった（そもそも書いてあることはさっぱりわからないわけですが）。いやまあ、こんなところまでたどり着けるかどうかこれはこれで楽しみですねぇ。