# Proof that QXQ is countable infinite

#### Jomo

##### Elite Member
$$\displaystyle \mbox{Prove that } \mathbb{Q}\times\mathbb{Q} \mbox{ is countably infinite.}$$

Can some of you please give me a nice proof for this? I just don't like the way I am seeing it.
Thanks,
Steve

Last edited by a moderator:

#### pka

##### Elite Member
$$\displaystyle \mbox{Prove that } \mathbb{Q}\times\mathbb{Q} \mbox{ is countably infinite.}$$

Can some of you please give me a nice proof for this? I just don't like the way I am seeing it.
This must be done in steps.
1. If there exists an injection( one-to-one) a set $$\displaystyle A$$ to a set $$\displaystyle B$$ then the cardinally of $$\displaystyle A$$ is no more than that of $$\displaystyle B$$.
2. Define a function $$\displaystyle \Theta : \mathbb{Z}^+\times\mathbb{Z}^+\to \mathbb{Z}^+$$ by $$\displaystyle \Theta(m,n)=2^m\cdot 3^n$$.
3. Now show that $$\displaystyle \Theta$$ is an injection so that the set $$\displaystyle \mathbb{Z}^+\times\mathbb{Z}^+$$ is countable.
4. Once we have that we extend that idea to any countable set, i.e. $$\displaystyle Q \times Q$$ is countable for any countable set $$\displaystyle Q$$.

Last edited by a moderator:
• Jomo and topsquark

#### lookagain

##### Senior Member
$$\displaystyle \mbox{Prove that } \mathbb{Q}\times\mathbb{Q} \mbox{ is countably infinite.}$$

Can some of you please give me a nice proof for this?
I feel I can present to you a demonstration.
The common demonstration of diagonal paths and switching back and forth to show that Q is countably infinite is
shown among these at this link:

:

If you write those fractions that do not repeat a value as members in the set Q, you would have:

$$\displaystyle Q \ = \ \{\tfrac11,\tfrac21,\tfrac12,\tfrac13,\tfrac31,\tfrac41,\tfrac32,\tfrac23,\tfrac14, ...\} \$$

Then, $$\displaystyle \ Q \times Q \ = \ \{\tfrac11,\tfrac21,\tfrac12,\tfrac13,\tfrac31,\tfrac41,\tfrac32,\tfrac23,\tfrac14, ...\} \ \times \ \{\tfrac11,\tfrac21,\tfrac12,\tfrac13,\tfrac31,\tfrac41,\tfrac32,\tfrac23,\tfrac14, ...\} \$$

This can be put into a similar style of listing as Q:

$$\displaystyle (\tfrac11,\tfrac11) \ \ (\tfrac11,\tfrac21) \ \ (\tfrac11,\tfrac12) \cdot \cdot \ \cdot$$
$$\displaystyle (\tfrac21,\tfrac11) \ \ (\tfrac21,\tfrac21) \ \ (\tfrac21,\tfrac12) \cdot \cdot \ \cdot$$
$$\displaystyle (\tfrac12,\tfrac11) \ \ (\tfrac12,\tfrac21) \ \ (\tfrac12,\tfrac12) \cdot \cdot \ \cdot$$
$$\displaystyle \cdot$$
$$\displaystyle \cdot$$
$$\displaystyle \cdot$$

So, using the similar diagonal listing, and not repeating duplicate pairs,

$$\displaystyle \ Q \times Q \ = \ \{(\tfrac11,\tfrac11), (\tfrac21,\tfrac11) ,(\tfrac11,\tfrac21), (\tfrac11,\tfrac12), (\tfrac21,\tfrac21), (\tfrac12,\tfrac11), (\tfrac13,\tfrac11), \cdot \cdot \ \cdot \}$$

Last edited by a moderator:
• Jomo and topsquark