Prove that the set of all subsets of $N$ is continuum.

214 Views Asked by At

From Cantor's theorem follows that the set of all subsets of $N$ is uncountable.

Cantor's theorem:

If $A$ is any set,then there is no bijection of $A$ onto the set $2^A$

But why this set is continuum? Cardinality of $R$ is continuum but I don't know how prove from this that set given above is also continuum.

Hint: think of an element of $P(N)$ as corresponding to a binary expansion-for a given subset A, let $x=\sum_{i\in A}2^i $ This gives you (almost) a bijection between P(N) and [0,1]

Can you explain why this given bijection?

1

There are 1 best solutions below

0
On

A quick proof would be (if you know that the Cantor set has cardinality $\mathfrak{c})$ every branch of the full binary tree of height $\omega$ is in bijection with $\mathcal{P}(\mathbb{N})$, and every branch corresponds to a single element of the Cantor set by decimal representation in base $3$. Moreover, that correspondence is a bijection.