8.1 無限濃度

十九世紀の終わりごろ、Fourierフーリエ 級数の収束を研究していた数学者 Georgゲオルグ Cantorカントール は、ある級数が「収束しない点は無限に存在するものの、ほとんどの場合で収束する」という事実を発見した。この事実を表明するため、無限集合の大きさを比較する方法が必要になった。無限集合の大きさを比較するために、Cantor は写像則 (定理 4.5.4) を無限集合に拡張した: 全単射が存在する二つの集合は同じ「大きさ」を持つと定めた。同様に、無限集合 \(A\), \(B\) が \(A \mathrel{\text{\small surj}} B\) (定義 4.5.2) を満たすとき \(A\) は \(B\) 以上の「大きさ」を持つとした。このとき、\(A\) から \(B\) への全射が存在しないとき \(A\) が \(B\) より「真に小さい (strictly smaller)」と言える。この関係は \(A \mathrel{\text{strict}} B\) と表記される:

有限集合を考えるとき、この「真に小さい」は単に要素が少ないことを意味する。これは写像則 (定理 4.5.4) から直ちに従う:

証明

■

その後 Cantor は Fourier 級数の研究を離れ、こういったアイデアに基づいて無限の大きさに関する理論を構築することに労力を注いだ。彼の理論は現在までに数学基礎論や情報科学で大きな結果を生んでいる。しかし、当時の Cantor は自身の研究によって多くの敵を生んだ: 当時の典型的な数学者は奇抜な無限集合の概念を「Cantorカントール の楽園 (Cantor's paradise)」と呼び、そんなものに何の意味があるのかと軽蔑の目を向けた。

Cantor のアイデアが持つ巧妙な特徴として、無限集合の「大きさ」を実際には定義しないことがある ── 「大きさ」の比較方法だけが定義される。

注意: 無限集合の「大きさ」を表す概念は本書でこれまでに定義していないし、今後も定義しない。そういった概念を定義するには順序数 (ordinal) と呼ばれる特別な整列性を持った無限集合の定義が必要になる。順序数の理論を学ぶには集合理論を本書が必要とするより深く理解しなければならないので、ここでは定義しないで進むことにする。集合間の関係 \(\text{surj}\) と \(\text{bij}\) がそれぞれ「 \(\cdots\) 以上に大きい」と「 \(\cdots\) と同じ大きさ」を意味することだけが利用される。

ただし、注意が必要な点がもう一つある: \(\text{surj}\) が「 \(\cdots\) 以上に大きい」を意味する、そして \(\text{bij}\) が「 \(\cdots\) と同じ大きさ」を意味する、と言ったのは比喩である。読者の想像する通り、有限集合を考えるとき成り立つ \(\text{surj}\) と \(\text{bij}\) に関する性質の多くは無限集合でも成り立つ。しかし、無限集合では成り立たない重要な性質もある ── その例はすぐに示される。そのため、この比喩は注意して使う必要がある: 無限集合を扱うときは、実際に証明するまで「 \(\cdots\) 以上に大きい」という文章から期待される性質を \(\text{surj}\) が含意すると思ってはいけない。

まずは有限集合と無限集合の両方で成り立つ \(\text{surj}\), \(\text{inj}\), \(\text{bij}\) に関する性質を見よう:

\(1.\) は、関係 \(R\) が「外 \(\leq 1\)」かつ「内 \(\geq 1\)」という全射関数の特徴を持つとき \(R^{-1}\) は「外 \(\geq\) \(1\)」かつ「内 \(\leq 1\)」という全域単射関数の特徴を持つことから分かる (「外 \(\leq 1\)」といった用語については定義 4.4.2 を参照)。\(2.\) は、全域関数の合成が全域関数である事実から分かる。\(\text{3.}\) と \(\text{4.}\) は、「\(R\) が全単射」と「\(R\) と \(R^{-1}\) が全射」が同値である事実と前半二つの結果から従う。これらの厳密な証明は練習問題 (問題 4.22) とする。

有限集合だけではなく無限集合でも成り立つ馴染み深い性質は他にもある。ただし、次に示す性質を証明するには深い洞察が必要になる:

言い換えれば、Schröder-Bernstein の定理は \(A\) が「\(B\) 以上の大きさ」であり、かつ \(B\) が「\(A\) 以上の大きさ」であるとき、\(A\) は「\(B\) と同じ大きさ」だと主張している。このように表現すると、この定理は成立して当然だから証明の必要もないと思うかもしれない。しかし、それは間違いである。\(A\) と \(B\) が無限集合のとき、この定理が主張する性質は自明でない。つまり、全射関数 \(f\colon A \to B\) と \(g\colon B \to A\) (いずれも全単射とは限らない) が存在したとしても、全単射 \(e\colon A \to B\) が存在するかどうかは全く分からない。この定理の証明では、\(f\) と \(g\) を利用して \(e\) を実際に構築する。詳細は練習問題 (問題 8.14) とする。

集合に関するもう一つの馴染み深い性質として、二つの集合 \(A\), \(B\) に対して「\(A\) が \(B\) 以上に大きい」と「\(B\) が \(A\) 以上に大きい」のいずれかが成り立つことがある。この性質は有限集合に対しては写像則から自明に分かる。無限集合に対しても成り立つものの、その成立が自明だと考えるのはここでも間違いである。

定理 8.1.5 を使うと、有限集合と無限集合の両方で成り立つ性質がさらにもう一つ証明できる:

証明 背理法で示す。関係 \(\text{(8.1)}\) と \(\operatorname{\text{\footnotesize NOT}} (A \mathrel{\text{strict}} C)\) の成立を仮定する。\(\operatorname{\text{\footnotesize NOT}} (A \mathrel{\text{strict}} C)\) は \(A \mathrel{\text{\small surj}} C\) を意味する。\(B \mathrel{\text{strict}} C \) と定理 8.1.5 から \(C \mathrel{\text{\small surj}} B\) を得る。つまり次の関係が分かった:

これと補題 8.1.3 の \(\text{2.}\) より \(A \mathrel{\text{\small surj}} B\) と結論できる。しかし、これは \(A \mathrel{\text{strict}} B\) と矛盾する。 ■

定理 8.1.5 の証明は省略する。本書で必要になるより厳密な集合理論の取り扱い ── 先ほど触れた順序数の定義など ── が必要になるためである。ただ、定理 8.1.5 を利用するのは補題 8.1.6 の証明だけなので、証明を示さないことには目をつぶってほしい。

8.1.1 異なる無限

無限集合では成り立たない有限集合の性質の一つに「新しい要素を追加すると大きくなる」がある。つまり、\(A\) が有限集合で \(b \notin A\) なら \(|A \cup \left\{ b \right\}| = |A| + 1\) が成り立つ。言い換えれば \(A\) と \(A \cup \left\{ b \right\}\) は同じ大きさを持たない。しかし \(A\) が無限集合だと、この二つの集合は「同じ大きさ」となる！

証明 先述の通り、\(A\) が有限なら \(A\) と \(A \cup \left\{ b \right\}\) は異なる大きさを持つ。よって後は、\(A\) が無限のとき \(A\) と \(A \cup \left\{ b \right\}\) が同じ「大きさ」を持つと示せばよい。

\(A\) は無限集合なので、\(A\) は間違いなく \(1\) 個以上の要素を持つ。そこで \(A\) の要素を一つ取って \(a_{0}\) とする。\(A\) は無限集合なので、\(A\) は \(2\) 個以上の要素を持つ。よって \(a_{0}\) でない \(A\) の要素が存在するので、それを \(a_{1}\) とする。同様の議論を続ければ、\(A\) の異なる要素からなる無限列 \(a_{0}\), \(a_{1}\), \(\ldots\), \(a_{n}\), \(\ldots\) が存在すると結論できる。この無限列を使えば、全単射 \(e\colon A \cup \left\{ b \right\} \to A\) を簡単に構築できる:

■

8.1.2 加算集合

集合 \(C\) が加算 (countable) とは、全ての要素を一列に並べられることを言う。つまり、\(C\) の全ての要素からなる次の形をした列が存在するなら \(C\) は加算である:

この列で要素が重複しないと仮定すれば、条件「\(C\) の全ての要素を一列に並べられる」は形式的に「\(f(i) ::= c_{i}\) という規則で定まる関数 \(f\colon \mathbb{N} \to C\) が全単射」と表現できる:

上記の形をした列が重複を許すなら、有限集合も加算の定義を満たす。例えば三要素集合 \(\left\{ 2,4,6 \right\}\) の要素は次のように並べられる:

この単純な観察からは、有限集合と無限集合を区別しない加算の別定義が得られる。つまり、集合 \(C\) が加算とは、\(C\) の全要素が含まれる次の形の列が存在することを意味する:

ただし、この列の要素は重複しても構わないとする。さらに正確に言えば、次のように定義できる:

加算の定義から分かる補題を示す:

証明は練習問題 (問題 8.15) とする。

最も基礎的な加算無限集合は \(\mathbb{N}\) そのものである。また、整数全体の集合 \(\mathbb{Z}\) も加算無限である。これは全ての整数を一列に並べられる事実から分かる:

この例では、列 \(\text{(8.2)}\) の第 \(n\) 要素は簡単な式で記述できる。\(f(n)\) が列 \(\text{(8.2)}\) の第 \(n\) 要素であるような全単射 \(f\colon \mathbb{N} \to \mathbb{Z}\) は次の規則で定義できる:

また、非負整数の組全体の集合を一列に並べる方法も存在するので、\(\mathbb{N} \times \mathbb{N}\) は加算無限集合である (問題 8.25)。この事実を使うと、非負有理数全体の集合 \(\mathbb{Q}^{\geq 0}\) が加算無限集合だと示せる。これは意外な事実かもしれない ── 有理数は任意の隣り合う整数の間にある隙間をギッシリ埋める (そして「隣り合う整数」は無限にある) 上に、任意の二つの有理数の間には異なる有理数が常に存在する。ここから、全ての有理数を一列に並べるなど不可能だと思っても不思議ではない。しかし問題 8.13 を解けば可能だと分かる。一般に、加算集合は和集合 (問題 8.24) とデカルト積 (問題 8.25) の演算について閉じている。ここから様々な集合が加算だと示せる:

補題 8.1.7 の証明を少しだけ変更すると、加算無限集合は無限集合の中で最も「小さい」と示せる。つまり:

証明は練習問題 (問題 8.12) とする。

無限集合に新しい要素を \(1\) 個の要素を加えても「大きさ」は変化しないので、任意の有限個の新しい要素を加えても無限集合の「大きさ」は変化しない: その有限集合の要素を一つずつ加えればよい。さらに強いことも言える: 無限集合に加算無限個の新しい要素を加えたとしても、加える前の無限集合と同じ「大きさ」の集合にしかならない (問題 8.18)。

ところで、無限集合に任意の有限個の新しい要素を加えた集合から元の無限集合への全単射が存在すると知って「では無限個の新しい要素を加えた場合でも同じことが言えるのか」と納得するのはよくある間違いである。特定の操作を任意の有限回実行できるからといって、その操作を無限回実行できるとは一般に限らない。例えば \(3\) に \(1\) を足す操作は任意回実行できる: 結果は \(3\) 以上の整数となる。しかし、\(3\) に \(1\) を無限回足した結果は存在しない。

8.1.3 冪集合は真に大きい

Cantor は「大きさ」の異なる無限集合が存在するという驚くべき事実を発見した。具体的には、任意の集合 \(A\) に対して \(\operatorname{pow}(A)\) は \(A\) より「真に大きい」ことを彼は証明した。つまり:

証明 \(A\) が \(\operatorname{pow}(A)\) より真に小さいと示すには、任意の関数 \(g \colon A \to \operatorname{pow}(A)\) が全射でないと示せばよい。終域 (定義 4.4.1) が非空集合である任意の部分関数は全域関数に拡張できる (理由を納得しておくこと) ので、\(g\) は全域関数だと仮定する。

\(g\) が全射でないと示すには、\(g\) の値域に含まれない非空部分集合 \(A_{g} \subseteq A\) を見つければよい。任意の要素 \(a \in A\) を取ったとき、値 \(g(a) \subseteq A\) が \(a\) を含むかどうかを考えることができる。\(A_{g}\) を次のように定める:

この \(A_{g}\) は well-defined な \(A\) の部分集合である。よって \(A_{g}\) は \(\operatorname{pow}(A)\) に属する。しかし \(A_{g}\) は \(g\) の値域に含まれない: \(g\) の値域に含まれる任意の集合 \(g(a)\) に対して、\(A_{g}\) と \(g(a)\) は \(a\) を含むかどうかが異なる。

より正確な議論を示す。背理法を用いる。\(A_{g}\) が \(g\) の値域に含まれると仮定する。このとき、ある \(a_{0} \in A\) で次の等式が成り立つ:

一方で \(A_{g}\) の定義より、全ての \(a \in A\) で次の関係が成り立つ:

\(a = a_{0}\) とすれば次の矛盾を得る:

よって \(A\) の冪集合には \(g\) の値域に含まれない集合 \(A_{g}\) が存在する。すなわち \(g\) は全射でない。 ■

Cantor の定理からは次の系が直ちに分かる:

証明 補題 8.1.9 より、「集合 \(U\) が非加算」と「\(\mathbb{N} \mathrel{\text{strict}} U\)」は同値である。 ■

定理 4.5.5 の証明で利用した \(n\) 要素集合の部分集合全体の集合から長さ \(n\) のビット列全体の集合 \(\left\{ 0, 1 \right\}^{n}\) への全単射と同じように、加算無限集合の部分集合全体から無限長ビット列全体の集合 \(\left\{ 0, 1 \right\}^{\omega }\) への全単射が存在する。つまり:

ここから次の事実が分かる:

加算集合と非加算集合の例

加算および非加算な集合がいくつか分かれば、補題 8.1.3 を使って様々な集合が加算または非加算だと証明できる。特に、この補題から分かる次の系が利用できる:

例えば、無限長ビット列全体の集合 \(\left\{ 0, 1 \right\}^{\omega}\) が非加算という先ほど示した事実を使えば、次の系の証明は難しくない:

この系を証明するために、実数の (無限) 十進展開を考える:

任意の実数 \(r\) を十進展開したときの小数点以下の部分をビット列として読むことで、\(r\) を無限長ビット列 \(b(r)\) に対応付けることを考える。\(r\) の十進展開が \(0\) と \(1\) 以外の桁を一つでも含むなら \(b(r)\) は未定義とする。例えば次の関係が成り立つ:

この \(b\) は実数から無限長ビット列への関数である¹。\(b\) は全域ではないものの、全射であることは容易に分かる。よって次の関係を得る:

これと系 8.1.16 の \(\text{(a)}\) から \(\mathbb{R}\) が非加算だと分かる。

別の例として、次の事実を証明してみよう:

この系を証明するために、非負整数の素因数分解を考える:

素因数分解の \(0\) でない指数を並べることで、非負整数 \(n\) から正整数の有限列 \(e(n)\) を作成できる。例えば:

この \(e\) は \(\mathbb{N}\) から \((\mathbb{Z}^{+})^{\ast}\) への関数である。\(e\) は全ての正整数に対して定義され、明らかに全射である。よって次の関係を得る:

これと系 8.1.16 の \(\text{(b)}\) から、正整数の有限列全体の集合は加算だと分かる。

さらに大きい無限

無限には「大きさ」には多くの種類がある。例えば、非負整数全体の集合 \(\mathbb{N}\) に繰り返し \(\operatorname{pow}\) を適用した結果は次の関係を満たす:

Cantor の定理 (定理 8.1.12) より、ここに並んだ任意の集合は一つ前の集合より真に大きい。しかし、これで終わりではない: これらの集合全ての和集合は、どの集合よりも真に大きいと示せる (問題 8.16)。同じ手続きを繰り返せば、より「大きい」無限を無限に生み出すことができる。

8.1.4 対角線論法

定理 8.1.12 の証明で使われた議論の流れを「対角線論法 (diagonal argument)」と呼ぶ。なぜなら、無限に大きい表を使って直感的に分かりやすく書き換えると、反例となる集合が対角線を利用して構築されるからである。「対角線」が分かりやすいように書き換えた議論を次に示す。\(\mathbb{N}\) から \(\left\{ 0, 1 \right\}^{\omega}\) への全単射が存在すると仮定する。このとき、無限長ビット列を何らかの順番で一列に並べることができる。\(\left\{ 0, 1 \right\}^{\omega}\) の任意の要素は、この列を最初から探していけば有限ステップで見つかる: 任意の非負整数は \(0\) から数えていけば見つかるのと同じである。この想像上の列は縦および横に無限に広がる次のような表で表せる:

この表を利用すると、全ての無限長ビット列が載っているはずの表に載っていない無限長ビット列が存在すると示せる。対角線上にあるビットに注目する:

次の部分が「対角線」論法と呼ばれる理由である: 対角線上にあるビットからなる列 \(\color{blue}{D}\) を構築する:

\(D\) の各桁の \({\color{blue}{0}}\) と \({\color{blue}{1}}\) を反転させた列を \({\color{red}{C}}\) とする:

このとき \(A_{n}\) の第 \(n\) 要素が \({\color{blue}{1}}\) のとき \({\color{red}{C}}\) の第 \(n\) 要素は \({\color{red}{0}}\) になり、逆も成り立つ。ここから \({\color{red}{C}}\) と \(A_{n}\) は異なると分かる。つまり任意の \(n\) に対して、\({\color{red}{C}}\) と \(A_{n}\) は少なくとも \(1\) 個の要素が異なる。よって \(\left\{ 0, 1 \right\}^{\omega}\) の要素 \({\color{red}{C}}\) は上述の表に含まれない ── 表には抜けがある！

対角線に並ぶ要素の列から構築した \({\color{red}{C}}\) は、定理 8.1.12 の証明で利用した集合 \(\left\{ a \in A \; | \; a \notin g(a) \right\}\) に対応する。両方とも非加算無限集合の加算部分集合を使って定義され、自身がその部分集合に含まれないという性質を持つ。そこから、任意の加算部分集合が全体の非加算集合より真に小さいことが証明される。