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

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

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

証明の方針は以下の通りです。2つの単射\(f:A\rightarrow B\)と\(g:B\rightarrow A\)が存在するものとします。写像\(f:A\rightarrow B\)の終集合を値域へ縮小して\(f:A\rightarrow f\left(A\right) \)とすると全射になるため、そもそも\(B=f\left(A\right) \)である場合には\(f\)が全単射となり目標は達成されます。そこで以下では\(f\left( A\right) \not=B\)である場合、すなわち\(f\left( A\right) \)が\(B\)の真部分集合である場合について考えます。\(f\left( A\right) \)が\(B\)の真部分集合である場合、それらの差集合は非空集合であるため、\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つの単射\(f:A\rightarrow B\)と\(g:B\rightarrow A\)が存在する場合、上の命題より、全単射\(h:A\rightarrow B\)の存在が保証されます。一般に、写像が全単射であることと、その逆写像が存在することは必要十分であり、さらに逆写像もまた全単射です。したがって、全単射\(h\)の逆写像に相当する全単射\(h^{-1}:B\rightarrow A\)が存在します。つまり、\(A\)から\(B\)への単射と\(B\)から\(A\)への単射が存在する場合、\(A\)から\(B\)への全単射と\(B\)から\(A\)への全単射が存在します。では、前提として与えられている単射\(f,g\)もまた全単射なのでしょうか。\(A,B\)が有限集合である場合には\(f,g\)もまた全単射になりますが（演習問題にします）、以下の例が示唆するように、\(A,B\)が無限集合である場合には、\(f\)や\(g\)は全単射であるとは限りません。

繰り返しになりますが、シュレーダー＝ベルンシュタインの定理は2つの単射\(f:A\rightarrow B\)と\(g:B\rightarrow A\)の存在から全単射\(h:A\rightarrow B\)の存在を保証するものであり（また、定理の証明から明らかであるように、単射\(f,g\)から全単射\(h\)を導出する具体的な手順を与えている）、2つの単射\(f,g\)が全単射であるとまでは言っていません。

単射と全射の関係

写像\(f:A\rightarrow B\)が単射であることは、その左逆写像\(g:B\rightarrow A\)が存在することと必要十分です。ただし、\(g\)が\(f\)の左逆写像であることとは、\begin{equation*}g\circ f=I_{A}
\end{equation*}が成り立つことを意味します。\(I_{A}:A\rightarrow A\)は恒等写像です。この事実は同時に、\(f\)が\(g\)の右逆写像であることを意味しますが、これは\(g\)が全射であることと必要十分です。以上より、\(A\)から\(B\)への単射が存在する場合、\(B\)から\(A\)への全射が存在することが明らかになりました。

選択公理を認める場合、写像\(f:A\rightarrow B\)が全射であることは、その右逆写像\(g:B\rightarrow A\)が存在することと必要十分です。ただし、\(g\)が\(f\)の右逆写像であることとは、\begin{equation*}f\circ g=I_{B}
\end{equation*}が成り立つことを意味します。\(I_{B}:B\rightarrow B\)は恒等写像です。この事実は同時に、\(f\)が\(g\)の左逆写像であることを意味しますが、これは\(f\)が単射であることと必要十分です。以上より、\(A\)から\(B\)への全射が存在する場合、\(B\)から\(A\)への単射が存在することが明らかになりました。

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

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

集合\(A,B\)について、\(A\)から\(B\)への単射と全射がそれぞれ存在する状況を想定します。これらは同じ写像である必要はありません。先に示したように、選択公理を認める場合、\(A\)から\(B\)への全射が存在するとき、\(B\)から\(A\)への単射が存在します。したがって、\(A\)から\(B\)への単射と\(B\)から\(A\)への単射がともに存在するため、シュレーダー＝ベルンシュタインの定理の定理より、\(A\)から\(B\)への全単射が存在します。

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

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

集合\(A,B\)について、\(A\)から\(B\)への全射と\(B\)から\(A\)への全射がともに存在する状況を想定します。選択公理を認める場合、このとき\(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つの命題より以下を得ます。

集合\(A,B\)について、\(A\)から\(B\)の部分集合への全単射と、\(B\)から\(A\)の部分集合への全単射がそれぞれ存在する状況を想定します。このとき上の命題より、\(A\)から\(B\)への単射と\(B\)から\(A\)への単射がともに存在するため、シュレーダー＝ベルンシュタインの定理より、\(A\)から\(B\)への全単射が存在します。

次回から関係について学びます。