Bijection from $\mathcal{P}(\mathbb{N})$ to $(0,1)$

Question

How can we construct a bijection from $\mathcal{P}(\mathbb{N})$ to $(0,1)$?

Here is what I know:

• $\mathcal{P}(\mathbb{N}) = \{A | A \text{ is a subset of } \mathbb{N}\}$

• Both $\mathcal{P}(\mathbb{N})$ and $(0,1)$ are uncountable, so such bijection exists <--- incorrect

• There are uncountable many functions from $(0,1)$ to $\mathbb{N}$

So I seek a bijection function that takes a set $A \in \mathcal{P}(\mathbb{N}) \mapsto x \in (0,1)$ and back...I don't see how this can be done

Is anyone familiar with this result?

Answer 1

The result is well known. There's a straightforward program for establishing it (although the last step is irritating):

• Subsets correspond to indicator functions
• Functions on $\mathbb{N}$ correspond to sequences
• Relate Boolean sequences to binary numerals
• Patch up the argument to deal with the countably many real numbers that have two different binary representations

e.g. the set of even natural numbers would correspond to the binary numeral

$$ 0.101010101010\ldots$$

(which is $2/3$). The set of primes would correspond to

$$ 0.001101010001\ldots$$

Without the patch, both the set $\{ 0 \}$ and the set of all positive natural numbers would correspond to $1/2$: i.e. to the numerals

$$ 0.100000\ldots $$ $$ 0.011111\ldots $$