カントールの対角線論法

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

カントールの対角線論法（カントールのたいかくせんろんぽう）とは、対角線（その正確な意味は場合場合で異なるが）の部分を巧みに利用して所望の性質を持つものをつくり出す、以下のような証明方法のことをいう。様々な場面で用いられる強力な手法である。

[編集] 自然数と実数の濃度

自然数から実数の区間 (0, 1] への全単射が存在しないこと、言い換えると1以下でかつ正であるような実数すべてに一つずつ番号をつけて数え上げることはできないということを、対角線論法を用いて証明すると次のようになる。この証明はカントールが1891年に得たものである。カントールはこの定理の区間縮小法を用いた証明を1874年に得ていた。対角線論法を用いた次の証明はもとの証明よりも簡単で、見通しのよいものになっている。

[編集] 証明

背理法による。自然数から区間 (0, 1] への全単射が存在すると仮定する。その写像を φ としよう。区間 (0, 1] に含まれる実数を小数のかたちに展開する。ただし、

0.1

は

0.09999...

のようにし、どの小数にも常に0以外の数字が無限に表れるようにする(0.999...が1に等しいことの証明)。こうすることで小数展開は一意的になる。仮定からこのような形の小数全体に一つずつ番号がつくはずである。

$\begin{matrix} \phi(1)&=&0.\mathbf{a}_{11}a_{12}a_{13}a_{14}\cdots\\ \phi(2)&=&0.a_{21}\mathbf{a}_{22}a_{23}a_{24}\cdots\\ \phi(3)&=&0.a_{31}a_{32}\mathbf{a}_{33}a_{34}\cdots\\ \vdots & & \vdots \end{matrix}$

のようになったとする。ここで、ある実数を考えて

$0.b_1 b_2 b_3 b_4 \cdots$

ただし

$b_{i} = \left\{ \begin{matrix} 1, & \mbox{if }a_{ii} \ne 1 \\ 2, & \mbox{if }a_{ii} = 1 \end{matrix} \right.$

とすると、これは (0, 1] に入っているが、どの φ(n) をとってきても、小数第 n 位が異なる。これは φ が全射であることに反し、矛盾。
Q.E.D.

ここで対角線とは、 $a_{11}, a_{22}, a_{33}, \cdots$ と n 番目の小数の小数第 n 位を順々にたどっていった部分に相当する。

実数全体と (0, 1] との間に全単射の存在することは容易に言えるので、上の定理は実数が可算でないということでもある。

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

次にもう一つ、任意の集合 X とそのべき集合 2^X との間に全単射が存在しないこと（カントールの定理、カントール、1890年）をやはり対角線論法を用いて証明する。この証明ではおのおのの集合 ψ(x) に対して x を含むかどうかで常に異なるような集合 A をつくり出す点が対角線を利用していることになる。

[編集] 証明

背理法による。全単射 ψ: X → 2^X が存在したとしよう。X の部分集合 A を

$A = \left\{ \begin{matrix} a \notin A, & \mbox{if }a \in \psi(a) \\ a \in A, & \mbox{if }a \notin \psi(a) \end{matrix} \right.$

で定義すると、A ∈ 2^X である。ψ は全射だから、ある x に対して A = ψ(x) とならなければならないが、x ∈ ψ(x) としても x ∉ ψ(x) としても矛盾を生じる。
Q.E.D.

実数の集合は自然数の集合のべき集合と濃度が等しいので、最初の定理は二番目の定理の特別な場合になる。この定理により、べき集合の濃度がもとの集合より大きくなるということは分かるが、ではその間に別の濃度は存在するのかという問題を考えることもでき、これは連続体仮説と呼ばれている。

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

"http://ja.wikipedia.org../../../%E3%82%AB/%E3%83%B3/%E3%83%88/%E3%82%AB%E3%83%B3%E3%83%88%E3%83%BC%E3%83%AB%E3%81%AE%E5%AF%BE%E8%A7%92%E7%B7%9A%E8%AB%96%E6%B3%95.html" より作成

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