集合の濃度

全単射で大きさを測る

全射 $A\to B$ があれば、各 $b$ に原像を一つ選べる範囲では逆向きの単射と関係しますが、一般論は選択に注意が必要です。本記事では具体的な写像を構成します。互いに単射があれば全単射が存在するというシュレーダー・ベルンシュタインの定理もあります。

整数と有理数

整数は $0,1,-1,2,-2,3,-3,\ldots$ とすべて並べられるため可算です。

有限個の可算集合の和は可算です。また添字と各集合の要素を自然数の組で管理できる具体的な可算和も可算です。一般論では選択に関する仮定が関わるため深入りしません。

実数は列挙できない

EXカントールの対角線論法

$(0,1)$ の実数を $x_1,x_2,\ldots$ とすべて列挙できたと仮定します。各数は末尾が9だけになる表示を使わない標準的な小数表示に固定します。

x_1=0.a_{11}a_{12}a_{13}\ldots, \quad x_2=0.a_{21}a_{22}a_{23}\ldots, \quad\ldots

新しい数 $y=0.b_1b_2b_3\ldots$ を、 $a_{nn}=1$ なら $b_n=2$ 、それ以外なら $b_n=1$ と定めます。 $y$ は第 $n$ 桁で $x_n$ と異なるため、どの $x_n$ とも一致しません。しかも1と2だけを使うので $0.4999\ldots=0.5000\ldots$ の二重表示問題を避けています。列挙にない $y$ ができて矛盾するため、 $(0,1)$ は非可算です。

開区間・閉区間・実数全体は適切な全単射を作れて同じ濃度です。有理数は数直線上でどの区間にも存在する「稠密」な集合ですが、それでも可算です。密度と濃度は別の概念です。

べき集合はさらに大きい

証明の核は、任意の写像 $f:A\to\mathcal P(A)$ に対して $D=\{a\in A\mid a\notin f(a)\}$ を作ることです。もし $D=f(d)$ となる $d$ があれば、 $d\in D\Leftrightarrow d\notin D$ となり矛盾します。したがって $f$ は全射になれません。これは実数の対角線論法と発想は近いものの、任意の集合のべき集合についての別の定理です。

練習問題

Q全単射を作る★☆☆

$\mathbb N$ と奇数全体の全単射を一つ示してください。

HINTヒントを見る

このサイトでは $0\in\mathbb N$ です。

ANS解答を見る

$f(n)=2n+1$ は自然数から正の奇数全体への全単射です。各奇数 $2k+1$ の原像は一意に $k$ です。

Q直積の可算性★★☆

$\mathbb N\times\mathbb N$ が可算である理由を説明してください。

HINTヒントを見る

$m+n$ が一定の対角線ごとに並べます。

ANS解答を見る

$(0,0)$ 、次に和が1の2点、和が2の3点、という順に有限個ずつ列挙すると全格子点が有限段階で現れます。無限なので可算無限です。

Q誤解を反例で検討する★★★

「真部分集合は必ず元の集合より濃度が小さい」は正しいですか。

HINTヒントを見る

自然数と偶数を使います。

ANS解答を見る

無限集合では偽です。偶数全体は $\mathbb N$ の真部分集合ですが、 $n\mapsto2n$ が全単射なので同じ濃度です。有限集合なら主張は真です。