カントールの対角線論法

カントールの対角線論法（カントールのたいかくせんろんぽう、英: Cantor's diagonal argument）は、数学における証明テクニック（背理法）の一つ。1891年にゲオルク・カントールによって非可算濃度を持つ集合の存在を示した論文^[1]の中で用いられたのが最初だとされている。その後対角線論法は、数学基礎論や計算機科学において写像やアルゴリズム等が存在しないことを示す為の代表的な手法の一つとなり、例えばゲーデルの不完全性定理、停止性問題の決定不能性、時間階層定理といった重要な定理の証明で使われている。

対角線論法

集合による表現

対角線論法とは、以下の補題を使って定理を証明する背理法のことである。

$X$ を集合とし、 $2^{X}$ を $X$ のべき集合とする。さらに $\psi$ を $X$ から $2^{X}$ への写像とする。 $X$ の部分集合 $Y$ を $Y=\{x\in X:x\notin \psi (x)\}$ により定義すると、 $\psi (x)=Y$ となる $x\in X$ は存在しない。

上の補題は以下のように示せる。 $\psi (x)=Y$ となる $x\in X$ が存在すると仮定したうえで $x$ が $Y$ の元であるか否かを考える。もし $x$ が $Y$ の元であれば $x\in Y=\psi (x)$ である。しかし $Y$ の定義より、 $Y$ は $x\notin \psi (x)$ を満たす $x$ の集合であるので、 $x\notin \psi (x)$ でなければならず、矛盾する。反対にもし $x$ が $Y$ の元でなければ $x\notin Y=\psi (x)$ であるが、 $Y$ の定義により、 $x\notin \psi (x)$ である $x$ は $Y$ の元でなければならず、やはり矛盾する。

関数による表現

以下の補題を使った論法も対角線論法と呼ばれる。後で見るように、実は以下の補題は前節で示した補題と同値である。

$X$ を集合とし、 $\phi :X\times X\rightarrow \{0,1\}$ を写像とする。 $\phi (x,y)$ を $\phi _{x}(y)$ と書くと、各 $x\in X$ に対し $\phi _{x}$ は $X$ から $\{0,1\}$ への写像である。 $g:X\rightarrow \{0,1\}$ を、 $g(x)=\neg \phi _{x}(x)$ により定義する。ここで、「 $\neg$ 」は0と1を反転する写像。すなわち、 $\neg {0}=1\quad$ 、 $\neg {1}=0\quad$ 。このとき、 $\phi _{x_{0}}=g$ となる $x_{0}\in X$ は存在しない。

実際、もしそのような $x_{0}\in X$ が存在すれば、 $\phi _{x_{0}}(x_{0})=g(x_{0})=\neg \phi _{x_{0}}(x_{0})$ となり矛盾する。第一の等号は $\phi _{x_{0}}=g$ より。第二の等号はgの定義より。

なお上の補題は $\phi$ の値域 $Z$ が {0,1} ではない場合にも一般化でき、 $\sigma :Z\rightarrow X$ を $\sigma (z)=z$ となる $z\in Z$ が存在しない写像とし、 $g(x)=\sigma \circ \phi _{x}(x)$ とすると、 $\phi _{x_{0}}=g$ となる $x_{0}\in X$ は存在しない。

べき集合2^Xは、Xから{0,1}への関数全体の集合と自然に同一視できる^{[注釈 1]}ことがよく知られているが、「関数による表現」の対角線論法と「集合による表現」の対角線論法はこの同一視を通して同値である事が証明できる。実際、ψを「集合による表現」で登場した関数とするとき、ψ(x)∈2^XはXから{0,1}への関数とみなせる。関数ψ(x)によるy∈Xの像をψ(x)(y)と書き、関数φ: X×X→{0,1}を、φ(x,y)=ψ(x)(y)として「関数による表現」の補題を使うことで、「集合による表現」の補題を証明できる。（逆もまた真。）

行列による表現

以下の補題を使った論法も対角線論法と呼ばれる。後で見るように、実は以下の補題は前節で示した補題と同値である。

Xを集合とし、{0,1}に値をとるX行X列の正方行列A={a_x,y}_x,y∈Xを考える。Aのx行目のなすベクトル{a_x,y}_y∈XをA_xと書く。行列Aの「対角線」{a_x,x}_x∈Xをビット反転させたベクトル{￢a_x,x}_x∈XをBとする。ここで「￢」は0と1を反転させる関数。このとき、任意のiに対し、B≠A_i。

実際Bの第i成分は￢a_x,xであるのに対し、A_xの第i成分はa_xであるので、B≠A_x。

ψ:X×X→{0,1}を(x,y)に対しa_x,yを対応させる関数とすることで、「関数による表現」の補題との同値性を証明できる。

論理式による表現

¬∃x∀y.(P(x,y)⇔¬P(y,y))　すなわち　∀x∃y.((P(x,y)∧P(y,y))∨(¬P(x,y)∧¬P(y,y)))

自然数の集合と[0, 1]区間の濃度の違い

自然数全体の集合 $\mathbb {N}$ から[0, 1]区間(=0以上1以下の実数全体の集合)への全単射が存在しないことを以下のように証明できる。後で見るように、この証明は暗に対角線論法を使っている。

なお、[0, 1]区間と実数全体の集合 $\mathbb {R}$ は濃度が等しいので、この事実は $\mathbb {N}$ から $\mathbb {R}$ への全単射が存在しないことを含意する。

