Proof that QXQ is countable infinite

Jomo

Elite Member
Joined
Dec 30, 2014
Messages
3,529
\(\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
Joined
Jan 29, 2005
Messages
8,102
\(\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:

lookagain

Senior Member
Joined
Aug 22, 2010
Messages
2,407
\(\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:
Top