自然数とそのべき集合 対角線論法の秘密

自然数の集合と、自然数の集合のべき集合との全単射ができないのは、カントールの定理で証明されている。しかし、この記事では、カントールの証明がどのような意味を持つのかを考えてみたい。

自然数のべき集合の要素は自然数の集合だ。たとえば A = {2, 4, 7} は自然数のべき集合の要素だ。これらが規則的に列挙できれば自然数のべき集合は自然数と全単射を作ることができるといえる。

これはべき集合の要素を2進数に置き換えることで簡単に列挙することができるように見える。自然数の集合が自然数の1を含んでいれば2進数の1桁目が1含んでいなければ0、同じように自然数の集合が自然数の2を含んでいれば2進数の2桁目が1、含んでいなければ0とする。こうするとべき集合を表す2進数と自然数の間に自然な全単射ができる。

しかし、そううまくはいかない。これは自然数の集合のうちで要素数が有限な集合にしか当てはまらないのだ。要素数が無限な集合の場合は、2進数も無限大になってしまう。

これは無限大という実体が存在するという実無限の考え方からは不都合になるが、自然数はどれだけでも大きくとることができるという可能無限の立場からは不都合ではない。この方法では無限要素の集合を捕まえることはできないが、自然数をどんどん大きくとっていくことによって、どれだけでも無限要素の集合に近いものは作り出すことができるからである。

しかしそう都合よくはいかないことをカントールの定理が証明している。自然数と自然数のべき集合との間に全単射が存在すると仮定すると、a が f(a) の要素として含まれないような自然数 a 全てを集めた集合を B とすると B = f(b) となるような自然数 b が存在する。ところが b が B の要素であれば b は B に含まれないはずなので矛盾するし、b が B の要素ではないと仮定してもやはり矛盾する。したがって、自然数と自然数のべき集合の間には全単射は存在しないことが証明される。


確かに、対角線論法を用いた鮮やかな証明だが、しかし、なぜここで対角線論法を持ち出さなければならなかったのかがよくわからない。また、対角線論法では自然数とべき集合の間にどんな問題があるのかも判然としない。

ここで対角線論法の意義を明らかにするために、有限の自然数とそのべき集合をどのように表現するかを考えてみよう。これは、次のような表を作るのが一番だ。例えば自然数 {1,2,3} の部分集合を次のような表に表してみよう。

* 1 2 3
a 0 0 0
b 1 0 0
c 0 1 0
d 1 1 0
e 0 0 1
f 1 0 1
g 0 1 1
h 1 1 1

表の列の数字はその列の自然数が部分集合に含まれているかどうかを示している。1ならばその列の自然数が含まれており、0ならば含まれていない。

各行の数列は部分集合を表している。部分集合 a は {1,2,3} のどの要素も含んでいないので a = {} である。同様に d の行は 1 と 2 を含むので、部分集合 d = {1,2} である。これらの集合 a, b, ... h を自然数に対応させた表を作ると次のようになる。

* * 1 2 3
1 a 0 0 0
2 b 1 0 0
3 c 0 1 0
4 d 1 1 0
5 e 0 0 1
6 f 1 0 1
7 g 0 1 1
8 h 1 1 1

この場合 a = f(1), b = f(2), c = f(3), ..., h = f(8) である。

ところで x が f(x) に含まれないような x の集合Bはどのような集合になるだろうか。上の演算表で 4 .. 8 は集合 {1,2,3} の要素ではないので、x が f(x) に含まれるかどうかの議論はできない。明らかに含まれないからだ。したがって x が f(x) に含まれるかどうかというのは上の3行までの a, b, c つまり 1, 2, 3 の正方行列でしか判断できない。

そこで、上の表の3行までをみると1も2も3もそれぞれに対応するa, b, c に含まれないから B = {1,2,3} すなわち上の表の行で表すと 1 1 1 なので B = h である。これに対応する自然数は 8 であるから、{1,2,3} のうちには存在しない。すなわち B = f(y) となるような自然数は {1,2,3} のうちには存在しないのだ。なぜなら B(=h) の行の数は、a, b, c の対角線部分のどれとも異なっているからだ。これを無理に {1,2,3} の中に求めてしまうとカントールの定理のようなパラドックスが発生してしまう。

自然数とそのべき集合の議論を上の表の 3 × 3 の正方行列の部分に限定する限り、自然数の集合とその部分集合との対応関係には、自然数に対応できない部分集合が発生するのが分かる。

