3
$\begingroup$

I was asked to prove that $\mathbb{Q}$ is countable. Though there are several proofs to this I want to prove it through a specific argument.

Let $\mathbb{Q} = \{x|n.x+m=0; n,m\in\mathbb{Z}\}$

I would like to go with the following argument: given that we know $\mathbb{Z}$ is countable, there are only countable many n and countable many m , therefore there can only be countable many equations AND COUNTABLE MANY SOLUTIONS.

The instructor told me that though he liked the argument, it doesn't follow directly that there can only be countable many solutions to those equations. Is there any way of proving that without it being a traditional proof of "$\mathbb{Q}$ is countable"?

  • 0
    Although it h$a$s some gaps, as noted in Henning’s answer, it’s an original approach that shows some thought.2012-09-11

2 Answers 2

3

Your argument can work, but as presented here there are several gaps in it to be closed:

  • Your definition of $\mathbb Q$ does not work unless you exclude the case $m=n=0$ -- otherwise everything is a solution. (Thanks, Brian).
  • You need to point out explicitly that each choice of $n$ and $m$ has at most one solution.
  • Just because there are countably many choices for $n$ and countably many choices for $m$, you haven't proved that there are countably many combinations of $n$ and $m$. You need either to explicitly reference an earlier proof that the Cartesian product of countable sets is countable, or prove this explicitly.
  • Since each rational can be hit by more than one $(m,n)$ pair, what you prove is really that $\mathbb Q$ is at most countable. You will need an argument that it doesn't have some lower cardinality. (Unless your definition of "countable" is "at most the cardinality of $\mathbb N$" rather than "exactly the cardinalty of $\mathbb N$", which happens). An explicit appeal to the Cantor-Bernstein theorem may be in order.
  • 0
    Oops, thanks. I overlooked that because the $n=0, m\ne 0$ case is harmless. :-)2012-09-11
0

This is simply isomorphic to the Cartesian product of two copies of $\mathbb{Z}$ .

$\mathbb{Z}\times\mathbb{Z}$ is countable and can be ordered by the lexicographic order so it is countable.

  • 2
    And you also say the product is countable, then mention an irrelevant order, and then re-conclude that the product is countable?2012-09-11