非可算集合

Basis
最終更新: タグ: Set Theory

前提知識

可算集合 のチェックポイントでは、Z\mathbb{Z}、Q\mathbb{Q}、さらには N×N\mathbb{N} \times \mathbb{N} もすべて可算無限であることを示した――うまい全単射を N\mathbb{N} との間に見つければいいのだ。そして カントールの定理 は P(N)\mathcal{P}(\mathbb{N}) が真に大きいことを証明した。このチェックポイントではそのギャップを具体的に見ていく。実数がまったくリストアップできないことの直接証明を見て、∣R∣|\mathbb{R}| が正確にどれくらいの大きさかを突き止めよう。

非可算とはどういうことか

可算集合 とは有限または N\mathbb{N} と全単射する集合だ。集合 AA が非可算 (uncountable) であるとは、AA が無限であり、かつ可算でない――つまり全単射 N→A\mathbb{N} \to A が存在しない――ことをいう。

この結果は鮮烈だ。a0,a1,a2,…a_0, a_1, a_2, \ldots というリストで AA のすべての元を含むことはできない。どんな列挙戦略を試みても、必ずこぼれ落ちる元が出てくる。カントールの定理 はすでに ∣N∣<∣P(N)∣|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| を示したので、P(N)\mathcal{P}(\mathbb{N}) は最初の候補だ。本当の問いは、日常的な集合の中でどれが非可算かということだ。

実数は非可算である

最も重要な非可算集合は R\mathbb{R} だ。直接攻めるのではなく、開区間 (0,1)(0,1) から始めよう。こちらの方が扱いやすく、すでに R\mathbb{R} とまったく同じ大きさを持つ。

(0,1)(0,1) と R\mathbb{R} が同じ大きさである理由。 写像 x↦tan⁡ ⁣(π(x−12))x \mapsto \tan\!\bigl(\pi(x - \tfrac{1}{2})\bigr) が全単射 (0,1)→R(0,1) \to \mathbb{R} を与えるので、∣(0,1)∣=∣R∣|(0,1)| = |\mathbb{R}| だ。

定理。 (0,1)(0,1) は非可算である。

証明。 (0,1)(0,1) が可算であると仮定して矛盾を導く。そうすると、すべての元を漏れなく並べた無限リスト r0,r1,r2,…r_0, r_1, r_2, \ldots を作れるはずだ。各 rir_i を十進展開で書く。

ri  =  0 . di0  di1  di2  ⋯r_i \;=\; 0\,.\,d_{i0}\;d_{i1}\;d_{i2}\;\cdots

ここで各桁 dij∈{0,1,…,9}d_{ij} \in \{0, 1, \ldots, 9\} だ。桁を無限行列に並べる――1行が1つの実数に、1列が1つの十進の位置に対応する。

位置 00位置 11位置 22位置 33⋯\cdots
r0r_0d00\mathbf{d_{00}}d01d_{01}d02d_{02}d03d_{03}
r1r_1d10d_{10}d11\mathbf{d_{11}}d12d_{12}d13d_{13}
r2r_2d20d_{20}d21d_{21}d22\mathbf{d_{22}}d23d_{23}
r3r_3d30d_{30}d31d_{31}d32d_{32}d33\mathbf{d_{33}}
⋮\vdots⋱\ddots

太字の対角成分 d00,d11,d22,…d_{00}, d_{11}, d_{22}, \ldots は各 rnr_n が位置 nn に置く桁を記録している。ここで、すべての対角の桁を変更して新しい実数 s=0 . s0  s1  s2  ⋯s = 0\,.\,s_0\;s_1\;s_2\;\cdots を構成する。

