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)$$
Is this idea for a proof that $\mathbb{Q}$ is countable correct?
2
$\begingroup$
elementary-set-theory
-
6Honestly, nobody needs that many question marks in the title. – 2012-03-22
-
0Just want to draw attention – 2012-03-22
-
3An extra 17 question marks will not make potential answerers more forthcoming. – 2012-03-22
-
5@jason: do not try to draw attention that way. Please. – 2012-03-22
-
0Besides, you have to be careful : 1/1 = 2/2. Does f(1) equal (1,1) or (2,2)? But the general idea of your proof is sound. – 2012-03-22
-
1Well, 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 :) – 2012-03-22
-
0is it just specifies that only consider the reduced one?? – 2012-03-22
-
0@jason: You either specify that the input must be in reduced form (don't forget to specify what to do with negatives!); or else you need to define $F$ in *terms* of the reduced form. – 2012-03-22
-
0Isn't it better to define a *surjection* from $\mathbb{Z}\times \mathbb{Z} \to \mathbb{Q}$ by $(a,b) \mapsto a/b$? This should imply that $card \mathbb{Q} \leq card \mathbb{Z}\times \mathbb{Z}$. – 2012-03-22
-
0is it true in general that comparing the cardinality giving info about injectivity and surjectivity although i think it would works in this case but in general may not be true – 2012-03-22
-
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