2005/11/12 [Sat]
■『無限』に潜む罠 〜 (続)素数の集合をごにょごにょすると… 
ROYGBさんがはてなで不思議なコメントをされていた。これはこの前まで僕がしていた勘違いと通じるところがある。
例えば、自然数を「２のべき乗」の和で表します。
……（中略）……
そして、自然数を表すのに使った「２のべき乗」を要素にもつ集合を考えると、そのべき集合は自然数の集合になると考えられます。
「２のべき乗の和で表します」とは、2進表示することと思ってよい。そして「そのべき集合は自然数の集合になると考えられます。」とは、冪集合が数え上げ可能（つまり『可付番』＝『可算』）であるということを意味している（はず(^^ゞ）。
これは数学的に言えば次のようになる。
濃度
の集合P = {
,
,
,
,
,
, … }の冪集合を集合Qとする。
Q = { φ,
,
,
,
,
,
,
,
, … }を考える。
Qの各元について、
の有無を第
桁で表すような文字列に置換することにより、
集合R = {
〜,
〜,
〜,
〜,
〜,
〜,
〜,
〜, … }を作る。（但し"〜"は以降"
"が続くことを表す）
このとき、Qは
であり、Rは左端を最下位ビットとして2進法で読めば、自然数の集合N {
,
,
, …}に対応するので明らかに自然数と等濃度で
何が間違っていたのだろうか？ これは僕が前のDiaryで犯した間違いと相同だ。
次のように考えるとそれがはっきりする。
� �2の羃乗の集合をAとする。
A = {,
,
, ...}
�◆�Aの冪集合をBとする。
B = {φ, ,
,
,
,
,
,
, … }
�� Bの各元について、含まれる数の和に置換した集合をCとする(ただしφは０とする)
C = {,
,
,
,
,
,
,
, … }
ここでAは濃度、Bは冪集合なので濃度
、Cは自然数の集合なので濃度
である。さらに、��の操作はBの各元に対して行っており、またそうして作成したCの元に重複はないので、集合Bと集合Cは1対1対応する。よってBとCの濃度は等しい（！！）。
もちろん、の集合と
の集合の濃度が等しいはずはなく、どこかに誤りがある。どこでしょう？
quintiaさんの説明を参考にここにもう一度書きます。
Bから��の手順により作られる集合はC（自然数の集合）ではない。有限番目を注目している限りはBとCが異なる集合であることには気づかない所がミソ。Bは冪集合であるので、 (
は任意の自然数)を全て含むような元も存在する。その元について��の操作を行うと発散するのでこれは自然数の元には含まれない。よってCの全ての元はBの元から作られるが、逆は必ずしも真ならず、Bの元には対応する元をC（自然数の集合）の中に持たないものがある(つまり全射でない)。そしてそのような元は無限個ある。たとえばBの元で
{,
,
,
,
,
, …} （つまり全ての元を含む）
の他に、
{,
,
,
,
, …} （
以外を全て含む）
{,
,
,
,
, …} （
以外を全て含む）
{,
,
,
,
, …} （
以外を全て含む）
{,
,
,
,
, …} （
以降を全て含む）
などいくらでも考えられる。
P,Q,Rの話に即して言えば、冪集合Qの元にはPの全元を含む集合も含まれており、これは集合Rにおいては全て"1"の無限長文字列に対応し、それに対応するNの元は存在しない。また、対応するNの元が存在しないようなQの元は無限個存在する。集合Rを、{000〜, 100〜, 010〜, １１０〜, ００１〜, …} （但し"〜"は以降"0"が続くことを表す）と表記していたのは実はごまかしで、"〜"を用いないような文字列（つまり後ろの方に無限に1が続くような文字列）も生成されるということです。有限番目までだけを線で結んで終わりにしちゃいけないんですね。だからって、無限回 線で結べってのもできない話なので困ってしまいますが(^^ゞ
要は、無限番目には悪魔が潜んでいる、ということでしょうか笑
自然数を２進数表記することで、自然数の集合から２の冪乗の集合をつくっていきます。その結果が無限集合になると考えるとおかしいのは、上で説明されている通りです。だからといって、有限集合でもおかしいし、そんな集合は存在しないとすると、自然数を２進数で表記することが出来ないとなるので、これもおかしいはず。どう考えても矛盾が出るのが不思議です…。
ROYGBさんが頭の中で思い描いているであろう命題は、『「2のべき乗の集合」のべき集合』の『有限集合の元だけを集めた部分集合』が自然数の集合と同じ濃度である、です。
それを証明することは私にはできませんが、直感的には正しい様に思います。
ひとまず。
2のべき乗を出発点にしたROYGBさんの例が、自然数の集合を作ることから「直感的には正しい」と思ったわけです。
コメントありがとうございます。
＞自然数の集合から２の冪乗の集合をつくっていきます
作れません。上述の�´↓�の過程を逆に辿る方法を用いる限り、それは不可能です。理由は以下の通りです。
集合Bから��の操作で作る集合を集合C’とすると、上述の通りC’⊃Cが成り立つ（∵Cには無限に潜む「悪魔」が含まれない笑）。そしてCの濃度がアレフ０でありC’の濃度がアレフ１である。従って、ROYGBさんの言うように自然数の集合Cから出発しても、C’は作れないしBも作れない。Cに��の逆操作を行って得られるのは高々{α: αはBの元のうち、有限集合である元}である。よって、そのような集合を冪集合と呼ぶことは誤りである（∵冪集合の元のうち、無限集合であるような元を欠いている）。
＞quintiaさん
なるほど〜 またもやスッキリしました!! quintiaさんに頼りっきりでスイマセン(^^; A（2のべき乗の集合）の冪集合の元は有限集合の元と無限集合の元に大きく2分されると。そして直感的には、有限集合の元だけ集めると可算集合になるのではないかと。よく分かりました。選択公理に対する理解も深まった気がします。
>>自然数の集合から２の冪乗の集合をつくっていきます
>作れません。
作れます。(^-^;A
自然数Xを2進数表記するということは、2のべき乗の和で表現することに他なりません。
なので、「和で表現する」のを「集合の元にする」に読み替えるだけで、2のべき乗を元に持つ集合で表現できます。
肝心なのは、
Xは無限に大きくなる、
わけですが、
Xを表現する2のべき乗の集合はたかだかn個の有限集合である、
点です。(ちなみにnはlog2(x)+1 小数点以下切り捨て。log2は普通の「2を底にした対数」のこと。)
「自然数の集合」を『「2のべき乗の集合」の集合』に全単射することは可能なのです。
当然、この『「2のべき乗の集合」の集合』は可算無限集合であり、『「2のべき乗の集合」のべき集合』ではありません。
あくまでも『「2のべき乗の集合」のべき集合の、「有限集合の元」からなる部分集合』です。
>ちなみにnはlog2(x)+1 小数点以下切り捨て。
は
ちなみにnはlog2(x)+1 小数点以下切り捨て より小さい値。
の間違いですね。
あ゛ーっ やっちゃった！！
>>自然数の集合から２の冪乗の集合をつくっていきます
>作れません。
たしかに作れますね。いや、ちょっとだけ言い訳をさせて下さい(^人^)
ROYGBさんが
＞順番を逆にしてみたらどうでしょう
と言われていたので、� 銑�の手順を丁度逆にたどるってことかと思って、「2の羃乗の集合の冪集合」を経由して「2の羃乗の集合」を作るものと解釈してしまったのです。で、��から�，惶掴世魑佞肪�ろうとしても無理だよという説明を上に書いてしまいました。
しかしいずれにせよ、自然数の集合から「2の羃乗の集合」は作れるので（2進法に置き換えるだけなので当然※ですね(^^ゞ）、局所的に見れば明らかに誤りです。御指摘ありがとうございます。
※これは選択公理によって可能となる操作なのかもしれませんが