カントールの対角線論法

出典: フリー百科事典『ウィキペディア（Wikipedia）』

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

[編集] 対角線論法

対角線論法とは、陰に陽に以下の補題を使って定理を証明する背理法の事で、例えば写像やアルゴリズム等の非存在性を示すのに使われる。

$X$ を集合とし、 $\phi : X \times X \rightarrow \{0,1\}$ を写像とする。 $φ(x, y)$ を $φ x (y)$ と書くと、各 $x \in X$ に対し $φ 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の定義より。

この補題を使う事で深遠な数学的事実をいくつも導く事ができる。「対角線論法」という名前の由来は、 $φ x (y)$ を $X \times X$ の「対角線」 $y = x$ 上に制限した写像 $φ x (x)$ を考える事から。

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

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

自然数全体の集合 $\mathbb{N}$ から[0, 1]区間(=0以上1以下の実数全体の集合)への全単射が存在しない事を対角線論法で証明できる。 [0, 1]区間と実数全体の集合 $\mathbb{R}$ は濃度が等しいので、この事実は $\mathbb{N}$ から $\mathbb{R}$ への全単射が存在しない事を含意する。

さて、仮に $\mathbb{N}$ から[0, 1]区間への全単射が存在したとしよう。すると[0, 1]区間の各元を $a_{1}, a_{2}, \cdots$ と番号づけする事ができる。

各 $x \in \mathbb{N}$ に対し $\phi_x : \mathbb{N} \rightarrow [0, 1]$ を、 $y \in \mathbb{N}$ に $a x$ の二進数展開の $y$ 桁目を対応させる写像とする。 ^[2]

さらに $g:\mathbb{N} \rightarrow \{0, 1\}$ を $g(x) = \neg \phi_x(x)$ によって定義する。すると対角線論法により、 $φ x = g$ となる $x \in \mathbb{N}$ は存在しない。

$b \in [0, 1]$ を、 $b$ の二進数展開の $x$ 桁目が $g (x)$ である小数とする。 $b$ は[0, 1]区間の元であるので、 $b = a_{x_0}$ を満たす $x 0$ が存在する。

しかしg(x₀)=bの二進数展開のx₀桁目 = $a_{x_0}$ の二進数展開のx₀桁目 = $\phi_{x_0}(x_0)$ となり矛盾する。

[編集] 集合とそのべき集合の濃度

Xを任意の集合とするとき、XからXの冪集合2^Xへの全単射が存在しない事（カントールの定理、カントール、1890年）を対角線論法で証明できる。

Xから{0,1}への写像全体の集合をFとすると、Fと2^Xを自然に同一視できる ^[3] ので、以下2^Xの代わりにFを用いる。

仮にXからFへの全単射φが存在したと仮定する。すると各x∈Xに対しφ(x)はXから{0,1}への写像である。以下写像φ(x):X→{0,1}の事をφ_xと書く。

g:X→{0,1}をg(x)=￢φ_x(x)によって定義する。すると対角線論法により、φ_x=gとなるx∈Xは存在しない。

これは $x \mapsto \phi_x$ が全射であった事に反する。

[編集] 自然数の集合と[0,1]区間の濃度が違う事の証明との関係

Nから{0,1}への写像全体の集合をFとする。 x∈[0,1]に対し、関数h_x:N→{0,1}を h_x(y)=(xの二進数展開のy桁目)により定義する。 ^[4] [0,1]区間とFの間には、全単射 $x \mapsto h_x$ が存在するので、 [0,1]とFの濃度は等しい。

自然数全体の集合Nから[0,1]区間への全単射が存在しない事を示した前述の証明は、 $x \mapsto h_x$ によって[0,1]とFを同一視すると、前述したXからFへの全単射が存在しない事の証明をX=Nに対して適応した場合に一致する。

[編集] ラッセルのパラドックスとの関係

カントールの定理とラッセルのパラドックスとの関係を見る為に、まずカントールの定理を別証明する。この証明は、前述の証明で2^XをFに置き換えずに直接証明したものと一致する。

仮にXから2^Xへの全単射φが存在したと仮定する。

Xの部分集合Dを、

$D = \{x \in X \mid x \notin \phi(x) \}$

により定義する。

φの全単射性より、D=φ(d)を満たすd∈Xが存在する。dはDの元であろうか。

d∈Dなら、Dの定義より $d \notin \phi(d)$ 。しかしD=φ(d)なので $d \notin D$ となり矛盾。
$d \notin D$ なら、Dの定義よりd∈φ(d)。しかしD=φ(d)なのでd∈Dとなり矛盾。

よってXから2^Xへの全単射は存在しない。

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

[編集] 連続体仮説

この定理により、べき集合の濃度がもとの集合より大きくなるということは分かるが、ではその間に別の濃度は存在するのかという問題を考えることもでき、これは一般連続体仮説と呼ばれている。とくに N の濃度（可算濃度）とそのべき集合の濃度（連続濃度）の間に別の濃度が存在するかという問題は連続体仮説と呼ばれ、ヒルベルトの23の問題の第1問題として挙げられた。一般連続体仮説はクルト・ゲーデルとポール・コーエンによって普通用いられる集合論の枠組みでは証明も反証もできないことが示された。

[編集] 停止性問題の決定不能性

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

以下簡単の為、プログラムの入力は全て自然数とする。プログラムは0と1からなる数字で書き表せるので、プログラム全体の集合と自然数全体の集合 $\mathbb{N}$ と自然に同一視できる。 ^[5] $\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が成立し、矛盾。したがって停止性問題を常に正しく解くプログラムは存在しない。

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

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

[編集] 関連項目

[編集] 参考文献・脚注

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

^ George Cantor (1891). “Uber ein elementare Frage der Mannigfaltigkeitslehre”. Deutsche Mathematiker-Vereinigung.
^ $a x$ の二進数展開が2つある事もある(例えば $0.1=0.01111\cdots$ )為、本当はこの部分の証明はもう少し複雑になる。
^ h∈Fに対し集合{x∈X|h(x)=1}∈2^Xを対応させる
^ ここでも、本当は二進数展開が一意ではない事を考慮しなければならない。
^ 本当は $\mathbb{N}$ の中にはプログラムに対応していないものもあるが、簡単の為その辺の事情は略する。

カテゴリ: 集合論 | 数学に関する記事

See also ebooksgratis.com: no banners, no cookies, totally FREE.