カントールの対角線論法（カントールのたいかくせんろんぽう、英: 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} より。