ベルンシュタインの定理（図つき）

以前のエントリベルンシュタインの定理がわからないといわれたので、わかってもらうべく図をつけて説明しようとエントリ集合と基数の説明を作成した。そこでは、集合論の「写像」「単射」「全射」「全単射」「基数」などの用語の定義した。
それを踏まえて本エントリではベルンシュタインの定理の証明を説明する。

AからBへの単射 f と、BからAへの単射 g が存在するとき、AとBには1対１対応h が存在する。すなわち、AとBの基数（濃度）が等しい。

	AからBへの単射 f と、BからAへの単射 g が存在するとする。
	AはBのgによる像g(B)とそれ以外の部分集合A - g(B)に分割できる。
	Aの部分集合A - g(B)に注目する。fでBの部分集合f(A - g(B))に写される。
	Bの部分集合f(A - g(B))をgで写すと像はAの部分集合gf(A - g(B))となるが、gf(A - g(B))とA - g(B)は共通要素を持たない。なぜならば、gf(A - g(B))⊆g(B)であるからである。
	Aの部分集合gf(A - g(B))をfで写すと像はBの部分集合fgf(A - g(B))となるが、fgf(A - g(B))とf(A - g(B))は共通要素を持たない。 前述のgf(A - g(B))とA - g(B)は共通要素を持たないことと、fが単射であり異なる要素が同じ要素に写ることはないからである。
	同様にAにおいて、gfgf(A - g(B))はA-g(B)ともgf(A-g(B))とも共通要素を持たない。 まず、gfgf(A - g(B))⊆g(B)であるからであるからA-g(B)と共通要素を持たない。 そして、前述のfgf(A - g(B))とf(A - g(B))は共通要素を持たないことと、gが単射であり異なるものが同じものに写ることはないからgf(A-g(B))とも共通要素を持たない。
	同様に無限にfとgで写すことを繰り返す。Aだけに着目するとAからA自身への単射gfを繰り返し適用していることになる。 Aは(A-g(B))、gf(A-g(B))、gfgf(A-g(B))、gfgfgf(A-g(B))、…、gfgf…gf(A-g(B))、…という部分集合とそれ以外の部分に分割される。それ以外の部分にXと名前を付けると、A-g(B)と共通要素を持たないことからX⊆g(B)が成り立つ。
	さてここで、AからBへの写像hを以下のように定義する。  aが(A-g(B))、gf(A-g(B))、gfgf(A-g(B))、gfgfgf(A-g(B))、…、gfgf…gf(A-g(B))、…のどれかの要素の場合、h(a):= f(a)  aがXの要素の場合、X⊆g(B)だから、あるBの要素bが存在して、a=g(b)となるはずである。 ここで、h(a) := b
fは単射であるので、(A-g(B))、gf(A-g(B))、gfgf(A-g(B))、gfgfgf(A-g(B))、…、gfgf…gf(A-g(B))、…hをこれらの部分集合上に制限した写像は単射である。 また、写像の定義より、hをX上に制限した写像は単射である。 hがA全体で単射であることを見るには、gfgf…gf(A-g(B))の要素a1とXの要素a2が同じ要素bに写らないことを示せばよい。もし、h(a1) = b = h(a2)とすると、gf(a1) = gh(a1) =g(b) = gh(a2) = a2となり、gf(…)の要素ではないというXの定義に反する。よって、hは単射である。
Bの要素bが、f(A-g(B))、fgf(A-g(B))、…、fgfgf…gf(A-g(B))のどれかの要素であれば、あるAの要素aがあって、fが単射であることによりaは(A-g(B))、gf(A-g(B))、…、gfgf…gf(A-g(B))のどれかの要素である。よって、h(a) = f(a) = b となる。 一方、Bの要素bが、f(A-g(B))、fgf(A-g(B))、…、fgfgf…gf(A-g(B))のどの要素でもないとすると、g(b)は(A-g(B))、gf(A-g(B))、…、gfgf…gf(A-g(B))のどの要素でもないから、g(B)∈Xである。hの定義により、h(g(b))=bである。 すなわち、Bのどんな要素bに対しても、h(a)=bとなるAの要素aが存在することになる。hは全射である。
以上より、hはAとBの全単射（1対1対応）となる。 （証明終わり）

応用としては、たとえば、数直線上の閉区間と開区間の基数が等しいことを直ちに証明できる。
実際, , を,をと置くとは単射であるから、ベルンシュタインの定理によりとの基数は等しいと結論付けることができる。