人気ブログランキング | 話題のタグを見る

カントールの定理と背理法

集合 X とそのべき集合 2^X との間に全単射が存在しないことを証明したカントールの定理は背理法による証明が用いられている。

集合 X からその冪集合 2X への写像 φ : X -> 2X において、つぎのような集合 Y = { x ∈ X : x /∈ φ(x) } に対応する x ∈ X は存在しない。なぜなら、x /∈Y ならば x ∈ Y でなければならないし、x /∈ Y ならば x ∈ Y にならなければならなくなるのでパラドックスが生じるからだ。

確かに X から 2^X への全単射があると仮定すると矛盾が生じるので、そのような全単射はないと結論付けられるが、背理法の問題点はこの全単射の全体像が見えないということだ。

たとえば、集合 X = {a, b, c} とそれ自身のべき集合と全単射していると仮定する。そうして a に対する X の集合を a' で表すようにすると {a, b, c} と a', b', c' との間に次のような対照表を作ることができるはずだ。

** a b c
a' 1 0 0
b' 1 0 1
c' 1 1 0

この対照表の行はどの集合が列のどの要素を要素として含んでいるかを表している。たとえば a' は a を要素として含んでいるが、b, c は含んでいない。すなわち a -> a' = {a} である。

ここで対照表の対角線分は写像で a が対応する a' に含まれているかどうかを表している。上の例では a ∈ a'、b /∈ b', c /∈ c' である。カントールの定理に現れる集合 Y があったとすると a /∈ Y, b ∈ Y, c ∈ Y である。これは a は含まれず、b は含まれ、c は含まれるということだから Y 0 1 1 となるような数列が行に現れるはずだ。ところで 0 1 1 という数列は対角成分を反転させてできている。したがって、a', b', c' のどの行とも一致しないので Y はこの対照表には表れない。

また、仮に Y が b' と一致していたとしよう。すると (b', b) の値は1にならなければならないはずだが、もとの表から (b', b) は0 であるはずだから矛盾する。なぜなら (b', b) = 0 だからこそ b ∈ Y なのだが、この場合 (Y, b) = (b' b) = 1 にならなければならないからだ。これは Y が a' であると仮定しても、c' であると仮定しても同じように矛盾が生じる。

パラドックスが発生するということは、そのような行の数列が対照表のなかには見つけられないということと同じなのだ。

背理法では Y 0 1 1 という数列が対照表の行には現れないということは証明するが、それでは 0 1 1 が表す集合 {b, c} はどこに行ったのかということまでは示してくれない。

実際、上の対照表に現れるべき数列は、X = {a, b, c} の要素数をはるかに超えて 2^3 = 8 もあるのである。

Prelude> table = [[x1,x2,x3] | x1 <- [0,1], x2 <- [0,1], x3 <- [0,1]]
Prelude> table
[[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]
Prelude> mapM_ print table
[0,0,0]
[0,0,1]
[0,1,0]
[0,1,1]
[1,0,0]
[1,0,1]
[1,1,0]
[1,1,1]

3 × 3 の対照表ではそのごく一部しか表現できない。3×3の対照表では表現できなかった 0 1 1 という集合も、非対称な表を考えればちゃんとその中に入っている。このように対角線論法は8ある可能性の3つだけを取り上げて対照表を作り、表現できない集合があると主張しているにすぎない。確かに正しいのだが不十分な観察だ。

有限集合だからそれは明白かもしれないが、カントールの定理は無限集合について証明したから重要なのだという主張もあるだろう。しかし、上の対照表はもちろん無限に拡張することができるが、それにつれて、対照表に記述できない集合も無限に増えていくのだ。どんなに無限に対照表を拡張していったとしても、それが対照行列である限り、冪集合の全てを記載するには不足している。

対角線論法による論証は、冪集合の要素の全てについて考慮するのではなく、その一部を正方行列の対照表に押し込めた場合に成立する論理なのだ。

おなじことが、すべての集合の集合についてもいえる。全ての集合の集合にはその集合のべき集合も必然的に含まれてしまう。このような場合に、集合の全てを全ての集合の集合という対称行列に埋め込もうとすれば、ラッセルのパラドックスが発生するのは当然なのだ。集合を矛盾なく取り扱うためには、すべての集合の集合という領域の中ですべてを組み立てるという無理を通さずに、非対称な対照表のなかに集合を構築していけば、ラッセルのパラドックスのような矛盾は発生しないのではないだろうか。

公理的集合論の公理は、集合にとって自然なものではなく、技巧的に、上のような正方対照表のなかで集合を組み立てようとしているように見える。集合とそのべき集合の非対称性を受け入れれば、ラッセルのタイプ理論のほうが、集合の世界を自然に組み立てていけるような気がする。ラッセルのタイプ理論は煩雑で使い難いとのことのようだが、Haskell のような厳密な型を取り扱う言語が、意外に使い勝手が良いのを考慮に入れると、集合論をタイプ理論で使い勝手良く構築するというのもあるのではないかという気がする。

おそらく、問題点は、無限集合を「全ての集合の集合」のようなくくり方をするところにあるのではないか。どのような集合 X であっても、そのなかに冪集合の要素をかかえこむことはできないのに、全ての集合の集合のようなくくり方をすると、それをできるかのような取扱をすることになるからだ。その場合ラッセルのパラドックスが発生するのは当然だ。

安易な実無限の乱用が、集合に矛盾があるような推論を導いているのではないだろうか。

by tnomura9 | 2019-01-02 23:40 | ラッセルのパラドックス | Comments(0)
<< 実無限と構成的集合 不動点とカリー化 >>