# Is this idea for a proof that $\mathbb{Q}$ is countable correct?

I first show that there exist a injection $f:\mathbb{Q}\rightarrow \mathbb{Z\times Z}$ and then we know that $\mathbb{Z \times Z}$ is a countable set so we deduce that $\mathbb{Q}$ is countable. And such injection is not difficult to get, just simply define $$F\left(\frac{p}{q}\right)=(p,q)$$

-
Honestly, nobody needs that many question marks in the title. – Antonio Vargas Mar 22 '12 at 16:18
Just want to draw attention – jason Mar 22 '12 at 16:18
An extra 17 question marks will not make potential answerers more forthcoming. – anon Mar 22 '12 at 16:19
@jason: do not try to draw attention that way. Please. – Mariano Suárez-Alvarez Mar 22 '12 at 16:20
Well, you have to pick a specific representation of your rational number as $\frac{p}{q}$ for $f$ to be well-defined, but that's pretty easy :) – Thomas Andrews Mar 22 '12 at 16:20

If you can construct such an injection, and you already know that $\mathbb{Z}\times\mathbb{Z}$ is countable, then you are correct.

However, you have to be careful with your definition. Right now, for example, your function is not well-defined, since $\frac{1}{2}$ could be mapped to different pairs depending on how you write it: if you like writing it as $\frac{1}{2}$, then $F(1/2) = (1,2)$. But if you like to write it as $5/10$ (because, after all, $\frac{1}{2}=0.5$), then $F(5/10) = (5,10)$; or if you like negative numbers and write it as $\frac{-1}{-2}$, then $F(-1/-2) = (-1,-2)$.

In other words, you need to be a bit more careful when specifying the definition of your function $F$. Right now, it's not correct.

-
do you mean that i have to specifies that $5/10=1/2=n/2n$and similar for the rest of the rational numbers? – jason Mar 22 '12 at 16:30
@jason: I mean that rational numbers can be expressed as fractions in many different ways. But your function right now depends on how you write the rational, rather than what the rational is. The function should not take different values on the same input depending on how you describe the input. So you need to make sure that your function is defined in terms of what the value is, not how you write it. There are several ways of doing this; one would be to specify a particular way in which the input needs to be written before applying the function. (cont) – Arturo Magidin Mar 22 '12 at 16:32
@jason (cont) Another would be to write a more complicated description of the function that takes into account that rationals may be written in many different ways, so that it describes a single output regardless of how the input is "fed in." I don't want to be more explicit because it would essentially give the game away and this is something you need to struggle a bit with on your own at least once. – Arturo Magidin Mar 22 '12 at 16:34

To extend Arturo's comment, and perhaps suggest a slight modification:

Consider the following way to construct the rational numbers: we define an equivalence relation on $\mathbb Z\times(\mathbb Z\setminus\{0\})$ defined as: $$(r,s)\sim(p,q)\iff r\cdot q=p\cdot s$$

For example, $(1,2)\sim(5,10)$ since $1\cdot10=10=5\cdot2$. We can consider the rational numbers as representatives of these equivalence classes or we can consider them as the equivalence classes.

This means that the number $\dfrac{p}{q}$ is actually the equivalence class of $(p,q)$.

Now consider the function which sends the pair $(p,q)$ to its equivalence class. This is of course a surjective map, and therefore the set of equivalence classes cannot be more than countably infinite.

(Note on the fact that I assume the surjective map has an injective inverse: since the domain of the surjection is well-orderable we can easily define the injective inverse, indeed this is what the OP defined - up to clarification that we take the rational number to be of such and such form, e.g. reduced fraction with positive denominator.)

-