集合の濃度と可算無限・非可算無限

有限集合の大きさは要素数ではかれる。

無限集合の大きさの表現には濃度を用いる。

無限集合の「大きさ」を表す概念である集合の濃度について,例を使いながらわかりやすく解説します。

写像についての知識があるとよいです。詳しくは 写像・単射・全射 をご覧ください。

※ この記事では自然数の集合 N\mathbb{N}00 を含めません。もちろん 00 が含まれる場合でも同じことが成立しますが,証明の書き方の都合上含まずに考えます。

集合論における濃度

集合 AA の「大きさ」 について考えます。AA が有限集合のときには,AA の要素数が「大きさ」と考えられますが,無限集合のときは要素数を数えることができません。無限集合の中でも「要素がたくさんある」ものと「要素があまりない」ものを区別するために,集合に対して濃度という概念が定義されます。

濃度の定義

集合 AA の濃度 A|A| を以下のように定義する。

  1. 有限集合 AA の濃度 A|A|AA の要素数とする。

  2. AA から BB への全単射(一対一対応)がある場合(またそのときに限って)A=B|A|=|B| とする。

  3. 集合 AA から BB への単射が存在するとき,AB|A|\leq |B| とする。

  • 単射とは xyx\neq y ならば f(x)f(y)f(x)\neq f(y) となる関数,つまり行き先がかぶらない関数のことでした。 → 写像・単射・全射
    単射があれば行き先の方が広い(狭くはない)というわけです。
  • 定義の2と3について,AB|A|\leq|B| かつ AB|A|\geq |B| なら A=B|A|=|B|が成立します。当たり前な気もしますが,これはベルンシュタインの定理と呼ばれ,証明はやや大変です。→ベルンシュタインの定理とその証明

濃度の例

有限集合

有限集合の場合はそのまま要素数を考えればよいです。

例1

S={1,2,,50}S = \{ 1 , 2, \cdots , 50 \} とすると A=50|A| = 50 である。

無限集合

例2

整数全体の集合 Z\mathbb{Z} の濃度と正の整数全体の集合 N\mathbb{N} の濃度は等しい。

濃度が等しいというのは全単射が存在するということです。そこで,整数全体の集合と正の整数全体の集合の間の一対一対応を作ることで証明します。

例2の証明

図のように一対一対応を構成できる。 整数と自然数の濃度が等しい

より正確には,整数全体の集合から正の整数全体の集合への関数 ff を以下のように定める:

