シュレーダー＝ベルンシュタインの定理（全単射の存在条件）

シュレーダー=ベルンシュタインの定理

集合\(A,B\)が与えられたとき、\(A\)から\(B\)への全単射が存在することを示すためにはそれを具体的に作ってみればよいのですが、もう少し一般的な原理から全単射の存在を保証することができます。まず、\(A\)から\(B\)への単射と\(B\)から\(A\)への単射がともに存在する場合には、\(A\)から\(B \)への全単射が存在します。これをシュレーダー=ベルンシュタインの定理（Schröder-Bernstein’s theorem）と呼びます。

証明の方針は以下の通りです。集合\(A,B\)に対して、2つの単射\begin{eqnarray*}f &:&A\rightarrow B \\
g &:&B\rightarrow A
\end{eqnarray*}が存在する状況を想定します。写像\(f:A\rightarrow B\)の終集合を値域へ縮小して、\begin{equation*}f:A\rightarrow f\left( A\right)
\end{equation*}とすれば全射になるため、そもそも\(B=f\left( A\right) \)である場合には\(f\)が全単射となり目標は達成されます。

そこで以下では\(f\left( A\right)\not=B\)である場合、すなわち\(f\left( A\right) \)が\(B\)の真部分集合である場合について考えます。\(f\left(A\right) \)が\(B\)の真部分集合である場合、それらの差集合\(B\backslash f\left( A\right) \)は非空集合であるため、それを、\begin{equation*}B_{0}=B\backslash f\left( A\right) \not=\phi
\end{equation*}と表記します。\(B_{0}\subset B\)であるため\(g\)による像\(g\left( B_{0}\right) \)をとることができます。そこで、\begin{equation*}A_{1}=g\left( B_{0}\right)
\end{equation*}と表記します。\(A_{1}\subset A\)であるため\(f\)による像\(f\left( A_{1}\right) \)をとることができます。そこで、\begin{equation*}B_{1}=f\left( A_{1}\right)
\end{equation*}と表記します。同様に、\begin{eqnarray*}
A_{2} &=&g\left( B_{1}\right) \\
B_{2} &=&f\left( A_{2}\right) \\
&&\vdots
\end{eqnarray*}などと像を順番にとった上で、これらの集合を要素とする\(A\)の部分集合族\(\left\{ A_{n}\right\}_{n=1}^{\infty }\)と\(B\)の部分集合族\(\left\{ B_{n}\right\} _{n=0}^{\infty }\)を作ります。その上で、これらの和集合\begin{equation*}\bigcup\limits_{n=1}^{\infty }A_{n},\quad \bigcup\limits_{n=0}^{\infty
}B_{n}
\end{equation*}をそれぞれとり、さらにその補集合\begin{equation*}
A\backslash \bigcup\limits_{n=1}^{\infty }A_{n},\quad B\backslash
\bigcup\limits_{n=0}^{\infty }B_{n}
\end{equation*}をとります。写像\(f:A\rightarrow B\)が単射であることなどを利用すると、このとき、\begin{equation*}f\left( A\backslash \bigcup\limits_{n=1}^{\infty }A_{n}\right) =B\backslash
\bigcup\limits_{n=0}^{\infty }B_{n}
\end{equation*}が成り立つため（演習問題）、写像\(f:A\rightarrow B\)の定義域と終集合を以下のように制限して得られる写像\begin{equation}f:A\backslash \bigcup\limits_{n=1}^{\infty }A_{n}\rightarrow B\backslash
\bigcup\limits_{n=0}^{\infty }B_{n} \quad \cdots (1)
\end{equation}は全射です。仮定より\(f:A\rightarrow B\)は単射であるため、\(\left( 1\right) \)は全単射です。また、\begin{equation*}g\left( \bigcup\limits_{n=0}^{\infty }B_{n}\right)
=\bigcup\limits_{n=1}^{\infty }A_{n}
\end{equation*}が成り立つため（演習問題）、写像\(g:B\rightarrow A\)の定義域と終集合を以下のように制限して得られる写像\begin{equation}g:\bigcup\limits_{n=0}^{\infty }B_{n}\rightarrow
\bigcup\limits_{n=1}^{\infty }A_{n} \quad \cdots (2)
\end{equation}は全射です。仮定より\(g:B\rightarrow A\)は単射であるため、\(\left( 2\right) \)は全単射です。全単射は逆写像を持ち、なおかつ逆写像もまた全単射であることから、\(\left(2\right) \)が全単射であることを踏まえると、\(\left(2\right) \)の逆写像に相当する以下のような全単射\begin{equation}g^{-1}:\bigcup\limits_{n=1}^{\infty }A_{n}\rightarrow
\bigcup\limits_{n=0}^{\infty }B_{n} \quad \cdots (3)
\end{equation}の存在が保証されます。こうして得られた2つの全単射\(\left( 1\right) ,\left(3\right) \)を組み合わせることにより、\(A\)から\(B\)への全単射を構成できます（演習問題）。

