カントールの対角線論法（カントールのたいかくせんろんぽう）は、数学における証明テクニック（背理法）の一つ。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 は存在しない。べき集合2は、Xから{0,1}への関数全体の集合と自然に同一視できる事がよく知られているが、「関数による表現」の対角線論法と「集合による表現」の対角線論法はこの同一視を通して同値である事が証明できる。実際、ψを「集合による表現」で登場した関数とするとき、ψ(x)∈2はXから{0,1}への関数とみなせる。関数ψ(x)によるy∈Xの像をψ(x)(y)と書き、関数φ: X×X→{0,1}を、φ(x,y)=ψ(x)(y)として「関数による表現」の補題を使う事で、「集合による表現」の補題を証明できる。（逆もまた真。）以下の補題を使った論法も対角線論法と呼ばれる。後で見るように、実は以下の補題は前節で示した補題と同値である。実際Bの第i成分は￢aであるのに対し、Aの第i成分はaであるので、B≠A。ψ:X×X→{0,1}を(x,y)に対しaを対応させる関数とする事で、「関数による表現」の補題との同値性を証明できる。自然数全体の集合formula_32から[0, 1]区間(=0以上1以下の実数全体の集合)への全単射が存在しない事を以下のように証明できる。後で見るように、この証明は暗に対角線論法を使っている。なお、[0, 1]区間と実数全体の集合formula_33は濃度が等しいので、この事実はformula_32からformula_33への全単射が存在しない事を含意する。さて、仮にformula_32から[0, 1]区間への全単射φが存在したとし、φ(i)をaと書く事にする。すると[0, 1]区間の各元をformula_37と番号づけする事ができた事になる。aを二進数展開したときのformula_38桁目をaとし、bを￢aとする。そしてbを小数点展開が0.bb…となる実数とする。このとき、bはformula_37のいずれとも異なる。実際iを任意に取るとき、aのi桁目はaであるのに対し、bのi桁目は￢aであるので、aとbは異なる。仮定より[0, 1]区間の全ての元はformula_37と番号づけされているはずなのに、[0, 1]区間の元であるはずのbはformula_37のいずれとも異なるので、矛盾。従ってformula_32から[0, 1]区間への全単射は存在しない。以上の論法は、行列A={a}に対して対角線論法の「行列による表現」を使ってベクトル{b}={￢a}がAのいずれの行とも異なる事を証明したものであると解釈できる。従って以上の論法は暗に対角線論法を使っている。カントールの定理とは次のようなものである。これは以下のように対角線論法を用いて次のように示される。上の "Y" の構成はラッセルのパラドックスで用いられる「自分自身を含まないような集合」と酷似していることに注意されたい。"X" を「全ての集合を含む集合」として同じことを行うと、2 は "X" の部分集合でありながらしかも "X" より濃度が大きくなり矛盾を生じる（カントールのパラドックス）。したがって、(公理的集合論の立場では)「すべての集合を含む集合」は集合ではなく、クラスになる。カントールの定理において、"X"として自然数の集合Nを考える。この冪集合の濃度2 は連続体濃度に等しいことが知られている。では、果たして可算濃度 |N| とその冪集合の濃度 2 の間に濃度が存在するのだろうか。つまりという主張が連続体仮説と呼ばれるものである。これはヒルベルトの23の問題の第1問題として挙げられた。またこれを一般化して、というのが、一般連続体仮説である。一般連続体仮説のZFからの無矛盾性をクルト・ゲーデルが、独立性を1963年にポール・コーエンがそれぞれ証明した。停止性問題の決定不能性も対角線論法で証明できる。（停止性問題の決定不能性が何かは停止性問題の項を参照）。以下簡単の為、プログラムの入力は全て自然数とする。プログラムは0と1からなる数字で書き表せるので、プログラム全体の集合と自然数全体の集合formula_32と自然に同一視できる。formula_45を次のように定義する："A"("x")が停止すればφ("A

出典:wikipedia