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