Assignment 1
Table of contents
url: https://ocw.mit.edu/courses/18-100a-real-analysis-fall-2020/resources/mit18_100af20_hw1/
Chapters and exercises given with a numbering are from Basic Analysis: Introduction to Real Analysis (Vol I) by J. Lebl.
Exercise 0.3.6
Prove:
1) $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$
2) $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$
Proof:
1) (Step 1) Show $ A \cap (B \cup C) \subseteq (A \cap B) \cup (A \cap C) $. If $ x \in A \cap (B \cup C) $, $ x \in A $, $ x \in B \land x \in C $. $\Rightarrow$ $ x \in A \cap B $, $ x \in A \cap C $ $\Rightarrow$ $ x \in (A \cap B) \cup (A \cap C) $.
(Step 2) If $ x \in (A \cap B) \cup (A \cap C) $, then $ {x \in A \cap B} \lor {x \in A \cap C} $ $\Rightarrow$ $ x \in A $; $ {x \in B} \lor {x \in C} $ $\Rightarrow$ $ {x \in A} \land {x \in B \cup C} $ $\Rightarrow$ $ x \in A \cap (B \cup C) $.
2) (Step 1) If $ x \in A \cup (B \cap C) $, then $ {x \in A} \lor {x \in B \cap C} $. If $ x \in A $, then $ x \in (A \cup B) \cap (A \cup C) $. If $ x \in B \cap C $, then $ {x \in B} \land {x \in C} $. Since $ B \subseteq A \cup B $, $ C \subseteq A \cup C $, so $ {x \in A \cup B} \land {x \in A \cup C} $ $\Rightarrow$ $ x \in (A \cup B) \cap (A \cup C) $.
(Step 2) If $ x \in (A \cup B) \cap (A \cup C) $, then $ {x \in A} \lor {x \in B} \land {x \in A} \lor {x \in C} $, if $ x \in A $, $ x \in A \cup (B \cap C) $. If $ x \notin A $, then $ {x \in B} \land {x \in C} $ $\Rightarrow$ $ x \in B \cap C $ $\Rightarrow$ $ x \in A \cup (B \cap C) $.
Exercise 0.3.11
Prove by induction that $ n < 2^n $ for all $ n \in \mathbb{N} $.
Proof:
(i) $ n = 1, \, 1 < 2^1 $
(ii) Suppose when $ n = k(k \geq 1), \, k < 2^k $.
Then for $ n = k+1, \, 2^{k+1} = 2^k \cdot 2 k \cdot 2 k+1 $
Then $ n < 2^n $ for all $ n \in \mathbb{N} $.
Exercise 0.3.12
Show that for a finite set $ A $ of cardinality $ n $, the cardinality of $ \mathcal{P}(A) $ is $ 2^n $.
Proof:
\[\mathcal{P}(A) = \{B : B \subseteq A\}\]Prove by induction.
(i) $ n = 0, k = \emptyset $. then $ \mathcal{P}(A) = {\emptyset} $ with $ \vert \mathcal{P}(A)\vert = 1 = 2^0 $
(ii) Suppose when $ n = k, \, l $ let $ \vert A_k\vert = k $, then $ \vert \mathcal{P}(A_k)\vert = 2^k $.
Let $ B $ be a set with $ \vert B\vert = k+1 $.
Put any element $ a \in B $. Define $ A := B \setminus {a} \Rightarrow \vert A\vert = k $.
Each subset of $ B $ can either contain $ a $ or not contain $ a $.
\(\mathcal{P}(B) = \mathcal{P}(A) \cup \{ S \cup \{a\} : S \in \mathcal{P}(A)\}\) and the union is disjoint. \(\vert \mathcal{P}(B)\vert = \vert \mathcal{P}(A)\vert + \vert \mathcal{P}(A)\vert = 2 \cdot 2^k = 2^{k+1}\)
Exercise 0.3.15
Prove that $ n^3 + 5n $ is divisible by 6 for all $ n \in \mathbb{N} $.
Prove by induction.
(i) $ n = 1, \, 1^3 + 5 \times 1 = 6 $
(ii) Suppose when $ n = k, \, k^3 + 5k $ is divisible by 6, then $\exists m \in \mathbb{N}, \, \text{s.t.} \, k^3 + 5k = 6m$
For $ n = k + 1 $,
\[\begin{aligned} (k + 1)^3 + 5(k + 1) &= (k^3 + 3k^2 + 3k + 1) + (5k + 5)\\ &= k^3 + 5k + (3k^2 + 3k + 6)\\ &= 6m + 6 + 3k(k + 1) \end{aligned}\]Since $ k(k + 1) $ is divisible by 2, $(k + 1)^3 + 5(k + 1)$ is divisible by 6.
Then $\forall n \in \mathbb{N}, \, n^3 + 5n$ is divisible by 6.
Exercise 0.3.19
Give an example of a countably infinite collection of finite sets $ A_1, A_2, \ldots $, whose union is not a finite set.
$A_n := {n}, \forall n \in \mathbb{N}, \bigcup_{n \geq 1} A_n = {1, 2, \ldots} = \mathbb{N}$
Thus $\vert \bigcup_{n \geq 1} A_n \vert = \vert \mathbb{N}\vert $ is countably infinite.
Problem 6
In this exercise, you will prove that
\[\vert \{q \in \mathbb{Q} : q > 0\}\vert = \vert \mathbb{N}\vert .\]In what follows, we will use the following theorem without proof:
Theorem. Let $ q \in \mathbb{Q} $ with $ q > 0 $. Then
\[q = p_1^{r_1} p_2^{r_2} \cdots p_N^{r_N}, \tag{†}\]
1) if $ q \in \mathbb{N} $ and $ q \neq 1 $, then there exists unique prime numbers $ p_1 < p_2 < \cdots < p_N $ and unique exponents $ r_1, \ldots, r_N \in \mathbb{N} $ such that2) if $ q \notin \mathbb{N} $, then there exist unique prime numbers $ p_1 < p_2 < \cdots < p_N $, $ q_1 < q_2 < \cdots < q_M $ with $ p_i \neq q_j $ for all $ i \in {1, \ldots, N} $, $ j \in {1, \ldots M} $, and unique exponents $ r_1, \ldots, r_N, s_1, \ldots s_M \in \mathbb{N} $ such that
\[q = \frac{p_1^{r_1} p_2^{r_2} \cdots p_N^{r_N}}{q_1^{s_1} q_2^{s_2} \cdots q_M^{s_M}}. \tag{‡}\]Define $ f : {q \in \mathbb{Q} : q> 0} \to \mathbb{N} $ as follows: $ f(1) = 1 $, if $ q \in \mathbb{N} \backslash {1} $ is given by (†), then
\[f(q) = p_1^{2r_1} \cdots p_N^{2r_N},\]and if $ q \in \mathbb{Q} \backslash \mathbb{N} $ is given by (‡), then
\[f(q) = p_1^{2r_1} \cdots p_N^{2r_N} q_1^{2s_1-1} \cdots q_M^{2s_M-1}.\](a) Compute $ f(4/15) $. Find $ q $ such that $ f(q) = 108 $.
(b) Use the Theorem to prove that $ f $ is a bijection.
(a) $ f\left(\frac{4}{15}\right) = 2^{2 \times 2} \cdot (3 \cdot 5) = 240 $
$f(q) = 108 = 2^2 \times 3^3\Rightarrow p_1=2, r_1=1, q_1=3, s_1=2, \therefore q=p_i^{r_1}/q_i^{s_1} = 2/9$
(b) (Step 1) Show that $ f $ is 1-1.
From theorem, $\forall q \in \mathbb{Q}, q 0$, the prime factorization is unique. If $ q = \frac{p_1^{r_1} \cdots p_N^{r_N}}{q_1^{s_1} \cdots q_M^{s_M}}, $ then $ f(q) = p_1^{2r_1} \cdots p_N^{2r_N} \cdot q_1^{2s_1-1} \cdots q_M^{2s_M-1} \in \mathbb{N} $.
Since $ p_i, q_j (i=1:N, j=1:M) $ are unique, and $ \mathbb{N} \to {2r:r \in \mathbb{N}}, \mathbb{N} \to {2s-1:s \in \mathbb{N}} $ are injective. Thus if $ f(q) = f(q’), q = q’ $
(Step 2) Show that $ f $ is onto, i.e. $\forall y \in \mathbb{N}, \exists x \in {q \in \mathbb{Q}: q >0}, \text{s.t.} f(x) = y $.
(i) If $ y \in \mathbb{N} \backslash {1}, $ by theorem, $\exists ! p_1 < \cdots < p_N, r_1, \cdots, r_N, \text{s.t.} y = p_1^{r_1} \cdots p_N^{r_N}$
$\exists x = p_1^{r_1/2} \cdots p_N^{r_N/2} \in {q \in \mathbb{Q}: q >0}, \text{s.t.} f(x) = y$
(ii) If $ y = 1, $ since $ f(1) = 1 \quad \exists x = 1 \in {q \in \mathbb{Q}: q >0}, \text{s.t.} f(x) = y $. $\therefore f$ is onto.
Thus, $f$ is bijective.