カントールの対角線論法

　カントールの対角線論法は、例えば自然数集合と区間$[0,1)$の実数全体の集合の全要素を1対1対応させることができるかを確かめるときにもちいる証明方法のことです。

自然数集合と区間$[0,1)$の実数全体の集合の全要素を1対1対応させることができるか？についてはおよそ以下のような論理の展開をおこないます。

　自然数と区間$[0,1)$内の実数をすべて1対1対応させることができる規則が存在すると仮定します。

\begin{array}{c}1&0.15353\cdots\\ 2&0.80505\cdots\\ 3&0.74788\cdots\\ 4&0.22402\cdots\\ 5&0.53391\cdots\\ \vdots&\vdots\end{array}

すると、上のような実数をすべて小数で表したリストをつくることができます。このとき、実数の小数表示は一意であるとし、$0.1$や$0.8125$のように桁数が有限な実数は後の桁に$0$を追加して無限小数として表すことにします。

このリストの上から$n$番目の実数の小数第$n$位を取り出して$0.$の後に一列に並べ、小数第$n$位がリストの$n$番目と一致する実数$x$をつくります。

この実数$x$の小数点以下の各桁に対し、例えば上図に従いその桁の数字から矢印の先の数字に置き換えるという変換をおこないます。

変換後の実数$x'$（例の場合は$x'=0.21812\cdots$）はリストの上から$n$番目の実数と小数第$n$位の数字が異なっており、実数の小数表示が一意であるために真となる命題「等しい実数の小数表示ならばすべての同じ位の数字は一致する」の対偶「1つでも同じ位の数字が一致しなければ異なる実数の小数表示である」よりリスト内のどの実数とも等しくない実数ということができます。

　実数$x'$は区間$[0,1)$内の実数であるにもかかわらずリストにない（自然数と対応していない）ということは、自然数と区間$[0,1)$内の実数をすべて1対1対応することができる規則が存在するという仮定と矛盾しています。

したがって、仮定は誤りで自然数と区間$[0,1)$内の実数をすべて1対1対応させることはできず、実数$x'$のように自然数と対応させることができない実数が存在することがわかります。

このようにリストの対角線上に着目して論理を進めていく方法であるため対角線論法と呼ばれています。