2005-11-12

ROYGBさんがはてなで不思議なコメントをされていた。これはこの前まで僕がしていた勘違いと通じるところがある。

例えば、自然数を「２のべき乗」の和で表します。
……（中略）……
そして、自然数を表すのに使った「２のべき乗」を要素にもつ集合を考えると、そのべき集合は自然数の集合になると考えられます。

「２のべき乗の和で表します」とは、2進表示することと思ってよい。そして「そのべき集合は自然数の集合になると考えられます。」とは、冪集合が数え上げ可能（つまり『可付番』＝『可算』）であるということを意味している（はず(^^ゞ）。
これは数学的に言えば次のようになる。

濃度 $\aleph_0$ の集合P = { $a_0$ , $a_1$ , $a_2$ , $a_3$ , $a_4$ , $a_5$ , … }の冪集合を集合Qとする。
Q = { φ, $\{a_0\}$ , $\{a_1\}$ , $\{a_0, a_1\}$ , $\{a_2\}$ , $\{a_0, a_2\}$ , $\{a_1, a_2\}$ , $\{a_0, a_1, a_2\}$ , $\{a_3\}$ , … }を考える。
Qの各元について、 $a_{i-1}$ の有無を第 $i$ 桁で表すような文字列に置換することにより、
集合R = { $000$ 〜, $100$ 〜, $010$ 〜, $110$ 〜, $001$ 〜, $101$ 〜, $011$ 〜, $111$ 〜, … }を作る。（但し"〜"は以降" $0$ "が続くことを表す）
このとき、Qは $\aleph_0$ の冪集合なので濃度 $\aleph_1$ であり、Rは左端を最下位ビットとして2進法で読めば、自然数の集合N　{ $0$ , $1$ , $2$ , $3$ , …}に対応するので明らかに自然数と等濃度で $\aleph_0$ である。しかし、QとRは作成手順より明らかに1対1対応の関係（＝全単射）である（！！？）

何が間違っていたのだろうか？　これは僕が前のDiaryで犯した間違いと相同だ。

次のように考えるとそれがはっきりする。
①　2の羃乗の集合をAとする。

A = { $2^0$ , $2^1$ , $2^2$ , ...}

②　Aの冪集合をBとする。

B = {φ, $\{2^0\}$ , $\{2^1\}$ , $\{2^0, 2^1\}$ , $\{2^2\}$ , $\{2^0, 2^2\}$ , $\{2^1, 2^2\}$ , $\{2^0, 2^1, 2^2\}$ , … }

③　Bの各元について、含まれる数の和に置換した集合をCとする(ただしφは０とする)

C = { $0$ , $1$ , $2$ , $3$ , $4$ , $5$ , $6$ , $7$ , … }

ここでAは濃度 $\aleph_0$ 、Bは冪集合なので濃度 $\aleph_1$ 、Cは自然数の集合なので濃度 $\aleph_0$ である。さらに、③の操作はBの各元に対して行っており、またそうして作成したCの元に重複はないので、集合Bと集合Cは1対1対応する。よってBとCの濃度は等しい（！！）。

もちろん、 $\aleph_0$ の集合と $\aleph_1$ の集合の濃度が等しいはずはなく、どこかに誤りがある。どこでしょう？

quintiaさんの説明を参考にここにもう一度書きます。
Bから③の手順により作られる集合はC（自然数の集合）ではない。有限番目を注目している限りはBとCが異なる集合であることには気づかない所がミソ。Bは冪集合であるので、 $2^i$ ( $i$ は任意の自然数)を全て含むような元も存在する。その元について③の操作を行うと発散するのでこれは自然数の元には含まれない。よってCの全ての元はBの元から作られるが、逆は必ずしも真ならず、Bの元には対応する元をC（自然数の集合）の中に持たないものがある(つまり全射でない)。そしてそのような元は無限個ある。たとえばBの元で
{ $2^0$ , $2^1$ , $2^2$ , $2^3$ , $2^4$ , $2^5$ , …}　（つまり全ての元を含む）
の他に、
{ $2^1$ , $2^2$ , $2^3$ , $2^4$ , $2^5$ , …}　（ $2^0$ 以外を全て含む）
{ $2^0$ , $2^2$ , $2^3$ , $2^4$ , $2^5$ , …}　（ $2^1$ 以外を全て含む）
{ $2^0$ , $2^1$ , $2^3$ , $2^4$ , $2^5$ , …}　（ $2^2$ 以外を全て含む）
{ $2^{100}$ , $2^{101}$ , $2^{102}$ , $2^{103}$ , $2^{104}$ , …}　（ $2^{100}$ 以降を全て含む）
などいくらでも考えられる。

P,Q,Rの話に即して言えば、冪集合Qの元にはPの全元を含む集合も含まれており、これは集合Rにおいては全て"1"の無限長文字列に対応し、それに対応するNの元は存在しない。また、対応するNの元が存在しないようなQの元は無限個存在する。集合Rを、{000〜, 100〜, 010〜, １１０〜, ００１〜, …}　（但し"〜"は以降"0"が続くことを表す）と表記していたのは実はごまかしで、"〜"を用いないような文字列（つまり後ろの方に無限に1が続くような文字列）も生成されるということです。有限番目までだけを線で結んで終わりにしちゃいけないんですね。だからって、無限回　線で結べってのもできない話なので困ってしまいますが(^^ゞ

要は、無限番目には悪魔が潜んでいる、ということでしょうか笑

T-pon’sよろず日記

『無限』に潜む罠　〜　(続)素数の集合をごにょごにょすると…