有限の対応

無限の対応

これがちょっと面倒。

Aとの対応から漏れたBの要素が無限にあるように見えますし、加えてAもよく見みると、まだ対応させていない、見落としていた要素が無限にあるように見えます。

無限の対応関係を考える為の道具を下に用意しました。

写像

集合$\displaystyle A$の任意の元に対してそれぞれ集合 $\displaystyle B$の元をただ一つずつ指定する規則 $\displaystyle f$ があるとき、$\displaystyle A$を$\displaystyle f$の定義域（あるいは始域）$\displaystyle{B}$を $\displaystyle f$の終域、$\displaystyle f$を$\displaystyle A$ から $\displaystyle B$ への写像という。この関係を、下式のように表す。

$\displaystyle f:A\rightarrow B$

$\displaystyle A{\stackrel {f}{{}\rightarrow {}}}B$

単射

集合 A を定義域、集合 B を終域とする写像 f: A → B が条件

$\displaystyle (\forall x,y\in A)\;{\big [}x\neq y\implies f(x)\neq f(y){\big ]}$

を満たすとき、 f を単射 (injection) とよぶ[1]。

単射

単射_非全射

ウィキペディア

つまり、写像 f: A → B に対し、2つの条件

全射性: f(A) = B

単射性: 任意の A の元 a1, a2 について、f(a1) = f(a2) ならば a1 = a2

がともに成り立つとき、写像 f は全単射 (bijective) であるという。この用語はブルバキによる。

ウィキペディア

 

写像 f の定義域を集合 X, 値域を集合 Y とする。写像 f が可逆 (invertible) であるとは、Y を定義域、X を値域とする写像 g で、条件

f(x)=y⟺g(y)=x

を満足するものが存在するときに言う。

以上の道具を用いて無限集合におけるベルンシュタインの定理を証明します。

開始。
A<Bと仮定しても一般性は失われません。

集合$A$を写像$f()$で飛ばすとすると、ベルンシュタインの定理の前提「単射である」より、$A$の要素には必ず相手$f(t)$がいます。…①

集合$B$の方が大きいと仮定しているので、$B$には$A$との対応を作れなかった余り$B_{0}$がいます。

また、①より$B$の濃度を$|A|$に制限すれば逆写像を作れるので、
$f(x)^(-1):(B\setminus B_{0})→x$(逆写像)
よって
$|A|=|(B\setminus B_{0})|$(全単射)
となります。

$B$の余り$B_{0}$を回収します。

仮定より、$g:B→A$は単射なので、①で余った要素$B_{0}$と対応する$g(B_{0})= A_{0}∈A-g(B_{0})$が$A$に必ず存在します。

また、$g(x)$は単射であるため下の画像のような二股の対応関係は作れません。

よって、$g(B_{0})$は$g(B-B_{0})$とは異なる集合$A_{0}$であると言えます。

全射かつ非単射

以上より、
$g(B_{0})^{-1}$により、$|A_{0}|=|B_{0}|$により全単射を構成できます。…②

①と②より、
$B$とその余り$B_{0}$をAと対応させられました。
よって、双方向単射なら$A$と$f(B-B_{0})$は全単射$|A|=|B|$が構成できます。

つまり、仮定した$A<B$は結論と矛盾します。

また、ここでの議論においては、論理的に$(|A|<|B|)=(|B|<|A|)$なので、背理法により、残る唯一の可能性は
$|A|=|B|$
だけとなります。

先程の①と合わせると、集合$A,B$の双方向からの単射が存在するならば、全単射が存在し、濃度が$|A|=|B|$が成り立ちます。

利用例