「集合と写像」2.2 可算と非可算1

ここでは,集合の濃度について,「可算」「非可算」ということばを紹介し,いくつかの集合の濃度が可算であることや \(\mathbb{R}\) が非可算であることなどについて解説する.

可算の定義

まず,この記事で最も中心的な話題となる「可算」を定義しよう.

定義 2.2.1 可算

任意に与えられた集合 \(A\) について,
$$|A|=|\mathbb{N}|$$
であるとき,すなわち,\(A\) と \(\mathbb{N}\) との間に全単射が存在するとき,\(A\) は可算集合である,可算である,\(A\) の濃度は可算である,などという.また,そのことを,
$$|A|=\aleph_0$$
と表記する1)\(\aleph_0\)はアレフゼロと読む.\(\aleph\)はヘブライ文字の最初の文字である.

 

すなわち,可算集合とは \(\mathbb{N}\) と「個数が等しい」ような集合である2)濃度を定義したときは,\(\mathbb{N}\) の濃度が「可算濃度」とよばれ,\(\aleph_0\) と表される.

 

では,可算集合の例を挙げよう.(このサイトでは \(0\in\mathbb{N}\) としているので注意されたい)

例 2.2.2 偶数と奇数

負でない偶数全体の集合を \(A\),正の奇数全体の集合を \(B\) としよう.このとき,写像 \(f:\mathbb{N}\to{}A,\ g:\mathbb{N}\to{}B\) を

\begin{align}
f(n)&=2n\notag\\
g(n)&=2n+1\notag
\end{align}

とすると,\(f,g\) はともに全単射である.したがって,

$$|A|=|B|=\aleph_0$$

例 2.2.3 整数

\(\mathbb{Z}\) は可算集合である.\(f:\mathbb{Z}\to\mathbb{N}\) を

$$f(n)=
\begin{cases}
2n & (0\leq{}n)\\
-(2n+1) & (n<0)
\end{cases}$$

とすれば,\(f\) は全単射になっている.したがって,

$$|\mathbb{Z}|=\aleph_0$$

例 2.2.4 有理数

\(\mathbb{Q}\) も可算である.\(\mathbb{N}\) から\(\mathbb{Q}\) への包含写像は単射であるので,\(|\mathbb{N}|\leq|\mathbb{Q}|\) である.

\(f\)を例 10.3 と同様に定義する.\(g:\mathbb{Q}\to\mathbb{N}\) を,任意に与えた \(\mathbb{Q}\) の元に対して既約表現 \(q/p\)(\(p>0\) で \(p,q\) は互いに素)を考え,

$$g\left(\frac{q}{p}\right)=2^{p}\cdot{}3^{f(q)}$$

とすれば,\(g\) は単射である.したがって,\(|\mathbb{Q}|\leq|\mathbb{N}|\) である.

以上から \(|\mathbb{N}|\leq|\mathbb{Q}|\) かつ \(|\mathbb{Q}|\leq|\mathbb{N}|\) であるので,ベルンシュタインの定理より \(|\mathbb{N}|=|\mathbb{Q}|\) である.

例 2.2.5 直積

\(|\mathbb{N}\times\mathbb{N}|=|\mathbb{N}|\) である.直観的には,\(\mathbb{N}\times\mathbb{N}\) の点を斜めに順番に数えていけば一対一対応ができあがる.具体的に式で \(\mathbb{N}\times\mathbb{N}\) から \(\mathbb{N}\) への全単射を与えると,

$$f(m,n)=\frac{1}{2}(m+n-1)(m+n-2)+m$$

となる.

 

高々可算

実は,無限集合はには,必ず,可算な部分集合が存在する.

感覚的には,\(A\) の異なる元を順番に与えて \(a_0,a_1,\cdots\) とすればよい.実際,帰納法により,無限集合ならば,任意の自然数 \(n\) について,元の個数が \(n\) の部分集合が存在することが示せる.しかし,これは,元の個数が「可算個」の部分集合の存在は保証してくれない.そこで,「選択公理」とよばれる主張を仮定して証明する.(選択公理については別の記事で解説する予定であり,この定理の証明はそこでも行う予定である.)

定理 2.2.6

無限集合には,可算な部分集合が存在する.

証明

任意に無限集合が与えられたとし,それを \(A\) とする.写像 \(f:\mathfrak{P}(A)\setminus\{\emptyset\}\to{}A\) が与えられていて,
$$f(X)\in{}X$$
が任意の空でない \(X\subset{}A\) に対して成り立っているとする3)\(\mathfrak{P}(A)\)は,\(A\)の部分集合全てからなる集合である.すなわち,\(X\in\mathfrak{P}(A)\Leftrightarrow{}X\subset{}A\) .すなわち,\(f\) により,\(A\) の空でない部分集合に対し,その元がひとつ選ばれているというわけである.なお,選択公理はこの部分で用いている.

この状況で,\(a_0,a_1,a_2,\cdots\) を次のように帰納的に定める.

  1. 任意に \(A\) の元をひとつ与え,それを \(a_0\) とする.
  2. \(a_0\) から \(a_n\) まで決定されているとする.このとき,\(a_{n+1}=f(A\setminus\{a_0,a_1,\cdots,a_n\})\) とする.\(A\) が無限集合であるので,\(A\setminus\{a_0,a_1,\cdots,a_n\}\) は空集合でなく,\(f\) の定義域に含まれている.

