# How can I show that the set of reals and the set of pairs of reals have the same cardinality?

How can I show that the set of reals and the set of pairs of reals have the same cardinality?

I know that since reals are uncountable infinite, I can't create a list of reals and talk about the $i^{th}$ real mapping to the $i^{th}$ real pair. So how can I construct a one-to-one and onto mapping $f: \mathbb R \to \mathbb R^2$?

Thank You

-
Try playing around with decimal expansion. – Alex B. Oct 12 '11 at 4:05
It is easier to see with reals in $(0,1)$ and $(0,1) \times (0,1)$. Do you know that all the reals have the same cardinality as the reals in $(0,1)$? – Ross Millikan Oct 12 '11 at 4:14
Rather than explicitly constructing a bijection between $\mathbb R$ and $\mathbb R^2$, which can get a bit tricky, it may be easier to construct surjections in each direction (one is trivial) and apply the law of trichotomy (which holds for cardinality under AC). – Ilmari Karonen Oct 12 '11 at 5:12
This question is closely related: math.stackexchange.com/questions/37834/… – Martin Sleziak Oct 12 '11 at 6:51

If $a$ is the cardinality of $\mathbb N$, then we have $$2^a\cdot2^a=2^{a+a}=2^a.$$

-
shouldn't 2^a+a = 2^(2a) ? – Jeff Oct 12 '11 at 4:54
Yes, we have $a+a=2a=a$ if $a$ is an infinite cardinal number. – Pierre-Yves Gaillard Oct 12 '11 at 4:55
alright, I see but how do i apply this concept to Reals and pairs of reals? – Jeff Oct 12 '11 at 6:15
@Pierre: To be exact, it is not always true that $x+x=x$ for infinite cardinals. However for $\aleph_0$ it is true that $\aleph_0+\aleph_0=\aleph_0$, even without the axiom of choice. – Asaf Karagila Oct 12 '11 at 7:12
Dear @Asaf: Thank you very much for your comment. I always take the axiom of choice for granted. (In fact I adhere to Bourbaki's set theory, and, as you certainly know much better than I, in this theory, the axiom of choice is not a separate axiom, but is "built in".) – Pierre-Yves Gaillard Oct 12 '11 at 8:52

Let the binary expansions of $(x,y)\in[0,1)\times[0,1)$ be $$\begin{array}{} x=\sum_{k=1}^\infty x_k2^{-k}&\text{and}&y=\sum_{k=1}^\infty y_k2^{-k} \end{array}$$ (finite where possible) where $(x_k,y_k)\in\{0,1\}\times\{0,1\}$. Define $f:[0,1)\times[0,1)\mapsto[0,1)$ by $$f(x,y)=\sum_{k=1}^\infty x_k2^{1-2k}+y_k2^{-2k}$$ that is, $f(x,y)$ interleaves the bits of $x$ and $y$. It is easy to see that $f$ is injective, which means the cardinality of $[0,1)\times[0,1)$ is less than or equal to that of $[0,1)$.

Define $g:[0,1)\mapsto[0,1)\times[0,1)$ by $g(x)=(x,0)$. $g$ is injective.

Use the Cantor-Bernstein-Schroeder Theorem to get the existence of a bijection between $[0,1)\times[0,1)$ and $[0,1)$.

-
so R^2 doesn't literaly mean R^2, by R^2 it refers to pairs of Reals. I need to construct the mapping between the reals to pairs of reals. – Jeff Oct 12 '11 at 5:57
@Jeff: what is the difference between $\mathbb{R}^2$ and pairs of reals? $(x,y)\in[0,1)\times[0,1)$ is another way of saying $x\in[0,1)$ and $y\in[0,1)$. – robjohn Oct 12 '11 at 6:06