3
$\begingroup$

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

  • 0
    @Jeff: The fact that the reals are uncountable does not mean that you cannot create a list of them. It just means that the list will be vastly longer than $\mathbb N$, and you'll need a longer set of indices.2011-10-12

2 Answers 2

3

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

  • 1
    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".)2011-10-12
2

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)$.

  • 1
    @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)$.2011-10-12