サムネイル|対角線論法の概要 カントールの対角線論法（カントールのたいかくせんろんぽう、）は、数学における証明テクニック（背理法）の一つ。1891年にゲオルク・カントールによって非可算濃度を持つ集合の存在を示した論文の中で用いられたのが最初だとされている。 その後対角線論法は、数学基礎論や計算機科学において写像やアルゴリズム等が存在しないことを示す為の代表的な手法の一つとなり、例えばゲーデルの不完全性定理、停止性問題の決定不能性、時間階層定理といった重要な定理の証明で使われている。
対角線論法 集合による表現 対角線論法とは、以下の補題を使って定理を証明する背理法のことである。
を集合とし、をのべき集合とする。さらにをからへの写像とする。の部分集合をにより定義すると、となるは存在しない。
上の補題は以下のように示せる。となるが存在すると仮定したうえでがの元であるか否かを考える。もしがの元であればである。しかしの定義より、はを満たすの集合であるので、でなければならず、矛盾する。反対にもしがの元でなければであるが、の定義により、であるはの元でなければならず、やはり矛盾する。
関数による表現 以下の補題を使った論法も対角線論法と呼ばれる。後で見るように、実は以下の補題は前節で示した補題と同値である。
を集合とし、 を写像とする。 を と書くと、各 に対し は から への写像である。 を、 により定義する。ここで、「 」は0と1を反転する写像。すなわち、 かつ。このとき、 となる は存在しない。
実際、もしそのような が存在すれば、 となり矛盾する。 第一の等号は より従う。第二の等号はの定義より。
なお上の補題は の値域 がではない場合にも一般化でき、 を となる が存在しない写像とし、 とすると、 となる は存在しない。
べき集合は、からへの関数全体の集合と自然に同一視できることがよく知られているが、「関数による表現」の対角線論法と「集合による表現」の対角線論法はこの同一視を通して同値である事が証明できる。実際、を「集合による表現」で登場した関数とするとき、はからへの関数とみなせる。関数によるの像をと書き、関数を、として「関数による表現」の補題を使うことで、「集合による表現」の補題を証明できる。（逆もまた真。）
行列による表現 以下の補題を使った論法も対角線論法と呼ばれる。後で見るように、実は以下の補題は前節で示した補題と同値である。
を集合とし、に値をとる行列の正方行列を考える。の行目のなすベクトルをと書く。行列の「対角線」ベクトルをビット反転させたベクトルをとする。ここで「」は0と1を反転させる関数。このとき、任意のに対し、。
実際の第成分はであるのに対し、の第成分はであるので、。
をに対しを対応させる関数とすることで、「関数による表現」の補題との同値性を証明できる。
論理式による表現 すなわち
自然数の集合と[0, 1]区間の濃度の違い 自然数全体の集合から区間(0以上1以下の実数全体の集合)への全単射が存在しないことを以下のように証明できる。後で見るように、この証明は暗に対角線論法を使っている。
なお、区間と実数全体の集合は濃度が等しいので、この事実はからへの全単射が存在しないことを含意する。
さて、仮にから区間への全単射が存在すると仮定とし、をと書くことにする。すると区間の各元をと番号づけすることができたことになる。
を二進数展開したときの桁目をとしの二進数展開が2つあることもある（例えば）為、本当はこの部分の証明はもう少し複雑になる。、をと表記する。
そしてbを小数点展開がとなる実数とする。このとき、はの桁目はであるのに対し、の桁目はであるので、とは異なる。
仮定より区間の全ての元はと番号づけされているはずなのに、区間の元であるはずのはのいずれとも異なるので、矛盾。 従ってから区間への全単射は存在しない。
なお、桁に対応する元は個存在するが、対角線論法においては桁に対して元の数を個として議論していることには注意が必要である。
以上の論法は、行列に対して対角線論法の「行列による表現」を使ってベクトルがのいずれの行とも異なることを証明したものであると解釈できる。従って以上の論法は暗に対角線論法を使っている。
カントールの定理
カントールの定理とは次のようなものである。
定理 を任意の集合とするとき、からの冪集合への全射が存在しない（従って特に全単射が存在しない）。つまり、の濃度よりの濃度のほうが真に大きい。
これは以下のように対角線論法を用いて次のように示される。
からへの全射が存在したと仮定する。により定義すると、対角線論法より、となるは存在しない。これはの全射性に反する。
上の の構成はラッセルのパラドックスで用いられる「自分自身を含まないような集合」と酷似していることに注意されたい。 を「全ての集合を含む集合」として同じことを行うと、 は の部分集合でありながらしかも より濃度が大きくなり矛盾を生じる（カントールのパラドックス）。したがって、(公理的集合論の立場では)「すべての集合を含む集合」は集合ではなく、真のクラスになる。
連続体仮説
カントールの定理において、として自然数の集合を考える。この冪集合の濃度 は連続体濃度に等しいことが知られている。では、果たして可算濃度とその冪集合の濃度 の間に濃度が存在するのだろうか。 つまり を満たす濃度 は存在しない という主張が連続体仮説と呼ばれるものである。これはヒルベルトの23の問題の第1問題として挙げられた。
またこれを一般化して、 任意の無限濃度 に対して、を満たすは存在しない と主張するのが一般連続体仮説である。一般連続体仮説のZFからの無矛盾性をクルト・ゲーデルが、ZFCからの独立性を1963年にポール・コーエンがそれぞれ証明した。
停止性問題の決定不能性 停止性問題の決定不能性も対角線論法で証明できる。 （停止性問題の決定不能性が何かは停止性問題の項を参照）。
以下簡単の為、プログラムの入力は全て自然数とする。 プログラムは0と1からなる数字で書き表せるので、 プログラム全体の集合と自然数全体の集合と自然に同一視できる。 本当はの中にはプログラムに対応していないものもあるが、 簡単の為その辺の事情は略する。 を次のように定義する： が停止すれば。そうでなければ。
以下をと表記する。 を、により定義する。 すると対角線論法により、となるは存在しない。
さて、仮に停止性問題を常に正しく解くプログラムが存在するとする。 を、なら停止せず、なら0を出力して停止するプログラムとすると、 との定義よりが成立し、矛盾。 したがって停止性問題を常に正しく解くプログラムは存在しない。
ゲーデルの第一不完全性定理の証明は 停止性問題の決定不能性の証明に酷似している。 したがってゲーデルの第一不完全性定理の証明も暗に対角線論法を利用している。
停止性問題の決定不能性を「有限時間」と「無限時間」という２つの時間階層の間の時間階層定理だと解釈すると、 時間階層定理の証明を停止性問題の決定不能性の証明の焼き直しとみなすことができる。 したがって時間階層定理の証明も対角線論法を使っていることが分かる。
脚注
注釈
出典
参考文献 Cantor's Diagonal Argument: カントールの証明の原文とその英訳
関連項目 濃度 停止性問題 パラドックス