ベルンシュタインの定理

ベルンシュタインの定理（ベルンシュタインのていり、カントール＝ベルンシュタイン＝シュレーダーの定理、シュレーダー＝ベルンシュタインの定理、カントール＝ベルンシュタインの定理とも、英: Schröder–Bernstein theorem）とは、集合 A から集合 B に単射があり、集合 B から集合 A へも単射があれば、集合 A から集合 B への全単射があるというものである。濃度においては、これは |A| ≤ |B| かつ |B| ≤ |A| ならば |A| = |B| である、ということを言っているわけで、非常に基本的な要請がこの定理によって満たされることになる。

歴史

数学ではよくあることだが、この定理は歴史的に込み入った事情を経て成立しており、歴史的経緯を正確に反映した名前を決めるのは難しい。伝統的によく用いられていた「シュレーダー＝ベルンシュタイン」は1898年に独立に公刊された2つの証明の著者を反映している。一方、歴史的に最初（1895年）にこの定理の主張を初めて発表したカントールの名前が加えられたり、シュレーダーの証明には誤りが含まれていたためシュレーダーの名前は加えられなかったり、という事情がある。さらに、歴史的にこの定理を初めて証明したデデキントの名前は普通加えられていない。

時系列をまとめると次のようになる。

1887年リヒャルト・デデキントがこの定理を証明するが発表せず
1895年ゲオルク・カントールの最初の集合論と超限数の論文に基数の比較可能性の帰結としてこの定理の主張が述べられる
1896年エルンスト・シュレーダーが証明を発表する
1897年カントールのセミナーに参加していた学生だったフェリックス・ベルンシュタインが証明を付ける
1897年ベルンシュタインの訪問を受けた後でデデキントが独立に2つ目の証明を見つける
1898年エミール・ボレルの著書の中で（1897年にチューリッヒでカントールから教わった）ベルンシュタインの証明が述べられる

デデキントの2つの証明はどちらも、自身によるモノグラフ中で示された、

A\subset B\subset C,|A|=|C|\Rightarrow |A|=|B|=|C|

に相当する命題に基づくものだった。カントールはこの定理に相当する現象を1882年か83年ごろには集合論と超限数の研究の過程で（選択公理の仮定の下で、ということになるが）発見していたとされる。

証明

集合 A と B との間に単射写像

f\colon A\to B,\ g\colon B\to A

が与えられたとする。集合族 $\{C_{n}\}_{n\in \mathbb {N} }$ を、次のように帰納的に定義する。

C_{0}:=A\setminus g(B),

C_{n 1}:=g(f(C_{n}))

これらの和集合を

C=\bigcup _{n\in \mathbb {N} }C_{n}

とすると、C の補集合は g の像に含まれる。ここで、g の単射性によって式

h(x)={\begin{cases}f(x)&{\text{if }}x\in C\\g^{-1}(x)&{\text{if }}x\notin C\end{cases}}

は写像を定めているが、このh は全単射になっている。実際、x ∈ C_i, y ∈ Aで $g^{-1}(y)=f(x)$ が成り立つならば y ∈ C_{i 1}となることから h の単射性が従う。一方、

g^{-1}(A\setminus C)=g^{-1}(A)\setminus g^{-1}(C)

であり、g^-1(A) = B と

\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\setminus C)=B\setminus f(C)$ であるが、これは h が全射であることを示している。

例

ベルンシュタインの定理を用いて、 $[0,\infty )$ から $(0,\infty )$ への全単射を構成する。
関数 $f\colon [0,\infty )\to (0,\infty )$ , $g\colon (0,\infty )\to [0,\infty )$ を $f(x)=x 1$ , $g(x)=x$ と定めると、どちらも単射である。
このとき、 $g\circ f(x)=x 1$ , $(g\circ f)^{n}(x)=x n$ であるから、

\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}

となる。
したがって、 $g^{-1}(x)=x$ に注意して、関数 $h\colon [0,\infty )\to (0,\infty )$ を

h(x)={\begin{cases}x 1&{\text{if }}x\in \mathbb {N} \\x&{\text{if }}x\notin \mathbb {N} \end{cases}}

と定めると、 $h$ は $[0,\infty )$ から $(0,\infty )$ への全単射になる。

脚注

参考文献

マーティン・アイグナー、ギュンター・ツィーグラー『天書の証明』蟹江幸博訳（縮刷版）、丸善出版、2012年9月（原著2002年12月）。ISBN 978-4-621-06535-8。http://pub.maruzen.co.jp/book_magazine/book_data/search/9784621065358.html。[[マーティン・アイグナー]]（[[:en:Martin Aigner|英語版]]）&rft.au=[[マーティン・アイグナー]]（[[:en:Martin Aigner|英語版]]）&rft.date=2012-09&rft.edition=縮刷版&rft.pub=丸善出版&rft.isbn=978-4-621-06535-8&rft_id=http://pub.maruzen.co.jp/book_magazine/book_data/search/9784621065358.html&rfr_id=info:sid/ja.wikipedia.org:ベルンシュタインの定理"> - 原タイトル：Proofs from The Book。
Hinkis, Arie (2013), Proofs of the Cantor-Bernstein theorem. A mathematical excursion, Science Networks. Historical Studies, 45, Heidelberg: Birkhäuser/Springer, doi:10.1007/978-3-0348-0224-6, ISBN 978-3-0348-0223-9, MR3026479, http://link.springer.com/book/10.1007/978-3-0348-0224-6/page/1