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
    If you add the condition $n\ne0$, then you just basicaly say that very $x\in\mathbb Q$ is of the form $x=\frac mn$, and thus $\mathbb Q=\bigcup\limits_{n\in\mathbb Z\setminus\{0\}} \{ \frac mn; m\in\mathbb Z\}$ is a union of countably many countable sets.2012-09-11
  • 0
    If you look at every point in the plane with integer coordinates (commonly called grid point), then try to find some intuitive way of assigning a rational number to (almost) every grid point such that every rational number is represented, then count in a rectangular outwards spiral from the origin.2012-09-11
  • 1
    I think you need to add $n\neq 0$ to your definition somewhere; otherwise, you haven't actually defined ${\Bbb Q}$. Once you add this, then for each pair of values for $m$ and $n$, there is only one possible $x$; and in total there are only countably many elements of ${\Bbb Q}$.2012-09-11
  • 0
    Although it has 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
    You also need to rule out $n=0$. (And of course *countable* means *of cardinality at most* $\omega$! :-))2012-09-11
  • 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.

  • 1
    How would such an isomorphism look like? Note that $\frac12=\frac24$ and that $\frac10$ is not even defined.2012-09-11
  • 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