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

1. ## 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:
$\displaystyle 0.\epsilon_1 \epsilon_2 \epsilon_3 ...$ where $\displaystyle \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.

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

Originally Posted by oblixps
The proof in my book starts out with saying each real number in [0, 1] can be expressed as a binary decimal:
$\displaystyle 0.\epsilon_1 \epsilon_2 \epsilon_3 ...$ where $\displaystyle \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 $\displaystyle [0,1]$ as a binary expansion the map is fine.

3. ## 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 $\displaystyle \mathcal{P}(\mathbb{N})$ go to the same value in $\displaystyle [0,1]$. That will show that $\displaystyle \mathcal{P}(\mathbb{N})$ is at least as large as $\displaystyle [0,1]$. And it's easy to show that $\displaystyle [0,1]$ is at least as large as $\displaystyle \mathcal{P}(\mathbb{N})$. And the conclusion follows.

4. ## 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.

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

Originally Posted by oblixps
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.

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

i'll let the map $\displaystyle 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 $\displaystyle \mathcal{P}(\mathbb{N})$ since each binary expansion represents some subset of the natural numbers and i will call this function $\displaystyle g: B \rightarrow \mathcal{P}(\mathbb{N})$. my goal is to show that $\displaystyle 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.

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

Originally Posted by oblixps
i'll let the map $\displaystyle 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 $\displaystyle \mathcal{P}(\mathbb{N})$ since each binary expansion represents some subset of the natural numbers and i will call this function $\displaystyle g: B \rightarrow \mathcal{P}(\mathbb{N})$. my goal is to show that $\displaystyle 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 $\displaystyle 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 $\displaystyle f:[0,1]\to B$, but $\displaystyle f$ is NOT a surjection since $\displaystyle .001010\overline{1}\notin\text{im }f$. But, right now we don't care. So, we know that $\displaystyle f:[0,1]\to B$ is an injection, and as you noted, one has that the natural map $\displaystyle 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 $\displaystyle B$ is equipotent to $\displaystyle \{0,1\}^{\mathbb{N}}$ (the set of all functions $\displaystyle f:\mathbb{N}\to[0,1]$) and you can then check that $\displaystyle 2^{\mathbb{N}}$ is equipotent to $\displaystyle \{0,1\}^\mathbb{N}$ via the map $\displaystyle 2^\mathbb{N}\ni S\to \mathbf{1}_S\in \{0,1\}^\mathbb{N}$ where $\displaystyle \mathbf{1}_S$ is the indicator function of $\displaystyle S$) so that $\displaystyle g\circ f:[0,1]\to 2^\mathbb{N}$ is an injection. But, consider the map $\displaystyle h:2^\mathbb{N}\to[0,1]$ given by $\displaystyle \{s_1,s_2,\cdots\}$ maps to $\displaystyle .s_1s_2\cdots$ where $\displaystyle s_1<s_2<\cdots$. In other words, take a subset $\displaystyle 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 $\displaystyle [0,1]\to2^\mathbb{N}$ and $\displaystyle 2^\mathbb{N}\to[0,1]$. We may then conclude by the Schroeder-Bernstein theorem. Is that satisfactory?

8. ## 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 $\displaystyle \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.

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

Originally Posted by oblixps
please correct me if i'm wrong but it seems like h is not injective. if i take the subset of $\displaystyle \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 $\displaystyle [0,1]\to 2^{\mathbb{N}}$ to get an injection. Namely, carry $\displaystyle S$ to $\displaystyle .\epsilon_1\epsilon_2\cdots$ where $\displaystyle \epsilon_k$ is $\displaystyle 1$ if $\displaystyle k\in S$ and zero otherwise. This is an injection.

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

Originally Posted by Drexel28
Haha, good call! I was being too hasty! One can do an almost inverse to our function $\displaystyle [0,1]\to 2^{\mathbb{N}}$ to get an injection. Namely, carry $\displaystyle S$ to $\displaystyle .\epsilon_1\epsilon_2\cdots$ where $\displaystyle \epsilon_k$ is $\displaystyle 1$ if $\displaystyle k\in S$ and zero otherwise. This is an injection.
Is it an injection? If I understand what you're saying, then the subsets $\displaystyle \{1\}$ and $\displaystyle \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 $\displaystyle \{0,1\}^\mathbb N}$ to [0,1] is to map the sequence $\displaystyle (x_1,x_2,x_3,\ldots)$ to the number given by the ternary expansion $\displaystyle 0.x_1x_2x_3\ldots.$ The numbers with an ambiguous binary representation correspond to pairs of distinct numbers in the ternary representation.

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

Originally Posted by Opalg
Is it an injection? If I understand what you're saying, then the subsets $\displaystyle \{1\}$ and $\displaystyle \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 $\displaystyle \{0,1\}^\mathbb N}$ to [0,1] is to map the sequence $\displaystyle (x_1,x_2,x_3,\ldots)$ to the number given by the ternary expansion $\displaystyle 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 $\displaystyle .0\overline{1}=.1$? The left hand side is equal to $\displaystyle \frac{1}{90}$ and the right hand side is equal to $\displaystyle \frac{1}{10}$.

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

Originally Posted by Drexel28
I don't understand. How is $\displaystyle .0\overline{1}=.1$? The left hand side is equal to $\displaystyle \frac{1}{90}$ and the right hand side is equal to $\displaystyle \frac{1}{10}$.
Ah, I see now: you were using decimal. I thought you were still in binary.

,
,

,

# cardinality of power set of natural numbers

Click on a term to search for related topics.