- ベストアンサー
2元生成の自由群は可算か？
- バナッハタルスキーのパラドックスを本で読んで証明を追っています。
- 2元から生成された自由群は可算であるかどうかについて疑問が生じました。
- 対角線論法と同じように考えると、2元から生成された自由群は連続濃度になってしまう可能性があります。
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
既に No.1 に、長さ n 以下の元が 2↑(n+1) 個 であることを書きました。 長さ n の元の各々に、第 (2↑n)+1 番から第 2↑(n+1) 番の番号を 適当に割り振ってゆけば、全ての元がに付番する ことができます。
その他の回答 (2)
- rinkun
- ベストアンサー率44% (706/1571)
間違えてはいけない。自由群の各要素は生成元の有限列であって可算列ではない。 そしてそのような有限列の全体は、可算集合である。これは列の長さによって分類して並べれば分かる。長さ1の列は2つ、長さ2の列は高々4つ、．．．長さnの列は高々2^n個で、それぞれ有限なのでそれらを長さ順に並べていけば全体として高々可算になる。
お礼
理解できました。 ご回答ありがとうございました。
- alice_44
- ベストアンサー率44% (2109/4759)
自由群で対角線論法を行うことはできません。 実数の非可算性を対角線論法で示したとき、 番号を付けて並べた実数には、 個々の元に無限の桁がありました。 有限小数でも、右側には 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 番目までに出終わる ようにはできないのです。
補足
ご回答ありがとうございます。 対角線論法が使えないことは理解できました。 連続濃度の証明に対角線論法が使えない ことを教えてくださったわけですが、これが直接 連続濃度でないことの証明 にはなりませんよね。 可算濃度であることの証明はできるのでしょうか。
お礼
詳しいご回答ありがとうございました。 ようやく理解できました。