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

• zenterix
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}$$

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

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.

PeroK

What does it mean to prove that ##|\{ q\in\mathbb{Q}: q>0 \} |=|\mathbb{N}|##?

This statement means proving that the set of positive rational numbers (fractions where the numerator and denominator are integers and the denominator is not zero) has the same cardinality (size) as the set of natural numbers. In other words, there is a one-to-one correspondence between the positive rational numbers and the natural numbers.

How can we construct a bijection between the positive rational numbers and the natural numbers?

One common method to construct a bijection is to list the positive rational numbers in a systematic way, such as using a diagonal argument. First, arrange the positive rational numbers in a grid where the numerator and denominator are natural numbers. Then, traverse this grid in a diagonal manner to ensure every positive rational number is counted exactly once. This traversal avoids duplicates by skipping fractions that can be simplified to already listed fractions. This way, each positive rational number can be uniquely paired with a natural number.

Why is the set of positive rational numbers countable?

The set of positive rational numbers is countable because we can list them in a sequence such that each rational number appears exactly once. This is possible because the set of pairs of natural numbers (which represent the numerator and denominator of the fractions) is countable, and we can map each pair to a unique natural number using a systematic method like the diagonal argument.

What is the significance of proving that ##|\{ q\in\mathbb{Q}: q>0 \} |=|\mathbb{N}|##?

Proving that the set of positive rational numbers has the same cardinality as the set of natural numbers demonstrates that both sets are countably infinite. This helps in understanding the nature of different sizes of infinity and provides insight into the structure of rational numbers compared to natural numbers. It also shows that even though rational numbers seem more numerous, they can still be matched one-to-one with natural numbers.

Can this method be applied to other sets to determine their cardinality?

Yes, similar methods can be used to determine the cardinality of other sets. For example, the set of all rational numbers (both positive and negative) can be shown to have the same cardinality as the set of natural numbers by creating a suitable bijection. Additionally, other countably infinite sets, like the set of integers, can also be mapped to the natural numbers using a systematic approach to establish a one-to-one correspondence.

Replies
1
Views
1K
Replies
20
Views
2K
Replies
1
Views
892
Replies
1
Views
852
Replies
13
Views
3K
Replies
2
Views
703
Replies
5
Views
1K
Replies
12
Views
2K
Replies
3
Views
1K
Replies
15
Views
3K