カントールの対角線論法
対角線論法とは、以下の補題を使って定理を証明する背理法のことである。
X {\displaystyle X} を集合とし、 2 X {\displaystyle 2^{X}} を X {\displaystyle X} のべき集合とする。さらに ψ {\displaystyle \psi } を X {\displaystyle X} から 2 X {\displaystyle 2^{X}} への写像とする。 X {\displaystyle X} の部分集合 Y {\displaystyle Y} を Y = { x ∈ X : x ∉ ψ ( x ) } {\displaystyle Y=\{x\in X:x\notin \psi (x)\}} により定義すると、 ψ ( x ) = Y {\displaystyle \psi (x)=Y} となる x ∈ X {\displaystyle x\in X} は存在しない。
上の補題は以下のように示せる。 ψ ( x ) = Y {\displaystyle \psi (x)=Y} となる x ∈ X {\displaystyle x\in X} が存在すると仮定したうえで x {\displaystyle x} が Y {\displaystyle Y} の元であるか否かを考える。
カントールの対角線論法(カントールのたいかくせんろんぽう、英: Cantor's diagonal argument)は、数学における証明テクニック(背理法)の一つ。1891年にゲオルク・カントールによって非可算濃度を持つ集合の存在を示した論文の中で用いられたのが最初だとされている。 その後対角線論法は、数学基礎論や計算機科学において写像やアルゴリズム等が存在しないことを示す為の代表的な手法の一つとなり、例えばゲーデルの不完全性定理、停止性問題の決定不能性、時間階層定理といった重要な定理の証明で使われている。
すると対角線論法により、g=φMとなるMは存在しない。
さて、仮に停止性問題を常に正しく解くプログラムHが存在するとする。 M(A)を、H(A,A)=YESなら停止せず、H(A,A)=NOなら0を出力して停止するプログラムとすると、 MとHの定義よりg(A)=φMが成立し、矛盾。 したがって停止性問題を常に正しく解くプログラムは存在しない。
ゲーデルの第一不完全性定理の証明は 停止性問題の決定不能性の証明に酷似している。 したがってゲーデルの第一不完全性定理の証明も暗に対角線論法を利用している。
停止性問題の決定不能性を「有限時間」と「無限時間」という2つの時間階層の間の時間階層定理だと解釈すると、 時間階層定理の証明を停止性問題の決定不能性の証明の焼き直しとみなすことができる。 したがって時間階層定理の証明も対角線論法を使っていることが分かる。
このとき、bは a 1 , a 2 , ⋯ {\displaystyle a_{1},a_{2},\cdots } のいずれとも異なる。実際iを任意に取るとき、aiのi桁目はai,iであるのに対し、bのi桁目は¬ai,iであるので、aiとbは異なる。
仮定より[0, 1]区間の全ての元は a 1 , a 2 , ⋯ {\displaystyle a_{1},a_{2},\cdots } と番号づけされているはずなのに、[0, 1]区間の元であるはずのbは a 1 , a 2 , ⋯ {\displaystyle a_{1},a_{2},\cdots } のいずれとも異なるので、矛盾。 従って N {\displaystyle \mathbb {N} } から[0, 1]区間への全単射は存在しない。
なお、n桁に対応する元は 2 n {\displaystyle 2^{n}} 個存在するが、対角線論法においてはn桁に対して元の数をn個として議論していることには注意が必要である。
以上の論法は、行列A={ai,j}i,jに対して対角線論法の「行列による表現」を使ってベクトル{bi}={¬ai,i}がAのいずれの行とも異なることを証明したものであると解釈できる。従って以上の論法は暗に対角線論法を使っている。