4
$\begingroup$

Is $2^{|\mathbb{N}|} = |\mathbb{R}|$? If so, how?

I was reading the Wiki page on the , and it says "Moreover, $\mathbb{R}$ has the same number of elements as the power set of $\mathbb{N}$", but I don't see how this is true?

I feel like it has something to do with binary, but I'm not too sure how it works? Do I have to show a map of all reals can be done in binary? I'm just very confused, and any advice would be appreciated!

  • 0
    and see this http://math.stackexchange.com/questions/1885700/cardinality-of-power-set-of-mathbb-n-is-equal-to-cardinality-of-mathbb-r/1885782 . Basically you can map $\{0,1\}^N$ to [0,1] via mapping $(x_1,x_2, x_3,..... )$ to $\sum x_i/2^i$. The sum is a decimal expansion but written in binary. So the set of such sums is all reals between [0.1]. It's a simple matter to show $|[0,1]| = |\mathbb R|$. So we have $|\{0,1\}^N| = 2^N = |[0,1]| = |\mathbb R|$2016-08-09

2 Answers 2

4

In short: A binary number $0.a_1a_2a_3\ldots$ can be identified with the set $\{n\in \mathbb N\mid a_n\ne 0\}$. A few details have to be checked, though

  • 0
    This maps the set of all {a1,a2,a3...} to {0.a1a2a3....} = [0.0000....,0.111111....] = [0,1] without duplicates as 0.11111.... = 1 but we don't have 1.0 represented. So that's fine. But we've shown it is 1-1 to [0,1] and not the reals. We can map [0, \infty) to [0,1) by mapping x to x/(x+1) and we can map (-\infty, 0] to (- 1, 0] by mapping x to x/(x - 1) so we can map (-infty, infty) to (-1, -1) which we can map to (0,1). getting 0 and 1 in there as well is an issue but it is minor.2016-08-09
0

You can have a bijection from $\{0,1\}^{\mathbb N}$ to $\mathbb P(\mathbb N)$. Take the vector $a\in \{0,1\}^{\mathbb N} $ and map it to $A\subset \mathbb N$ with $i \in A \Leftrightarrow a_i = 1$. (It's easy to show that is a bijection)

Now as $|\mathbb P(\mathbb N)| = |\mathbb R|$, you can construct a bijection from $\{0,1\}^{\mathbb N}$ to $\mathbb R$. Note that I have used $\{0,1\}$ instead of your 2.