T-pon’sよろず日記

2005/11/12 [Sat]

『無限』に潜む罠 〜 (続)素数の集合をごにょごにょすると… 00:02 『無限』に潜む罠 〜 (続)素数の集合をごにょごにょすると…を含むブックマーク

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

例えば、自然数を「2のべき乗」の和で表します。

……(中略)……

そして、自然数を表すのに使った「2のべき乗」を要素にもつ集合を考えると、そのべき集合は自然数の集合になると考えられます。

「2のべき乗の和で表します」とは、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とする(ただしφは0とする)

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〜, 110〜, 001〜, …} (但し"〜"は以降"0"が続くことを表す)と表記していたのは実はごまかしで、"〜"を用いないような文字列(つまり後ろの方に無限に1が続くような文字列)も生成されるということです。有限番目までだけを線で結んで終わりにしちゃいけないんですね。だからって、無限回 線で結べってのもできない話なので困ってしまいますが(^^ゞ


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

ROYGBROYGB 2005/11/13 12:06 順番を逆にしてみたらどうでしょう。2の冪乗の集合から考えるのではなく、自然数の集合から考えます。
自然数を2進数表記することで、自然数の集合から2の冪乗の集合をつくっていきます。その結果が無限集合になると考えるとおかしいのは、上で説明されている通りです。だからといって、有限集合でもおかしいし、そんな集合は存在しないとすると、自然数を2進数で表記することが出来ないとなるので、これもおかしいはず。どう考えても矛盾が出るのが不思議です…。

quintiaquintia 2005/11/13 15:35 T-ponさんが説明したのは「無限集合のべき集合には、元に『無限集合』がある」ことを見逃してはいけないということ。それを「悪魔が潜んでいる」を表現しています。
ROYGBさんが頭の中で思い描いているであろう命題は、『「2のべき乗の集合」のべき集合』の『有限集合の元だけを集めた部分集合』が自然数の集合と同じ濃度である、です。
それを証明することは私にはできませんが、直感的には正しい様に思います。
ひとまず。

quintiaquintia 2005/11/13 18:43 証明することができないとしたのは一般化した「可算無限集合Xのべき集合の、有限集合の元だけからなる部分集合が可算集合である」という命題です。
2のべき乗を出発点にしたROYGBさんの例が、自然数の集合を作ることから「直感的には正しい」と思ったわけです。

T-ponT-pon 2005/11/14 01:21 >ROYGBさん
コメントありがとうございます。
>自然数の集合から2の冪乗の集合をつくっていきます
作れません。上述の´↓の過程を逆に辿る方法を用いる限り、それは不可能です。理由は以下の通りです。

集合Bからの操作で作る集合を集合C’とすると、上述の通りC’⊃Cが成り立つ(∵Cには無限に潜む「悪魔」が含まれない笑)。そしてCの濃度がアレフ0でありC’の濃度がアレフ1である。従って、ROYGBさんの言うように自然数の集合Cから出発しても、C’は作れないしBも作れない。Cにの逆操作を行って得られるのは高々{α: αはBの元のうち、有限集合である元}である。よって、そのような集合を冪集合と呼ぶことは誤りである(∵冪集合の元のうち、無限集合であるような元を欠いている)。

>quintiaさん
なるほど〜 またもやスッキリしました!! quintiaさんに頼りっきりでスイマセン(^^; A(2のべき乗の集合)の冪集合の元は有限集合の元と無限集合の元に大きく2分されると。そして直感的には、有限集合の元だけ集めると可算集合になるのではないかと。よく分かりました。選択公理に対する理解も深まった気がします。

quintiaquintia 2005/11/14 07:44 >T-ponさん
>>自然数の集合から2の冪乗の集合をつくっていきます
>作れません。
作れます。(^-^;A
自然数Xを2進数表記するということは、2のべき乗の和で表現することに他なりません。
なので、「和で表現する」のを「集合の元にする」に読み替えるだけで、2のべき乗を元に持つ集合で表現できます。
肝心なのは、
Xは無限に大きくなる、
わけですが、
Xを表現する2のべき乗の集合はたかだかn個の有限集合である、
点です。(ちなみにnはlog2(x)+1 小数点以下切り捨て。log2は普通の「2を底にした対数」のこと。)
「自然数の集合」を『「2のべき乗の集合」の集合』に全単射することは可能なのです。
当然、この『「2のべき乗の集合」の集合』は可算無限集合であり、『「2のべき乗の集合」のべき集合』ではありません。
あくまでも『「2のべき乗の集合」のべき集合の、「有限集合の元」からなる部分集合』です。

quintiaquintia 2005/11/14 07:47 ん?
>ちなみにnはlog2(x)+1 小数点以下切り捨て。

ちなみにnはlog2(x)+1 小数点以下切り捨て より小さい値。
の間違いですね。

T-ponT-pon 2005/11/14 11:10 (誤字が多かったので上記を削除・修正しました)
あ゛ーっ やっちゃった!!
>>自然数の集合から2の冪乗の集合をつくっていきます
>作れません。
たしかに作れますね。いや、ちょっとだけ言い訳をさせて下さい(^人^)

ROYGBさんが
>順番を逆にしてみたらどうでしょう
と言われていたので、 銑の手順を丁度逆にたどるってことかと思って、「2の羃乗の集合の冪集合」を経由して「2の羃乗の集合」を作るものと解釈してしまったのです。で、から,惶掴世魑佞肪ろうとしても無理だよという説明を上に書いてしまいました。
しかしいずれにせよ、自然数の集合から「2の羃乗の集合」は作れるので(2進法に置き換えるだけなので当然※ですね(^^ゞ)、局所的に見れば明らかに誤りです。御指摘ありがとうございます。

※これは選択公理によって可能となる操作なのかもしれませんが