Prove that the set of positive rational numbers is countable

Question

While I was studying Discrete Mathematics, I faced a question that I do not understand how to solve even after looking at the answer. The question asks me to prove that the set of positive rational numbers is countable by showing that:

The function K is a one-to-one correspondence between the set of positive rational numbers and the set of positive integers if $K(\frac{m}{n})=P_1^{2a_1}P_2^{2a_2}...P_s^{2a_s}Q_1^{2b_1-1}Q_2^{2b_2-1}...Q_t^{2b_t-1}$, where $gcd(m,n)=1$ and the prime-power factorizations of m and n are $m=P_1^{a_1}P_2^{a_2}...P_s^{a_s}$ and $n=Q_1^{b_1}Q_2^{b_2}...Q_t^{b_t}$.

Attempt:

$K(\frac{m}{n})=P_1^{2a_1}P_2^{2a_2}...P_s^{2a_s}Q_1^{2b_1-1}Q_2^{2b_2-1}...Q_t^{2b_t-1}=(P_1^{a_1}P_2^{a_2}...P_s^{a_s})^2\frac{(Q_1^{b_1}Q_2^{b_2}...Q_t^{b_t})^2}{(Q_1Q_2...Q_t)}=m^2\frac{n^2}{Q_1Q_2...Q_t}$

I am going to prove that the function is a one-to-one correspondence by showing that when $x=y$, then $f(x)=f(y)$, and when $f(x)=f(y)$, then $x=y$.

1. If $x=y$, then $f(x)=f(y)$

Let $x=\frac{a}{b},y=\frac{c}{d}, gcd(a,b)=gcd(c,d)=1$

$b=b_1^{k_1}b_2^{k_2}...b_t^{k_t}$ and $d=d_1^{s_1}d_2^{s_2}...d_i^{s_i}$

Since $x=y$ and gcd(a,b) and gcd(c,d) are 1, a=c and b=d.

Because $b=d, b_1^{k_1}b_2^{k_2}...b_t^{k_t}=d_1^{s_1}d_2^{s_2}...d_i^{s_i}$ and $ b_1b_2...b_t=d_1d_2...d_i$

$K(\frac{a}{b})=a^2\frac{b^2}{b_1b_2...b_t}=c^2\frac{d^2}{d_1d_2...d_i}=K(\frac{c}{d})$

Hence, proved.

2. If $f(x)=f(y)$, then $x=y$.

However, I have no idea how to prove this part.

If there are other more formal ways to solve the question, please teach me. I really need your help. Thank you

Answer 1

"I am going to prove that the function is a one-to-one correspondence by showing that when $x=y$, then $f(x)=f(y)$, and when $f(x)=f(y)$, then $x=y$": wrong. Show only the second point. The first one has nothing to do with injectivity. It only means $f$ is well-defined, as a function. By the formulation of the exercise, you can take it for granted.

To prove that $K$ is injective, you can indeed try to show that $$K(x)=K(y)\implies x=y$$ but in order to do so, you will have to get a good understanding of how this map works, and that understanding will allow to prove directly that $K$ is not only injective, but bijective.

For this, consider the prime factorization of an arbitrary natural number $N$, and show that there exists a unique positive rational number $x$ such that $K(x)=N$: let $$N=\prod_{p\in Z}p^{k_p}$$ where $Z$ is a finite set of prime numbers and each $k_p$ is a positive integer.

Partition it: $Z=X\sqcup Y$ where $X=\{p\in Z\mid k_p\text{ is even}\}$ and $Y=\{p\in Z\mid k_p\text{ is odd}\}$.

Define $u_p:=\frac{k_p}2$ if $p\in X$, and $v_p:=\frac{k_p+1}2$ if $p\in Y$. Then, $$K(x)=N\iff x=m/n,\quad\text{where}\quad m=\prod_{p\in X}p^{u_p}\quad\text{and}\quad n=\prod_{p\in Y}p^{v_p}.$$