この関係は自然数 {1,2,3} の要素を増やして自然数全体の集合を拡充していくことができる。しかし、表の上部の正方行列の部分の性質についての議論は変わらないので無限に自然数を増やしても必ず正方行列の縦の自然数に対応できない部分集合が発生する。

ただし、これは表の冒頭の正方行列に限って議論しているからだ。カントールの対角線論法では暗黙にこの正方行列を仮定しているようだ。

したがって、カントールの定理にも関わらず、長方形の対応表を作っていけば、どれだけでも自然数のべき集合に全単射を作っていくことができる。ただし、自然数を無限大にまで拡張したときにそのような全単射が作れるかどうかは不定である。どちらも無限大になってしまうからだ。

実無限の観点からは、自然数の全体を仮定するので、演算表の横の自然数と縦の自然数の数は一致しなければならないので必然的に正方行列の議論になる。したがって、自然数とそのべき集合の全単射は不可能である。しかし、可能無限の立場からは、全ての自然数が縦と横で一致する必要はないので、長方形の演算表を縦方向にどんどん長くしていくことで、限りなく全単射の範囲を広げてていくことができるのである。

カントールの定理では自然数と自然数のべき集合の全単射を考えると矛盾すると証明するだけで、自然数と自然数のべき集合の濃度がどれくらい違うのかを示してはくれない。可能無限の立場をとっても、縦方向と横方向も無限に大きくしても完全な全単射になるとは論証できないが、可能無限の立場からは実用的にはどれだけでも全単射の範囲を広げることができる。コンピュータで真の実数を扱うことはできないが、どれだけでも精度を上げることができるのと同じだ。もともと、可能無限の考え方からは無限集合の全ての要素という考え方はない。

追記

上の説明ではカントールの定理でなぜパラドックスが発生するかは説明できていないので追加する。自然数の集合 A = (1,2,3} について自然数と A の部分集合の対応関係の関数 g の演算表を次のように定義してみる。3行目が空白なのは理由がある。x には対応する集合に含まれない自然数の集合を作りたいからだ。

この演算表からは c = g(1), d = g(2) であることが分かる。問題は x = g(3) としたときに x が対応する集合に属さない自然数を集めた集合になるように演算表を定めることができるかどうかだ。

* * 1 2 3
1 c 0 1 0
2 d 1 1 0
3 x * * *

この表で対角線の成分に注意するとそれは各行の自然数が対応する集合の要素として含まれているかを示している。この場合 c の対角線部分は 0 だから 1 は c に含まれていない。また、d の対角線部分は 1 だから 2 は対応する d の要素として含まれている。そこで対応する集合に含まれない自然数は 1 で対応する集合に含まれる自然数は 2 である。したがって、x の行の数列は次のようになる

3 x 1 0 *

xの 1 列目と 2 列目は上の2つの業の対角線部部分を反転したものになる。ところで、x の3列目の値は * になっているが、これを完成させれば 3 は自分自身が対応する集合に含まれない自然数の集合に対応することになる。ところが、3 が 1 であるとすると x は 3 を含むことになり定義からこれは 0 でなければならないし、x の3列目が 0 であるとするとそれは 1 でなければならないことになる。つまり、カントールの定理のパラドックスになっている。

このようにカントールの定理が証明したのは、自然数と自然数の部分集合の対応関係が正方行列になるという仮定の上での議論であったことが分かる。つまり、べき集合を作成するための自然数の集合と、べき集合に対応させるための自然数の集合の数が同じであるはずだという暗黙の過程がある。しかし、可能無限の立場からは両者の拡大速度が異なっていても問題ないのである。

無限集合にすべての要素を考えることができないといったのはこの理由からだ。無限集合とは要素を次々に生成していく集合のことであり、要素が生成される速度については制限がない。全単射は、単にある範囲までの要素同士の間で1対1対応が見られるという意味でしかない。そのため自然数とその部分集合である偶数との全単射が可能になるのだ。

カントールの定理には実無限の立場から、この無限集合の拡大の速度が同じになる正方行列を仮定してしまったための推論ではないのだろうか。無限集合にすべての要素を仮定する実無限の考え方は便利な道具ではあるが、可能無限からの無限に全てはないという見方からの検討も必要なのではないだろうか。

[PR]
by tnomura9 | 2017-06-12 18:55 | ラッセルのパラドックス | Comments(0)
<< 無限集合とは何か 無限集合の全単射 >>