カントールは次のような論法を生み出した。P(X)はXの冪集合とする。

カントールの対角線論法（定理1）

集合Xに対して

写像φ:X→P(X)を一つ定める。この時、Y={x∈X|x∉φ(x)}⊂Xととると、φ(t)=Yとなるt∈Xは存在しない。

[証明]

φ(t)=Yとなるtをとれたと仮定しよう。背理法によって証明する。t∈Yとする。この時、t∉φ(t)である。よって、φ(t)=Yに矛盾する。

t∉Yとする。t∈φ(t)である。これはφ(t)=Yに矛盾する。よってこのようなtは取れないことがわかった◽︎

適当な写像φ:X→P(X)に対して、φ(x)がxを含まないようなxを取るとその集合はφの行き先にないということである。さらにわかりやすくいう。Xの元にx∈φ(x)であれば1、x∉φ(x)であれば0を割り振る。この時、Yを0が割り振られた元の集まりであるとする。この時、Y=φ(t)となるようなtには0でも1でもない値が割り振られてしまう。

この論法は意味がわかりやすい言い換えが存在する。

対角線論法の言い換え（定理2）

Xを集合として、

任意に写像Φ:X×X→{0, 1}を構成する。この時、写像r:{0, 1}→{0, 1}をr(0)=1, r(1)=0によって定義する。この時、xを固定すると、φ(x, ・)は一変数写像になる。G(x)=r⚪︎φ(x, x)によって定義する。この時、φ(t, x)=G(x)となるようなtは存在しない。

この言い換えの方が、どこが対角線なのかがわかりやすい。集合Xの元のマス目を作って、φ(x, y)を対応するところにおいていく。

例：X={1, 2, 3}の時

　1　2　3　列番号

1 1　0　0

2 0　0　1

3 1　1　1

行

番

号

この時、このマス目から対角線の成分、要するにφ(x, x)をとり、それの0, 1を反転させる。これをψとおいてやると、ψ(1)=0, ψ(2)=1, ψ(3)=0。さて、この対応というのは、このマス目を行番号を固定して列番号を変数とする写像が行番号の分だけ提示されているものとしてみなすと、このψ(x)という写像は、このマス目で提示されたどの写像とも一致しない。

実際に、Φ1={(1, 1), (2, 0), (3, 0)}, φ2={(1, 0), (2, 0), (3, 1)}, φ3={(1, 1), (2, 1), (3, 1)}であり、どれもψ={(1, 0), (2, 1), (3, 0)}とは一致していないことがわかる。

なぜこのようなことが起こるのかというと、これは簡単で、そうなるようにψを定めてやったからである。ψは必ずφtとx=tを代入したときに異なる。

なぜならそのようになるようにビットを反転させたからである。

定理1と定理2が同値であることを示そう。

[証明]

定理2が成り立つのなら定理1が成り立つことを示す。次の事実を用いる：

P(X)と、写像φ:X→{0, 1}を全て集めたものの集合は、自然に同一視できる。

これは、P(X)の元にxが含まれているかいないか、と、φ(x)が1か0かが自然と同じもののようにできることからわかる。

さて、任意に写像ψ:X→P(X)をとる。この時、ψ(x)は上の事実によって、X→{0, 1}への写像と同一視できる。さて、この時、ψ(x)を写像として見て、もう一つ変数yを加えると、

ψ(x)(y):X→{0, 1}となる。さて、ここで、G(x)=r⚪︎ψ(x)(x)と定義する。

この時、ψ(t)(x)=G(x)となるtは存在しない。Gが表すようなP(X)の元について考える。

ψ(x)は{x∈X|x∈ψ(x)}であるから、r⚪︎ψ(x)の表す、要するにGの表す集合というのは、{x∈X|x∉ψ(x)}ということになる。これについて、ψ(t)=Gとなるtが存在しないことがわかっているので、これによって定理1は示された。

定理1が成り立つなら定理2が成り立つことは、上の議論と逆向きの方向に辿っていけば良いだけであるので割愛する◽︎

さて、対角線論法の直接的な帰結として次の定理が得られる。

1.カントールの定理

|X|<|P(X)|

2.n<2^n n≧0, n∈N

[証明]

1→2であるので、1を示す。X≦P(X)はi(x)={x}となるように単射写像i:X→P(X)を定めてやれば十分に示せている。XからP(X)への全射が存在しないことを示す。これは対角線論法の1から明らかである。

対角線論法はこれだけではない。次のような証明の仕方も対角線論法と呼ばれる。

アスコリ・アルツェラの定理

どのような実数の有界な閉区間[a, b]を定義域とする関数列f_nに対しても、f_nが一様有界で同程度連続であれば、一様収束する部分列が存在する。

[証明]

対角線論法の部分：

x_i∈Qを適当に取っておく。f_n(x_1)が収束するような部分列f_n_1(x)をとる。これはf_nの一様有界性とボルツァーノ・ワイエルシュトラスの定理より言うことができる。

この部分列に対して、f_n_1(x_2)が収束するような部分列f_n_2(x)をとる。これを繰り返していくことで、f_n_n(x)を得る。f_n_n(x_k), 1≦k≦n を列として取ると、これはf_n_nの構成法を見ればわかるように収束する。（収束する列の部分列は同じ値に収束することから言える。）

つまり、n個の互いに異なる有理数{x_i}を取ってきても、関数列f_nには、どの有理数x_iを代入しても極限が存在するような部分列が存在する。

対角線論法ではない部分：

よって、有理数の稠密性によって、[a, b]に対して、端点aに十分近い有理数q_1と、q_1より大きく、q_1に十分近い有理数q_2......そして、有理数q_(n-1)とbに十分近い有理数q_nを取れる。（注：これは要するに、n個の有理数で、[a, b]を十分に細かく分割することを表している。）

よって、先ほどのf_n_n(x)をf_nの部分列としてとる。すると、f_n_nはどのように実数x∈[a, b]をとっても、それに十分近く、q_i≦x<q_(i+1)となるq_iたちを取れるので、同程度連続性より、f_n_n(x)は一様に収束することがわかる。（注：この議論はε-δ論法をきちんと用いることで厳密にできる。）

つまり、有限回の操作によって、f_m_nを作り、ここから、m=nとなるものを抽出する、対角線論法擬きも対角線論法と呼ばれるのである。

ここで、この対角線論法もどきでは、背理法を用いていないということに注意しよう。対角線論法はある種不可能性を示すものだが、これは対角線成分から部分列を抽出するとうまくいくという論法である。考えとして一致しているのは、同じ集合Xの直積の対角線部分を取り出していることのみであることに注意したい。