Results 1 to 12 of 12

Math Help - proving that [0,1] has the same cardinality as the power set of N

  1. #1
    Member
    Joined
    Aug 2008
    Posts
    249

    proving that [0,1] has the same cardinality as the power set of N

    The proof in my book starts out with saying each real number in [0, 1] can be expressed as a binary decimal:
    0.\epsilon_1 \epsilon_2 \epsilon_3 ... where \epsilon_i = 0 \ or \ 1 (i = 1, 2, 3, ...)

    Listing out all the real numbers expressed as binary decimals, one can see that it forms a one to one correspondence with the power set of N since the numbers in binary basically represent the different subsets of N.

    however there is a problem with this reasoning. if a binary number ends with an infinite sequence of 0s or 1s then two binary numbers can represent the same real number. therefore it will no longer be a bijection. i can't seem to think of a way to circumvent this problem.

    i tried thinking about matching the 2 equivalent binary numbers with the 2 equivalent decimal numbers that all represent the same real number. that way we would get a bijection but it would be from the set [0, 1] with possibly infinitely many numbers repeated to the power set of N. This would no longer be a bijection between just the set of real numbers in [0, 1] and the power set of N so this doesn't seem to work. any help is greatly appreciated. thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    Re: proving that [0,1] has the same cardinality as the power set of N

    Quote Originally Posted by oblixps View Post
    The proof in my book starts out with saying each real number in [0, 1] can be expressed as a binary decimal:
    0.\epsilon_1 \epsilon_2 \epsilon_3 ... where \epsilon_i = 0 \ or \ 1 (i = 1, 2, 3, ...)

    Listing out all the real numbers expressed as binary decimals, one can see that it forms a one to one correspondence with the power set of N since the numbers in binary basically represent the different subsets of N.

    however there is a problem with this reasoning. if a binary number ends with an infinite sequence of 0s or 1s then two binary numbers can represent the same real number. therefore it will no longer be a bijection. i can't seem to think of a way to circumvent this problem.

    i tried thinking about matching the 2 equivalent binary numbers with the 2 equivalent decimal numbers that all represent the same real number. that way we would get a bijection but it would be from the set [0, 1] with possibly infinitely many numbers repeated to the power set of N. This would no longer be a bijection between just the set of real numbers in [0, 1] and the power set of N so this doesn't seem to work. any help is greatly appreciated. thanks.
    I don't know if you're looking for an explanation of their proof or a different proof. Which is it? If you're looking for an interpretation, I think your issue isn't really an issue. There is a well-definedness issue, but if you just state that there is only one representation of an element of [0,1] as a binary expansion the map is fine.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Feb 2008
    Posts
    410

    Re: proving that [0,1] has the same cardinality as the power set of N

    I don't think you need a bijection. It's okay if two subsets of \mathcal{P}(\mathbb{N}) go to the same value in [0,1]. That will show that \mathcal{P}(\mathbb{N}) is at least as large as [0,1]. And it's easy to show that [0,1] is at least as large as \mathcal{P}(\mathbb{N}). And the conclusion follows.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Aug 2008
    Posts
    249

    Re: proving that [0,1] has the same cardinality as the power set of N

    what i'm having trouble seeing is that, if you just state there there is only one representation of an element of [0, 1] as a binary expansion then it feels like you are "cutting out" or excluding some subsets of N. so although every real number in [0, 1] is mapped to, not every element in the power set of N gets mapped to so my intuition keeps telling me that it shouldn't be a bijection. is there a way to show that this map is still a bijection? i'm having trouble consolidating this part.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    Re: proving that [0,1] has the same cardinality as the power set of N

    Quote Originally Posted by oblixps View Post
    what i'm having trouble seeing is that, if you just state there there is only one representation of an element of [0, 1] as a binary expansion then it feels like you are "cutting out" or excluding some subsets of N. so although every real number in [0, 1] is mapped to, not every element in the power set of N gets mapped to so my intuition keeps telling me that it shouldn't be a bijection. is there a way to show that this map is still a bijection? i'm having trouble consolidating this part.
    Write out, precisely and in full, the math you are trying to interpret. I.e. use LaTeX to write out the map, try to prove bijectivity, and point out where the problem is. If you do that I guarantee we can help you. If you are looking for a different proof, then the obvious choice (as [b]hatsoff[/tex] mentioned) is to appeal to Schroeder-Bernstein theorem, but I don't think this is what you want.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Aug 2008
    Posts
    249

    Re: proving that [0,1] has the same cardinality as the power set of N

    i'll let the map f: [0, 1] \rightarrow B where B is the set of binary expansions of the real numbers in [0, 1]. Now i know that the set B is in bijection with  \mathcal{P}(\mathbb{N}) since each binary expansion represents some subset of the natural numbers and i will call this function g: B \rightarrow \mathcal{P}(\mathbb{N}) . my goal is to show that  g \ o \ f is a bijection by showing that both g and f are bijections. the issue i have is that 2 elements of B map to one element of [0, 1] so f is not a bijection. if i declare that if an element of [0, 1] maps to 2 elements of B, choose the element of B that ends with infinitely many 0s, then what i have now is a bijection but it doesn't seem to be a bijection between [0, 1] and B since i have removed some number of elements from B. If i call the set A to be the set B with the "equivalent) expansions removed, then i have defined a bijection between [0, 1] and A but i need a bijection between [0, 1] and B. i am a little unsure of how the set B and the function f should be defined.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    Re: proving that [0,1] has the same cardinality as the power set of N

    Quote Originally Posted by oblixps View Post
    i'll let the map f: [0, 1] \rightarrow B where B is the set of binary expansions of the real numbers in [0, 1]. Now i know that the set B is in bijection with  \mathcal{P}(\mathbb{N}) since each binary expansion represents some subset of the natural numbers and i will call this function g: B \rightarrow \mathcal{P}(\mathbb{N}) . my goal is to show that  g \ o \ f is a bijection by showing that both g and f are bijections. the issue i have is that 2 elements of B map to one element of [0, 1] so f is not a bijection. if i declare that if an element of [0, 1] maps to 2 elements of B, choose the element of B that ends with infinitely many 0s, then what i have now is a bijection but it doesn't seem to be a bijection between [0, 1] and B since i have removed some number of elements from B. If i call the set A to be the set B with the "equivalent) expansions removed, then i have defined a bijection between [0, 1] and A but i need a bijection between [0, 1] and B. i am a little unsure of how the set B and the function f should be defined.
    Ok, so we'll go down the following route and see if you like it. Consider your map f:[0,1]\to B, demanding that you choose the representation where each thing does not end in infinitely many one's, but instead the one with infinitely many zeros you have defined an injection f:[0,1]\to B, but f is NOT a surjection since .001010\overline{1}\notin\text{im }f. But, right now we don't care. So, we know that f:[0,1]\to B is an injection, and as you noted, one has that the natural map g:B\to 2^{\mathbb{N}} is a bijection (this is easy to prove, I think you already know this, but just in case--evidently B is equipotent to \{0,1\}^{\mathbb{N}} (the set of all functions f:\mathbb{N}\to[0,1]) and you can then check that 2^{\mathbb{N}} is equipotent to \{0,1\}^\mathbb{N} via the map 2^\mathbb{N}\ni S\to \mathbf{1}_S\in \{0,1\}^\mathbb{N} where \mathbf{1}_S is the indicator function of S) so that g\circ f:[0,1]\to 2^\mathbb{N} is an injection. But, consider the map h:2^\mathbb{N}\to[0,1] given by \{s_1,s_2,\cdots\} maps to .s_1s_2\cdots where s_1<s_2<\cdots. In other words, take a subset S\subseteq\mathbb{N}, order it, and then map it to the associated decimal via that ordering. This is obviously an injection. Thus, we have injections [0,1]\to2^\mathbb{N} and 2^\mathbb{N}\to[0,1]. We may then conclude by the Schroeder-Bernstein theorem. Is that satisfactory?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Aug 2008
    Posts
    249

    Re: proving that [0,1] has the same cardinality as the power set of N

    please correct me if i'm wrong but it seems like h is not injective. if i take the subset of  \mathbb{N} to be {12, 34} then the decimal i get is 0.1234 but when i take the subset to be {1, 234} then the decimal i get is 0.1234 as well.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    Re: proving that [0,1] has the same cardinality as the power set of N

    Quote Originally Posted by oblixps View Post
    please correct me if i'm wrong but it seems like h is not injective. if i take the subset of  \mathbb{N} to be {12, 34} then the decimal i get is 0.1234 but when i take the subset to be {1, 234} then the decimal i get is 0.1234 as well.
    Haha, good call! I was being too hasty! One can do an almost inverse to our function [0,1]\to 2^{\mathbb{N}} to get an injection. Namely, carry S to .\epsilon_1\epsilon_2\cdots where \epsilon_k is 1 if k\in S and zero otherwise. This is an injection.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7

    Re: proving that [0,1] has the same cardinality as the power set of N

    Quote Originally Posted by Drexel28 View Post
    Haha, good call! I was being too hasty! One can do an almost inverse to our function [0,1]\to 2^{\mathbb{N}} to get an injection. Namely, carry S to .\epsilon_1\epsilon_2\cdots where \epsilon_k is 1 if k\in S and zero otherwise. This is an injection.
    Is it an injection? If I understand what you're saying, then the subsets \{1\} and \mathbb{N}\setminus\{1\} have the same image in [0,1], since 0.0111... (recurring) is the same as 0.1.

    I think that the simplest way to get an injection from \{0,1\}^\mathbb N} to [0,1] is to map the sequence (x_1,x_2,x_3,\ldots) to the number given by the ternary expansion 0.x_1x_2x_3\ldots. The numbers with an ambiguous binary representation correspond to pairs of distinct numbers in the ternary representation.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    Re: proving that [0,1] has the same cardinality as the power set of N

    Quote Originally Posted by Opalg View Post
    Is it an injection? If I understand what you're saying, then the subsets \{1\} and \mathbb{N}\setminus\{1\} have the same image in [0,1], since 0.0111... (recurring) is the same as 0.1.

    I think that the simplest way to get an injection from \{0,1\}^\mathbb N} to [0,1] is to map the sequence (x_1,x_2,x_3,\ldots) to the number given by the ternary expansion 0.x_1x_2x_3\ldots. The numbers with an ambiguous binary representation correspond to pairs of distinct numbers in the ternary representation.
    I don't understand. How is .0\overline{1}=.1? The left hand side is equal to \frac{1}{90} and the right hand side is equal to \frac{1}{10}.
    Last edited by Plato; August 27th 2011 at 04:47 PM. Reason: LaTeX fix
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7

    Re: proving that [0,1] has the same cardinality as the power set of N

    Quote Originally Posted by Drexel28 View Post
    I don't understand. How is .0\overline{1}=.1? The left hand side is equal to \frac{1}{90} and the right hand side is equal to \frac{1}{10}.
    Ah, I see now: you were using decimal. I thought you were still in binary.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving Equal Cardinality
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 12th 2011, 12:41 PM
  2. Proving cardinality of sets
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: April 29th 2011, 10:54 AM
  3. Power sets and cardinality
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 28th 2009, 01:49 PM
  4. Induction proof: Cardinality of power sets
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 10th 2009, 05:59 PM
  5. Proving Cardinality
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 30th 2008, 01:32 PM

Search Tags


/mathhelpforum @mathhelpforum