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?

  • 4
    $\begingroup$ Just because both are uncountable is no guarantee that a bijection exists. There are, in fact, infinitely many nonequivalent uncountable cardinalities, starting with $\mathbb{R}$, and then $\mathcal{P}(\mathbb{R})$, and $\mathcal{P}(\mathcal{P}(\mathbb{R}))$, and $\mathcal{P}(\mathcal{P}(\mathcal{P}(\mathbb{R})))$, and ... $\endgroup$ – Lee Mosher Jun 15 '16 at 1:06

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 $$

  • $\begingroup$ What if we map $A\subset N$ to $\sum_{a\in A} 2\cdot 3^{-(a+1)}$ then we map the Cantor set into $[0,1]$? In such a way we almost circumvent the patch, we just need to deal with the endpoints, that is easy: given an enumeration of the rational numbers in $[0,1]$ such that $q_0=0$ and $q_1$, we send $q_n$ into $q_{n+2}$. $\endgroup$ – Jack D'Aurizio Jun 15 '16 at 2:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.