Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have learnt that the cardinality of the power set of the natural numbers is equal to the cardinality of the real numbers. What is the function that gives the one-to-one correspondence between these two sets?

I have also learnt that there exists no set whose cardinality is strictly between the natural numbers and the real numbers. Is there a proof of this or at least some intuitiveness behind it?

share|improve this question
1  
not elementary: en.wikipedia.org/wiki/Continuum_hypothesis –  Vinicius M. Nov 5 '13 at 22:45
    
The simplest function (though one must elaborate to get rid of a few kinks) is : Interprete a subset $A$ of $\mathbb N$ as a 0-1-sequence ($a_n=1$ iff $n\in A$) and then interprete that sequence as a binary exoansion of a rea number. –  Hagen von Eitzen Nov 5 '13 at 22:47

3 Answers 3

up vote 2 down vote accepted

It's not quite correct to ask for "the function", because if there is one then there are many. Moreover, explicit bijections are highly overrated. We can write one, but it's much much oh so much easier to use the Cantor-Bernstein theorem, and simply exhibit two injections.

If you do insist on writing an actual bijection, let me identify $\mathcal P(\Bbb N)$ with infinite binary sequences (which is quite standard). Now let me describe the steps. We would like to take a binary sequence to the real number in $[0,1]$ which has this binary string as an expansion. However some numbers, e.g. $\frac12=0.1\bar0_2=0.0\bar1_2$, one sequence with finitely many $1$'s and the other has finitely many $0$'s.

  1. First enumerate all the strings which contain finitely many $0$'s the strings containing finitely many $1$'s. One can show that both sets are countably infinite, one can even enumerate them in a very nice way. Write them as $p_n$ for the $n$-th sequence with finitely many zeros and $q_n$ for the $n$-th sequence with finitely many $1$'s.

    The next step is to take $f\colon2^\Bbb N\to2^\Bbb N$ defined as: $$f(x)=\begin{cases} q_{2k} & x=p_k\\ q_{2k+1} & x=q_k\\ x &\text{otherwise}\end{cases}$$ Easily this is an injection whose range is $2^\Bbb N\setminus\{p_n\mid n\in\Bbb N\}$.

  2. Now map $x\in\Bbb N$ to $r\in[0,1)$ such that, $$r=\sum_{n\in\Bbb N}\frac{f(x)(n)}{2^{n+1}}$$ that is the real number whose binary expansion is $f(x)$. One can show that this is a surjective function, since if a number has a binary expansion then it has one which has infinitely many $0$'s. It is also injective since if a real number one has two different binary expansions then we can show that exactly one of them has finitely many $0$'s and the other finitely many $1$'s. But since we use $f(x)$, this is impossible.

  3. Find a bijection between $[0,1)$ and $\Bbb R$. Usually one does that by first "folding $0$ in" and having a bijection between $[0,1)$ and $(0,1)$ and then using something like $\frac{2x-1}{x(x-1)}$ or a similar function for a bijection with $\Bbb R$.


Using the Cantor-Bernstein theorem is much easier.

  1. First note that that $\Bbb R$ can inject into $\mathcal P(\Bbb Q)$ by mapping $r$ to $\{q\in\Bbb Q\mid q<r\}$. Since $\Bbb Q$ is countable there is a bijection between $\cal P(\Bbb Q)$ and $\cal P(\Bbb N)$. So $\Bbb R$ injects into $\cal P(\Bbb N)$.

  2. Then note that we can map $x\in2^\Bbb N$ to the continued fraction defined by the sequence $x$. Or to a point in $[0,1]$ defined by $\sum\frac{x(n)}{3^{n+1}}$, which we can show is injective in a somewhat easier proof.

Finally, as mentioned the last part is false. From the usual axioms of modern set theory (read: $\sf ZFC$) we cannot prove nor disprove that there are no intermediate cardinalities between $\Bbb N$ and $\Bbb R$. The proof of that is difficult and require a deep understanding of modern [read: axiomatic] set theory, as well logic.

If the last part somehow confused you, perhaps my answer to this question can help, Why is the Continuum Hypothesis (not) true?.

share|improve this answer
    
"First note that that R can inject into P(Q) by mapping r to {q∈Q∣q<r}." - Could you explain why this is? –  LTS Nov 6 '13 at 8:03
    
Oliver, given $r_1\neq r_2$ then either $r_1<r_2$ or $r_2<r_1$. Assume the first holds, then there is a rational $q$ such that $r_1<q<r_2$. Now we have that the set associated with $r_2$ includes $q$, whereas the set associated with $r_1$ does not. So the map is injective. –  Asaf Karagila Nov 6 '13 at 8:05
    
Thanks, I'm convinced, but it does seem strange that between any two real numbers there is a rational, when the real numbers have a larger cardinality than the rational numbers. –  LTS Nov 6 '13 at 8:26
    
Yes, it is strange. Then you get used to the idea, then you finally understand the idea (because you had time to understand the mathematics behind it). –  Asaf Karagila Nov 6 '13 at 8:27
1  
What is the largest rational below $e$? –  Asaf Karagila Nov 6 '13 at 13:04

