読む編集履歴表示

ベルンシュタインの定理

ウィキペディアから、無料の百科事典

ベルンシュタインの定理（ベルンシュタインのていり、カントール＝ベルンシュタイン＝シュレーダーの定理、シュレーダー＝ベルンシュタインの定理、カントール＝ベルンシュタインの定理とも、英: Schröder–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年エルンスト・シュレーダーが証明を発表する^[6]
1897年カントールのセミナーに参加していた学生だったフェリックス・ベルンシュタインが証明を付ける
1897年ベルンシュタインの訪問を受けた後でデデキントが独立に2つ目の証明を見つける
1898年エミール・ボレルの著書^[2]の中で（1897年にチューリッヒでカントールから教わった）ベルンシュタインの証明が述べられる

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

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

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

ベルンシュタインによる証明

以下に示す、「 $g\circ f$ を何度も適用する」アイデアに基づく証明はフェリックス・ベルンシュタインによるものだとされている。^[8]

（証明始）集合 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$ の像に含まれる。 $C_{0}=A\setminus g(B)$ が $C$ の中に含まれるからである。

ここで、g の単射性によって式

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

は写像を定めているが、この $h$ は全単射になっている。実際、 $x\in C_{i},y\in A$ で $g^{-1}(y)=f(x)$ が成り立つならば $y\in 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 )$ への全単射になる。

不動点定理による証明

冪集合に対する不動点定理の系としてベルンシュタインの定理を証明することができる。この証明はタルスキとクナスターの1927年に発表された研究に基づく。^[9]

定理：冪集合に対する不動点定理

集合 $X$ とその冪集合上の単調な写像 $\Phi \colon 2^{X}\to 2^{X}$ があったとする。つまり $S\subseteq T\Longrightarrow \Phi (S)\subseteq \Phi (T)$ が成り立つとする。

このとき $\Phi$ は不動点を持つ。つまり、 $\Phi (U)=U$ を満たす部分集合 $U\subseteq X$ が存在する。

（証明）実際に不動点となる部分集合 $U$ を構成すれば良い。

${\mathcal {D}}=\{S\subseteq X\mid S\subseteq \Phi (S)\}$ という集合族 ${\mathcal {D}}$ を考える。そして、その（包含関係による順序に関する）上限を取って $U=\bigcup _{S\in {\mathcal {D}}}S$ と定義する。以下、このようにして構成した $U$ が実際に不動点であることを示していこう。

任意に $S\in {\mathcal {D}}$ が与えられたとしよう。このとき ${\mathcal {D}}$ の定義から ${\begin{alignedat}{2}S&\subseteq \Phi (S)\\&\subseteq \Phi (U)\end{alignedat}}$ が成りたつ。 $S\in {\mathcal {D}}$ は任意だったから、和をとって $U\subseteq \Phi (U)$ が結論できる。すなわち $U\in {\mathcal {D}}$ であり、 $U$ は集合族 ${\mathcal {D}}$ の最大元である。

ここで写像 $\Phi$ の単調性から $\Phi (U)\subseteq \Phi (\Phi (U))$ であり、これは $\Phi (U)\in {\mathcal {D}}$ を意味する。したがって $U$ が最大元であったことから $\Phi (U)\subseteq U$ である。これにより、両方向の包含関係が示せたので $\Phi (U)=U$ が従う。（証明終）

定理：ベルンシュタインの定理

単射 $f\colon A\to B$ と単射 $g\colon B\to A$ があるとき、全単射 $h:A\to B$ が存在する。

（証明） $B\neq \emptyset$ であると仮定しても一般性を失わない。そこで $b\in B$ が何か存在するとして良いので、 $g(B)$ の外ではこれを返すものとして $g^{-1}\colon A\to B$ を定めておく。

