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