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

更新日時 2022/01/29

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

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

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

集合論における濃度

集合 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

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

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

例1の証明

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

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

f(x)=2x+1(x0),f(x)=2x(x<0)f(x)=2x+1\:(x\geq 0),\\f(x)=-2{x}\:(x <0)

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

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

例2

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

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

例3

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

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

例3の大雑把な証明

正の有理数全体の集合 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(\frac{1}{1})=1,\:f(\frac{1}{2})=2,\:f(\frac{2}{1})=3,\:f(\frac{1}{3})=4,\:

f(31)=5,f(14)=6,f(23)=7,f(\frac{3}{1})=5,\:f(\frac{1}{4})=6,\:f(\frac{2}{3})=7,\cdots

有理数と整数の全単射

例4

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

例5

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

有理数と実数の間には濃度の意味でギャップがあります。例5の証明にも対角線論法を使います。例4と同じ記事:カントールの定理の証明と対角線論法の末尾で証明しています。

  • ここまでの結果から,N=Z=Q<R|\mathbb{N}|=|\mathbb{Z}|=|\mathbb{Q}|<|\mathbb{R}| がわかりました。
  • N=Z=Q|\mathbb{N}|=|\mathbb{Z}|=|\mathbb{Q}| のことを 0\aleph_0 と書くことがあります。「アレフ・ゼロ」と読みます。
  • 実は,任意の無限集合 AA に対して NA|\mathbb{N}|\leq|A| です。つまり,0\aleph_0 は無限集合の濃度の中で「最小」です。
  • また,2N=R|2^{\mathbb{N}}|=|\mathbb{R}| です。大雑把なイメージですが,小数の2進数表示を考えると,たしかに 2N2^{\mathbb{N}}[0,1][0,1] が同じ濃度になりそうです。
例6

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

証明

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

  • 基本的には f(x)=xf(x)=x
  • ただし,もし x=1n(n=1,2,)x=\dfrac{1}{n}\:(n=1,2,\dots) なら f(x)=1n+1f(x)=\dfrac{1}{n+1}
    つまり,11213141\to\dfrac{1}{2}\to\dfrac{1}{3}\to\dfrac{1}{4}\to\cdots とうつす

可算無限と非可算無限

  • 正の整数全体の集合 N\mathbb{N} と濃度が等しい集合を可算集合といいます。可算集合の要素は可算無限個などと言います。可算無限とは「無限個あるけど番号をふっていける程度」の無限です。
  • 上記の例から分かるように,整数は可算無限個であるのはもちろん,有理数も可算無限個です。
  • 可算集合は N\mathbb{N} との間に全単射があるので,要素に 11 から順番に番号をふっていくことができます。そのため可付番集合とも言います。
  • 無限集合であり,可算集合でないものを非可算集合と言います。実数全体や複素数全体は非可算無限です。非可算無限とは「番号をふることすらできない」無限です。

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