There was a question in our exam which wanted us to prove that $\mathbb{R}$ and $\mathbb{R^2}$ both have same Cardinality. My approach to prove this problem was to try to make a bijection between $\mathbb{R}$ and $\mathbb{R^2}$. You can see my proof below, but the teacher assistant gave to my proof 3.5 out of 10! Can you tell me what is wrong with my proof?!

This is my proof:

To prove that $\mathbb{R}$ and $\mathbb{R^2}$ both have same size, it's sufficient to show that there is a bijection between these two. consider $f : \mathbb{R} \rightarrow \mathbb{R^2}$ which images each $x\in \mathbb{R}$ to $(x,0)$. this function is clearly one to one.

Assume another function $g : \mathbb{R^2} \rightarrow \mathbb{R}$.The function formula is this:

give any $(x,y) \in \mathbb{R^2}$ . Write x and y by their standard decimal expansion (you can't use infinitely many 9 in expansion), so $(x,y)=(A_0A_1...A_n.a_0a_1...., B_0B_1...B_m.b_0b_1...)$ without loss of generalitty assume that $m\ < n$ . say $g(x,y)=A_0B_0A_1b_1...A_mB_mA_{m+1}...A_n.KFa_0b_0a_1b_1....$, which $K=0$ if x is positive and $K=1$ if x is not. and Also $F=0$ if y is positive and $ F=1$ if y is not. it's obvious that the function $g$ is one to one.

so by using the Schroeder-Bernstein Theorem there is a bijection between $\mathbb{R}$ and $\mathbb{R^2}$.

So, we proved that $\mathbb{R} \sim \mathbb{R^2}$ .

  • 1
    $\begingroup$ Is $g$ well-defined? As you know, decimal expression for rationals is not unique. $\endgroup$ – Hanul Jeon May 5 '15 at 15:04
  • $\begingroup$ @tetori yeah I've mentioned it there, I said that we must use standard decimal expansions (we can't use infinitely many 9 for example). $\endgroup$ – F.K May 5 '15 at 15:06
  • 1
    $\begingroup$ My comment was about the integer parts. Suppose that the encoded version has $12345$ before the decimal point. How do we recover the integer parts of $x$ and $y$? There are several possibilities. It can be fixed, but as it stands it is incorrect. Still, if that was the only gap, then $3.5/10$ seems a little harsh. $\endgroup$ – André Nicolas May 5 '15 at 15:34
  • 2
    $\begingroup$ In short, the problem is that it is absolutely not obvious that $g$ is one-to-one. $\endgroup$ – Jack M May 5 '15 at 15:37
  • 1
    $\begingroup$ A preliminary bijection of $\mathbb{R}$ with $(0,1)$, giving a bijection of $\mathbb{R}^2$ with $(0,1)^2$, is useful, we get rid of the integer parts issue. It means you don't need to encode signs in the first $2$ places after the decimal point, and avoids the integer parts issue. In my comment I was dealing with salvaging your approach. $\endgroup$ – André Nicolas May 5 '15 at 16:32

Your map is in fact not injective. Note that it sends $(100,1)$ and $(10,10)$ to $1100$.

The reason for the low score is most likely that one can't simply say "it's obvious" that the map is injective. While we can modify the integer parts to be injective (say, by using a canonical mapping from $\mathbb Z^2$ to $\mathbb Z$), it's necessary to give an actual argument that the function is injective. So we need to describe a process for recovering the sign, integer part, and decimal part.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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