Prove ##|\{ q\in\mathbb{Q}: q>0 \} |=|\mathbb{N}|##.

[zenterix]

Homework Statement

In this exercise, you will prove that

$$|\{ q\in\mathbb{Q}: q>0 \} |=|\mathbb{N}|\tag{1}$$

In what follows, we will use the following theorem without proof

Theorem. Let $q\in\mathbb{Q}$ with $q>0$. Then

1) if $q\in\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\in\mathbb{N}$ such that

$$q=p_1^{r_1}p_2^{r_2}...p_N^{r_N}\tag{2}$$

2) if $q\notin\mathbb{N}$, then there exist unique prime numbers
$p_1<...<p_N, q_1<...<q_M$ with $p_i\neq q_j$ for all
$i\in\{1,...,N\}$, $j\in\{1,...,M\}$, and unique exponents $r_1,...,r_N,s_1,...,s_M\in\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_M}}\tag{3}$$

Define $f:\{q\in\mathbb{Q}:q>0\}\to\mathbb{N}$ as follows

$f(1)=1$

$f(q)=p_1^{2r_1}...p_N^{2r_N}$ if $q\in\mathbb{N}\backslash{1}$ is given by
(2).

$f(q)=p_1^{2r_1}...p_N^{2r_N}q_1^{2s_1-1}...q_M^{2s_M-1}$ if $q\in \mathbb{Q} \backslash \mathbb{N}$ is given by (3).

Relevant Equations

(a) Compute $f(4/15)$. Find $q$ such that $f(q)=108$

(b) Use the theorem to prove that $f$ is a bijection.

This problem is the final exercise of problem set 1 on MIT OCW's course 18.100A, Real Analysis.

Since there are no solutions available for this problem set, I would like to show my attempt at a solution here and ask if it is correct.

Here is the problem statement (also available as problem 6 on the problem set)

My question is really about (b).

Let me just give my answer to (a) first

Since $q=\frac{4}{15}\notin\mathbb{N}$ and $q>0$ then we can write it as in (3).

Thus

$$f(4/15)=f\left (\frac{2^2}{3\cdot 5}\right )=2^{2\cdot 2}\cdot 3^{2\cdot 1-1}\cdot 5^{2\cdot 1-1}=2^4\cdot 3\cdot 5=240$$

Next, we want to find a $q$ such that $f(q)=108$.

Since $q\in\mathbb{N}$ we can write it as a product of primes as in (2). In the following factorization we can see that one of the factors is odd, suggesting that the $q$ we are looking for is in $\mathbb{Q}\backslash\mathbb{N}$.

$$108=2^2\cdot 3^3=2^2\cdot 3^{2\cdot 2-1}\cdot$$

Thus, we have $2r_1=2\implies r_1=1$ and $2s_1-1=3\implies s_1=2$ and

$$q=\frac{2}{3^2}=\frac{2}{9}$$

Now we get to (b). My question is about this proof.

First I will show that $f$ is injective. Then I will show that it is surjective.

Claim 1: $f$ is injective

Proof

The domain of $f$ is $\{q\in\mathbb{Q}: q>0$.

If $q\in\mathbb{N}$ then

- $f(1)=1=2^2$

- if $q\in\mathbb{N}\backslash \{1\}$ then

$$f(q)=(p_1^{r_1}...p_N^{r_N})^2=q^2\tag{4}$$

Thus,

$$\forall q_1,q_2\in\mathbb{N}, q_1\neq q_2\implies f(q_1)\neq f(q_2)\tag{5}$$

Now consider the rest of the domain, namely $q\in\mathbb{Q}\backslash\mathbb{N}$.

Then,

$$f(q)=(p_1^{r_1}...p_N^{r_N})^2 q_1^{2s_1-1}...q_M^{2s_M-1}\tag{6}$$

A few facts

a) (6) is not equal to 1 since we have a product of primes, which are all $\geq 2$.

b) Some of the prime factors are raised to an odd power. Since none of these factors can be factored further, then we can't split such odd powers into two equal natural number factors, and the entire $f(q)$ cannot be factored into the expression $n^2$ for some $n\in\mathbb{N}$. Thus, for any of these $q_1\in\mathbb{Q}\backslash\mathbb{N}$, $f(q_1)$ does not equal an $f(q_2)$ for $q_2\in\mathbb{N}$.

$$\forall q_1\in\mathbb{Q}\backslash\mathbb{N},\ \forall q_2\in\mathbb{N},\ f(q_1)\neq f(q_2)\tag{7}$$

c) By part 1. of the theorem there is a unique natural number with the factorization of $f(q)$ in (6).

d) For every $q_1, q_2 \in \mathbb{Q}\backslash\mathbb{N}$, the corresponding factorizations $f(q_1)$ and $f(q_2)$ are different because the factorizations of $q_1$ and $q_2$ are different: in each of the latter, the set of prime factors of numerator and denominator with their exponents are unique (by part 2. of the theorem).

