I'm a CS student trying to get into some deeper math. I started following MITOCW course on Real Analisys, but I'm stuck in one of the exercises from the start of the course. Given the following theorem and the defined function $f$, I have to prove that $f$ is a bijection from $\mathbb{Q}^+$ to $\mathbb{N}$ (i.e., $\mathbb{Q}^+$ is countably infinite).
Theorem. Let $q ∈ \mathbb{Q}$ with $q > 0$. Then
if $q ∈ \mathbb{N}$ and $q \neq 1$, then there exists unique prime numbers $p_1 < p_2 < · · · < p_N$ and unique exponents $r_1, . . . , r_N ∈ N$ such that $$ q = p_1^{r_1} p_2^{r_2} · · · p_N^{r_N} , (†)$$
if $q ∈ \mathbb{Q}/ \mathbb{N}$, then there exist unique prime numbers $p_1 < p_2 < · · · < p_N$ , $q_1 < q_2 < · · · < q_M$ with $p_i \neq q_j$ for all $i ∈ {1, . . . , N}$, $j ∈ {1, . . . M}$, and unique exponents $r_1, . . . , r_N$, $s_1, . . ., s_M ∈ \mathbb{N}$ such that $$q = \frac{p_1^{r_1} p_2^{r_2} · · · p_N^{r_N}}{ q_1^{s_1} q_2^{s_2} · · · q_M^{s_N}}, (‡)$$
\
Define $f : \{q ∈ \mathbb{Q} : q > 0\} → \mathbb{N}$ as follows: $f(1) = 1$, if $q ∈ \mathbb{N}$ \ $\{1\}$ is given by $(†)$, then $$f(q) = p_1^{2r_1} p_2^{2r_2} · · · p_N^{2r_N},$$ and if $q ∈ \mathbb{Q}$\ $\mathbb{N}$ is given by $(‡)$, then $$f(q) = p_1^{2r_1} · · · p_N^{2r_N}q_1^{2s_1 - 1} · · · q_M^{2s_N - 1}$$
To prove that $f$ is bijective I have to prove that $f$ is both injective and surjective. I have some idea on how to go about proving the injective part, but i'm completly lost when it comes to the surjective proof.
For the case $(†)$, $f(q) = q^2$. I can prove by contradiction that $q^2$ is a injective function (using the definition: $f(q_1) = f(q_2) \iff q_1 = q_2$).
For case $(‡)$, my line of thinking is the following (although I don't think it is rigourous enough, or even correct altogether): since each number $q$ has a unique combination of prime numbers $p_1, ..., p_N, q_1, ..., q_M$, and exponents $r_1, ..., r_N, s_1, ..., s_M$, and, since each exponent gets mapped by a injective function either $h(x) = 2x$ or $h(x) = 2x - 1$, and there is no overlapping between the range of those functions (i.e., one produces even numbers and the other produces odd numbers), then each value $q$ is gonna be mapped to a unique value $f(q)$.
I guess my questions would then be:
Am in the right track for proving the injective property? Can someone give me a more rigourus proof?
How do I even start to go about prooving the surjective case?