さて、仮に $\mathbb {N}$ から[0, 1]区間への全単射φが存在したとし、φ(i)をa_iと書くことにする。すると[0, 1]区間の各元を $a_{1},a_{2},\cdots$ と番号づけすることができたことになる。

a_iを二進数展開したときの $j$ 桁目をa_i,jとし^{[注釈 2]}、b_iを￢a_i,iとする。

そしてbを小数点展開が0.b₁b₂…となる実数とする。このとき、bは $a_{1},a_{2},\cdots$ のいずれとも異なる。実際iを任意に取るとき、a_iのi桁目はa_i,iであるのに対し、bのi桁目は￢a_i,iであるので、a_iとbは異なる。

仮定より[0, 1]区間の全ての元は $a_{1},a_{2},\cdots$ と番号づけされているはずなのに、[0, 1]区間の元であるはずのbは $a_{1},a_{2},\cdots$ のいずれとも異なるので、矛盾。従って $\mathbb {N}$ から[0, 1]区間への全単射は存在しない。

なお、n桁に対応する元は $2^{n}$ 個存在するが、対角線論法においてはn桁に対して元の数をn個として議論していることには注意が必要である。

以上の論法は、行列A={a_i,j}_i,jに対して対角線論法の「行列による表現」を使ってベクトル{b_i}={￢a_i,i}がAのいずれの行とも異なることを証明したものであると解釈できる。従って以上の論法は暗に対角線論法を使っている。

カントールの定理

カントールの定理とは次のようなものである。

定理: Xを任意の集合とするとき、XからXの冪集合2^Xへの全射が存在しない（従って特に全単射が存在しない）。つまり、Xの濃度より2^Xの濃度のほうが真に大きい。

これは以下のように対角線論法を用いて次のように示される。

Xから2^Xへの全射ψが存在したとする。

Y=\{x\in X:x\notin \psi (x)\}

により定義すると、対角線論法より、ψ(x)=Yとなるx∈Xは存在しない。これはψの全射性に反する。

上の Y の構成はラッセルのパラドックスで用いられる「自分自身を含まないような集合」と酷似していることに注意されたい。 X を「全ての集合を含む集合」として同じことを行うと、2^X は X の部分集合でありながらしかも X より濃度が大きくなり矛盾を生じる（カントールのパラドックス）。したがって、(公理的集合論の立場では)「すべての集合を含む集合」は集合ではなく、真のクラスになる。

連続体仮説

カントールの定理において、Xとして自然数の集合Nを考える。この冪集合の濃度2^N は連続体濃度に等しいことが知られている。では、果たして可算濃度 |N| とその冪集合の濃度 2^N の間に濃度が存在するのだろうか。つまり

|N| < m < 2^N なる濃度 m は存在しない

という主張が連続体仮説と呼ばれるものである。これはヒルベルトの23の問題の第1問題として挙げられた。

またこれを一般化して、

無限濃度 n に対して、n < m < 2ⁿ なる m は存在しない

というのが、一般連続体仮説である。一般連続体仮説のZFからの無矛盾性をクルト・ゲーデルが、独立性を1963年にポール・コーエンがそれぞれ証明した。

停止性問題の決定不能性

停止性問題の決定不能性も対角線論法で証明できる。（停止性問題の決定不能性が何かは停止性問題の項を参照）。

以下簡単の為、プログラムの入力は全て自然数とする。プログラムは0と1からなる数字で書き表せるので、プログラム全体の集合と自然数全体の集合 $\mathbb {N}$ と自然に同一視できる。 ^{[注釈 3]} $\phi :\mathbb {N} \times \mathbb {N} \mapsto \{0,1\}$ を次のように定義する： A(x)が停止すればφ(A,x)=1、そうでなければφ(A,x)=0。

以下φ(A,x)のことをφ_A(x)と定義する。 $g:\mathbb {N} \mapsto \{0,1\}$ を、g(A)=￢φ_A(A)により定義する。すると対角線論法により、g=φ_MとなるMは存在しない。

さて、仮に停止性問題を常に正しく解くプログラムHが存在するとする。 M(A)を、H(A,A)=YESなら停止せず、H(A,A)=NOなら0を出力して停止するプログラムとすると、 MとHの定義よりg(A)=φ_Mが成立し、矛盾。したがって停止性問題を常に正しく解くプログラムは存在しない。

ゲーデルの第一不完全性定理の証明は停止性問題の決定不能性の証明に酷似している。したがってゲーデルの第一不完全性定理の証明も暗に対角線論法を利用している。

停止性問題の決定不能性を「有限時間」と「無限時間」という２つの時間階層の間の時間階層定理だと解釈すると、時間階層定理の証明を停止性問題の決定不能性の証明の焼き直しとみなすことができる。したがって時間階層定理の証明も対角線論法を使っていることが分かる。

脚注

[脚注の使い方]

注釈

^ W∈2^Xに対し、その特性関数χ_Wを対応させることで同一視できる。ここでχ_W: X → {0,1}は、x∈Wとなるときおよびそのときのみχ_W(x)=1となる関数。
^ $a_{i}$ の二進数展開が2つあることもある（例えば $0.1=0.01111\cdots$ ）為、本当はこの部分の証明はもう少し複雑になる。
^ 本当は $\mathbb {N}$ の中にはプログラムに対応していないものもあるが、簡単の為その辺の事情は略する。

出典

^ George Cantor (1891). Uber ein elementare Frage der Mannigfaltigkeitslehre. Deutsche Mathematiker-Vereinigung.

参考文献

Cantor's Diagonal Argument: カントールの証明の原文とその英訳