集合\(A,B\)に対して2つの単射\begin{eqnarray*}f &:&A\rightarrow B \\
g &:&B\rightarrow A
\end{eqnarray*}が存在する場合、先の命題より、全単射\begin{equation*}
h:A\rightarrow B
\end{equation*}の存在が保証されます。写像が全単射であることと、その逆写像が存在することは必要十分であり、さらに逆写像もまた全単射です。したがって、全単射\(h\)の逆写像に相当する全単射\begin{equation*}h^{-1}:B\rightarrow A
\end{equation*}が存在します。つまり、\(A\)から\(B\)への単射と\(B\)から\(A\)への単射が存在する場合、\(A\)から\(B\)への全単射と\(B\)から\(A\)への全単射がともに存在します。では、前提として与えられている単射\(f,g\)もまた全単射なのでしょうか。\(A,B\)が有限集合である場合には\(f,g\)もまた全単射になりますが（演習問題）、以下の例が示唆するように、\(A,B\)が無限集合である場合には、\(f\)や\(g\)は全単射であるとは限りません。シュレーダー＝ベルンシュタインの定理は2つの単射\(f,g\)の存在から全単射\(h\)の存在を保証するものであり（また、定理の証明から明らかであるように、単射\(f,g\)から全単射\(h\)を導出する具体的な手順を与えている）、2つの単射\(f,g\)が全単射であるとまでは言っていません。

単射と全射の関係

集合\(A,B\)について、\(A\)から\(B\)への単射が存在する場合には、\(B\)から\(A\)への全射が存在することが保証されます。

先の命題とは逆に、集合\(A,B\)について、\(A\)から\(B\)への全射が存在する場合には、\(B\)から\(A\)への単射が存在することが保証されます。ただし、こちらの主張が成り立つことを保証するためには選択公理が必要です。

選択公理は無限集合に関する命題であるため、集合\(A,B\)が有限集合である場合には、上の命題において選択公理は必要ありません。いずれにせよ、以上の2つの命題から以下を得ます。

単射と全射から全単射を導く

集合\(A,B\)について、\(A\)から\(B\)への単射と全射がそれぞれ存在する状況を想定します。これらは同じ写像である必要はありません。この場合、\(A\)から\(B\)への全単射が存在することが保証されます。ただし、選択公理が必要です。

この命題のポイントは、存在が保証されている\(A\)から\(B\)への単射と全射は異なる写像でもよいということです（それらが同じ写像ならば、その写像そのものが全単射であることは自明）。つまり、\(A\)から\(B\)への全単射を具体的に構成できない場合でも、\(A\)から\(B\)への単射と全射をそれぞれ構成できるのであれば、\(A\)から\(B\)への全単射の存在を保証できるということです。

繰り返しになりますが、選択公理は無限集合に関する命題であるため、\(A,B\)が有限集合である場合には、上の命題において選択公理は必要ありません。

全射と全射から全単射を導く

集合\(A,B\)について、\(A\)から\(B\)への全射と\(B\)から\(A\)への全射がともに存在する場合、\(A\)から\(B\)への全単射が存在することが保証されます。ただし、選択公理が必要です。

繰り返しになりますが、選択公理は無限集合に関する命題であるため、\(A,B\)が有限集合である場合には、上の命題において選択公理は必要ありません。

全単射と全単射から全単射を導く

集合\(A,B\)に対して単射\(f:A\rightarrow B\)が存在する場合、\(f\)の終集合を値域に縮小して\(f:A\rightarrow f\left( A\right) \)とすれば全単射になります。値域\(f\left( A\right) \)は終集合\(B\)の部分集合であることを踏まえた上で、この主張を一般的な形で表現したものが以下の命題です。

逆に、集合\(A,B\)について、\(A\)から\(B\)の部分集合\(Y\)への全単射\(f:A\rightarrow Y\)が存在するものとします。この全単射\(f\)の終集合を\(Y\)から\(B\)へ拡張して\(f:A\rightarrow B\)とすると、差集合\(B\backslash Y\)のいかなる要素\(b\)に対しても\(f\left( a\right)=b\)を満たす\(A\)の要素\(a\)は存在しないため\(f:A\rightarrow B\)はもはや全射ではありません。ただ、\(f\)の終集合を\(Y\)から\(B\)へ拡張しても\(f\)が\(A\)のそれぞれの要素\(a\)に対して定める像\(f\left( a\right) \)は不変であるため、\(f\)は依然として単射です。したがって以下の命題を得ます。

以上の2つの命題より以下を得ます。

以上の命題を踏まえると以下が導かれます。

演習問題