Bernsteinの定理
Introduction
集合の濃度についてのお話です．
集合 の間に全単射が存在するとき，
と表します．また，
から
への単射が存在するとき，
と表します．
集合の濃度は，（記号の使い方から察せられるように）順序関係の公理を満たします．つまり，次の3つが成り立ちます．
かつ
1.と2.は定義から直ちにわかりますが，3.は明らかではありません．これを保証するのが，Bernsteinの定理です．この記事ではその証明を紹介します．
Bernstainの定理とその証明
定理
かつ
証明1
示すべきことはすなわち，
ということです．まず，単射 の存在を仮定します．
このとき，任意に をとれば，それは
に含まれるか含まれないかのいずれかです．つまり，
によって引き戻せるか引き戻せないかどちらか，ということです．
は単射なので，引き戻せる場合，
は一意に定まることに注意します．
についても同様に，
によって引き戻せるか引き戻せないかのいずれかです．
ここで，次のように を分割します．
\begin{gather}
A=A_A\sqcup A_B\sqcup A_\infty,\\
A_A=\{a\in A\mid\exists n\geq 0,\ \exists a'\in A\setminus g(B),\ a=(g\circ f)^n(a')\},\\
A_B=\{a\in A\mid\exists n\geq 0,\ \exists b'\in B\setminus f(A),\ a=(g\circ f)^n\circ g(b')\},\\
A_\infty=A\setminus(A_A\sqcup A_B).
\end{gather} は，
によって繰り返し引き戻したとき，
の元からそれ以上引き戻せなくなるもの，
は，
によって繰り返し引き戻したとき，
の元からそれ以上引き戻せなくなるもの，
はそれら以外，つまり無限に引き戻せるものの全体です．
についても同様の分割
\begin{gather}
B=B_A\sqcup B_B\sqcup B_\infty,\\
B_A=\{b\in B\mid\exists n\geq 0,\ \exists a'\in A\setminus g(B),\ b=(f\circ g)^n\circ f(a')\},\\
B_B=\{b\in B\mid\exists n\geq 0,\ \exists b'\in B\setminus f(A),\ b=(f\circ g)^n(b')\},\\
B_\infty=B\setminus(B_A\sqcup B_B).
\end{gather}を考えます．ここで， には
によって一度も引き戻せない元も含まれることに注意します．
このとき，まず と
が成り立つので，この部分では
の誘導する写像は全単射です．
一方， には
によって一度も引き戻せない元が含まれないため，
の分割の際に触れた注意により，
は言えず，この部分では
の誘導する写像は全単射であることが言えません．しかし，
が成り立つので，
が誘導する写像は全単射になります．
以上により， 上では
，
上では
と定めることで，全単射
が構成できます．
証明2（2/18加筆）
以上の証明は参考文献の証明を少し書き換えたものなのですが，記事を書いた後も「わかるけどなんだかわかった気がしない…」という感覚があったので，改めて考えてみました．
証明の流れは，「2つの単射から全単射
を構成する」というものでした．単射は仮定しているので，うまい具合に全射を作ってやればいいわけです．
証明1の分割で生じた状況を整理すると，
ここで，全射であるときとそうでないときの違いは，無限に引き戻せる場合を除けば，「定義域・値域の元が によって引き戻せる回数が偶数回か奇数回か」です．
1.と4.においては，定義域 の元の引き戻せる回数は偶数回，値域
の元の引き戻せる回数は奇数回であり，このとき
の誘導する写像は全射になります．
一方，3.においては，定義域 の元の引き戻せる回数は奇数回，値域
の元の引き戻せる回数は偶数回であり，このとき
の誘導する写像は全射になりません．なぜなら，証明1でも述べたように，値域
に含まれる「0回しか引き戻せない元（一度も引き戻せない元）」が
の像には含まれないからです．
このように考えると，証明1で「 の元からそれ以上引き戻せなくなる」「
の元からそれ以上引き戻せなくなる」「無限に引き戻せる」と分割しましたが，「引き戻せる回数が偶数回か奇数回か」が大事だということがわかります．
それでは，改めて証明を書き直してみましょう．
証明2
を
\begin{align}
A_0&=\{f,gによって奇数回だけ引き戻せるAの元の全体\},\\
A_1&=A\setminus A_1,
\end{align} を
\begin{align}
B_0&=\{f,gによって偶数回だけ引き戻せるBの元の全体\},\\
B_1&=B\setminus B_0
\end{align}と分割します（です）．このとき，
\begin{align}
f&\colon A_1\to B_1\\
g&\colon B_0\to A_0
\end{align}は全単射なので， 上では
，
上では
と定めれば，
は全単射です．
はじめの証明よりは簡潔で見通しも良くなったのではないかと思います．
証明3（2/19加筆）
証明2は，「引き戻せる回数の偶奇」に着目した構成でした．より具体的に，逐次的に構成してみましょう．
やはり「2つの単射 から全単射
を構成する」方針で，基本的には
を用いて，どの部分で
を用いる必要があるかを考えていきます．
まず， によって
の元を
に写すことは当然できないので，
では
を用います．
すると， によって
の元を
に写すことができなくなるので，
では
を用います．
すると， によって
の元を
に写すことができなくなるので，
では
を用います．
これを繰り返し， とおくと，
上では
，
上では
となります．
また， は0回だけ引き戻せる元の全体，
は1回だけ引き戻せる元の全体，
は2回だけ引き戻せる元の全体，…となり，これらの和
は，証明2の
と一致します．手続きが異なるだけで，構成の仕方は同じだということがわかります．
そして， は単射なので，
\begin{align}
g^{-1}(A_0)&=g^{-1}\left(\bigcup_{i=1}^{\infty}A_i\right)\\
&=g^{-1}\left(\bigcup_{i=1}^{\infty}g(B_i)\right)\\
&=\bigcup_{i=1}^{\infty}B_i=B_0,\\
f(A\setminus A_0)&=f(A)\setminus f\left(\bigcup_{i=1}^{\infty}A_i\right)\\
&=(B\setminus B_1)\setminus \bigcup_{i=2}^{\infty}B_i\\
&=B\setminus B_0 =B\setminus g^{-1}(A_0)
\end{align}となり，やはり が全射であることが示せました．
まとめ
証明2は非常に簡潔ですが，どういう着想で辿り着いたのか少し見えづらくなっている気がします．一方で，証明3は順番に の適用範囲を拡大していく様子がよく見えます．
証明3では，はじめに ，つまり一度も引き戻せない元をどう扱うかが問題でした．そのためには，1回だけ引き戻せる元，2回だけ引き戻せる元，…を順番に考え，
の適用範囲を
に置き換えていく，という手続きをとっています．
これをいっぺんにまとめて考えたのが証明2である，と理解するのがよいかなと思います．
