Results 1 to 10 of 10

Math Help - Powerset P(N) uncountable proof

  1. #1
    Member
    Joined
    Oct 2009
    Posts
    195

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Tinyboss's Avatar
    Joined
    Jul 2008
    Posts
    433
    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:
    [tex]|\mathcal{P}(\mathbb{N})|=|\mathbb{R}|[/tex]

    gives

    |\mathcal{P}(\mathbb{N})|=|\mathbb{R}|.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2009
    Posts
    195
    Quote Originally Posted by Tinyboss View Post
    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:
    [tex]|\mathcal{P}(\mathbb{N})|=|\mathbb{R}|[/tex]

    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member Tinyboss's Avatar
    Joined
    Jul 2008
    Posts
    433
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2009
    Posts
    195
    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}.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member Tinyboss's Avatar
    Joined
    Jul 2008
    Posts
    433
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Oct 2009
    Posts
    195
    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?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Oct 2009
    Posts
    195
    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by davismj View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by davismj View Post
    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!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: April 22nd 2011, 07:05 AM
  2. Proof of an uncountable set domain produce an infinite sum map
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: September 6th 2009, 02:35 AM
  3. Uncountable proof
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: September 2nd 2009, 06:06 PM
  4. subset and powerset proof by contra
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 7th 2009, 06:26 PM
  5. Replies: 4
    Last Post: October 11th 2008, 01:42 PM

Search Tags


/mathhelpforum @mathhelpforum