自然数全体の集合は実数全体の集合よりも濃度が小さい ということはよく話題に上がっているような気がします.

そこで 無限集合の濃度は無数に存在することを示します.

主張: 任意の集合$A$に対して $$ |A| < |2^A|. $$

証明:

\[A \to 2^A; x \mapsto \{ x \}\]

を考えると, この関数は明らかに単射なので, $|A| \le |2^A|$ が成り立つ.

$A$から$2^A$への全単射が存在しないことを示す.

そこで 写像$f \colon A \to 2^A$を全単射とする.

\[B := \{ x \in A; x \notin f(x) \}\]

を考える. $B \notin f(A)$, すなわち 全て$x \in A$に対して $f(x) \neq B$であることを示す.

$x \in A$に対して $x \in f(x)$もしくは $x \notin f(x)$である.

1) $x \in f(x)$であるとき: $B$の定義より$x \notin B$である. よって $x \notin B$かつ $x \in f(x)$より $f(x) \neq B$が成り立つ.

2) $x \notin f(x)$であるとき: $B$の定義より $x \in B$である. よって $x \in B$かつ$x \notin f(x)$より$f(x) \neq B$が成り立つ.



外部リンク