Proving Rational Numbers are Countable in a Different Way Prove that positive rational numbers are countable using the partitions:
$P_i= \lbrace x \in \mathbb{Q}^+ | x= {p \over{q}}, p+q=i, \gcd(p,q)=1 \rbrace$
where $\gcd(p, q)$ is the greatest common divisor of the integers $p$ and $q$.
Hint: Follow through steps


*

*Show that union $\cup _{i \in \mathbb{N}^+} P_i=\mathbb{Q}^+$.

*Show that each $P_i$ is finite.

*Prove that if each $P_i$ is written in the form


$P_i= \lbrace x_{i1},...,x_{ij},....x_{in_i} \rbrace$,
following mapping $f: \mathbb{Q}^+ \rightarrow \mathbb{N}^+$ is defined for every positive rational number and  it is one-to-one:
$f(x_{ij})=(\sum\limits_{k=1}^{i-1}{|P_k|})+j$
Although I have hints, I can't find the answer. Can you help me?
 A: For the first hint, show that any rational number $q\in\mathbb{Q}^+$ can be written as $q=\frac{a}{b}$ where $a,b\geq 0$ and gcd$(a,b)=1$. Then $q\in P_{a+b}$. It follows that $\bigcup_{i}P_i=\mathbb{Q}^+$.
Secondly, it's clear that each $P_i$ is finite since there only finitely many couples $(p,q)$ such that $p+q=i$ for a fixed $i$.
The third one is a bit more tricky, but try to take it step by step. First show that the map is well-defined then that it's injective and lastly surjective, if you have troubles doing so, explain what you tried and where it fails.
A: Q 1. Double inclusion: for $x$ of $Q^+$ write  $x=\frac{p}{q}$ and $gcd(p,q)=1$ so $x\in P_{p+q}$ finally $$\mathbb{Q}^+\subset \bigcup_{i\in \mathbb{N}^+} P_i$$ the other inclusion is obvious
Q 2. $P_i$ is finite because  $g:P_i\to [1,i]^2$ such that for all $x=\frac{p}{q}$ such that $gcd(p,q)=1$ we have $g(x)=(p,q)$ is one-to-one (prove it)$
Q 3. Because of the first question every rational number lies in some $P_i$ so every rational number is of the form $x_{ij}$ with $j\leq n_i=|P_i|$ ( writting $P_i$ of the given form is justified by the question $2$) and we have  for $i'\leq i$:
$$f(x_{ij})-f(x_{i'j'})= \sum_{k=i'}^{i-1}|P_i|+j-j'$$
if $i>i'$ we can write $f(x_{ij})-f(x_{i'j'})\geq|P_{i'}|-j'+j>0$ because $j> 0$ and $|P_{i'}|\geq j'$ so if $f(x_{ij})=f(x_{i'j'})=0$ then $i=i'$ it follows imediatly that $j=j'$
(your function is also onto)
