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

全単射が存在することを示す方法として、全単射を具体的に作るのではなく、もう少し一般的な原理を利用することもできます。今回はシュレーダー=ベルンシュタインの定理について解説します。
次のページ >

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

集合\(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\)の終集合を\(B\)から値域\(R\left( f\right) \)へ縮小して\(f:A\rightarrow R\left( f\right) \)とすると\(f\)は全射になるため、そもそも\(B=R\left( f\right) \)である場合には\(f\)が全単射です。そこで以下では\(B\not=R\left( f\right) \)である場合、すなわち\(R\left( f\right) \)が\(B\)の真部分集合である場合について考えます。

\(R\left( f\right) \)が\(B\)の真部分集合である場合、それらの差集合は非空です。そこでそれを、\begin{equation*}
B_{0}=B\backslash R\left( f\right) \not=\phi
\end{equation*}で表記します。\(B_{0}\subset B\)であるため、\(g\)による\(B_{0}\)の像\(g\left( B_{0}\right) \)をとることができます。それを、\begin{equation*}
A_{1}=g\left( B_{0}\right)
\end{equation*}で表記します。\(A_{1}\subset A\)であるため、\(f\)による\(A_{1}\)による像\(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} \tag{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} \tag{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} \tag{3}
\end{equation}の存在が保証されます。こうして得られた2つの全単射\(\left( 1\right) ,\left( 3\right) \)を組み合わせることにより、\(A\)から\(B\)への全単射を構成できます(確認してください)。

命題(シュレーダー=ベルンシュタインの定理)
集合\(A,B\)について、\(A\)から\(B\)への単射と\(B\)から\(A\)への単射がともに存在するとき、\(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\)は全単射であるとは限りません。

例(シュレーダー=ベルンシュタインの定理)
実数からなる閉区間\(\left[ 0,1\right] \)と\(\left[ 0,2\right] \)について、写像\(f:\left[ 0,1\right] \rightarrow \left[ 0,2\right] \)はそれぞれの\(x\in \left[ 0,1\right] \)に対して、\begin{equation*}
f\left( x\right) =x
\end{equation*}を像として定める一方、写像\(g:\left[ 0,2\right] \rightarrow \left[ 0,1\right] \)はそれぞれの\(y\in \left[ 0,2\right] \)に対して、\begin{equation*}
g\left( y\right) =\frac{x}{4}
\end{equation*}を像として定めるものとします。\(f\)と\(g\)はともに単射であるため(確認してください)、シュレーダー=ベルンシュタインの定理より、全単射\(h:\left[ 0,1\right] \rightarrow \left[ 0,2\right] \)が存在します。しかし、\(f\)と\(g\)はともに全単射ではありません。実際、\(f\)については、例えば、\begin{equation*}
\exists 2\in \left[ 0,2\right] ,\ \forall x\in \left[ 0,1\right] :f\left(
x\right) =x\not=2
\end{equation*}が成り立つため全射ではなく、\(g\)については、例えば、\begin{equation*}
\exists 1\in \left[ 0,1\right] ,\ \forall x\in \left[ 0,2\right] :f\left(
x\right) =\frac{x}{4}\not=1
\end{equation*}が成り立つため全射ではありません。

繰り返しになりますが、シュレーダー=ベルンシュタインの定理は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\)への全射が存在することが明らかになりました。

命題(単射と全射の関係)
集合\(A,B\)について、\(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\)について、\(A\)から\(B\)への全射が存在するとき、\(B\)から\(A\)への単射が存在する。
証明を見る(プレミアム会員限定)

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

命題(単射と全射の関係)
選択公理を認める場合、集合\(A,B\)について、\(A\)から\(B\)への単射が存在することと、\(B\)から\(A\)への全射が存在することは必要十分である。
証明を見る(プレミアム会員限定)

 

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

集合\(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\)への単射と全射をそれぞれ構成できるのであれば、\(A\)から\(B\)への全単射の存在を保証できるということです。

 

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

集合\(A,B\)について、\(A\)から\(B\)への全射と\(B\)から\(A\)への全射がともに存在する状況を想定します。選択公理を認める場合、このとき\(A\)から\(B\)への単射と\(B\)から\(A\)への単射が存在するため、シュレーダー=ベルンシュタインの定理より、\(A\)から\(B\)への全単射が存在します。

命題(全射と全射から導かれる全単射)
選択公理を認める場合、集合\(A,B\)について、\(A\)から\(B\)への全射と\(B\)から\(A\)への全射がともに存在するならば、\(A\)から\(B\)への全単射が存在する。
証明を見る(プレミアム会員限定)

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

 

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

