2元生成の自由群は可算か？

2元生成の自由群は可算か？

バナッハタルスキーのパラドックスを本で読んで証明を追っています。
その途中、2元から生成された自由群（と同型な群）は可算であるから…、との表記が証明なしにありました。
これは正しいですか？
対角線論法と同じように以下のように考えました。
生成元をh,kとしたとき、可算濃度と仮定すると全ての元を
e
h
k
hh
hk
…
と順番に並べることができます。
i番目の元のi文字目がhならk、何もない場合やkならh（i=1,2,…）と定めてできたものはすべての元と異なるので矛盾するように思うのですが…

あるいは、可算の長さである元について、その選び方は2^（可算無限）となり、全体としても連続濃度になってしまうと思います。

No.3 ベストアンサー 回答者： alice_44 回答日時： 2010/07/23 08:42

既に No.1 に、長さ n 以下の元が 2↑(n+1) 個

であることを書きました。

長さ n の元の各々に、第 (2↑n)+1 番から第 2↑(n+1) 番の番号を
適当に割り振ってゆけば、全ての元がに付番する
ことができます。

この回答へのお礼

詳しいご回答ありがとうございました。
ようやく理解できました。

お礼日時：2010/07/24 12:01

No.2 回答者： rinkun 回答日時： 2010/07/22 09:48

間違えてはいけない。

自由群の各要素は生成元の有限列であって可算列ではない。
そしてそのような有限列の全体は、可算集合である。これは列の長さによって分類して並べれば分かる。長さ1の列は2つ、長さ2の列は高々4つ、．．．長さnの列は高々2^n個で、それぞれ有限なのでそれらを長さ順に並べていけば全体として高々可算になる。

この回答へのお礼

理解できました。
ご回答ありがとうございました。

お礼日時：2010/07/24 11:59

No.1 回答者： alice_44 回答日時： 2010/07/22 00:15

自由群で対角線論法を行うことはできません。

実数の非可算性を対角線論法で示したとき、
番号を付けて並べた実数には、
個々の元に無限の桁がありました。
有限小数でも、右側には 0 がずっと続いていて、
三桁の 0.123 から小数第 7 位を取り出したり
することができたのです。

一方、自由群では、どの元も長さが有限です。
それが禍して、並べた n 番目の元から
第 n 文字を取り出せないことがあります。

例えば、h, k が生成する自由群の元を
h, k, hh, hk, kk, … のように並べると、
2番目の元の第2文字を取り出すことができません。

これは、元を並べる順番には依らない性質です。
二元が生成する長さ n の元は 2↑n 個あります。
よって、n 文字以内の元は 2↑(n+1) 個です。
この個数が n に対して指数的に増えるため、
自由群の元をどのように並べても、
長さ n 未満の元が n 番目までに出終わる
ようにはできないのです。

この回答への補足

ご回答ありがとうございます。
対角線論法が使えないことは理解できました。

連続濃度の証明に対角線論法が使えない
ことを教えてくださったわけですが、これが直接
連続濃度でないことの証明
にはなりませんよね。
可算濃度であることの証明はできるのでしょうか。

補足日時：2010/07/22 03:12