COMPASS

真の理解のためのシンプルな数学のノート

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください(532 ピクセル以上推奨).

集合の濃度

理論

濃度

 この記事では, 無限集合の「大きさ」をどのように比較するかについて学ぶ. 集合の「大きさ」は, $2$ つの集合の間に $1$ 対 $1$ の対応があるかによって調べられる.

定義≪集合の対等関係≫

 集合 $A$ と $B$ の間に全単射 $f:A\to B$ が存在するとき, $A,$ $B$ は対等(equinumerous)であるといい, $A \sim B$ と表す.

例≪対等関係≫

 整数全体 $\mathbb Z$ と偶数全体 $2\mathbb Z$ は対等である. $f:\mathbb Z\to 2\mathbb Z;x\mapsto 2x$ という全単射が存在するからである.

定理≪対等関係の同値性≫

 集合の対等関係は同値関係である.

定義≪集合の濃度とその大小≫

(1)
集合の対等関係による類別を考えて, 集合 $A$ に対等な集合の成す類を $A$ の濃度(cardinality)と呼び, $|A|$ で表す.
(2)
集合 $A$ から $B$ への単射が存在するとき, $|A| \leqq |B|$ または $|B| \geqq |A|$ と表す. また, $\mathfrak m \leqq \mathfrak n,$ $\mathfrak m \neq \mathfrak n$ であることを $\mathfrak m < \mathfrak n$ または $\mathfrak n > \mathfrak m$ と表す.
(3)
非負整数全体の濃度を $\aleph _0$ で, 実数全体の濃度を $\aleph$ で表す. 濃度が $\aleph _0$ の集合を可算集合(countable set)と呼び, 有限集合と可算集合を合わせて高々な可算集合(at most countable set)と呼ぶ. 高々可算集合でない集合を非可算集合(discountable set)と呼ぶ.

例≪集合の濃度とその大小≫

 整数全体を $\mathbb Z,$ 有理数全体を $\mathbb Q,$ 実数全体を $\mathbb R,$ 複素数全体を $\mathbb C$ で表すとき, \[\aleph _0 = |\mathbb Z| = |\mathbb Q|, \quad \aleph = |\mathbb R| = |\mathbb C|.\]

定理≪Bernstein の定理≫

\[\mathfrak m \leqq \mathfrak n,\ \mathfrak m \geqq \mathfrak n \Longrightarrow \mathfrak m = \mathfrak n.\]
 濃度の大小関係は, 明らかに順序関係である. 選択公理を使うと, 次の定理が証明される.

定理≪濃度の比較可能定理≫

 濃度の大小関係は全順序関係である.

定理≪Cantor の定理≫

 集合 $A$ が空集合でないならば, \[ |A| < |\mathcal P(A)|.\] 特に, \[\aleph _0 < \aleph.\]

