有限の集合
この定理は「集合の濃度（元の個数の一般化）」において、不等号の性質が成り立つことを保証する非常に強力なツールです。前提: A から B への単射と、B から A への単射が存在する。結論: A と B は「同じ濃度（要素のサイズが等しい）」であり、全単射が存在する数学における「単射（英: injection）」とは、異なる要素を写像（関数）によって飛ばしたとき、行き先が必ず異なる値になる性質のことです。単射（$\le$）：はみ出してもいいから、重複なく席を割り当てられる。全単射（$=$）：余りも重複も一切なく、ピッタリ1対1で対応する。Gemini
$A,B$の濃度が有限だと仮定。
$|A|<|B|$
だと仮定
$a_{2}→b_{2}$
$a_{3}→b_{3}$
$\vdots$
$ →b_{n}$
$x≠y⇒f(x)≠f(y)$
$x=y⇒f(x)=f(y)$
なので始域の要素は終域のどれかと必ず対応します。終域が余ることはありません。
よって背理法より
$(|A|<|B|)⇒|A|>|B|∨|A|=|B|$…①
逆関数の定義より
$b_{1}→a_{1}$
$b_{2}→a_{2}$
$b_{3}→a_{3}$
$\vdots$
$ →a_{n}$
$(|A|>|B|)⇒|A|<|B|∨|A|=|B|$
$|A|=|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 の定義域を集合 X, 値域を集合 Y とする。写像 f が可逆 (invertible) であるとは、Y を定義域、X を値域とする写像 g で、条件
- f(x)=y⟺g(y)=x
を満足するものが存在するときに言う。
無限集合におけるベルンシュタインの定義を証明します。
A<Bと仮定しても一般性は失われません。
集合$A$から関数$f(x)$により単射を飛ばすと仮定すると、ベルンシュタインの仮定より、$A$の要素には必ず相手がいます。…①
また、集合$B$の方が大きいと仮定しているので、$B$には$A$との対応を作れなかった$B_{0}$がいます。
次はこの$B$の余りを回収します。
仮定より$B_{0}$には変わらず相手がいます。
つまり、$g(f(B_{0}))$で$A$へ必ず送れます。
また、$(B)$単射なので
$g(f(B_{0}))^{1}$で$A→B$
の逆写像が作れます。
先程の①と合わせると、集合$A,B$の双方向からの単射が存在するならば、全単射が存在し、濃度が$|A|=|B|$が成り立ちます。
利用例
全単射を構成する必要がないので、無限の範囲の濃度の比較に便利です。
開区間$A:(0,1)$と閉区間$B:[0,1]$
開区間→閉区間の場合は
$f(x)=x$
で対応させられます。
閉区間から開区間へら
$f(x)=\frac{x}{2}+0.1$
で対応させられます。
これは閉区間から開区間を一位に対応させられます。
$+0.1$を入れたのは
$x=0⇒0+ 0.1$
となり、$x=0$の場合は閉区間から飛ばした先が閉区間からはみ出してしまうからです。
集合A,Bはベルンシュタインの定理を満たすので濃度は同値になります。
コメント