sn  ≔  {1if dnn≠1,2if dnn=1.(1)s_n \;\coloneqq\; \begin{cases} 1 & \text{if } d_{nn} \neq 1, \\ 2 & \text{if } d_{nn} = 1. \end{cases} \tag{1}

各桁 sns_n は {1,2}\{1, 2\} に属するので s∈(0,1)s \in (0, 1) だ。しかし各 nn について、規則 (1)(1) が sn≠dnns_n \neq d_{nn} を保証するため、ss と rnr_n は位置 nn で異なり、s≠rns \neq r_n となる。したがって ss は (0,1)(0,1) の実数でありながらリスト r0,r1,r2,…r_0, r_1, r_2, \ldots のどこにも現れない――リストが完全だという仮定に矛盾する。□\square

なぜ 1 と 2 を使うのか？ sn∈{1,2}s_n \in \{1, 2\} を選ぶのは微妙な落とし穴を避けるためだ。0.09‾0.0\overline{9} と 0.1000…0.1000\ldots は同じ実数を表す。{1,2}\{1,2\} から取った桁はこうした衝突を引き起こさないので、ss は一意な十進展開を持ち、証明に穴がない。

この論法の構造は カントールの定理 の対角集合とまったく同じだ。nn 番目の候補と nn 番目の座標で食い違うオブジェクトを定義する、というわけだ。あちらでは集合への帰属を反転させ、こちらでは十進の桁を変える。同じ自己破壊的なロジックが両方に効いている。

連続体の濃度

R\mathbb{R} が非可算であることがわかったので、その濃度に名前をつけよう。連続体の濃度 (cardinality of the continuum) を次のように定義する。

c  ≔  ∣R∣.\mathfrak{c} \;\coloneqq\; |\mathbb{R}|.

カントールの定理 では ∣P(N)∣=∣R∣|\mathcal{P}(\mathbb{N})| = |\mathbb{R}| を約束した。証明には両方向への単射が必要で、それらを全単射に変換する定理を使う。

冪集合を実数直線に埋め込む

冪集合 のチェックポイントでは、各部分集合 S⊆NS \subseteq \mathbb{N} が特性関数 (characteristic function) χS ⁣:N→{0,1}\chi_S \colon \mathbb{N} \to \{0,1\}（χS(n)=1\chi_S(n) = 1 iff n∈Sn \in S）を持つことを示した。これを使って次のように定義する。

φ(S)  ≔  ∑n∈S3−(n+1).\varphi(S) \;\coloneqq\; \sum_{n \in S} 3^{-(n+1)}.

φ(S)\varphi(S) は3進（三進法）展開が 0 . χS(0)  χS(1)  χS(2)  ⋯0\,.\,\chi_S(0)\;\chi_S(1)\;\chi_S(2)\;\cdots（3進の桁として 0 と 1 のみを使う）となる実数だ。φ\varphi が単射であることを確認するには、S≠TS \neq T として kk を対称差 S△TS \mathbin{\triangle} T の最小インデックスとする――たとえば k∈Sk \in S かつ k∉Tk \notin T とすると、

φ(S)−φ(T)  ≥  3−(k+1)−∑n>k3−(n+1)  =  3−(k+1)−12⋅3k+1  =  12⋅3k+1  >  0,\varphi(S) - \varphi(T) \;\geq\; 3^{-(k+1)} - \sum_{n > k} 3^{-(n+1)} \;=\; 3^{-(k+1)} - \frac{1}{2 \cdot 3^{k+1}} \;=\; \frac{1}{2 \cdot 3^{k+1}} \;>\; 0,

よって φ(S)≠φ(T)\varphi(S) \neq \varphi(T) だ。単射 φ ⁣:P(N)↪[0,1]\varphi \colon \mathcal{P}(\mathbb{N}) \hookrightarrow [0,1] から次が得られる。

∣P(N)∣  ≤  ∣[0,1]∣  =  c.|\mathcal{P}(\mathbb{N})| \;\leq\; |[0,1]| \;=\; \mathfrak{c}.

実数直線を冪集合に埋め込む

(0,1)(0,1) の各 xx は 2進展開 x=0 . b0  b1  b2  ⋯x = 0\,.\,b_0\;b_1\;b_2\;\cdots（bn∈{0,1}b_n \in \{0,1\}）を持つ。（二進有理数 (dyadic rationals)――m/2km/2^k の形のもの――は2進展開が二つあるが、各自において非終端のものを選ぶ。）次のように定義する。

ψ(x)  ≔  {n∈N∣bn=1}.\psi(x) \;\coloneqq\; \{n \in \mathbb{N} \mid b_n = 1\}.

(0,1)(0,1) の異なる2つの実数は選んだ展開が異なるので、ある位置で異なり、異なる部分集合に写される。単射 ψ ⁣:(0,1)↪P(N)\psi \colon (0,1) \hookrightarrow \mathcal{P}(\mathbb{N}) から次が得られる。

c  =  ∣(0,1)∣  ≤  ∣P(N)∣.\mathfrak{c} \;=\; |(0,1)| \;\leq\; |\mathcal{P}(\mathbb{N})|.

カントール–ベルンシュタイン–シュレーダーの定理を適用する

両方向の単射が得られた。次の定理――ここでは証明なしで述べる――がそれらを全単射に変換する。

定理（カントール–ベルンシュタイン–シュレーダー (Cantor–Bernstein–Schroeder)）。 単射 A↪BA \hookrightarrow B と B↪AB \hookrightarrow A が存在するならば、∣A∣=∣B∣|A| = |B| である。

∣P(N)∣≤c|\mathcal{P}(\mathbb{N})| \leq \mathfrak{c} と c≤∣P(N)∣\mathfrak{c} \leq |\mathcal{P}(\mathbb{N})| を証する φ\varphi と ψ\psi にこれを適用すると、

∣P(N)∣  =  ∣R∣  =  c.(2)|\mathcal{P}(\mathbb{N})| \;=\; |\mathbb{R}| \;=\; \mathfrak{c}. \tag{2}

これが カントールの定理 で約束した等式だ――自然数の冪集合は実数直線とまったく同じ大きさを持つ。

記法 2ℵ02^{\aleph_0} について。 自然数の濃度を ℵ0≔∣N∣\aleph_0 \coloneqq |\mathbb{N}| と書く。冪集合 のチェックポイントでは有限集合について ∣P(A)∣=2∣A∣|\mathcal{P}(A)| = 2^{|A|} を確立した。同じ指数記法が無限基数にも拡張され、∣P(N)∣=2ℵ0|\mathcal{P}(\mathbb{N})| = 2^{\aleph_0} となる。すると式 (2)(2) は次のように読める。

c  =  2ℵ0,\mathfrak{c} \;=\; 2^{\aleph_0},

有限の公式の気持ちのいいこだまだ。

よく知られた集合の多くが同じ非可算の大きさを持つ

R\mathbb{R} だけでなく、すでに知っている多くの集合が濃度 c\mathfrak{c} を持つ。

集合理由
(0,1)(0,1)x↦tan⁡(π(x−12))x \mapsto \tan(\pi(x - \tfrac{1}{2})) が全単射 (0,1)→R(0,1) \to \mathbb{R} を与える
[0,1][0,1]R\mathbb{R} との間に単射を両方向に作り、カントール–ベルンシュタイン–シュレーダーで等号を得る
R\mathbb{R}c\mathfrak{c} の定義
Rn\mathbb{R}^n（任意の n≥1n \geq 1）nn 座標の十進桁をインターリーブして1つの実数にエンコードできる
C\mathbb{C}C≅R2\mathbb{C} \cong \mathbb{R}^2 なので $
P(N)\mathcal{P}(\mathbb{N})式 (2)(2)

印象的な教訓がある。次元を増やしても、複素数に移行しても、N\mathbb{N} の冪集合を取っても、濃度は c\mathfrak{c} を超えない。

連続体の先の階層

カントールの定理 は R\mathbb{R} を含む任意の集合に適用できる。式 (2)(2) から出発して各ステップで ∣⋅∣<∣P(⋅)∣|\cdot| < |\mathcal{P}(\cdot)| を適用すると、狭義単調増加な列が得られる。

∣N∣  <  ∣R∣  =  ∣P(N)∣  <  ∣P(R)∣  <  ∣P(P(R))∣  <  ⋯|\mathbb{N}| \;<\; |\mathbb{R}| \;=\; |\mathcal{P}(\mathbb{N})| \;<\; |\mathcal{P}(\mathbb{R})| \;<\; \bigl|\mathcal{P}(\mathcal{P}(\mathbb{R}))\bigr| \;<\; \cdots

最大の濃度は存在しない。冪集合操作は常に真に大きな無限を生み出すので、無限は無数に異なる大きさで存在する。

連続体仮説

自然な疑問が生まれる。濃度が ∣N∣|\mathbb{N}| と ∣R∣|\mathbb{R}| の間に厳密にある集合 AA は存在するのだろうか？　これが連続体仮説 (Continuum Hypothesis, CH) だ。

連続体仮説。 ∣N∣<∣A∣<∣R∣|\mathbb{N}| < |A| < |\mathbb{R}| を満たす集合 AA は存在しない。

CH は ZFC――集合論の標準公理系――から独立していることがわかっている。ゲーデル (Gödel, 1940) は CH を仮定しても ZFC と矛盾しないことを証明し、コーエン (Cohen, 1963) は CH の否定を仮定しても矛盾しないことを証明した。ZFC の公理だけからは CH を証明することも否定することもできない。これは、標準的な基礎論の中で決定不能であることが証明された、重要な数学的命題の最初の画期的な例のひとつだ。

まとめ

  • 集合が非可算であるとは、無限であり N\mathbb{N} との全単射が存在しないことだ――リスト a0,a1,a2,…a_0, a_1, a_2, \ldots でその集合を列挙し尽くすことはできない。
  • カントールの対角線論法を十進展開に適用すると、(0,1)(0,1)――したがって R\mathbb{R}――が非可算であることが証明される。規則 (1)(1) で定義した対角実数 ss は、各 rnr_n と位置 nn で異なるので、いかなるリストの試みも打ち破る。
  • 対角線のアイデアは カントールの定理 を映している。すべてのリスト候補と対応する座標で食い違うオブジェクトを設計する――あちらでは集合への帰属ビット、こちらでは十進の桁。
  • 連続体の濃度は c≔∣R∣=2ℵ0\mathfrak{c} \coloneqq |\mathbb{R}| = 2^{\aleph_0}（ℵ0≔∣N∣\aleph_0 \coloneqq |\mathbb{N}|）だ。
  • 2つの単射――三進エンコードによる P(N)↪[0,1]\mathcal{P}(\mathbb{N}) \hookrightarrow [0,1] と2進展開による (0,1)↪P(N)(0,1) \hookrightarrow \mathcal{P}(\mathbb{N})――がカントール–ベルンシュタイン–シュレーダーの定理と組み合わさって ∣P(N)∣=c|\mathcal{P}(\mathbb{N})| = \mathfrak{c}（式 (2)(2)）を確立する。
  • 多くの集合が濃度 c\mathfrak{c} を共有する。(0,1)(0,1)、[0,1][0,1]、任意の n≥1n \geq 1 に対する Rn\mathbb{R}^n、C\mathbb{C}、P(N)\mathcal{P}(\mathbb{N}) がそれだ。
  • カントールの定理を R\mathbb{R} に適用すると塔が続く。∣N∣<∣R∣<∣P(R)∣<∣P(P(R))∣<⋯|\mathbb{N}| < |\mathbb{R}| < |\mathcal{P}(\mathbb{R})| < |\mathcal{P}(\mathcal{P}(\mathbb{R}))| < \cdots であり、無限の濃度は無数に存在する。
  • 連続体仮説――∣N∣|\mathbb{N}| と ∣R∣|\mathbb{R}| の間に厳密な濃度を持つ集合が存在するかどうか――はゲーデル (1940) とコーエン (1963) が証明したように ZFC から独立している。