In $f(q_i)$, the factors are the same as in $q_i$. In addition, since each of the two groups of exponents (the ones on prime factors from the numerator of $q$, and the ones on prime factors from the denominator of $q$) are formed by an injection from $\mathbb{N}\to\mathbb{N}$ (namely, $n\to 2n$ and $n\to 2n-1$) then given a set of prime factors with exponents associated with $q$(the set is unique), the corresponding set of prime factors with exponents associated with $f(q)$ will be unique since distinct exponents on $q$ factors map necessarily to distinct exponents on $f(q)$ factors.

Thus, again we have that

$$\forall q_1,q_2\in\mathbb{Q}\backslash\mathbb{N}, q_1\neq q_2\implies f(q_1)\neq f(q_2)\tag{8}$$

By (5), (7) and (8) $f$ is injective.

$\square$

Claim 2: $f$ is surjective

Proof

Assumption 1: there is some $n\in\mathbb{N}$ such that there is no $q\in\{q\in\mathbb{Q}:q>0\}$ with $f(q)=n$.

By part 1. of the theorem, $n=p_1^{r_1}...p_N^{r_N}$.

There are two cases: $r_1,...,r_N$ are all even or at least one of these exponents is odd.

Case 1: $r_1,...,r_N$ are all even then $r_i=2m_i$ for $i=1,...,N$ and $n=(p_1^{m_1}...p_N^{m_N})^2$ so $f(p_1^{m_1}...p_N^{m_N})=n$. This contradicts assumption 1.

Case 2: Suppose the first $k$ $r_i$'s are even and the rest are odd.

Then $r_i=2m_i$ for $i=1,...,k$ and $r_i=2m_i-1$ for $i=k+1,...,N$.

Then,

$$n=(p_1^{m_1}...p_k^{m_k})^2p_{k+1}^{2m_{k+1}-1}...p_N^{2m_N-1}$$

and if $q=\frac{p_1^{m_1}...p_k^{m_k}}{p_{k+1}^{m_{k+1}}...p_N^{m_N}}$ then $f(q)=n$. Again, this contradicts assumption 1.

In both possible cases, we reach a contradiction.

Thus, for all $n\in\mathbb{N}$ there is $q\in\{q\in\mathbb{Q}:q>0\}$ with $f(q)=n$ and hence $f$ is surjective.

$\square$

Thus, by claims 1 and 2, $f$ is a bijection.

[1]: https://ocw.mit.edu/courses/18-100a-real-analysis-fall-2020/mit18_100af20_hw1.pdf

 

[andrewkirk]

By suggesting the use of that number theory theorem, they push you towards a much more laborious proof than is needed.
All we need to do is to find a surjection from N to Q+ and another surjection the other way.
A surjection from Q+ to N is the map from each positive rational to its closest integer, subject to a minimum of 1 and breaking ties by rounding up. That surjection proves that $|\mathbb Q^+| \ge |\mathbb N|$.

An opposite surjection is $f\circ g$ where $f:\mathbb N^2 \to \mathbb Q^+$ and $g:\mathbb N\to \mathbb N^2$ such that
$$f(m,n) = m/n$$ and $g$ maps natural number $k$ to the $k$th step in a trail that starts at (1,1) and progressively covers the integer lattice points in each of the squares with vertices (1,1), (1, j), (j, 1), (j,j) for increasing j.
So the first few values of $g(k)$ are:
(1,1),
(2,1),(2,2),(1,2),
(1,3),(2,3),(3,3),(3,2),(3,1)
(4,1),(4,2),(4,3),(4,4),(3,4),(2,4),(1,4)
.....
$g$ is a surjection from $\mathbb N$ to all pairs of positive integers, since any lattice point must eventually be reached by the trail, and $f$ is a surjection from all such pairs to $\mathbb Q^+$, since every positive rational can be expressed as the ratio of two positive integers.
So by composition, $f\circ g$ is a surjection from $\mathbb N$ to $\mathbb Q^+$.
Hence $|\mathbb N | \ge|\mathbb Q^+|$.
Putting that together with the other inequality gives $\mathbb N = \mathbb Q^+$.

 

[PeroK]

MIT takes a strange approach because the cardinality of the naturals and rarionals is not dependent on prime factorisation.

 

[nuuskur]

I agree, this is so over the top. We know that
$$|\mathbb N| \leqslant |\mathbb Q^+| \leqslant |\mathbb Q| \leqslant |\mathbb Z\times\mathbb Z| \leqslant |\mathbb N \times\mathbb N| \leqslant |\mathbb N|.$$
The unique factorisation theorem is useful to find injections $\mathbb N\times\mathbb N \to \mathbb N$. Of course, Cantor-Bernstein is implicitly assumed here, but I think it's a reasonable thing to do. It can be quite tedious to come up with explicit bijections.