■

[集合論] Cantor-Bernsteinの定理（Jech本p.28 Theorm 3.2）

　Part I 第三章に突入である．冒頭にCardinalityの定義は，正則性公理（基礎の公理）あるいは選択公理を使うとの気になる話があった．選択公理から整列可能定理の流れかと思ったが，本節ではその手法とのこと．正則性公理によるものは，調べると宇宙（Universe）の構造（すべての集合は整礎的）から，Scottのトリックにより濃度を定義するとの道筋らしいが，いまのところ私にはチンプンカンプンである．Jech本でも扱っていないように見える．ただ，Jech本でも『The Axiom of Choice』の方には何か書いてあるとの情報を得て，調査してみると11章がそのままのテーマのようである．将来のネタのひとつとしておこう（すでにポチっている．Dover本だから安いよ安いよー電子版もあるよー）．

　さて，Cantor-Bernsteinの定理は集合の濃度の比較に関する有名な定理である．証明にはone-to-one写像を作る必要があるが，仕掛けは初等的で選択公理すら不要というなかなかすばらしい定理である．ちなみに私はよく Cantor-Bendixsonと書き間違えそうになる．

X,Yを集合として，XからYの上へのone-to-one写像が存在するとき

|X|=|Y|

XからYの中への one-to-one写像が存在するとき
|X| \le |Y|
と（形式的に）書く．

＜定理（Cantor-Bernstein）＞

|A| \le |B| かつ |B| \le |A| \Rightarrow |A|=|B|

＜証明＞Jech本の証明がえらい短いなと思ったら，『後は簡単だからできるよね』と読者に放り投げられていたので受けて立ってみよう．本文に従い，まず，セットアップの情報から問題をすこし簡単にする．
　中への単射 f_1:A\to B，f_2:B\to Aが存在する．B':=f_2(B)，A_1:=f_2(f_1(A))とすると A_1 \subset B' \subset Aで，|A_1|=|A|かつ|B'|=|B|となっているので，最初から

A_1 \subset B \subset A　で　上へのone-to-one f:A \to A_1が存在する
と考えればよい．これは要するに集合Aの部分集合とAの濃度が同じなら，それらの間に挟まれる部分集合はすべてこの同じ濃度になるということである．

A_0:=A,\ A_{n+1}:=f(A_n);\ B_0:=B,\ B_{n+1}:=f(B_n)
と定義する．
　このとき B_{n+1} \subset A_{n+1} \subset B_n \subset A_n.
（∵ A_1 \subset B_0 \subset A_0は成立しており，これをfで送ればnが一つ増加するので普通の帰納法で証明される）
上の関係式より，n,mが異なると (A_n-B_n)\cap (A_m-B_m)=\emptysetであることがわかるので，写像 g:A\to Aを
g(x) = \begin{cases} f(x) & \mbox{if }x\in A_n-B_n\mbox{ for some }n, \\ x & \mbox{otherwize.} \end{cases}
と定義する．
このgがAからBの上へのone-to-one写像であることがわかれば定理の証明も完結するが，これが読者への宿題となっている．

C:=\cup_n (A_n-B_n)と定義しておく．
＜gがone-to-oneであることの証明＞
　g(x)=g(y)と仮定する．x,y \in Cまたはx,y \in A-Cだとx=yがすぐに出るので，（必要ならx,yを入れ替えて）x \in Cかつy \in A-Cという場合のみが問題となる．x \in A_n-B_nとして，f(x)=y. するとy \in A_{n+1}なので y \in B_{n+1}でなければならないが（∵ y\notin A_{n+1}-B_{n+1}），y=f(b);\ b\in B_nと書けて，f(x)=f(b)より x=b \in B_nとなるが，これは仮定x \in A_n-B_nに反する□

＜gがBの上への写像であることの証明＞
　x\in A-B=A_0-B_0なら g(x)=f(x) \in A_1 \subset B. x \in Bなら g(x)は f(x)\ or\ xなのでいずれもg(x) \in Bである．よってgの値域はBに入っている．これが全射であることを示そう．b\in Bを任意の元として，b\in A-Cなら g(b)=bなのでb\in ran\ gである．b\in Cならば \exists n > 0 (b \in A_n-B_n)．そこで b=f(a)なるa\in A_{n-1}-B_{n-1}が存在する．このとき b=f(a)=g(a)なので，b\in ran\ gである□