WIIS

写像

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

目次

Mailで保存
Xで共有

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

集合\(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\)について、\(A\)から\(B\)への単射と\(B\)から\(A\)への単射がともに存在するとき、\(A\)から\(B\)への全単射が存在する。
証明

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

例(シュレーダー=ベルンシュタインの定理)
半開区間\((0,1]\)と開区間\(\left( 0,1\right) \)の間に全単射が存在することを示します。それぞれの\(x\in (0,1]\)に対して、\begin{equation*}f\left( x\right) =\frac{x}{2}+\frac{1}{4}
\end{equation*}を定める写像\(f:(0,1]\rightarrow \left(0,1\right) \)と、それぞれの\(x\in\left( 0,1\right) \)に対して、\begin{equation*}g\left( x\right) =x
\end{equation*}を定める写像\(g:\left( 0,1\right)\rightarrow (0,1]\)に注目します。これらはともに単射です。実際、\(x_{1},x_{2}\in (0,1]\)を任意に選んだとき、\begin{eqnarray*}f\left( x_{1}\right) =f\left( x_{2}\right) &\Leftrightarrow &\frac{x_{1}}{2}+\frac{1}{4}=\frac{x_{2}}{2}+\frac{1}{4} \\
&\Rightarrow &x_{1}=x_{2}
\end{eqnarray*}となるため\(f\)は単射です。また、\(x_{1},x_{2}\in (0,1]\)を任意に選んだとき、\begin{equation*}g\left( x_{1}\right) =g\left( x_{2}\right) \Leftrightarrow x_{1}=x_{2}
\end{equation*}となるため\(g\)は単射です。したがって、シュレーダー=ベルンシュタインの定理より、全単射\begin{equation*}h:(0,1]\rightarrow \left( 0,1\right)
\end{equation*}が存在します。

集合\(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\)が全単射であるとまでは言っていません。

例(シュレーダー=ベルンシュタインの定理)
写像\(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] \)はそれぞれの\(x\in \left[ 0,2\right] \)に対して、\begin{equation*}g\left( x\right) =\frac{x}{4}
\end{equation*}を定めるものとします。\(f\)と\(g\)はともに単射であるため、シュレーダー=ベルンシュタインの定理より全単射\begin{equation*}h:\left[ 0,1\right] \rightarrow \left[ 0,2\right] \end{equation*}が存在します。しかし、\(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*}が成り立つため全射ではありません。

 

単射と全射の関係

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

命題(単射と全射の関係)
集合\(A,B\)について、\(A\)から\(B\)への単射が存在するとき、\(B\)から\(A\)への全射が存在する。
証明

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

先の命題とは逆に、集合\(A,B\)について、\(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\)への全単射が存在することが保証されます。ただし、選択公理が必要です。

命題(単射と全射から全単射を導かれる全単射)
集合\(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\)への全射と\(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\)への全単射が存在する。
証明

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

例(全単射と全単射から導かれる全単射)
集合\(A,B\)について、\(A\)から\(B\)の部分集合への全単射\(f\)と、\(A\)の部分集合から\(B\)への全単射\(g\)が存在するものとします。全単射には逆写像が存在してそれもまた全単射になるため、\(g\)の逆写像\(g^{-1}\)が存在して、これは\(B\)から\(A\)の部分集合への全単射になります。したがってこの場合、先の命題より\(A\)から\(B\)への全単射が存在します。

 

演習問題

問題(全単射の存在)
集合\(A,B,C\)の間に以下の包含関係\begin{equation*}A\subset B\subset C
\end{equation*}が成り立つものとします。さらに、\(A\)から\(C\)への全単射が存在するものとします。このとき、\(A\)から\(B\)への全単射が存在することを示してください。
解答を見る

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

問題(全単射の存在)
集合\(\left( 0,1\right) \times \left( 0,1\right) \)から集合\(\left( 0,1\right) \)への全単射が存在することを示します。以下の問いに答えてください。

  1. \(x\in \left( 0,1\right) \)を選んだとき、これは\(0\)より大きく\(1\)より小さい実数であるため、\(x\)を10進展開すると、\begin{equation}x=0.x_{1}x_{2}x_{3}\cdots _{\left( 10\right) } \quad \cdots (1)\end{equation}となります。以上を踏まえた上で、\(x\in \left(0,1\right) \)の10進展開は一意的に定まるとは限らないことを示してください。
  2. \(x\in \left( 0,1\right) \)の10進展開が一意的に定まるようにルールを修正してください。
  3. 以上を踏まえた上で、\(\left( 0,1\right) \times \left( 0,1\right) \)から\(\left( 0,1\right) \)への単射を具体的に提示してください。
  4. \(\left( 0,1\right) \)から\(\left( 0,1\right) \times \left(0,1\right) \)への単射を具体的に提示してください。
  5. \(\left( 0,1\right) \times \left( 0,1\right) \)から\(\left(0,1\right) \)への全単射が存在することを示してください。
解答を見る

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

関連知識

Mailで保存
Xで共有

質問とコメント

プレミアム会員専用コンテンツです

会員登録

有料のプレミアム会員であれば、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

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