ベルンシュタインの定理
ベルンシュタインの定理（カントール＝ベルンシュタイン＝シュレーダーの定理、シュレーダー＝ベルンシュタインの定理、カントール＝ベルンシュタインの定理とも）とは、集合 A から集合 B に単射 があり、集合 B から集合 A へも単射があれば、集合 A から集合 B への全単射があるというものである。濃度においては、これは |A| ≤ |B| かつ |B| ≤ |A| ならば |A| = |B| である、ということを言っているわけで、非常に基本的な要請がこの定理によって満たされることになる。
歴史
数学ではよくあることだが、この定理は歴史的に込み入った事情を経て成立しており、歴史的経緯を正確に反映した名前を決めるのは難しい。伝統的によく用いられていた「シュレーダー＝ベルンシュタイン」は1898年に独立に公刊された2つの証明[1][2]の著者を反映している。一方、歴史的に最初（1895年）にこの定理の主張を初めて発表したカントールの名前が加えられたり、シュレーダーの証明には誤りが含まれていた[3]ためシュレーダーの名前は加えられなかったり、という事情がある。さらに、歴史的にこの定理を初めて証明したデデキントの名前は普通加えられていない。
時系列をまとめると次のようになる。
- 1887年 リヒャルト・デデキントがこの定理を証明する[4]が発表せず
- 1895年 ゲオルク・カントールの最初の集合論と超限数の論文[5]に基数の比較可能性の帰結としてこの定理の主張が述べられる
- 1896年 エルンスト・シュレーダーが証明を発表する[6]
- 1897年 カントールのセミナーに参加していた学生だったフェリックス・ベルンシュタインが証明を付ける
- 1897年 ベルンシュタインの訪問を受けた後でデデキントが独立に2つ目の証明を見つける
- 1898年 エミール・ボレルの著書[2]の中で（1897年にチューリッヒでカントールから教わった）ベルンシュタインの証明が述べられる
デデキントの2つの証明はどちらも、自身によるモノグラフ[7]中で示された、
- <math> A \subset B \subset C, | A | = | C | \Rightarrow | A | = | B | = | C | </math>
に相当する命題に基づくものだった。カントールはこの定理に相当する現象を1882年か83年ごろには集合論と超限数の研究の過程で（選択公理の仮定の下で、ということになるが）発見していたとされる。
証明
集合 A と B との間に単射写像
- <math>f \colon A \to B,\ g \colon B \to A</math>
が与えられたとする。 集合族 <math>\{ C_n \}_{n \in \mathbb{N}}</math> を、次のように帰納的に定義する。
- <math>
C_0 := A \setminus g(B),
</math>
- <math>
C_{n+1} := g( f( C_n ) )
</math> これらの和集合を
- <math>C = \bigcup_{n \in \mathbb{N}} C_n</math>
とすると、C の補集合は g の像に含まれる。ここで、g の単射性によって式
- <math>h(x) = \begin{cases}
f(x)& \text{if }x \in C \\
g^{-1}(x)& \text{if } x \notin C
\end{cases}</math> は写像を定めているが、このh は全単射になっている。実際、x ∈ Ci, y ∈ Aで <math>g^{-1}(y) = f(x)</math> が成り立つならば y ∈ Ci + 1となることから h の単射性が従う。一方、
- <math>g^{-1}(A\setminus C) = g^{-1}(A)\setminus g^{-1}(C)</math>
であり、g-1(A) = B と
- <math>\quad g^{-1}(C) = g^{-1}(C \setminus C_0) = \cup_{i=1}^\infty g^{-1}(C_i) = \cup_{i=1}^\infty g^{-1}(g (f (C_{i-1}))) = \cup_{i=0}^\infty f(C_i) = f(C)</math>
から、<math>g^{-1}(A \setminus C) = B \setminus f(C)</math>であるが、これは h が全射であることを示している。
例
ベルンシュタインの定理を用いて、 <math>[0, \infty)</math> から <math>(0, \infty)</math> への全単射を構成する。
関数 <math>f\colon [0, \infty) \to (0, \infty)</math>, <math> g\colon (0, \infty) \to [0, \infty)</math>
を <math>f(x)=x+1</math>, <math>g(x)=x</math> と定めると、どちらも単射である。
このとき、<math>g\circ f(x)=x+1</math>, <math>(g\circ f)^n(x)=x+n</math> であるから、
- <math>\bigcup_{n \in \mathbb{N}}(g\circ f)^n([0, \infty)\setminus g((0, \infty)))=\bigcup_{n \in \mathbb{N}}(g\circ f)^n([0, \infty)\setminus (0, \infty))=\bigcup_{n \in \mathbb{N}}(g\circ f)^n(\{0\})=\bigcup_{n \in \mathbb{N}}\{n\}=\mathbb{N}</math>
となる。
したがって、 <math>g^{-1}(x)=x</math> に注意して、関数 <math>h\colon [0, \infty) \to (0, \infty)</math> を
- <math>h(x) = \begin{cases}
x+1& \text{if }x \in \mathbb{N}\\
x& \text{if } x \notin \mathbb{N}
\end{cases}</math> と定めると、<math>h</math> は <math>[0, \infty)</math> から <math>(0, \infty)</math> への全単射になる。
