カントールの対角線論法のソースを表示

'''カントールの対角線論法'''（カントールのたいかくせんろんぽう、{{lang-en-short|Cantor's diagonal argument}}）は、数学における証明テクニック（背理法）の一つ。1891年に[[ゲオルク・カントール]]によって非可算濃度を持つ集合の存在を示した論文<ref>{{cite paper |author=George Cantor|title=Uber ein elementare Frage der Mannigfaltigkeitslehre|publisher=Deutsche Mathematiker-Vereinigung|date=1891}}</ref>の中で用いられたのが最初だとされている。
その後対角線論法は、数学基礎論や計算機科学において写像やアルゴリズム等が存在しないことを示す為の代表的な手法の一つとなり、例えば[[ゲーデルの不完全性定理]]、[[停止性問題]]の決定不能性、[[時間階層定理]]といった重要な定理の証明で使われている。
<!--
[[自然数]]からの全射が存在しないような集合、言い換えるとその元に一つずつ番号をつけて数え上げることはできないような集合の存在を、対角線論法を用いて以下のように証明することができる。この証明は[[ゲオルグ・カントール|カントール]]が[[1891年]]に発表したものである。カントールはこの定理の区間縮小法を用いた証明を[[1874年]]に得ていたが、対角線論法を用いた以下の証明はもとの証明よりも簡単で、見通しのよいものになっている。

うまく本文に組み込めなかったので、いったん削除。
-->

==  対角線論法 ==
=== 集合による表現 ===
'''対角線論法'''とは、以下の補題を使って定理を証明する[[背理法]]のことである。

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

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

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

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

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

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

べき集合2<sup>X</sup>は、Xから{0,1}への関数全体の集合と自然に同一視できる<ref group="注釈">W∈2<sup>X</sup>に対し、その特性関数χ<sub>W</sub>を対応させることで同一視できる。ここでχ<sub>W</sub>: X → {0,1}は、x∈Wとなるときおよびそのときのみχ<sub>W</sub>(x)=1となる関数。</ref>ことがよく知られているが、「関数による表現」の対角線論法と「集合による表現」の対角線論法はこの同一視を通して同値である事が証明できる。実際、ψを「集合による表現」で登場した関数とするとき、ψ(x)∈2<sup>X</sup>はXから{0,1}への関数とみなせる。関数ψ(x)によるy∈Xの像をψ(x)(y)と書き、関数φ: X×X→{0,1}を、φ(x,y)=ψ(x)(y)として「関数による表現」の補題を使うことで、「集合による表現」の補題を証明できる。（逆もまた真。）
<!--「対角線論法」という名前の由来は、 <math>\phi_{x}(y)</math> を <math>X \times X</math> の「対角線」 <math>y = x</math> 上に制限した写像 <math>\phi_{x}(x)</math> を考えることから。-->

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

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

実際Bの第i成分は￢a<sub>x,x</sub>であるのに対し、A<sub>x</sub>の第i成分はa<sub>x</sub>であるので、B≠A<sub>x</sub>。

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

=== 論理式による表現 ===
¬∃x∀y.(P(x,y)⇔¬P(y,y))　すなわち　∀x∃y.((P(x,y)∧P(y,y))∨(¬P(x,y)∧¬P(y,y)))

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

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

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

a<sub>i</sub>を[[二進記数法|二進数展開]]したときの<math>j</math>桁目をa<sub>i,j</sub>とし<ref group="注釈"><math>a_i</math>の二進数展開が2つあることもある（例えば<math>0.1=0.01111\cdots</math>）為、本当はこの部分の証明はもう少し複雑になる。</ref>、b<sub>i</sub>を￢a<sub>i,i</sub>とする。

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

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

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

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

== カントールの定理 ==
{{main|カントールの定理}}
[[カントールの定理]]とは次のようなものである。

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

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

:Xから2<sup>X</sup>への全射ψが存在したとする。<math>Y=\{x\in X: x\notin\psi(x)\}</math>により定義すると、対角線論法より、ψ(x)=Yとなるx∈Xは存在しない。これはψの全射性に反する。

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

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

またこれを一般化して、
: 無限濃度 ''n'' に対して、''n'' < ''m'' < 2<sup>''n''</sup> なる ''m'' は存在しない
というのが、一般連続体仮説である。一般連続体仮説のZFからの無矛盾性を[[クルト・ゲーデル]]が、独立性を1963年に[[ポール・コーエン (数学者)|ポール・コーエン]]がそれぞれ証明した。

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

以下簡単の為、プログラムの入力は全て自然数とする。
プログラムは0と1からなる数字で書き表せるので、
プログラム全体の集合と自然数全体の集合<math>\mathbb{N}</math>と自然に同一視できる。
<ref group="注釈">本当は<math>\mathbb{N}</math>の中にはプログラムに対応していないものもあるが、
簡単の為その辺の事情は略する。</ref>
<math>\phi:\mathbb{N} \times \mathbb{N} \mapsto \{0,1\}</math>を次のように定義する：
''A''(''x'')が停止すればφ(''A'',''x'')=1、そうでなければφ(''A'',''x'')=0。

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

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

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

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

== 脚注 ==
{{脚注ヘルプ}}
=== 注釈 ===
{{Notelist}}
=== 出典 ===
{{Reflist}}

== 参考文献 ==
* [http://uk.geocities.com/frege@btinternet.com/cantor/diagarg.htm Cantor's Diagonal Argument]: カントールの証明の原文とその英訳

== 関連項目 ==
* [[濃度_(数学)|濃度]]
* [[停止性問題]]
* [[パラドックス]]

{{集合論}}
{{DEFAULTSORT:かんとおるのたいかくせんろんほう}}
[[Category:集合論]]
[[Category:論証]]
[[Category:証明法]]
[[Category:ゲオルク・カントール]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]