カントールの対角線論法
カントールの対角線論法(カントールのたいかくせんろんぽう、Cantor's diagonal argument)は、数学における証明テクニック(背理法)の一つ。1891年にゲオルク・カントールによって非可算濃度を持つ集合の存在を示した論文の中で用いられたのが最初だとされている。
その後対角線論法は、数学基礎論や計算機科学において写像やアルゴリズム等が存在しないことを示す為の代表的な手法の一つとなり、例えばゲーデルの不完全性定理、停止性問題の決定不能性、時間階層定理といった重要な定理の証明で使われている。
対角線論法とは、以下の補題を使って定理を証明する背理法のことである。
Xを集合とし、2XをXのべき集合とする。さらにψをXから2Xへの写像とする。Xの部分集合YをY=\{x\in X: x\notin\psi(x)\}により定義すると、ψ(x)=Yとなるx∈Xは存在しない。
上の補題は以下のように示せる。ψ(x)=Yとなるx∈Xが存在すると仮定したうえでxがYの元であるか否かを考える。もしxがYの元であればx∈Y=ψ(x)である。しかしYの定義より、Yはx\notin\psi(x)を満たすxの集合であるので、x\notin\psi(x)でなければならず、矛盾する。反対にもしxがYの元でなければx\notin Y=\psi(x)であるが、Yの定義により、x\notin\psi(x)であるxはYの元でなければならず、やはり矛盾する。
以下の補題を使った論法も対角線論法と呼ばれる。後で見るように、実は以下の補題は前節で示した補題と同値である。
X を集合とし、\phi : X \times X \rightarrow \{0,1\} を写像とする。 \phi(x,y) を \phi_{x}(y) と書くと、各 x \in X に対し\phi_{x} はX から \{0,1\} への写像である。g : X \rightarrow \{0, 1\} を、 g(x) = \neg \phi_{x}(x) により定義する。ここで、「 \neg 」は0と1を反転する写像。すなわち、 \neg{0} = 1\quad 、 \neg{1} = 0\quad 。このとき、 \phi_{x_0} = g となる x_0 \in X は存在しない。
実際、もしそのような x_{0} \in X が存在すれば、 \phi_{x_0}(x_0)=g(x_0)=\neg \phi_{x_0}(x_0) となり矛盾する。
第一の等号は \phi_{x_0}=g より。第二の等号はgの定義より。
なお上の補題は \phi の値域 Z が {0,1} ではない場合にも一般化でき、
\sigma : Z \rightarrow X を \sigma(z) = z となる z \in Z が存在しない写像とし、g(x)=\sigma\circ\phi_x(x) とすると、 \phi_{x_0}=g となる x_0 \in X は存在しない。
べき集合2Xは、Xから{0,1}への関数全体の集合と自然に同一視できることがよく知られているが、「関数による表現」の対角線論法と「集合による表現」の対角線論法はこの同一視を通して同値である事が証明できる。実際、ψを「集合による表現」で登場した関数とするとき、ψ(x)∈2XはXから{0,1}への関数とみなせる。関数ψ(x)によるy∈Xの像をψ(x)(y)と書き、関数φ: X×X→{0,1}を、φ(x,y)=ψ(x)(y)として「関数による表現」の補題を使うことで、「集合による表現」の補題を証明できる。(逆もまた真。)
以下の補題を使った論法も対角線論法と呼ばれる。後で見るように、実は以下の補題は前節で示した補題と同値である。
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}を(x,y)に対しax,yを対応させる関数とすることで、「関数による表現」の補題との同値性を証明できる。
¬∃x∀y.(P(x,y)⇔¬P(y,y)) すなわち ∀x∃y.((P(x,y)∧P(y,y))∨(¬P(x,y)∧¬P(y,y)))
自然数全体の集合\mathbb{N}から[0, 1]区間(=0以上1以下の実数全体の集合)への全単射が存在しないことを以下のように証明できる。後で見るように、この証明は暗に対角線論法を使っている。
なお、[0, 1]区間と実数全体の集合\mathbb{R}は濃度が等しいので、この事実は\mathbb{N}から\mathbb{R}への全単射が存在しないことを含意する。
さて、仮に\mathbb{N}から[0, 1]区間への全単射φが存在したとし、φ(i)をaiと書くことにする。すると[0, 1]区間の各元をa_{1}, a_{2}, \cdotsと番号づけすることができたことになる。
aiを二進数展開したときのj桁目をai,jとし、biを￢ai,iとする。
そしてbを小数点展開が0.b1b2…となる実数とする。このとき、bはa_{1}, a_{2}, \cdotsのいずれとも異なる。実際iを任意に取るとき、aiのi桁目はai,iであるのに対し、bのi桁目は￢ai,iであるので、aiとbは異なる。
仮定より[0, 1]区間の全ての元はa_{1}, a_{2}, \cdotsと番号づけされているはずなのに、[0, 1]区間の元であるはずのbはa_{1}, a_{2}, \cdotsのいずれとも異なるので、矛盾。
従って\mathbb{N}から[0, 1]区間への全単射は存在しない。
なお、n桁に対応する元は2^n個存在するが、対角線論法においてはn桁に対して元の数をn個として議論していることには注意が必要である。
以上の論法は、行列A={ai,j}i,jに対して対角線論法の「行列による表現」を使ってベクトル{bi}={￢ai,i}がAのいずれの行とも異なることを証明したものであると解釈できる。従って以上の論法は暗に対角線論法を使っている。
カントールの定理とは次のようなものである。
Xを任意の集合とするとき、XからXの冪集合2Xへの全射が存在しない(従って特に全単射が存在しない)。つまり、Xの濃度より2Xの濃度のほうが真に大きい。
これは以下のように対角線論法を用いて次のように示される。
Xから2Xへの全射ψが存在したとする。Y=\{x\in X: x\notin\psi(x)\}により定義すると、対角線論法より、ψ(x)=Yとなるx∈Xは存在しない。これはψの全射性に反する。
上の Y の構成はラッセルのパラドックスで用いられる「自分自身を含まないような集合」と酷似していることに注意されたい。
X を「全ての集合を含む集合」として同じことを行うと、2X は X の部分集合でありながらしかも X より濃度が大きくなり矛盾を生じる(カントールのパラドックス)。したがって、(公理的集合論の立場では)「すべての集合を含む集合」は集合ではなく、真のクラスになる。
カントールの定理において、Xとして自然数の集合Nを考える。この冪集合の濃度2N は連続体濃度に等しいことが知られている。では、果たして可算濃度 |N| とその冪集合の濃度 2N の間に濃度が存在するのだろうか。
|N| < m < 2N なる濃度 m は存在しない
という主張が連続体仮説と呼ばれるものである。これはヒルベルトの23の問題の第1問題として挙げられた。
またこれを一般化して、
無限濃度 n に対して、n < m < 2n なる m は存在しない
というのが、一般連続体仮説である。一般連続体仮説のZFからの無矛盾性をクルト・ゲーデルが、独立性を1963年にポール・コーエンがそれぞれ証明した。
停止性問題の決定不能性も対角線論法で証明できる。
(停止性問題の決定不能性が何かは停止性問題の項を参照)。
以下簡単の為、プログラムの入力は全て自然数とする。
プログラムは0と1からなる数字で書き表せるので、
プログラム全体の集合と自然数全体の集合\mathbb{N}と自然に同一視できる。
\phi:\mathbb{N} \times \mathbb{N} \mapsto \{0,1\}を次のように定義する:
A(x)が停止すればφ(A,x)=1、そうでなければφ(A,x)=0。
以下φ(A,x)のことをφA(x)と定義する。
g:\mathbb{N} \mapsto \{0,1\}を、g(A)=￢φA(A)により定義する。
すると対角線論法により、g=φMとなるMは存在しない。
さて、仮に停止性問題を常に正しく解くプログラムHが存在するとする。
M(A)を、H(A,A)=YESなら停止せず、H(A,A)=NOなら0を出力して停止するプログラムとすると、
MとHの定義よりg(A)=φMが成立し、矛盾。
したがって停止性問題を常に正しく解くプログラムは存在しない。
停止性問題の決定不能性の証明に酷似している。
したがってゲーデルの第一不完全性定理の証明も暗に対角線論法を利用している。
停止性問題の決定不能性を「有限時間」と「無限時間」という2つの時間階層の間の時間階層定理だと解釈すると、
時間階層定理の証明を停止性問題の決定不能性の証明の焼き直しとみなすことができる。
したがって時間階層定理の証明も対角線論法を使っていることが分かる。