2
$\begingroup$

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)$

  • 0
    @jason: Assuming the axiom of choice then surjection from $A$ onto $B$ implies the existence of an injection from $B$ into $A$. Without the axiom of choice this is certainly false. However if $A$ is *countable* and has a surjection onto $B$ then you can define an injective inverse. I remarked about that in my answer.2012-03-22

2 Answers 2

6

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.

  • 0
    @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.2012-03-22
2

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.)