Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\sim$ be the equivalence relation on $\mathbb{R}$ defined by: for all x,y in $\mathbb{R}$:

$ x\sim y$ iff $x - y \in \mathbb{Q}$

I also have an equivalence relation at $\mathbb{R^2}$ defined by: ($x_0$, $x_1$) $\sim_2$ ($y_0$, $y_1$) if and only if $x_0 - y_0 \in \mathbb{Q}$ and $x_1 - y_1 \in \mathbb{Q}$

Proof that the structure ($\mathbb{R}$,$\sim$) is isomorphic with ($\mathbb{R^2}$,$\sim_2$)

I already know in both structures I have countable many elements per equivalence class, and there are uncountably many, the same cardinality as $\mathbb{R}$, of that classes. So I wanted to make such an isomorphism that sends classes to other classes, but I don't know how to do it.

Is it sufficient to use the axiom of choice uncountable many times to choose a new class every time?

share|cite|improve this question

Constructing an explicit bijection is going to be hard and not particularly enlightening. The intended solution is most probably more abstract than that.

Do you already know that $|A\times B|=\max(|A|,|B|)$ when at least one of $A$ and $B$ is infinite?

Can you prove that each equivalence class (in both structures) is countably infinite?

Since $|\mathbb R|=|\mathbb R^2|$, what does this say about the number of equivalence classes in each structure? (Hint: not merely that there are "uncountably many").

If you can show that there are equally many equivalence classes, what you have proved is exactly that there is some bijection between one set of equivalence classes and the other, no matter that you may not have a nice way to define that bijection.

share|cite|improve this answer
Thanks! I see now I was not quite specific about the number of equivalence classes but I already knew that they are as many as $\mathbb{R}$. What's hard for me to get is the last part. Is it right that I need the axiom of choice to conclude I can make a bijection, out of the fact that I have equally many equivalence classes on both sides? – Suze Oct 24 '12 at 18:35
@Loes: Once you know there are equally many equivalence classes, you don't need Choice to conclude that there is a bijection that takes equivalence classes to equivalence classes. (This is exactly what "equally many" means). But you do need Choice in order to extend this bijection to a bijection that works on individual elements and goes directly $\mathbb R\to\mathbb R^2$. Specifically, you need to choose a bijection between each equivalence class and $\mathbb N$ for all equivalence classes simultaneously. – Henning Makholm Oct 24 '12 at 18:39

One way is to start with a bijection $\varphi:\Bbb Q\to\Bbb Q^2$. $\Bbb Q$ is one of the $\sim_1$-equivalence classes, and $\Bbb Q^2$ is one of the $\sim_2$-equivalence classes, so this is at least a start. Now we want to extend $\varphi$ to a bijection $\widehat\varphi:\Bbb R\to\Bbb R^2$ in such a way that for all $x,y\in\Bbb R$, $x\sim_1 y$ iff $\widehat\varphi(x)\sim_2\widehat\varphi(y)$.

One nice way is to appeal to the axiom of choice twice to get a set $A\subseteq\Bbb R$ that contains exactly one member of each $\sim_1$-class except the class $\Bbb Q$ and a set $B\subseteq\Bbb R^2$ that contains exactly one member of each $\sim_2$-class except the class $\Bbb Q^2$. $|A|=|B|=|\Bbb R|$ (why?), so there is a bijection $\psi:A\to B$. Now let

$$\widehat\varphi:\Bbb R\to\Bbb R^2:x\mapsto\begin{cases} \varphi(x),&\text{if }x\in\Bbb Q\\ \psi(a)+\varphi(x-a),&\text{if }x\sim_1 a\in A\;, \end{cases}$$

and prove that $\widehat\varphi$ has the desired properties. (Addition in $\Bbb R^2$ is, as usual, component-wise.)

share|cite|improve this answer

Your Answer


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.