復習になりますが、集合\(A,B\)について単射\(f:A\rightarrow B\)が存在する場合、\(f\)の終集合を\(B\)から\(f\)の値域\(R\left( f\right) \)に縮小して得られる写像\(f:A\rightarrow R\left( f\right) \)は全単射です。値域\(R\left( f\right) \)は終集合\(B\)の部分集合であることを踏まえた上で、この結論を一般的な形で表現したものが以下の命題です。

命題(単射から導かれる全単射)
集合\(A,B\)について、単射\(f:A\rightarrow B\)が存在する場合には、部分集合\(Y\subset B\)と全単射\(f:A\rightarrow Y\)が存在する。
証明を見る(プレミアム会員限定)

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

命題(全単射から導かれる単射)
集合\(A,B\)について、部分集合\(Y\subset B\)と全単射\(f:A\rightarrow Y \)が存在する場合には、単射\(f:A\rightarrow B\)が存在する。
証明を見る(プレミアム会員限定)

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

命題(単射と全単射の関係)
集合\(A,B\)について、単射\(f:A\rightarrow B\)が存在することは、部分集合\(Y\subset B\)と全単射\(f:A\rightarrow Y\)が存在するための必要十分条件である。
証明を見る(プレミアム会員限定)

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

命題(全単射と全単射から導かれる全単射)
集合\(A,B\)について、\(A\)から\(B\)の部分集合\(Y\)への全単射\(f:A\rightarrow Y\)と、\(B\)から\(A\)の部分集合\(X\subset A\)への全単射\(f:B\rightarrow X\)がともに存在するならば、\(A\)から\(B\)への全単射が存在する。
証明を見る(プレミアム会員限定)
例(全単射と全単射から導かれる全単射)
実数からなる閉区間\(\left[ a,b\right] \subset \mathbb{R}\)を任意に選んだとき、\(\mathbb{R}\)から\(\left[ a,b\right] \)への全単射が存在することを示します。まず、恒等写像\begin{equation*}
I_{\left[ a,b\right] }:\left[ a,b\right] \rightarrow \left[ a,b\right] \end{equation*}は全単射ですが、\(\left[ a,b\right] \)は\(\mathbb{R}\)の部分集合であるため、\(I_{\left[ a,b\right] }\)は\(\left[ a,b\right] \)から\(\mathbb{R}\)の部分集合への全単射です。続いて、写像\(f:\left( -1,1\right) \rightarrow \mathbb{R}\)はそれぞれの\(x\in \left( -1,1\right) \)に対して、\begin{equation*}
f\left( x\right) =\frac{x}{1-x^{2}}
\end{equation*}を像として定めるものとします。\(f\)は全単射であるため(確認してください)、その逆写像\(f^{-1}:\mathbb{R}\rightarrow \left( -1,1\right) \)が存在し、この\(f^{-1}\)もまた全単射です。任意の2つの開区間の間には全単射が存在するため(演習問題にします)、全単射\(g:\left( -1,1\right) \rightarrow \left( a,b\right) \)が存在します。そこで、合成写像\(g\circ f^{-1}:\mathbb{R}\rightarrow \left( a,b\right) \)を構成すると、これは全単射どうしの合成であるため、\(g\circ f^{-1}\)もまた全単射です。しかも\(\left( a,b\right) \)は\(\left[ a,b\right] \)の部分集合であるため、\(g\circ f^{-1}\)は\(\mathbb{R}\)から\(\left[ a,b\right] \)の部分集合への全単射です。以上で、\(\left[ a,b\right] \)から\(\mathbb{R}\)の部分集合への全単射\(I_{\left[ a,b\right] }\)と、\(\mathbb{R}\)から\(\left[ a,b\right] \)の部分集合への全単射\(g\circ f^{-1}\)の存在が保証されたため、先の命題より、\(\mathbb{R}\)から\(\left[ a,b\right] \)への全単射が存在します。

次回は~について学びます。

次へ進む 質問・コメントを投稿する 演習問題(プレミアム会員限定)
Share on facebook
Share on twitter
Share on email
次のページ >

プレミアム会員サービス

ユーザー名とメールアドレスを入力して有料(500円/月)のプレミアム会員へアップグレードすることにより、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題、解答など)へのアクセスが可能に。
会員サービス
ログイン

プレミアム会員だけが質問やコメントを投稿・閲覧できます。

アカウント
ログイン