|| 単射と全単射について
前提『集合 A,B のどちらの方向にも単射が存在する』
結論『集合 A,B の間には全単射が存在する』
スポンサーリンク
「集合の濃度（大きさ）の定義」から見たら、
↓みたいに書くこともできます。
\begin{array}{lllll} \displaystyle |A|≤|B|&∧&|B|≤|A|&&⇒&&|A|=|B| \end{array}
これが「ベルンシュタインの定理」の主張です。
同時に、これは「全単射の作り方」を示すものでもあります。
目次
必要条件「この定理がなんで発見されたのか」
有限集合だと「当然のように成立する」
無限集合だと「どうなるか不明瞭」
集合の濃度「集合が持ってる要素の数（大きさ）」
単射「片方が全部、もう片方に被りなく写る」
全射「片方が全部、もう片方に全部写る（被っても）」
全単射「1対1の対応で、被りは無い」
具体例「サイズが無限の集合の一例」
方針「実際に全単射を作ってみる」
前提の確認「単射が双方向にある」
証明の核「単射の存在から、全単射を導く」
証明文「全単射を作れたらゲームセット」
直観的には、これはすごく当たり前の話です。
「全部」「重複（被り）も無く」
「どちらからも写る」なら、
\begin{array}{lllllll} \displaystyle 1&-&2 \\ \\ 2&-&3 \\ \\ 3&-&4 \end{array}
普通に考えれば、当然「要素数は同じ」
疑問の余地はまあ無いです。
\begin{array}{lllll} \displaystyle x+1&:&\{ 1,2,3 \} &\to&\{ 2,3,4 \} \\ \\ \displaystyle x-1&:&\{ 2,3,4 \} &\to&\{ 1,2,3 \} \end{array}
必然、「全単射」も作れるでしょう。
一対一の対応（紐づけ）をとる方法は
この場合、直感的にすぐ分かります。
しかし、これはあくまで「有限」の場合。
\begin{array}{lllll} \displaystyle (0,1)&&0<x<1 \\ \\ (0,\infty) &&0<x<\infty \end{array}
要素数（基数）が無限の場合
これはほんとに正しいのか。
これが分かりません。
まあそんなわけで、
『無限』ではどうなんだってことを確認した結果
どうやら正しいぞ、となったのがこの定理で、
結果として、
これによって『全単射の作り方』が明確になりました。
その点で、この定理には意味があります。
『全体を1対1対応させたい』時とか
そういう場面で使う考え方なので
覚えておいて損は無いです。
必要条件（具体的な根拠）
ベルンシュタインの定理は、
主に「無限の要素を持つ集合」を考えるのに必要なもので、
要素数が『有限』の集合に対しては、
特に意味のあるものではありません。
というのも、
『有限』の場合、これは明らかに成立するんですよ。
有限の場合
『双方向に単射がある』場合を考えてみます。
具体的な例を出すなら、例えば、
集合 \{1,2,3\} と
集合 \{4,8,12\} でなら、
\begin{array}{llllll} \displaystyle 1&⇆&4 \\ \\ 2&⇆&8 \\ \\ 3&⇆&12 \end{array}
まあ簡単にこういうのが作れますし、
他にも↓みたいなのも考えられます。
\begin{array}{llllll} \displaystyle f&:&1&\to&8 \\ \\ &&2&\to&4 \\ \\ &&3&\to&12 \\ \\ \\ g&:&4&\to&1 \\ \\ &&8&\to&3 \\ \\ &&12&\to&2 \end{array}
規則性は無いので採用されにくいですが、
こういう写像があるのもまた事実です。
で、このように『要素数が同じ』ということは、
\begin{array}{llllll} \displaystyle f&:&1&\to&8 \\ \\ &&2&\to&4 \\ \\ &&3&\to&12 \\ \\ \\ f^{-1}&:&1&←&8 \\ \\ &&2&←&4 \\ \\ &&3&←&12 \end{array}
考えられる単射の「矢印の向きを逆」にすれば、
「双方向の矢印（全単射）」が得られるということで、
ベルンシュタインの定理は明らかなこととして導けます。
要素数が違う場合
念のため、要素数が異なる場合も確認しておきます。
\begin{array}{llllllll} \displaystyle f&:&1&\to&8 \\ \\ &&2&\to&4 \\ \\ && &&12 \end{array}
まあその場合はこんな感じになるんですけど、
この場合、両方に「単射」を定義することはできません。
\begin{array}{llllllll} \displaystyle g&:&1&←&8 \\ \\ &&2&←&4 \\ \\ && &←&12 \end{array}
『要素数が多い方』から
『要素数が少ない方』へ「全て写す」なら、
必ず「被り」が出てしまいます。
確認しておくと、単射というのはそもそも、
『始域の全てが違う結果へ写る』写像なので
『要素数が少ない方から多い方へ』のものになります。
\begin{array}{llllllll} \displaystyle g&:&1&←&8 \\ \\ &&2&←&4 \\ \\ && &←&12 \end{array}
なのでこの場合、
どうやっても \{4,8,12\}→\{1,2\} の単射は作れません。
はい。まあそういうわけなので、
『どちらともに単射が存在する』ことは、
「どちらかの要素数が多い」と両立できないんです。
ということはつまり、有限の場合は
『単射が双方向にある』ってことは、
『要素数が同じになる』ってことでもあるわけですね。
少なくとも『有限』の場合なら、
これは簡単に確認できます。
無限の場合
『有限』の範囲なら、
「双方向に単射が存在する」場合
確実に「全単射」が作れます。
\begin{array}{lllll} \displaystyle 2x&:&(0,1)&\to&(0,2) \\ \\ \displaystyle \frac{1}{2}x&:&(0,1)&←&(0,2) \end{array}
しかし、「無限」の場合は
なんかちょっと、そうとは言い切れない感じがしませんか？
というのも、
例えば『自然数』と『有理数』なんですけど、
| 1 | 2 | 3 | 4 | 5 | … | |
| 1 | 1/1\,(\textcolor{skyblue}{1}) | 2/1\,(\textcolor{skyblue}{2}) | 3/1\,(\textcolor{skyblue}{4}) | 4/1\,(\textcolor{skyblue}{6}) | 5/1\,(\textcolor{skyblue}{10}) | |
| 2 | 1/2\,(\textcolor{skyblue}{3}) | 2/2 | 3/2\,(\textcolor{skyblue}{7}) | 4/2 | 5/2\,(\textcolor{skyblue}{13}) | |
| 3 | 1/3\,(\textcolor{skyblue}{5}) | 2/3\,(\textcolor{skyblue}{8}) | 3/3 | 4/3\,(\textcolor{skyblue}{14}) | 5/3 | |
| 4 | 1/4\,(\textcolor{skyblue}{9}) | 2/4 | 3/4\,(\textcolor{skyblue}{15}) | 4/4 | 5/4 | |
| 5 | 1/5\,(\textcolor{skyblue}{11}) | 2/5\,(\textcolor{skyblue}{16}) | 3/5 | 4/5 | 5/5 | |
| \vdots |
実はこの２つの間には、全単射が存在するんです。
感覚的には『有理数の方が明らかに多い』んですけど、
実際には、この２つのサイズは同等なんですよ。
はい。とまあこういう事例を考えると、
なんかちょっと分かんなくなるというか。
本当に無限の場合でもこれが成り立つのか
だいぶ疑問に思えてしまうわけです。
概念の定義の確認
とりあえず必要な知識の確認と
「定理に必要になる前提」の整備をしておきます。
ここではざっと扱いますが、
この３つについての基礎知識は必須
しっかり理解できてない方は、
できれば見ておくことを推奨します。
まあ、知らなくてもだいたい分かるとは思いますが。
集合の存在
『集合』というのは、
要は「中身のある袋」のようなものですね。
\begin{array}{lllllll} \displaystyle \mathrm{List}_{\mathrm{attribute}}&=&\{ \mathrm{name} &, \mathrm{id}&, \mathrm{pass} \} \\ \\ \mathrm{List}_1&=&\{ \mathrm{Yamada} &, \mathrm{00001}&, \mathrm{abcd12345} \} \end{array}
\begin{array}{llllll} \displaystyle \mathrm{Yamada} &∈& \mathrm{List}_1 \\ \\ \mathrm{pass} &∈& \mathrm{List}_{\mathrm{attribute}} \end{array}
『要素・元』は小文字で表現することが多いです。
具体的には a∈A , b∈B とか
こういう書かれ方をよく見ます。
ベルンシュタインの定理に限らず、
集合を使う話でこの考え方は必須。
なのでまず、
ここで『集合の存在』を確定させておきます。
とりあえず「 A,B 」としておく感じで。
写像の存在
「集合」と「写像」の感覚っていうのは、
要は『値の範囲』と『関数』の関係に似ていて、
\begin{array}{lllllll} a&∈&A \\ \\ b&∈&B \end{array}
\begin{array}{lllllll}\displaystyle f(a)&=&b \end{array}
「集合」を語る上では切っても切り離せません。
というか、関数は写像の一部です。
インプットとアウトプットが決まるとき、
\begin{array}{lllll} \displaystyle f&:&a&\to&b \end{array}
その手順として自動的に定義されます。
とまあ写像はそんな感じなので、
ここで『写像の存在』も確定させておきますね。
A から B への写像
\begin{array}{llllll} f&:&A&\to&B \end{array}
B から A への写像
\begin{array}{llllll} g&:&A&←&B \end{array}
この二つは、この時点ではただの『写像』とします。
「全射」「単射」「全単射」かは、まだ決めません。
単射の定義
次に『単射』の定義を確認します。
これは「全てのものが違う結果になる」
っていう感覚を実現したい感じで、
\begin{array}{llllllll} \Bigl( a_1&≠&a_2 \Bigr)&&⇒&&\Bigl( f(a_1)&≠&f(a_2) \Bigr) \end{array}
その感覚を数式で表すとこうですから、
\begin{array}{llllll} ∀a_1,a_2∈A& \Bigl[ \Bigl( a_1&≠&a_2 \Bigr)&⇒&\Bigl( f(a_1)&≠&f(a_2) \Bigr) \Bigr] \end{array}
論理式としては、
こんな感じに定義されています。
全射の定義
これは「終域を全てカバーできる」感じで、
つまりは『全ての終域に写る』を実現したいので、
\begin{array}{lllll} f(A)&=&B \end{array}
こんな感じになります。
\begin{array}{llllllll} ∀b∈B&\Bigl[&∃a∈A & \Bigl[ f(A)&=&B \Bigr] &\Bigr] \end{array}
まあなので、
論理式はこんな感じですね。
全単射の定義
名前で分かる通り、
「全射かつ単射」がこれの定義です。
まあつまり、
『全ての終域に写る』上に、
『全て違う結果に写る』ことになるので、
\begin{array}{lllll} \displaystyle (0,1)&&0<x<1 \\ \\ (0,2)&&0<x<2 \end{array}
\begin{array}{llllll} \displaystyle f&:&(0,1)&\to&(0,2) \\ \\ g&:&(0,2)&\to&(0,1) \end{array}
\begin{array}{llllll} \displaystyle f(x)&=&2x \\ \\ g(x)&=&\displaystyle \frac{1}{2}x \\ \\ &=&f^{-1}(x) \end{array}
具体的にはこんな感じになります。
今回示したい「ベルンシュタインの定理」の核
着地したい地点はここです。
要素数が無限の集合と全単射
この定理の核心部分は、
根本的には以下のような感じになります。
\begin{array}{llrll} A&:&\displaystyle [0,\infty) \\ \\ &&∀x&0≤x<\infty \\ \\ \\ B&:&(0,\infty) \\ \\ &&∀x&0<x<\infty \end{array}
この２つの集合を考えた時、
「全単射はあるのか」
つまり『サイズは同じなのか』を考えた時、
この定理の考え方が使われるんですよ。
というのも、この２つの集合の間では、
「全単射」を考えるのは難しいです。
\begin{array}{llllllll} \displaystyle f(x)&=&x &&× \end{array}
0 が結びつかない
とまあこのように、
「単射」なら簡単に思いつくんですが、
『全単射』となると、
単純な形を考えるのは難しいです。
\begin{array}{lllll} \displaystyle f&:&A&→&B \\ \\ g&:&B&→&A \end{array}
\begin{array}{llll} \displaystyle f(x)&=&x+α \\ \\ g(x)&=&x \end{array}
とまあこのような問題を考えた時、
ベルンシュタインの定理を使うんですね。
\begin{array}{llrll} A&:&\displaystyle [0,\infty) \\ \\ B&:&(0,\infty) \end{array}
確認しておくと、こうです。
なので、特異な点 0 をうまく回避しなければ、
全単射をうまく作ることはできません。
まあですから、
簡単に予想できることとして、
「 0 を含む写像」と
「 0 を含まない写像」の２つが必要
ということは分かって、
\begin{array}{llllllllll} \displaystyle F_{\mathrm{bijection}}(x)&=&\displaystyle \left\{\begin{array}{lllllll} \displaystyle f_{\mathrm{in}}(x) && \mathrm{if} &0∈A ∧\cdots \\ \\ f_{\mathrm{out}}(x) && \mathrm{if} &0∉A ∧\cdots \end{array} \right. \end{array}
それらの「値の範囲」もまた、
別々にする必要があることもなんとなく分かります。
\begin{array}{rlc} \displaystyle 0,1,2,3,4,5,\cdots ∈ \mathrm{N} \end{array}
\begin{array}{lllll} F_{\mathrm{bijection}}&:& [0,\infty) & \to &(0,\infty) \end{array}
\begin{array}{llllllllll} \displaystyle F_{\mathrm{bijection}}(x)&=&\displaystyle \left\{\begin{array}{lllllll} \displaystyle x+1 && \mathrm{if} &x∈\mathrm{N} \\ \\ x && \mathrm{if} &x∉\mathrm{N} \end{array} \right. \end{array}
具体的には、例えばこんな感じに、
片方の範囲を限定することで、
うまいこと 0 を処理できたりするわけですが、
この時に何をしたのか。
どうやってこれに行き着いたのか。
なんか、よく分かりませんよね？
\begin{array}{lllll} \displaystyle f&:&[0,\infty)&→& (0,\infty) \\ \\ g&:& (0,\infty) &→& [0,\infty) \end{array}
\begin{array}{llllllll} \displaystyle g(x)&=x \\ \\ f(x)&=x+1 \\ \\ \\ g\circ f(x)&=g(x+1)&=x+1 \\ \\ g\circ f\circ g \circ f(x)&= g\circ f(x+1)&=x+2 \\ \\ (g\circ f)^3(x) &= g\circ f(x+2)&=x+3 \\ \\ &\vdots \\ \\ (g\circ f)^n(x) &=x+n \\ \\ &\vdots \end{array}
材料はこんな感じなんですが、
この手順を形式化したやつが、
実はこのベルンシュタインの定理なんですよ。
\begin{array}{llllll} \displaystyle [0,\infty) &\setminus & g\Bigl((0,\infty)\Bigr) \\ \\ [0,\infty) &\setminus &(0,\infty) \\ \\ \\ \Bigl( \{0\}\cup (0,\infty) \Bigr) & \setminus& (0,\infty) \\ \\ \{0\} \end{array}
ざっと１つずつ解説するなら、
これは『一定の操作 g 』を使うと出てくるだろう
『 f\circ g\Bigl((0,\infty)\Bigr) での [0,\infty) の被り』を表していて、
\begin{array}{rlll} &\displaystyle [0,\infty)\setminus g\Bigl((0,\infty)\Bigr) & \{0\} \\ \\ \displaystyle g\circ f & \Bigl( [0,\infty)\setminus g\Bigl((0,\infty)\Bigr) \Bigr) & \{1\} \\ \\ \displaystyle (g\circ f)^2 & \Bigl( [0,\infty)\setminus g\Bigl((0,\infty)\Bigr) \Bigr) & \{2\} \\ \\ \displaystyle (g\circ f)^3 & \Bigl( [0,\infty)\setminus g\Bigl((0,\infty)\Bigr) \Bigr) & \{3\} \\ \\ & \vdots \\ \\ \displaystyle (g\circ f)^n & \Bigl( [0,\infty)\setminus g\Bigl((0,\infty)\Bigr) \Bigr) & \{n\} \end{array}
この被りと取りこぼしを全部集めて、
それを１つにまとめる。
\begin{array}{llllll} \displaystyle \bigcup_{n=0}^{\infty} (g\circ f)^n \Bigl( [0,\infty)\setminus g\Bigl((0,\infty)\Bigr) \Bigr) &=& \displaystyle \bigcup_{n=0}^{\infty} \{n\} \\ \\ &=&\{0,1,2,3,4,\cdots\} \\ \\ &=&\mathrm{N} \end{array}
そうしてできた「 f で写す部分」と
「 g^{-1} で写すだいたいの範囲」で区分けして、
\begin{array}{lllll} f(x)&=&x+1 \\ \\ g(x)&=&x \\ \\ \\ g^{-1}(x)&=&x\end{array}
\begin{array}{llllllllll} \displaystyle F_{\mathrm{bijection}}(x)&=&\displaystyle \left\{\begin{array}{lllllll} \displaystyle x+1 && \mathrm{if} &x∈\mathrm{N} \\ \\ x && \mathrm{if} &x∉\mathrm{N} \end{array} \right. \end{array}
全単射の写像を導く
とまあ大まかにはこんな感じのことをしてます。
わりと複雑ですが、
分解してみると単純なことしか言っていません。
分からなければ、よく見てみてください。
証明
というわけで、ベルンシュタインの定理を証明してみます。
確認しておくと、こいつの主張は↓です。
\begin{array}{llllllll} \displaystyle f&:&A&\to&B \\ \\ g&:&A&←&B \end{array}
この写像 f,g が単射である場合、
A,B の間に『全単射を作れる』
\begin{array}{llllllll} \displaystyle \Bigl(& |A|&≤&|B| &∧& |B|&≤&|A| &\Bigr)&\to& &|A|&=&|B| \end{array}
あるいはこんな感じのことを言っています。
証明される前の段階では、
『有限だと当たり前』で、
『無限でも全単射を作れれば要素数は同じ』
この２つだけが分かっていて、
他のことは分かっていません。
まあつまり、
「単射しか分からない」状況で、
「確実に全単射が作れるか」はまだ分かっていません。
方針
要は「どっちにも単射がある」なら
「全単射作れるよね？」って話なので、
\begin{array}{llllllll} \displaystyle f&:&A&\to&B \\ \\ g&:&A&←&B \end{array}
この単射を使って、
どうにか全単射を作ればそれで終わりそうです。
まあそれが難しいんですが、
方針と言っても、正直これくらいしかありませんね。
他、使えそうな情報としては、
「単射」ですから、
\begin{array}{lllll} \displaystyle A_{\mathrm{miss}} &=& A &\setminus &g(B) \\ \\ B_{\mathrm{miss}} &=& B &\setminus &f(A) \end{array}
この「取りこぼし」をうまく紐づければ、
どうにか全単射は作れそうな気がします。
前提の確認
再三の確認になりますが、
確定している前提は１つだけ。
\begin{array}{llllllll} \displaystyle f&:&A&\to&B \\ \\ g&:&A&←&B \end{array}
この写像 f,g が「単射」であること。
以上です。他にはありません。
証明の核
「単射」を使って「全単射」を導くこと。
これがゴールです。シンプルですね。
加えて、単射は存在しています。
\begin{array}{lllll} \displaystyle A_{\mathrm{miss}} &=& A &\setminus &g(B) \\ \\ B_{\mathrm{miss}} &=& B &\setminus &f(A) \end{array}
つまり「写るもの」と「写らないもの」があって、
この「写らないもの」を『写るようにして』
出てくるだろう『被り』を処理すれば、
\begin{array}{lllll} f(\displaystyle A_{\mathrm{miss}}) &=& g^{-1}g\Bigl( f(\displaystyle A_{\mathrm{miss}}) \Bigr) \end{array}
最終的に、全単射を導けそうな気がします。
とりあえず双方向の単射を作ってみる
「単射」の確認をしておきます。
\begin{array}{llllllll} \displaystyle f&:&A&→&B \\ \\ \displaystyle g&:&B&→&A \end{array}
当然ですが、
これで「簡単に全単射が作れる」場合、
\begin{array}{llllll} \displaystyle f(x)&=&2x &&\Bigl( f:(0,1)\to(0,2) \Bigr)\\ \\ f^{-1}(x)&=&\displaystyle \frac{1}{2}x &&\Bigl( f^{-1}:(0,2)\to(0,1) \Bigr) \end{array}
つまりこのようになる場合、
特に証明の必要はありません。
しかし、これで表すことができない場合、
つまり『全域を含む単射を簡単に作れない』場合、
\begin{array}{llllllll} \displaystyle f(x)&=&x+α &&\Bigl( f:[0,\infty)\to(0, \infty ) \Bigr) \\ \\ &&&&(0,α) \\ \\ \\ g(x)&=&\displaystyle x &&\Bigl( g:(0, \infty )\to[0, \infty ) \Bigr) \\ \\ &&&&\{0\} \end{array}
これだけでは不十分です。
(0,α)\,\,\,\,\{0\} という取りこぼしがあります。
そう、こういう『全域は含まない』けれど、
『だいたい含める写像は簡単に作れる』場合を考える時、
「取りこぼし」をうまく処理する必要があるんですよ。
全単射の構成
ひとまず、事実確認をしておきます。
↑の整理ですね。
２つの単射
\begin{array}{llllll} \displaystyle f&:&A&\to&B \\ \\ g&:&B&\to&A \end{array}
取りこぼし
\begin{array}{lllll} \displaystyle A_{\mathrm{miss}} &=& A &\setminus &g(B) \\ \\ B_{\mathrm{miss}} &=& B &\setminus &f(A) \end{array}
かぶり
\begin{array}{lllll} f(\displaystyle A_{\mathrm{miss}}) &=& g^{-1}g\Bigl( f(\displaystyle A_{\mathrm{miss}}) \Bigr) \end{array}
とりあえず、つらつらと書いておきます。
（ちなみに g(f(x)) と g\circ f(x) の意味は同じです）
条件分岐の整理
単射である写像 f,g を考えた時、
それが「簡単に全単射を作れない」のなら、
\begin{array}{llll} \displaystyle A_{\mathrm{miss}} &=& A &\setminus &g(B) \end{array}
必然、単射による写しの漏れ・取りこぼしが発生します。
で、この「取りこぼしがある」ことを考えると、
「集合 A の一部だけ」しか B とは紐づいていないので、
\begin{array}{lllll} \displaystyle f( A_{\mathrm{miss}}) &=& f \Bigl( A &\setminus &g(B) \Bigr) \end{array}
この部分をどうにか結びつけないことには、
A,B の中身を、全て1対1で結びつけることはできません。
とはいえこの時点で分かる通り、
大まかには以下のように分岐していて、
\begin{array}{llll} A \\ \\ \displaystyle A_{\mathrm{miss}} &=& A &\setminus &g(B) \end{array}
それぞれに f と g^{-1} を対応付ければ、
\begin{array}{lllllllll} \displaystyle f(x)&&x∈ A &\setminus &g(B) \\ \\ g^{-1}(x) && x∈ A \end{array}
うまいこと全単射を作れそうな気はします。
が、これでは明らかに被りが発生します。
片方が「 A 全域」ですからまあ当然なんですが、
\begin{array}{lllllllll} \displaystyle A&⊃& \Bigl( A &\setminus &g(B) \Bigr) \end{array}
この被りがある以上、
このままでは全単射を構成することができません。
はい。とまあそういうわけなので、
ここからは、この「被り」を特定して、
それを取り除くという操作が必要になります。
なので、次はそのような操作を考えてみましょうか。
被りの解消
というわけで「被り」なんですが、
これは『写像を経由する』ことで特定します。
確認しておくと、
「f による全ての紐づけ」はできてますが、
このまま「 f を作用させる」場合、
『 g^{-1} で紐づけされているもの』にも作用させてしまいます。
\begin{array}{llllll} \displaystyle f(x) &=&x+1 &&x∈[0,\infty)\setminus g\Bigl((0, \infty )\Bigr) \\ \\ g^{-1}(x) &=&x && x∈ (0, \infty ) \end{array}
例えばこんな感じに、
明らかに「1対1の対応（全単射）」をうまく作れていません。
\begin{array}{lllll} \displaystyle f(0)&=&1 \\ \\ g^{-1}(1)&=&1 \end{array}
具体的にはこの部分で。
とまあこんな具合に被りの特定はできるんですが、
これをうまく調整しようとすると、
例えば「 1 を取り除く」場合、
\begin{array}{llllll} \displaystyle f(x) &=&x+1 &&x∈[0,\infty)\setminus g\Bigl((0, \infty )\Bigr) \cup \{1\} \\ \\ g^{-1}(x) &=&x && x∈ (0, \infty ) \setminus \{1\} \end{array}
\begin{array}{lllll} \displaystyle f(1)&=&2 \\ \\ g^{-1}(2)&=&2 \end{array}
今度はこのような被りが発生してしまって、
また似たようなことをしなければならなくなります。
はい。とまあこのような「被り」がある以上、
このままでは全単射にはなりません。
なので、
『被りが出ないようにする』ために、
そのような「単射による操作」が必要で、
\begin{array}{llllll} \displaystyle A_{1}^{\mathrm{miss}} &=& A\setminus g(B) \\ \\ A_{2}^{\mathrm{out}}&= & g\circ f\Bigl( A\setminus g(B) \Bigr) \\ \\ A_{3}^{\mathrm{out}}&= & g\circ f\Bigl( g\circ f\Bigl( A\setminus g(B) \Bigr) \Bigr) \\ \\ &\vdots \\ \\ A_{n+1}^{\mathrm{out}}&= & g\circ f\Bigl( A_{n}^{\mathrm{out}} \Bigr) \end{array}
そのために必要になるのが、
こんな感じの「 f(x) の結果」と
「それに紐づく g( f(x) ) の結果」なんです。
\begin{array}{clll} \displaystyle f( A_{1}^{\mathrm{miss}} ) \\ \\ f( A_{2}^{\mathrm{out}} ) \\ \\ f( A_{3}^{\mathrm{out}} ) \\ \\ \vdots \\ \\ f( A_{n}^{\mathrm{out}} ) \\ \\ \vdots \end{array}
f を「作用させた結果 f(x) を導く」ことで、
「 g^{-1}(x) の x 」を改めて取り除き、
g^{-1} の紐づけに被らないようにします。
\begin{array}{lllllllll} \displaystyle f(x)&=&x+1 &&[0,\infty)\setminus g\Bigl( (0,\infty) \Bigr) \\ \\ g(x)&=&x && [0,\infty)\setminus (0,\infty) \\ \\ \\ \\ f(0)&=&1 &&\{0\}&&0 \to 1 \\ \\ g(f(0)) &=&1 && &&1← f(0) \\ \\ g^{-1}(1) &=&1 && && 1\to f(0) \\ \\ \\ && && \{0\}\cup \{1\} \\ \\ \\ f(1)&=&2 &&\{1\} && 1 \to 2 \\ \\ g(f(1)) &=&2 && && 2 ← f(1) \\ \\ g^{-1}(2) &=&2 && && 2 \to f(1) \\ \\ &\vdots \end{array}
\{0\}\cup\{1\}\cup \{2\}\cup\{3\}\cup \cdots \cup \{n\}
\begin{array}{lllllllllll} f(n)&=&n+1 &&\{n\} && n \to n+1 \\ \\ g(f(n)) &=&n+1 && && n+1 ← f(n) \\ \\ g^{-1}(n+1) &=&n+1 && && n+1 \to f(n) \\ \\ &\vdots \end{array}
具体的にはこんな感じに。
\begin{array}{llllll} \displaystyle A_{\mathrm{ex}}&=& \displaystyle \bigcup_{i=1}^{\infty}A^{\mathrm{out}}_{i} \end{array}
こうすると、
『 f を作用させた結果と被るもの以外』は、
全て g^{-1} によって B と1対1の対応が取れるようになって、
\begin{array}{lllll} \displaystyle f(x)&&x∈ A_{\mathrm{ex}} \\ \\ g^{-1}(x)&&x∉ A_{\mathrm{ex}} \end{array}
このように「被りの無い」状態を作れます。
この場合の g は、例えば x のような
「恒等写像」と考えるとイメージしやすいと思います。
（恒等写像は 1 を入れたら 1 を返す感じの写像のこと）
取りこぼしと被り・それ以外
以上のことから、
整理すると↓のような感じに。
\begin{array}{llllllll} \displaystyle f&:&A&→&B \\ \\ \displaystyle g&:&B&→&A \end{array}
『どちらの方向にも、単射が存在する』
まずこの前提が確定。
A\setminus g(B)
そして「単射による取りこぼし」を考えて、
\begin{array}{llllll} \displaystyle A_{1}^{\mathrm{miss}} &=& A\setminus g(B) \\ \\ A_{2}^{\mathrm{out}}&= & g\circ f\Bigl( A\setminus g(B) \Bigr) \\ \\ A_{3}^{\mathrm{out}}&= & g\circ f\Bigl( g\circ f\Bigl( A\setminus g(B) \Bigr) \Bigr) \\ \\ &\vdots \\ \\ A_{n+1}^{\mathrm{out}}&= & g\circ f\Bigl( A_{n}^{\mathrm{out}} \Bigr) \end{array}
\begin{array}{llllll} \displaystyle A_{\mathrm{ex}}&=& \displaystyle \bigcup_{i=1}^{\infty}A^{\mathrm{out}}_{i} \end{array}
次に「被り」を考慮。
最終的に、
↓のような『全単射』の写像が得られます。
\begin{array}{llllll} \displaystyle F_{ \mathrm{1\mathrm{to}1} }(x)&=&\displaystyle \left\{\begin{array}{llllllll} f(x)&&\Bigl(x∈ A_{\mathrm{ex}} \Bigr) \\ \\ g^{-1}(x) && \Bigl(x∉ A_{\mathrm{ex}} \Bigr) \end{array} \right. \end{array}
これがこの定理の核ですね。
ここまでくれば、
後はもう消化試合になります。
証明文
前提
単射 f,g が存在する。
基数が有限ではない集合 A,B が存在する。
\begin{array}{llllllll} \displaystyle f&:&A&→&B \\ \\ \displaystyle g&:&B&→&A \end{array}
材料
集合 A,B の間には、
以下のような全単射 F_{ \mathrm{1\mathrm{to}1} } が存在する。
\begin{array}{llllll} \displaystyle A_{1}^{\mathrm{miss}} &=& A\setminus g(B) \\ \\ A_{2}^{\mathrm{out}}&= & g\circ f\Bigl( A\setminus g(B) \Bigr) \\ \\ A_{3}^{\mathrm{out}}&= & g\circ f\Bigl( g\circ f\Bigl( A\setminus g(B) \Bigr) \Bigr) \\ \\ &\vdots \\ \\ A_{n+1}^{\mathrm{out}}&= & g\circ f\Bigl( A_{n}^{\mathrm{out}} \Bigr) \end{array}
\begin{array}{llllll} \displaystyle A_{\mathrm{ex}}&=& \displaystyle \bigcup_{i=1}^{\infty}A^{\mathrm{out}}_{i} \end{array}
\begin{array}{llllll} \displaystyle F_{ \mathrm{1\mathrm{to}1} }(x)&=&\displaystyle \left\{\begin{array}{llllllll} f(x)&&\Bigl(x∈ A_{\mathrm{ex}} \Bigr) \\ \\ g^{-1}(x) && \Bigl(x∉ A_{\mathrm{ex}} \Bigr) \end{array} \right. \end{array}
結論
双方向に単射 f,g が存在する場合、
全単射を作ることが可能である
|A|=|B|
ということは、基数の関係もこうなる。
以上、ベルンシュタインの定理はこんな感じです。
ほぼ「全単射の作り方」なので、
それ以外はオマケと思って問題ありません。
１次元と２次元
ちなみにこの定理から
\begin{array}{llllll} \displaystyle |R|&=&|R\times R| \\ \\ &&|R\times R|&=&|R\times R\times R| \\ \\ &&&&|R\times R\times R|&=&\cdots &=&|R\times \cdots \times R| \end{array}
この結果が得られます。
ちょっと意味わかんないかもしれませんが
\begin{array}{llllll} \displaystyle f(x)&=&(x,1) \end{array}
まずこれは考えるまでもなくこう
\begin{array}{llllll} \displaystyle [0,1)&→&[0,1)\times [0,1) &&〇 \\ \\ [0,1)&←&[0,1)\times [0,1) &&？ \end{array}
「２次元 → １次元 の単射」については
考えるのが少々難しいですが
\begin{array}{llllll} \displaystyle [0,1)\times [0,1) &&→&& ？ \end{array}
『 x,y から被りなく値が定まる』
『 x,y を調整すれば任意の値を作れる』
\begin{array}{llllll} \displaystyle x&=&0.a_1a_2a_3\cdots \\ \\ y&=&0.b_1b_2b_3\cdots \end{array}
\begin{array}{llllll} \displaystyle h(x,y) &=& 0.a_1b_1a_2b_2\cdots \\ \\ h(x,y) &=& 0.b_1a_1b_2a_2\cdots \end{array}
そういった要望から
このような「単射 h 」の存在が導けるので
\begin{array}{llllll} \displaystyle [0,1)&→&[0,1)\times [0,1) &&〇 \\ \\ [0,1)&←&[0,1)\times [0,1) &&〇 \end{array}
\begin{array}{llllll} \displaystyle \Bigl| [0,1) \Bigr|&=&\Bigl| [0,1)\times [0,1) \Bigr| \end{array}
このようになります。
\begin{array}{llllll} \displaystyle |R|&=&|R\times R| \end{array}
同様に、これも導けるので
『次元数を上げる』→『濃度は変わらない』
これが導かれます。
\begin{array}{llllll} \displaystyle |R|&=&|R\times R| \\ \\ &&|R\times R|&=&|R\times R\times R| \end{array}
不思議な話ですが
この結果から
\begin{array}{llllll} \displaystyle |R|&=&|R\times R\times R| \end{array}
「線」を分割すると
「どこまでも広い空間」を作れる
ということが分かります。
実数と区間
実数 (-\infty,\infty) と区間 [0,1) の濃度
\begin{array}{llllll} \displaystyle \Bigl| [0,1) \Bigr|&=&|R| \end{array}
これについても解説しておきます。
\begin{array}{llllll} \displaystyle [0,1) &←&R \end{array}
ちなみにこれは直接的にではなく
\begin{array}{llllll} \displaystyle \Bigl| (0,1) \Bigr|&→&|R| \end{array}
\begin{array}{llllll} \displaystyle f(x)&=&\displaystyle \tan \left( xπ -\frac{π}{2} \right) \end{array}
グラフの形から分かるこの全単射と
\begin{array}{llllll} \displaystyle 0,1,2,3,4,...&∈&N \end{array}
\begin{array}{llllllllll} \displaystyle f(x)&=&\displaystyle \left\{\begin{array}{lllllll} \displaystyle x+1 && \mathrm{if} &x∈\mathrm{N} \\ \\ x && \mathrm{if} &x∉\mathrm{N} \end{array} \right. \end{array}
\begin{array}{llllll} \displaystyle \Bigl| (0,1) \Bigr|&=&\Bigl| [0,1) \Bigr| \end{array}
この全単射から
\begin{array}{llllll} \displaystyle \displaystyle &&\displaystyle \Bigl| (0,1) \Bigr|&=&|R| \\ \\ \displaystyle \Bigl| [0,1) \Bigr| &=&\displaystyle \Bigl| (0,1) \Bigr| \end{array}
間接的に示すことができます。