ベルンシュタインの定理

ベルンシュタインの定理（ベルンシュタインのていり、カントール＝ベルンシュタイン＝シュレーダーの定理、シュレーダー＝ベルンシュタインの定理、カントール＝ベルンシュタインの定理とも、）とは、集合 "A" から集合 "B" に単射 があり、集合 "B" から集合 "A" へも単射があれば、集合 "A" から集合 "B" への全単射があるというものである。濃度においては、これは |"A"| ≤ |"B"| かつ |"B"| ≤ |"A"| ならば |"A"| = |"B"| である、ということを言っているわけで、非常に基本的な要請がこの定理によって満たされることになる。
歴史.
数学ではよくあることだが、この定理は歴史的に込み入った事情を経て成立しており、歴史的経緯を正確に反映した名前を決めるのは難しい。伝統的によく用いられていた「シュレーダー＝ベルンシュタイン」は1898年に独立に公刊された2つの証明の著者を反映している。一方、歴史的に最初（1895年）にこの定理の主張を初めて発表したカントールの名前が加えられたり、シュレーダーの証明には誤りが含まれていたためシュレーダーの名前は加えられなかったり、という事情がある。さらに、歴史的にこの定理を初めて証明したデデキントの名前は普通加えられていない。
時系列をまとめると次のようになる。
デデキントの2つの証明はどちらも、自身によるモノグラフ中で示された、
に相当する命題に基づくものだった。カントールはこの定理に相当する現象を1882年か83年ごろには集合論と超限数の研究の過程で（選択公理の仮定の下で、ということになるが）発見していたとされる。
証明.
集合 "A" と "B" との間に単射写像
が与えられたとする。
集合族
formula_3
を、次のように帰納的に定義する。
これらの和集合を
とすると、"C" の補集合は "g" の像に含まれる。ここで、"g" の単射性によって式
は写像を定めているが、この"h" は全単射になっている。実際、"x" ∈ "C""i", "y" ∈ "A"で formula_8 が成り立つならば "y" ∈ "C""i" + 1となることから "h" の単射性が従う。一方、
であり、"g"-1("A") = "B" と
から、formula_11であるが、これは "h" が全射であることを示している。
例.
ベルンシュタインの定理を用いて、 formula_12 から formula_13 への全単射を構成する。
関数 formula_14, formula_15
を formula_16, formula_17 と定めると、どちらも単射である。
このとき、formula_18, formula_19 であるから、
となる。
したがって、 formula_21 に注意して、関数 formula_22 を
と定めると、formula_24 は formula_12 から formula_13 への全単射になる。