-

自然数のべき集合と実数の濃度が等しいことの証明が、ググっても出てこなくてぐぬぬしてる。


発端は、自分が過去に書いた記事から。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝

ある集合の、部分集合全体からなる集合をべき集合という。
例えばX＝{1,2}のべき集合をP(X)で表すことにすると
P(X)＝{ { } , {1} , {2} , {1,2} }である。

問
自然数全体からなる集合Nのべき集合P(N)の要素の個数は加算無限個か？

答え
Nの無限部分集合全てからなる集合族をQ(N)としAをその元とする。
f(A)＝Σ[n∈A](2^(-n))
とすると f は Q(N)→[0,1] の全単射である。
Q(N)⊂P(N)なのでP(N)の要素は非加算無限個。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝

これ自体は間違いない（はず）。普通に対角線論法使えばいいんだけどね。
[0,1]区間内の実数の２進小数表示の一意性を保証するために、有限小数として表示可能なものも全て無限小数で表示することにしている。
１０進法で1/2に当たる数は、
0.1000000…　ではなく
0.0111111…　で表示し、{2,3,4,…}と対応させることにしている。
だから、ここに挙げたfでは、定義域をNの冪集合全体にすると、全射ではあっても単射ではない。

じゃあどんな全単射が存在するかというのがちょっと思い浮かばない。


余談：Nの冪集合は加算？、と一瞬でも思ってしまった雑魚がこちら。
{ }　1
{1}　2
{2}　3
{1,2}　4
{3}　5
{1,3}　6
{2,3}　7
{1,2,3}　8
…
Nそのものと対応する自然数がないことは明らか。