An explicit mapping is difficult to write out. But you can see one possible way on constructing it through this argument showing that the power set of $\mathbb{Z}$ and $\mathbb{R}$ have the same cardinality. I'll start by showing $\mathbb{R}$ is uncountable and then use that idea to show that the two sets have the same cardinality.

First, we show the classic Cantor proof that $\mathbb{R}$ is uncountable. It would suffice to show that $[0,1]$ is uncountable. We assume that every real number $x\in [0,1]$ has a decimal expansion that does not end in an infinite sequence of 9's. Suppose that $\mathbb{R}$ is countable. We could then construct a bijection from $\mathbb{Z}_+$ to $[0,1]$. Writing out $x$'s decimal expansion,$$x_1 = n_{1,1}n_{1,2},\cdots,n_{1,j}$$ $$ x_2 = n_{2,1}n_{2,2},\cdots,n_{2,j}$$ and so on, where $n_{i,j}$ is some number in $\{0,1,2,3,4,5,6,7,8,9\}$. Suppose all the number appeared in the order we wrote above. Now let $y_j=1$ if $n_{j,j}=0$ and $y_j=0$ if $n_{j,j}>0$. But we now have disagreement with $y_j$ and $x_j$ at the $n$th position! So $y_{j}$ is not on our list. However, $y_j$ is a real number. Therefore, the interval $[0,1)$ is uncountable. Moreover, the reals are uncountable.

Now we define a function $f: [0,1)\rightarrow \mathbb{Z}_+$. Notice $x \in [0,1)$ has a unique binary expansion (as the previous restriction on non repeating infinite 9's is equivalent to non infinite repeating 1's). So $x=\sum_{i=1}^{\infty} \, \frac{x_i}{2^i}$, where each $x_i$ is either 0 or 1. So we have $f(x)=\{i \, \, | \, \, i \in \mathbb{Z}_+ \wedge x_i=1\}$ as an injection. Notice that we can also define an injection $g:P(\mathbb{Z}_+)\rightarrow [0,1)$ by $x_{i,n}=0$ if $i \notin n$ and $x_{i,n}=1$ if $i \in n$, where $n\in P(\mathbb{Z}_+)$. Then using the ordinary decimal expansion on $n$, we have an injection. Then by the Cantor-Schroeder-Bernstein Theorem, there is a bijective function from $P(\mathbb{Z}_+)$ and $[0,1)$. But we have injective function $h(x)=\frac{x}{2}$ from $[0,1]$ to $[0,1)$ and the injective function $i(x)=x$ from $[0,1)$ to $[0,1]$. Hence, there is a bijective function from $[0,1]$ to $[0,1)$. Therefore, there is a bijective function from $P(\mathbb{Z}_+)$ to $\mathbb{R}$. So they must have the same cardinality, but by above, $\mathbb{R}$ is uncountable. Then $P(\mathbb{Z})$ is uncountable and of the same cardinality as $\mathbb{R}$.

As for your other question, it is not known if there is a set with cardinality between that of $\mathbb{N}$ and $\mathbb{R}$. It is certainly not a trivial question and is known as the Continuum Hypothesis.

share|improve this answer
    
This part confuses me "Now let $y_j=1$ if $n_{j,j}=0$ and $y_j=0$ if $n_{j,j}>0$" –  LTS Nov 5 '13 at 23:04
    
Sorry, I did this a long time ago for a homework set. We are constructing a number that can't be in the list above (that is, it can't be any of the $x_i$). We call this new number $y$ and it's decimal digits are given by $y_i$. So $y_1$ is the first digit after the decimal and so on. Now start at the first number in our 'countable list $x_1$, if the digit in the 1st spot is $0$, let $y_1=1$ and if its not zero let $y_1=0$. Then look at the second decimal digit of $x_2$, if it is $0$ then $y_2=1$ and if it is not $0$, then $y_2=0$. Continue this process indefinitely. –  mathematics2x2life Nov 5 '13 at 23:13
    
....(continued from above). Now think carefully. This number $y$ we have just made can't be in the list. So it isn't any one of the $x_i$. But this is a contradiction! We just listed all of the 'countably' many reals in $[0,1]$. So the real numbers in $[0,1]$ must be uncountable. Therefore, the real numbers are uncountable. –  mathematics2x2life Nov 5 '13 at 23:14
    
Later we use the fact because $[0,1]$ is uncountable that $[0,1)$ is uncountable, which is obvious. –  mathematics2x2life Nov 5 '13 at 23:16

The easiest method I know of is to relate elements in $\mathcal{P}(\mathbf{N})$ to binary sequences in $(0,1)$. For any $A \subset \mathbf{N}$ there is a natural sequence $(a_n)$ such that $a_n = 1$ if $n \in A$, $a_n=0$ if $n \notin A$. Then, we can view any $x\in (0,1)$ as $\sum_{n=1}^{\infty}\frac{a_n}{2^n}$, where $a_i \in \{0,1\}$.

Once you have this, use the map $x \mapsto f(x)=\tan(\pi (x-1/2))$ to produce all real numbers. You must be slightly careful, though, since rational numbers yield two real representations. However, the idea should be clear and give you some insight for why this is true.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.