- #1

zenterix

- 678

- 83

- 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)

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.

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##

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

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**

ProofProof

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##.Proof

Assumption 1:

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