f(x)={2x+1(x0)2x(x<0) f(x)= \begin{cases} 2x+1 & (x\geq 0)\\ -2{x} & (x < 0) \end{cases}

例えば f(2)=4f(-2)=4f(1)=2f(-1)=2f(0)=1f(0)=1f(1)=3f(1)=3f(2)=5f(2)=5 などとなり,ffZ\mathbb{Z} から N\mathbb{N} への全単射である。

整数の方が自然数よりもたくさん(二倍くらい)あるじゃないか!と思いますが,濃度という観点から見ると両者は同じです。

例3

偶数全体の集合と整数全体の集合の濃度は等しい。

証明はさきほどと同様に全単射を構成してやればOKです。簡単にできます。

例4

正の整数全体の集合と有理数全体の集合の濃度は等しい。

直感的には有理数の方が圧倒的にたくさんありますが,濃度という観点から見ると両者は同じなのです!

例4の大雑把な証明

正の有理数全体の集合 Q+\mathbb{Q}_+N\mathbb{N} の濃度が等しいことを言えばよい。

正の有理数 qp\dfrac{q}{p}p+qp+q を小さい順に並べて既約分数のみ残して番号を振っていけば,Q+\mathbb{Q}_+ から N\mathbb{N} への全単射が構成できる:

f(11)=1,f(12)=2,f(21)=3,f(13)=4,f(31)=5,f(14)=6,f(23)=7,\begin{aligned} &f \left( \frac{1}{1} \right) =1,\: f \left( \frac{1}{2} \right) =2,\: f \left( \frac{2}{1} \right) =3,\: f \left( \frac{1}{3} \right) =4,\:\\ &f \left( \frac{3}{1} \right) =5,\: f \left( \frac{1}{4} \right) =6,\: f \left( \frac{2}{3} \right) =7, \cdots \end{aligned}

有理数と整数の全単射

例5

半開区間 [0,1)[0,1) と開区間 (0,1)(0,1) の濃度は等しい。

証明

全単射 f(x)f(x) を以下のように構成できる。

  • 基本的には f(x)=xf(x)=x
  • x=1x=1 なら f(1)=0f(1) = 0
  • x=1n(n=2,)x=\dfrac{1}{n}\:(n=2,\dots) なら f(x)=1n1f(x)=\dfrac{1}{n-1}
    つまり,14131210\cdots \to \dfrac{1}{4} \to \dfrac{1}{3} \to \dfrac{1}{2} \to 1 \to 0 とうつす
例6

R=(0,1)|\mathbb{R}| = |(0,1)|

証明

f(x)=tan(πxπ2)f(x) = \tan \left( \pi x - \dfrac{\pi}{2} \right) と定義すると f:(0,1)Rf : (0,1) \to \mathbb{R} である。

g(x)=1πarctanx+12g(x) = \dfrac{1}{\pi} \arctan x + \dfrac{1}{2} が逆写像となるため,ff は全単射である。

冪集合の濃度,自然数と実数の違い

例7

任意の集合 AA に対して,AA のべき集合の濃度は AA の濃度より真に大きい(カントールの定理)。→カントールの定理の証明と対角線論法

例8

実数全体の集合の濃度は有理数全体の集合の濃度より真に大きい。

有理数と実数の間には濃度の意味でギャップがあります。

対角線論法を使うことで証明することができます。詳しくは カントールの定理の証明と対角線論法 を読んでみてください。

例7の「冪集合の濃度は元の集合の濃度よりも大きい」ことを用いて証明をすることができます。

証明

例7より 2N=R|2^{\mathbb{N}}| = |\mathbb{R}| を示せばよい。

例5,6より R=[0,1)|\mathbb{R}| = |[0,1)| であるため,2N=[0,1)|2^{\mathbb{N}}| = |[0,1)| を示そう。

A2NA \in 2^{\mathbb{N}} に対して f(A)=nA12n f(A) = \sum_{n \in A} \dfrac{1}{2^n} と定める。

例えば A={2,3,5,7,8}A = \{ 2,3,5,7,8 \} ならば f(A)=107256f(A) = \dfrac{107}{256} になる。A=A = \emptyset であれば f(A)=0f(A) = 0 である。

小数の2進数展開を考えれば ff は全単射である。よって 2N=[0,1)=R|2^{\mathbb{N}}| = |[0,1)| = |\mathbb{R}| となる。

可算無限と非可算無限

ここまでの結果から,N=Z=Q<R|\mathbb{N}|=|\mathbb{Z}|=|\mathbb{Q}|<|\mathbb{R}| がわかりました。

自然数の集合の濃度 N|\mathbb{N}| のことを 0\aleph_0 と書くことがあります。「アレフ・ゼロ」と読みます。

実は,任意の無限集合 AA に対して NA|\mathbb{N}|\leq|A| です。つまり,0\aleph_0 は無限集合の濃度の中で「最小」です。

正の整数全体の集合 N\mathbb{N} と濃度が等しい集合を可算集合(可付番集合)といいます。可算集合の要素は可算無限個などと言います。

可算無限とは「無限個あるけど番号をふっていける程度」の無限です。

上記の例から分かるように,整数は可算無限個であるのはもちろん,有理数も可算無限個です。

無限集合であり,可算集合でないものを 非可算集合 と言います。実数全体や複素数全体は非可算無限です。

非可算無限とは「番号をふることすらできない」無限です。

非可算無限のなかでも実数と同じ濃度であるものを \aleph と書きます。しばしば 連続体濃度 ということがあります。

連続体仮説

自然数の集合より真に大きいが,実数の集合よりは真に小さい集合はあるのでしょうか?

つまり 0<A<\aleph_0 < |A| < \aleph を満たす集合 AA は存在するのでしょうか?

これは 連続体仮説 と呼ばれています。実は現代数学で主に用いられている公理系では,連続体仮説が真か偽か証明することはできないとされています。

無限の世界はまだまだ不思議だらけですね。興味がある方はぜひ調べてみてください。

整数と有理数の濃度が等しいというのは感覚的に理解しがたいですね。