Proving Rational Numbers are Countable in a Different Way

Question

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

1. Show that union $\cup _{i \in \mathbb{N}^+} P_i=\mathbb{Q}^+$.
2. Show that each $P_i$ is finite.
3. 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?

Answer 1

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.

Answer 2

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)