_{x_{0}}(x_{0})}となり矛盾する。_{x_{0}}=g}より。第二の等号はgの定義より。集合2Xは、Xから{0,1}への関数全体の集合と自然に同一視できる[2]事がよく知られているが、「関数による表現」の対角線論法と「集合による表現」の対角線論法はこの同一視を通して同値である事が証明できる。実際、ψを「集合による表現」で登場した関数とするとき、ψ(x)∈2XはXから{0,1}への関数とみなせる。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を対応させる関数とする事で、「関数による表現」の補題との同値性を証明できる。1]区間(=0以上1以下の実数全体の集合)への全単射が存在しない事を以下のように証明できる。後で見るように、この証明は暗に対角線論法を使っている。}への全単射が存在しない事を含意する。1]区間への全単射φが存在したとし、φ(i)をaiと書く事にする。}と番号づけする事ができた事になる。j}桁目をai,jとし[3]、biを¬ai,iとする。bを小数点展開が0.b1b2...となる実数とする。}のいずれとも異なる。実際iを任意に取るとき、aiのi桁目はai,iであるのに対し、bのi桁目は¬ai,iであるので、aiとbは異なる。}のいずれとも異なるので、矛盾。1]区間への全単射は存在しない。以上の論法は、行列A={ai,j}i,jに対して対角線論法の「行列による表現」を使ってベクトル{bi}={¬ai,i}がAのいずれの行とも異なる事を証明したものであると解釈できる。従って以上の論法は暗に対角線論法を使っている。詳細は「カントールの定理」を参照カントールの定理とは次のようなものである。定理Xを任意の集合とするとき、XからXの冪集合2Xへの全射が存在しない(従って特に全単射が存在しない)。Xの濃度より2Xの濃度のほうが真に大きい。これは以下のように対角線論法を用いて次のように示される。Xから2Xへの全射ψが存在したとする。(x)\}}により定義すると、対角線論法より、ψ(x)=Yとなるx∈Xは存在しない。これはψの全射性に反する。構成はラッセルのパラドックスで用いられる「自分自身を含まないような集合」と酷似していることに注意されたい。濃度が大きくなり矛盾を生じる(カントールのパラドックス)。「連続体仮説」を参照カントールの定理において、Xとして自然数の集合Nを考える。連続体濃度に等しいことが知られている。間に濃度が存在するのだろうか。存在しないという主張が連続体仮説と呼ばれるものである。これはヒルベルトの23の問題の第1問題として挙げられた。存在しないというのが、一般連続体仮説である。一般連続体仮説のZFからの無矛盾性をクルト・ゲーデルが、独立性を1963年にポール・コーエンがそれぞれ証明した。決定不能性も対角線論法で証明できる。(停止性問題の決定不能性が何かは停止性問題の項を参照)。以下簡単の為、プログラムの入力は全て自然数とする。}と自然に同一視できる。A(x)が停止すればφ(A,x)=1、そうでなければφ(A,x)=0。以下φ(A,x)の事をφA(x)と定義する。\{0,1\}}を、g(A)=¬φA(A)により定義する。すると対角線論法により、g=φMとなるMは存在しない。仮に停止性問題を常に正しく解くプログラムHが存在するとする。MとHの定義よりg(A)=φMが成立し、矛盾。したがって停止性問題を常に正しく解くプログラムは存在しない。停止性問題の決定不能性の証明に酷似している。したがってゲーデルの第一不完全性定理の証明も暗に対角線論法を利用している。時間階層定理の証明を停止性問題の決定不能性の証明の焼き直しとみなすことができる。W∈2Xに対し、その特性関数χWを対応させる事で同一視できる。{0,1}は、x∈WとなるときおよびそのときのみχW(x)=1となる関数。})為、本当はこの部分の証明はもう少し複雑になる。簡単の為その辺の事情は略する。3.0のもとで利用可能です。プライバシーデスクトップ。