教材一覧
MAPPING

シュレーダー=ベルンシュタインの定理(全単射の存在条件)

< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有

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

集合\(A,B\)が与えられたとき、\(A\)から\(B\)への全単射が存在することを示すためにはそれを具体的に作ってみればよいのですが、もう少し一般的な原理から全単射の存在を保証することができます。まず、\(A\)から\(B\)への単射と\(B\)から\(A\)への単射がともに存在する場合には、\(A\)から\(B\)への全単射が存在します。これをシュレーダー=ベルンシュタインの定理(Schr\”{o}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\)について、\(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\)は全単射であるとは限りません。

例(シュレーダー=ベルンシュタインの定理)
写像\(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\)の終集合を値域に縮小して\(f:A\rightarrow f\left( A\right) \)とすれば全単射になります。値域\(f\left( A\right) \)は終集合\(B\)の部分集合であることを踏まえた上で、この結論を一般的な形で表現したものが以下の命題です。

命題(単射から導かれる全単射)
集合\(A,B\)について、\(A\)から\(B\)への単射が存在する場合には、\(A\)から\(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\)は依然として単射です。したがって以下の命題を得ます。

命題(全単射から導かれる単射)
集合\(A,B\)について、\(A\)から\(B\)の部分集合への全単射が存在する場合には、\(A\)から\(B\)への単射が存在する。

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

命題(単射と全単射の関係)
集合\(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\)の部分集合から\(B\)への全単射\(g\)が存在するものとします。全単射には逆写像が存在してそれもまた全単射になるため、\(g\)の逆写像\(g^{-1}\)が存在して、これは\(B\)から\(A\)の部分集合への全単射になります。したがってこの場合、上の命題より\(A\)から\(B\)への全単射が存在します。

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

< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

全単射

全単射

単射かつ全射であるような写像を全単射と呼びます。全単射は終集合のそれぞれの要素に対して、それを像とする定義域の要素を1つずつ持つような写像です。全単射どうしの合成写像もまた全単射になります。

全単射

全単射と逆写像

写像が全単射であることと、その写像の逆写像が存在することは必要十分です。また、逆写像が存在するとき、それは左逆写像や右写像と一致します。

DISCUSSION

質問とコメント

プレミアム会員専用コンテンツです
ログイン】【会員登録