Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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"?

share|improve this question
    
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. –  Martin Sleziak Sep 11 '12 at 7:40
    
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. –  Arthur Sep 11 '12 at 7:51
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}$. –  user22805 Sep 11 '12 at 8:14
    
Although it has some gaps, as noted in Henning’s answer, it’s an original approach that shows some thought. –  Brian M. Scott Sep 11 '12 at 8:58

2 Answers 2

up vote 3 down vote accepted

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.
share|improve this answer
    
You also need to rule out $n=0$. (And of course countable means of cardinality at most $\omega$! :-)) –  Brian M. Scott Sep 11 '12 at 8:52
    
Oops, thanks. I overlooked that because the $n=0, m\ne 0$ case is harmless. :-) –  Henning Makholm Sep 11 '12 at 9:00

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.

share|improve this answer
1  
How would such an isomorphism look like? Note that $\frac12=\frac24$ and that $\frac10$ is not even defined. –  Rasmus Sep 11 '12 at 8:25
2  
And you also say the product is countable, then mention an irrelevant order, and then re-conclude that the product is countable? –  rschwieb Sep 11 '12 at 23:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.