カントールの対角線論法

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