- Thread starter Jomo
- Start date

- Joined
- Jan 29, 2005

- Messages
- 7,797

This must be done in steps.\(\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.

- 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\).
- Define a function \(\displaystyle \Theta : \mathbb{Z}^+\times\mathbb{Z}^+\to \mathbb{Z}^+\) by \(\displaystyle \Theta(m,n)=2^m\cdot 3^n\).
- Now show that \(\displaystyle \Theta\) is an injection so that the set \(\displaystyle \mathbb{Z}^+\times\mathbb{Z}^+\) is countable.
- 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:

I feel I can present to you a\(\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?

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: