カントールの対角線論法

カントールの対角線論法は、数学における証明テクニックの一つ。1891年にゲオルク・カントールによって非可算濃度を持つ集合の存在を示した論文の中で用いられたのが最初だとされている。 その後対角線論法は、数学基礎論や計算機科学において写像やアルゴリズム等が存在しないことを示す為の代表的な手法の一つとなり、例えばゲーデルの不完全性定理、停止性問題の決定不能性、時間階層定理といった重要な定理の証明で使われている。

1. 対角線論法
--------

1.1. 集合による表現
------------

対角線論法とは、以下の補題を使って定理を証明する背理法のことである。

を集合とし、をのべき集合とする。さらにをからへの写像とする。の部分集合をにより定義すると、となるは存在しない。上の補題は以下のように示せる。となるが存在すると仮定したうえでがの元であるか否かを考える。もしがの元であればである。しかしの定義より、はを満たすの集合であるので、でなければならず、矛盾する。反対にもしがの元でなければであるが、の定義により、であるはの元でなければならず、やはり矛盾する。

1.2. 関数による表現
------------

以下の補題を使った論法も対角線論法と呼ばれる。後で見るように、実は以下の補題は前節で示した補題と同値である。

を集合とし、 を写像とする。 を と書くと、各 に対し は から への写像である。 を、 により定義する。ここで、「 」は0と1を反転する写像。すなわち、 、 。このとき、 となる は存在しない。実際、もしそのような が存在すれば、 となり矛盾する。 第一の等号は より。第二の等号は//g//の定義より。

なお上の補題は の値域 が {0,1} ではない場合にも一般化でき、 を となる が存在しない写像とし、 とすると、 となる は存在しない。

べき集合2Xは、Xから{0,1}への関数全体の集合と自然に同一視できることがよく知られているが、「関数による表現」の対角線論法と「集合による表現」の対角線論法はこの同一視を通して同値である事が証明できる。実際、ψを「集合による表現」で登場した関数とするとき、ψ∈2XはXから{0,1}への関数とみなせる。関数ψによるy∈Xの像をψと書き、関数φ: X×X→{0,1}を、φ=ψとして「関数による表現」の補題を使うことで、「集合による表現」の補題を証明できる。

1.3. 行列による表現
------------

以下の補題を使った論法も対角線論法と呼ばれる。後で見るように、実は以下の補題は前節で示した補題と同値である。

Xを集合とし、{0,1}に値をとるX行X列の正方行列A={ax,y}x,y∈Xを考える。Aのx行目のなすベクトル{ax,y}y∈XをAxと書く。行列Aの「対角線」{ax,x}x∈Xをビット反転させたベクトル{￢ax,x}x∈XをBとする。ここで「￢」は0と1を反転させる関数。このとき、任意のiに対し、B≠Ai。実際Bの第i成分は￢ax,xであるのに対し、Axの第i成分はaxであるので、B≠Ax。

ψ:X×X→{0,1}をに対しax,yを対応させる関数とすることで、「関数による表現」の補題との同値性を証明できる。

1.4. 論理式による表現
-------------

¬∃x∀y.⇔¬P)　すなわち　∀x∃y.∧P)∨∧¬P))

2. 自然数の集合と[0, 1]区間の濃度の違い
------------------------

自然数全体の集合から[0, 1]区間への全単射が存在しないことを以下のように証明できる。後で見るように、この証明は暗に対角線論法を使っている。

なお、[0, 1]区間と実数全体の集合は濃度が等しいので、この事実はからへの全単射が存在しないことを含意する。

さて、仮にから[0, 1]区間への全単射φが存在したとし、φをaiと書くことにする。すると[0, 1]区間の各元をと番号づけすることができたことになる。

aiを二進数展開したときの桁目をai,jとし、biを￢ai,iとする。

そしてbを小数点展開が0.b1b2…となる実数とする。このとき、bはのいずれとも異なる。実際iを任意に取るとき、aiのi桁目はai,iであるのに対し、bのi桁目は￢ai,iであるので、aiとbは異なる。