証明: Cantor の対角線論法

 写像 $A \to \mathcal P(A);a \mapsto \{ a\}$ は単射であるから, \[ |A| \leqq |\mathcal P(A)|.\] そこで, $A$ と $\mathcal P(A)$ が対等であるとして矛盾を導く. 全単射 $f:A \to \mathcal P(A)$ の存在を仮定する. このとき, $f(a) = \varnothing$ なる $a \in A (\neq \varnothing )$ が存在するから, \[ A' = \{ a \in A|a \in f(a)\} \neq \varnothing\] である. $A' \in \mathcal P(A)$ であるから, \[ f(\alpha ) = A' \quad \cdots [1]\] なる $\alpha \in A$ が存在する.
  • $\alpha \in A'$ とすると, $A'$ の定義から $\alpha \notin f(\alpha )$ となるが, $[1]$ からは $\alpha \in f(\alpha )$ となってしまう. これは不合理である.
  • $\alpha \notin A'$ とすると, $A'$ の定義から $\alpha \in f(\alpha )$ となるが, $[1]$ からは $\alpha \notin f(\alpha )$ となってしまう. これは不合理である.
よって, $\alpha \in A'$ と $\alpha \notin A'$ のどちらも起こらないという矛盾が生じる. ゆえに, $A$ と $\mathcal P(A)$ は対等でなく, $|A| < |\mathcal P(A)|$ が成り立つ.
 $\mathbb R$ の構成法により $\mathbb R$ は $\mathrm{Map}\,(\mathbb N,\{ 0,1\})$ と対等であり, したがって $\mathcal P(\mathbb N)$ と対等であるから, $A = \mathbb N$ に対して上記の結果を適用すると $\aleph _0 < \aleph$ となる.

問題

濃度

問題≪Hilbert の無限ホテル≫

 次の集合が正の整数全体 $\mathbb Z_+$ と対等であることを示せ.
(1)
非負整数全体 $\mathbb Z_+\cup\{ 0\}.$
(2)
$0$ でない整数全体 $\mathbb Z\setminus\{ 0\}.$
(3)
$\mathbb Z_+\times\mathbb Z_+.$ 

解答例

(1)
全単射 $f_1:\mathbb Z_+\cup\{ 0\}\to\mathbb Z_+;n\mapsto n+1$ が存在するから, $\mathbb Z_+\cup\{ 0\} \sim \mathbb Z_+$
(2)
全単射 \[ f_2:\mathbb Z\setminus\{ 0\}\to\mathbb Z_+;n\mapsto\begin{cases} 2n & (n > 0), \\ 2|n|-1 & (n < 0) \end{cases}\] が存在するから, $\mathbb Z\setminus\{ 0\} \sim \mathbb Z_+.$
(3)
$\mathbb Z_+\times\mathbb Z_+$ の元を, 各成分の和がに近い順に, 次いで第 $2$ 成分が小さい順に, 正の整数に対応させていくと, 全単射 $f_3:\mathbb Z_+\times\mathbb Z_+\to\mathbb Z_+$ ができるから, $\mathbb Z_+\times\mathbb Z_+ \sim \mathbb Z_+.$

解説≪Hilbert の無限ホテル≫

 この問題について, 次のような有名なクイズがある: あるところに, 無限の数の部屋を有するホテルがある. そのホテルの受付係の求人票には,「無限に関する知識が必要である」と書いてあった. このホテルには無限に部屋があるのだから, 客に部屋を割り当てるには何の問題もないはずではないか? そう思いながらも, ポールはそのホテルの受付係で働き始めた.
(1)
あの夜, ホテルはすでに満室であったが, $1$ 人の客がやってきた. ポールはある方法を使ってその客を宿泊させることができた. 彼は, 無限について知っていて良かったと思った. ポールはどのようにして, 新しい客を泊めることができたか? [答え: すでに泊まっていた客全員を部屋番号が $1$ つずつ大きい部屋に移動させ, $1$ 号室に新しい客を泊めた. つまり, 新しい客に $0$ の番号をつけて, $n$ 番目の客を $f_1(n) = n+1$ 号室に移した.]
(2)
ほっとしたのもつかの間, 次の夜は, 相変わらず満室の無限ホテルに満員の無限バスが到着した. ポールはどのようにすれば, バスの乗客全員を泊めることができるか? [答え: $n$ 号室にいた客を $2n$ 号室に移し, バスの乗客を奇数番目の部屋に泊める. つまり, バスの乗客に負の番号をつけて, $n$ 番目の客を $f_2(n)$ 号室に移す.]
(3)
さらに翌日, 無限ホテルはすべて空室であったが, それぞれ満員の無限バスで満車の無限フェリーが近くの港に到着した. ポールはどのようにすれば, すべての客を泊めることができるか? [答え: バスに番号をつけ, バスごとに乗客に番号をつけて, $m$ 号車の $n$ 番目の乗客を $f_3(m,n)$ 号室に移す.]
 なお, (2) において, 移動する客の「比率」は, いくらでも小さくすることができる. 実際, $m$ を正の整数とし, $mn$ 号室にいた客を $m(2n)$ 号室に移し, バスの乗客を $m(2n-1)$ 号室に泊めれば, 部屋番号が $m$ の倍数以外の客は移動する必要がなくなる. この $m$ の値はいくらでも大きくとることができる.