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

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

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} の元であるか否かを考える。もし x {\displaystyle x} が Y {\displaystyle Y} の元であれば x ∈ Y = ψ ( x ) {\displaystyle x\in Y=\psi (x)} である。しかし Y {\displaystyle Y} の定義より、 Y {\displaystyle Y} は x ∉ ψ ( x ) {\displaystyle x\notin \psi (x)} を満たす x {\displaystyle x} の集合であるので、 x ∉ ψ ( x ) {\displaystyle x\notin \psi (x)} でなければならず、矛盾する。反対にもし x {\displaystyle x} が Y {\displaystyle Y} の元でなければ x ∉ Y = ψ ( x ) {\displaystyle x\notin Y=\psi (x)} であるが、 Y {\displaystyle Y} の定義により、 x ∉ ψ ( x ) {\displaystyle x\notin \psi (x)} である x {\displaystyle x} は Y {\displaystyle Y} の元でなければならず、やはり矛盾する。
関数による表現

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

X {\displaystyle X} を集合とし、 ϕ : X × X → { 0 , 1 } {\displaystyle \phi :X\times X\rightarrow \{0,1\}} を写像とする。 ϕ ( x , y ) {\displaystyle \phi (x,y)} を ϕ x ( y ) {\displaystyle \phi _{x}(y)} と書くと、各 x ∈ X {\displaystyle x\in X} に対し ϕ x {\displaystyle \phi _{x}} は X {\displaystyle X} から { 0 , 1 } {\displaystyle \{0,1\}} への写像である。 g : X → { 0 , 1 } {\displaystyle g:X\rightarrow \{0,1\}} を、 g ( x ) = ¬ ϕ x ( x ) {\displaystyle g(x)=\neg \phi _{x}(x)} により定義する。ここで、「 ¬ {\displaystyle \neg } 」は0と1を反転する写像。すなわち、 ¬ 0 = 1 {\displaystyle \neg {0}=1\quad } 、 ¬ 1 = 0 {\displaystyle \neg {1}=0\quad } 。このとき、 ϕ x 0 = g {\displaystyle \phi _{x_{0}}=g} となる x 0 ∈ X {\displaystyle x_{0}\in X} は存在しない。

実際、もしそのような x 0 ∈ X {\displaystyle x_{0}\in X} が存在すれば、 ϕ x 0 ( x 0 ) = g ( x 0 ) = ¬ ϕ x 0 ( x 0 ) {\displaystyle \phi _{x_{0}}(x_{0})=g(x_{0})=\neg \phi _{x_{0}}(x_{0})} となり矛盾する。第一の等号は ϕ x 0 = g {\displaystyle \phi _{x_{0}}=g} より。第二の等号はgの定義より。

なお上の補題は ϕ {\displaystyle \phi } の値域 Z {\displaystyle Z} が {0,1} ではない場合にも一般化でき、 σ : Z → X {\displaystyle \sigma :Z\rightarrow X} を σ ( z ) = z {\displaystyle \sigma (z)=z} となる z ∈ Z {\displaystyle z\in Z} が存在しない写像とし、 g ( x ) = σ ∘ ϕ x ( x ) {\displaystyle g(x)=\sigma \circ \phi _{x}(x)} とすると、 ϕ x 0 = g {\displaystyle \phi _{x_{0}}=g} となる x 0 ∈ X {\displaystyle x_{0}\in X} は存在しない。

べき集合2Xは、Xから{0,1}への関数全体の集合と自然に同一視できる[注釈 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)))
自然数の集合と[0, 1]区間の濃度の違い

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

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

さて、仮に N {\displaystyle \mathbb {N} } から[0, 1]区間への全単射φが存在したとし、φ(i)をaiと書くことにする。すると[0, 1]区間の各元を a 1 , a 2 , ⋯ {\displaystyle a_{1},a_{2},\cdots } と番号づけすることができたことになる。

aiを二進数展開したときの j {\displaystyle j} 桁目をai,jとし[注釈 2]、biを¬ai,iとする。

そしてbを小数点展開が0.b1b2…となる実数とする。このとき、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のいずれの行とも異なることを証明したものであると解釈できる。従って以上の論法は暗に対角線論法を使っている。
カントールの定理詳細は「カントールの定理」を参照