# Thread: Powerset P(N) uncountable proof

1. ## Powerset P(N) uncountable proof

Show that the set $P(\mathbb{N})$ is equivalent to $\mathbb{R}$. (From lecture, we know that $P(\mathbb{N})$ is uncountable. The question is how to put this set in a 1-1 correspondence with $\mathbb{R}$.)

\emph{Proof.} Let $x \in \mathbb{R}$ be any real number and ${x_n} \rightarrow x$ a sequence that converges to x in $\mathbb{R}$ such that the ith element of ${x_n}$ is the ith decimal approximation to x. Now, consider the decimal expansion of $x_i = d_0 + d_1(10)^{-1} + \ldots + d_i(10)^{-i}$, and to each $x_i$ correspond the set $\{{d_0},{d_1(10)},\ldots,{(10^i)d_i}\}. \\$

Now, letting $i \rightarrow \infty,$ we have that our x corresponds to the set $\{{d_0},{d_1(10)},\ldots\} \in P(\mathbb{N})$. Since x was arbitrary, this holds for any real number $x \in \mathbb{R}$. Thus, we have established a one-to-one correspondence $\mathbb{R} \mapsto P(\mathbb{N})$, and therefore, $P(\mathbb{N})$ is uncountable.

Is this proof correct? Do I really need a converging sequence to x?

And how do I get LaTeX to show up here?

2. It's probably more convenient to show an injection in each direction, from which you can conclude that the cardinalities are equal.

For P(N)->R, map a subset S of N to the real number less than 1 given in decimal notation by putting a 1 in the nth place after the decimal if n is in S, and a 0 otherwise. Of course, ternary or some other base would work, but not binary--you don't want to mess with non-unique representations of the same real number.

For R->P(N), choose a real number x in (0,1), and represent it in binary. Then do the same thing as above, but in reverse. Every rational number with a power-of-2 denominator has two such representations; choose the terminating one. A bijection between R and (0,1) is all you need to finish (actually, just an injection into (0,1) will do).

To do LaTeX:
$$|\mathcal{P}(\mathbb{N})|=|\mathbb{R}|$$

gives

$|\mathcal{P}(\mathbb{N})|=|\mathbb{R}|$.

3. Originally Posted by Tinyboss
It's probably more convenient to show an injection in each direction, from which you can conclude that the cardinalities are equal.

For P(N)->R, map a subset S of N to the real number less than 1 given in decimal notation by putting a 1 in the nth place after the decimal if n is in S, and a 0 otherwise. Of course, ternary or some other base would work, but not binary--you don't want to mess with non-unique representations of the same real number.

For R->P(N), choose a real number x in (0,1), and represent it in binary. Then do the same thing as above, but in reverse. Every rational number with a power-of-2 denominator has two such representations; choose the terminating one. A bijection between R and (0,1) is all you need to finish (actually, just an injection into (0,1) will do).

To do LaTeX:
$$|\mathcal{P}(\mathbb{N})|=|\mathbb{R}|$$

gives

$|\mathcal{P}(\mathbb{N})|=|\mathbb{R}|$.
We know R is uncountable. Thus to show that P(N) is uncountable, we just have to establish a one to one correspondence from R to P(N).

Is my mapping sufficient?

4. Depends on which statement of the problem is correct. Your title just says "P(N) is uncountable", but the first line says "P(N) is equivalent to R" (which I took to mean they have the same cardinality). If all you want to do is show it's uncountable, I'd suggest Cantor's diagonal argument. Yours seems fine, too, although I'd just say, "choose a decimal expansion of x" instead of worrying about a convergent sequence.

5. I think there's a problem with your mapping from P(N) |-> R:

Consider the following subsets of P(N)

{{1},{2},{3}} and {{1,2,3}}. Wouldn't both map to 0.111?

I guess the hardest part of this problem is mapping the following things distinctly:

{{1},{2},{3}}, {{1,2,3}} and {{123}.

6. We map elements, not subsets, of P(N) into R.

In fact there can be no injection from subsets of P(N) into R, since P(N) has the cardinality of R, and P(P(N)) has strictly greater cardinality.

7. I think I understand a little better, but not entirely.

So we need to map P(N) into R. so P(N) = {{},{1},{2},{3},....{123},...{1,2,3},...}. What do these six distinct elements of P(N) map to?

0, 0.1, 0.01, 0.001, 0.00 . . . 1, and 0.111?

8. Last question. We've established an injection in each direction. According to baby rudin (the book I'm studying out of), equivalence follows a bijection, and our injections are not onto in either direction. I understand intuitively why this is sufficient, but not rigorously.

9. Originally Posted by davismj
Last question. We've established an injection in each direction. According to baby rudin (the book I'm studying out of), equivalence follows a bijection, and our injections are not onto in either direction. I understand intuitively why this is sufficient, but not rigorously.
Have a look at the page.

10. Originally Posted by davismj
Show that the set $P(\mathbb{N})$ is equivalent to $\mathbb{R}$. (From lecture, we know that $P(\mathbb{N})$ is uncountable. The question is how to put this set in a 1-1 correspondence with $\mathbb{R}$.)

\emph{Proof.} Let $x \in \mathbb{R}$ be any real number and ${x_n} \rightarrow x$ a sequence that converges to x in $\mathbb{R}$ such that the ith element of ${x_n}$ is the ith decimal approximation to x. Now, consider the decimal expansion of $x_i = d_0 + d_1(10)^{-1} + \ldots + d_i(10)^{-i}$, and to each $x_i$ correspond the set $\{{d_0},{d_1(10)},\ldots,{(10^i)d_i}\}. \\$

Now, letting $i \rightarrow \infty,$ we have that our x corresponds to the set $\{{d_0},{d_1(10)},\ldots\} \in P(\mathbb{N})$. Since x was arbitrary, this holds for any real number $x \in \mathbb{R}$. Thus, we have established a one-to-one correspondence $\mathbb{R} \mapsto P(\mathbb{N})$, and therefore, $P(\mathbb{N})$ is uncountable.

Is this proof correct? Do I really need a converging sequence to x?

And how do I get LaTeX to show up here?
No one has seemed to mention the wildly applicable Cantor's Theorem (whose proof is simpler than even establishing a bijection $2^{\mathbb{N}}$ and $\mathbb{R}$) which says that $\#(2^{\mathbb{N}}\right)>\aleph_0=\#(\mathbb{N})$ which is the definition of uncountability.

Edit: Man--I should have read the actual posts instead of the title and the responses. Sorry!