まず証明のアイデアを説明しよう。写像 $f$ の単射性から、値域を制限すれば全単射 ${\tilde {f}}\colon A\to f(A)$ が得られる。一方で $g$ も単射なので $g^{-1}$ を $g(B)$ 上に制限した写像 $g^{-1}|_{g(B)}\colon g(B)\to B$ も全単射である。この２つの全単射をうまく貼り合わせることができる、というのが言いたいことである。

そこで部分集合 $S\subseteq A$ において貼り合わせがうまく行く条件を考えてみよう。このとき $f$ は $S\cong f(S)$ という全単射を誘導する。また $g^{-1}$ は $A\setminus S\cong B\setminus f(S)$ という全単射を誘導するはずである。したがって貼り合わせがうまく行く条件は、 $A\setminus S=g(B\setminus f(S))$ が成り立つことである。両辺の補集合を取ると、これは $S=A\setminus g(B\setminus f(S))$ と言い換えることができる。これはまさしく不動点条件である。

そこで写像 $\Phi \colon 2^{A}\to 2^{A}$ を $\Phi (S)=A\setminus g(B\setminus f(S))$ で定める。これは偶数回集合の差をとっているので単調な関数であり、したがって不動点定理より $\Phi (S^{*})=S^{*}$ となる部分集合が存在する。これはつまり最初のアイデア説明で述べた全単射の貼り合わせができるということであり、したがって全単射 $A\cong B$ は存在する。（証明終わり）

脚注

[脚注の使い方]

↑ Schröder, E. (1898), “Über zwei Definitionen der Endlichkeit und G. Cantor'sche Sätze”, Abh. Kaiserl. Leop.-Car. Akad. Naturf 71: 301-362
1 2 Borel, E. (1898). Leçons sur la théorie des fonctions. Paris: Gauthier-Villars et fils
↑ Korselt, A. (1911), “Über einen Beweis des Äquivalenzsatzes”, Math. Ann. 70: 295-296, doi:10.1007/BF01461161
↑ Dedekind, R. (1932). Gesammelte Werke III. Braunschweig
↑ Cantor, G. (1895), “Beiträge zur Begründung der transfiniten Mengenlehre I”, Math. Ann. 46: 481–512, doi:10.1007/BF02124929
↑ Schröder, E. (1896), “Über G. Cantor'sche Sätze”, Jahresbericht der Deutschen Mathematiker-Vereinigung 5: 81-82
↑ Dedekind, R. (1893). Was sind und was sollen die Zahlen?. Braunschweig
↑ “The Cantor–Bernstein theorem: how many proofs?” (英語). 2026年10月30日閲覧。
↑ “B. Knaster, Un théorème sur les fonctions d’ensembles, Annales de la Société Polonaise de Mathématique 6（1928）”. 2026年10月30日閲覧。

参考文献

マーティン・アイグナー（英語版）、ギュンター・ツィーグラー（英語版）『天書の証明』蟹江幸博訳（縮刷版）、丸善出版、2012年9月（原著2002年12月）。ISBN 978-4-621-06535-8。 - 原タイトル：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, MR 3026479

外部リンク

法則の辞典『ベルンシュタインの定理』 - コトバンク
Weisstein, Eric W. “Schröder-Bernstein Theorem”. mathworld.wolfram.com (英語).
Cantor-Schroeder-Bernstein theorem in nLab

集合論

基本

演算

関係

性質	反射関係推移関係推移閉包対称関係非対称関係反対称関係完全関係同値関係同値類 well-defined 整礎関係逆関係関係の合成
写像	定義域終域値域単射全射全単射逆写像像と逆像恒等写像制限包含写像合成射影商写像指示関数配置集合族添字集合順序対順序組列集合族グラフ部分写像対応
順序	前順序有向半順序全順序整列稠密有界単調写像順序同型辞書式順序順序型推移的集合順序数 0 後続極限自然数ハッセ図超限帰納法ツォルンの補題整列可能定理整礎的集合フォン・ノイマン宇宙