Prove that $|\mathbb{Q}| = |\mathbb{Q} \times \mathbb{Q}|$

Question

I have a discrete maths question that requires me to prove the cardinality of the rationales is the same as the cardinality of the Cartesian product of the rationales. I have a feeling it is easy to prove this using Schroder-Bernstein theorem. And this is what I've got so far:

Define $f: \mathbb{Q} \to \mathbb{Q} \times \mathbb{Q}$ in the following way:

for $a/b \in \mathbb{Q}$, and $\gcd(a,b)=1, f(a,b) = (a,b)$ and it is easy to show this is an injection, but what about the other around? (i.e. to find an injection from $\mathbb{Q} \times \mathbb{Q} \to \mathbb{Q}$)

Any help would be appreciated!

Thanks :)

Answer 1

If your aim is not about finding an explicit bijection but just some injections in order to use Cantor-Bernstein theorem then the simplest way is to invoke the mapping of countable sets with $\mathbb N$.

For instance since there exists an injection $\phi: \mathbb Q\hookrightarrow \mathbb N$, let's map all elements of the first $\mathbb Q$ to $2^n$ and the ones of the second $\mathbb Q$ to $3^m$.

Then you inject $\mathbb Q^2$ into $\{2^n3^m\mid (m,n)\in\mathbb N^2\}\subset\mathbb N$ with $\psi(q_1,q_2)=2^{\phi(q_1)}3^{\phi(q_2)}$.

This reduces the problem in exhibiting such a $\phi$ but again $\mathbb Q^+$ is not much different from $\mathbb N^2$ and you can use the same method.

If $q=\frac ab$ then define $\phi$ as $\phi(q)=2^a3^b$ and you are done.

You can refine a bit to deal with negatives (for instance multiply by $5$ is $a<0$), but this is the principle.

The difficulty is hidden when you use Cantor-Bernstein theorem.

Answer 2

Since $|\mathbb Q|=|\mathbb N|$ you have that $|\mathbb Q^2| = |\mathbb N^2|$. By diagonal enumeration of pairs of natural numbers you have $|\mathbb N^2|=|\mathbb N|$. So we get

$$|\mathbb Q^2|=|\mathbb N^2|=|\mathbb N|=|\mathbb Q|$$

---

If you want to produce a concrete mapping note that every rational number can be written as uniquely as:

$$q = \prod p_j^{\alpha_j}$$

Where $\alpha_j\in\mathbb Z$ and that $\alpha_j$ eventually will be zero all the way to infinity (and $p_j$ is the prime numbers starting with index 0). To map a pairs of rational numbers you just interleave theirs corresponding sequences of exponents - which is a bijective operation since we can deinterleave it. That is:

$$\phi\left(\prod p_j^{\alpha_j}, \prod p_j^{\beta_j}\right) = \prod p_{2j}^{\alpha_j}p_{2j+1}^{\beta j} $$