Proof that QXQ is countable infinite

[Steven G]

[math]\mbox{Prove that } \mathbb{Q}\times\mathbb{Q} \mbox{ is countably infinite.}[/math]
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

 

[pka]

[math]\mbox{Prove that } \mathbb{Q}\times\mathbb{Q} \mbox{ is countably infinite.}[/math]
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 \).

 

[lookagain]

[math]\mbox{Prove that } \mathbb{Q}\times\mathbb{Q} \mbox{ is countably infinite.}[/math]
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:

proof of rationals are countable - Google Search

:

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 \} \)