読む編集履歴表示

カントールの対角線論法

ウィキペディアから、無料の百科事典

カントールの対角線論法（カントールのたいかくせんろんぽう、英: 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$ かつ $\neg {1}=0$ 。このとき、 $\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\}$ への関数全体の集合と自然に同一視できることがよく知られているが、「関数による表現」の対角線論法と「集合による表現」の対角線論法はこの同一視を通して同値である事が証明できる。実際、 $\psi$ を「集合による表現」で登場した関数とするとき、 $\psi (x)\in 2^{X}$ は $X$ から $\{0,1\}$ への関数とみなせる。関数 $\psi (x)$ による $y\in X$ の像を $\psi (x)(y)$ と書き、関数 $\psi :X\times X\rightarrow \{0,1\}$ を、 $\psi (x,y)=\psi (x)(y)$ として「関数による表現」の補題を使うことで、「集合による表現」の補題を証明できる（逆もまた真）。

行列による表現

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

$X$ を集合とし、 $\{0,1\}$ に値をとる $X$ 行 $X$ 列の正方行列 $A=\{a_{x,y}\}_{x,y\in X}$ を考える。 $A$ の $x$ 行目のなすベクトル $\{a_{x,y}\}_{x,y\in X}$ を $A_{x}$ と書く。行列 $A$ の「対角線」ベクトル $\{a_{x,x}\}_{x\in X}$ をビット反転させたベクトル $\{\neg a_{x,x}\}_{x\in X}$ を $B$ とする。ここで「 $\neg$ 」は0と1を反転させる関数。このとき、任意の $i$ に対し、 $B\neq A_{i}$ 。

実際 $B$ の第 $i$ 成分は $\neg a_{x,x}$ であるのに対し、 $A_{x}$ の第 $i$ 成分は $a_{x}$ であるので、 $B\neq A_{x}$ 。

$\phi :X\times X\rightarrow \{0,1\}$ を $(x,y)$ に対し $\neg a_{x,y}$ を対応させる関数とすることで、「関数による表現」の補題との同値性を証明できる。

論理式による表現

$\neg \exists x\forall y.(P(x,y)\Leftrightarrow \neg P(y,y)$ すなわち $(P(x,y)\land P(y,y))\lor (\neg P(x,y)\land \neg P(y,y)$

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

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

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

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

$a_{i}$ を二進数展開したときの $j$ 桁目を $a_{i,j}$ とし^{[注釈 1]}、 $b_{i}$ を $\neg a_{i,i}$ と表記する。

そしてbを小数点展開が $0.b_{1}b_{2}\cdots$ となる実数とする。このとき、 $b$ は $a_{i}$ の $i$ 桁目は $a_{i,i}$ であるのに対し、 $b$ の $i$ 桁目は $\neg 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}=\{\neg a_{i,j}\}$ が $A$ のいずれの行とも異なることを証明したものであると解釈できる。従って以上の論法は暗に対角線論法を使っている。

カントールの定理

→詳細は「カントールの定理」を参照

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

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

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

X

から

2^{X}

への全射

\psi

が存在したと仮定する。

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

により定義すると、対角線論法より、

\psi (x)=Y

となる

x\in X

は存在しない。これは

\psi

の全射性に反する。

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

連続体仮説

→詳細は「連続体仮説」を参照

カントールの定理において、 $X$ として自然数の集合 $\mathbb {N}$ を考える。この冪集合の濃度 $2^{\mathbb {N} }$ は連続体濃度に等しいことが知られている。では、果たして可算濃度 $|\mathbb {N} |$ とその冪集合の濃度 $|2^{\mathbb {N} }|$ の間に濃度が存在するのだろうか。つまり $|\mathbb {N} |<m<|2^{\mathbb {N} }|$ を満たす濃度 $m$ は存在しないという主張が連続体仮説と呼ばれるものである。これはヒルベルトの23の問題の第1問題として挙げられた。

またこれを一般化して、

任意の無限濃度

n

に対して、

n<m<2^{n}

を満たす

m

は存在しない

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

停止性問題の決定不能性

停止性問題の決定不能性も対角線論法で証明できる。

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

以下 $\phi (A,x)$ を $\phi _{A}(x)$ と表記する。 $g:\mathbb {N} \mapsto \{0,1\}$ を、 $g(A)=\neg \phi _{A}(x)$ により定義する。すると対角線論法により、 $g=\phi _{M}$ となる $M$ は存在しない。

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