仮定より[0, 1]区間の全ての元はと番号づけされているはずなのに、[0, 1]区間の元であるはずのbはのいずれとも異なるので、矛盾。 従ってから[0, 1]区間への全単射は存在しない。

なお、n桁に対応する元は個存在するが、対角線論法においてはn桁に対して元の数をn個として議論していることには注意が必要である。

以上の論法は、行列A={ai,j}i,jに対して対角線論法の「行列による表現」を使ってベクトル{bi}={￢ai,i}がAのいずれの行とも異なることを証明したものであると解釈できる。従って以上の論法は暗に対角線論法を使っている。

3. カントールの定理
-----------

カントールの定理とは次のようなものである。

定理//X//を任意の集合とするとき、//X//から//X//の冪集合2//X//への全射が存在しない。つまり、//X//の濃度より2//X//の濃度のほうが真に大きい。これは以下のように対角線論法を用いて次のように示される。

Xから2Xへの全射ψが存在したとする。により定義すると、対角線論法より、ψ=Yとなるx∈Xは存在しない。これはψの全射性に反する。上の //Y// の構成はラッセルのパラドックスで用いられる「自分自身を含まないような集合」と酷似していることに注意されたい。//X// を「全ての集合を含む集合」として同じことを行うと、2//X// は //X// の部分集合でありながらしかも //X// より濃度が大きくなり矛盾を生じる。したがって、「すべての集合を含む集合」は集合ではなく、真のクラスになる。

3.1. 連続体仮説
----------

カントールの定理において、//X//として自然数の集合Nを考える。この冪集合の濃度2N は連続体濃度に等しいことが知られている。では、果たして可算濃度 |N| とその冪集合の濃度 2N の間に濃度が存在するのだろうか。 つまり

|N| < //m// < 2N なる濃度 //m// は存在しないという主張が連続体仮説と呼ばれるものである。これはヒルベルトの23の問題の第1問題として挙げられた。

またこれを一般化して、

無限濃度 //n// に対して、//n// < //m// < 2//n// なる //m// は存在しないというのが、一般連続体仮説である。一般連続体仮説のZFからの無矛盾性をクルト・ゲーデルが、独立性を1963年にポール・コーエンがそれぞれ証明した。

4. 停止性問題の決定不能性
--------------

停止性問題の決定不能性も対角線論法で証明できる。 。

以下簡単の為、プログラムの入力は全て自然数とする。 プログラムは0と1からなる数字で書き表せるので、 プログラム全体の集合と自然数全体の集合と自然に同一視できる。を次のように定義する：//A//が停止すればφ=1、そうでなければφ=0。

以下φのことをφ//A//と定義する。を、g=￢φ//A//により定義する。 すると対角線論法により、//g//=φ//M//となる//M//は存在しない。

さて、仮に停止性問題を常に正しく解くプログラム//H//が存在するとする。//M//を、//H//=YESなら停止せず、//H//=NOなら0を出力して停止するプログラムとすると、//M//と//H//の定義より//g//=φ//M//が成立し、矛盾。 したがって停止性問題を常に正しく解くプログラムは存在しない。

ゲーデルの第一不完全性定理の証明は 停止性問題の決定不能性の証明に酷似している。 したがってゲーデルの第一不完全性定理の証明も暗に対角線論法を利用している。

停止性問題の決定不能性を「有限時間」と「無限時間」という２つの時間階層の間の時間階層定理だと解釈すると、 時間階層定理の証明を停止性問題の決定不能性の証明の焼き直しとみなすことができる。 したがって時間階層定理の証明も対角線論法を使っていることが分かる。

5. 脚注
-----

5.1. 注釈
-------

5.2. 出典
-------

6. 参考文献
-------

[1]: カントールの証明の原文とその英訳

7. 関連項目
-------

濃度
停止性問題
パラドックス