このようにすると,\(i\not=j\) ならば \(a_i\not=a_j\) であるので,\(\{a_n\mid{}n\in\mathbb{N}\}\) は無限集合であり,\(A\) の可算部分集合である.

(証明終)

 

定理 2.2.6 より,無限集合について次のことがいえる.

系 2.2.7

\(A\) が無限集合ならば,$$\aleph_0\leq|A|$$

また,直観的な表現をするなら,無限集合の中で一番「小さいサイズ」が可算なので,以下のような言葉を定義しておく.この記事ではこれ以降使わないが,数学を勉強する際にはしばしば見かけるであろう.

定義 2.2.8 高々可算

有限集合(空集合も含む)と可算集合を併せて「高々可算な集合」という.

 

非可算集合

可算という言葉を定義する以上は,可算ではない集合もあるだろうというふうに思われることと思う.実際,\(\mathbb{R}\)が可算ではないのである.

定義 2.2.8 非可算集合

有限集合でも可算集合でもない集合,すなわち,高々可算ではない集合のことを「非可算集合」という.

定理 2.2.9

\(\mathbb{R}\) は非可算集合である.

証明

証明は,背理法による.\(\mathbb{R}\) が可算であると仮定する.このとき,\({}(0,1)\) も可算集合である.これは,ベルンシュタインの定理と定理 2.2.6,\(|(0,1)|\leq|\mathbb{R}|=\aleph_0\) からわかる.\(f:\mathbb{N}\to{}(0,1)\) を全単射とする.

各正整数 \(n\) に対し,\(f(n)\) を \(10\) 進小数展開し4)このとき,展開の方法が2通り存在する数がある.そのような数は有限小数で表記できるので,有限小数による表記を採用すると約束しておけば議論が明確になる.このルールの下では,例えば,\(0.09999\cdots\) は \(0.1\) と表記される.ある位から \(9\) が無限に続くならば,繰り上がりを行って表記を修正するのだ.こうすると,小数展開の表記は一意に定まる.,小数第 \(n\) 位が奇数なら \(a_n=2\),偶数なら \(a_n=1\) として数列 \(\{a_n\}\) をつくる.これから実数 \(0.a_1a_2a_3\cdots\) をつくると,これは \({}(0,1)\) の元であるが任意の正整数 \(n\) について \(f(n)\) と異なる.これは矛盾である.

(証明終)

 

以上よりわかることは,\(\aleph_0<|\mathbb{R}|\) である.濃度が定義された際には,\(\mathbb{R}\) の濃度を「連続体濃度」と呼ぶ.また,\(|\mathbb{R}|\) を \(\aleph\) と書く5)\(\aleph\)はアレフと読む..こうすれば,定理 10.9 は \(\aleph_0<\aleph\) とも書くことができる.

前の記事:2.1 濃度の大小,ベルンシュタインの定理

次の記事:2.3 直積やべき集合と濃度,カントールの定理


参考書籍

この記事の内容を勉強するにあたり,定番で,筆者も使用している本を紹介します.(定価は2020年05月16日時点のものを表記しています.)

 

まずひとつ目は,内田 伏一著「集合と位相」,通称「内田」です.筆者は主にこちらを使用しています.

数学の基礎となっている集合論の内容と位相空間論の内容をまとめた本です6)普通,大学の数学科では「集合と位相」というタイトルで講義が開講されるので,それに合わせた内容になっています..なお,筆者が用いているのはこれの旧版で,増補改訂版では,演習問題の解答が拡充されているようです.


 

 

  ふたつ目は,松坂 和夫著「集合・位相入門」,通称「松坂」です. 内田同様,位相空間まで網羅した内容となっているほか,濃度の演算や順序数の古典的な扱いにふれられています(内田では省略されている).なお,筆者は,こちらの本も旧版を使っています.  


 

前の記事:2.1 濃度の大小,ベルンシュタインの定理

次の記事:2.3 直積やべき集合と濃度,カントールの定理

References   [ + ]

1. \(\aleph_0\)はアレフゼロと読む.\(\aleph\)はヘブライ文字の最初の文字である.
2. 濃度を定義したときは,\(\mathbb{N}\) の濃度が「可算濃度」とよばれ,\(\aleph_0\) と表される.
3. \(\mathfrak{P}(A)\)は,\(A\)の部分集合全てからなる集合である.すなわち,\(X\in\mathfrak{P}(A)\Leftrightarrow{}X\subset{}A\)
4. このとき,展開の方法が2通り存在する数がある.そのような数は有限小数で表記できるので,有限小数による表記を採用すると約束しておけば議論が明確になる.このルールの下では,例えば,\(0.09999\cdots\) は \(0.1\) と表記される.ある位から \(9\) が無限に続くならば,繰り上がりを行って表記を修正するのだ.こうすると,小数展開の表記は一意に定まる.
5. \(\aleph\)はアレフと読む.
6. 普通,大学の数学科では「集合と位相」というタイトルで講義が開講されるので,それに合わせた内容になっています.