MA2108S Homework sets 1, 2, 3

Qi Ji [A0167793L]

22nd Feb 2019

Homework 1


We borrow some standard notation from Set Theory, so when \(X\) is a set and \(n\in{\mathbb{N}}\cup{\left\{\, 0 \,\right\}}\), \([X]^n\) denotes the set \({\left\{\, x\subset X: \left\lvert x \right\rvert = n \,\right\}}\).

To show that \([{\mathbb{N}}]^{<\omega}\) is countable, we first express it as the disjoint union \[ [{\mathbb{N}}]^{<\omega} = [{\mathbb{N}}]^0 \sqcup [{\mathbb{N}}]^1 \sqcup [{\mathbb{N}}]^2 \sqcup \dots \]

Note that for each \(i\in{\mathbb{N}}\), \([{\mathbb{N}}]^i\) is countable. This is because \({\mathbb{N}}\times{\mathbb{N}}\) is countable, so by induction \({\mathbb{N}}^i\) is countable, and we can embed \([{\mathbb{N}}]^i\) inside \({\mathbb{N}}^i\) by simply sorting the elements. So let \((f_i)_{i\in{\mathbb{N}}\cup{\left\{\, 0 \,\right\}}}\) be a sequence of witnesses, that is for each \(i\in{\mathbb{N}}\cup{\left\{\, 0 \,\right\}}\), \(f_i : [{\mathbb{N}}]^i \to {\mathbb{N}}\) is injective. Then by Rudin 2.12, \([{\mathbb{N}}]^{<\omega}\) is a countable union of countable sets which is countable. \(\square\)

Rudin Chapter 1 Q5

Let \(\beta = -\sup(-A)\).

To see that \(\beta\) is a lower bound of \(A\), let \(a \in A\), then \(-a \in -A\). Because \(-\beta = \sup(-A)\), we have \(-a < -\beta \implies a > \beta\).

To see that \(\beta\) is the greatest lower bound, now suppose \(\beta' > \beta\) is another lower bound of \(A\), then \(-\beta' < -\beta = \sup(-A)\). Choose witness \(c \in A\) such that \(-\beta' < -c < -\beta\) and we have \(\beta' > c > \beta\), in particular \(\beta' > c\) which contradicts \(\beta'\) being a lower bound. \(\square\)

Rudin Chapter 1 Q6

  1. First note that \[ mq = pn. \] Now let \(\alpha = (b^m)^{1/n}\) and \(\beta = (b^p)^{1/q}\), we use freely properties of integer exponents in a multiplicative group and uniqueness of \(n\)-th root (for positive base) to see that \[\begin{align*} \alpha^{nq} &= (b^m)^q = b^{mq} \text{, and}\\ \beta^{nq} &= (b^q)^n = b^{pn} \end{align*}\] again because \(b > 0\) we have \(\alpha, \beta > 0\), and since \(\alpha^{nq} = \beta^{nq}\), uniqueness of \(nq\)-th root for positive base tells us that \(\alpha = (b^m)^{1/n} = \beta = (b^p)^{1/q}\). \(\square\)

  2. let \(r = m/n, s=p/q\) where \(m,n,p,q\) integers with \(n>0, q>0\), then \[r + s = \frac{m}{n} + \frac{p}{q} = \frac{mq + pn}{nq} \] now \[\begin{align*} b^r b^s &= b^{m/n} b^{p/q} \\ &= b^{mq/nq} b^{pn/nq} \\ &= (b^{mq})^{1/nq} (b^{pn})^{1/nq} \\ &= (b^{mq} b^{pn})^{1/nq} \tag*{by cor of 1.21} \\ &= (b^{mq+pn})^{1/nq} \\ &= b^{r+s} \end{align*}\] where the second last step is due to the same property for integer exponents in any multiplicative group. \(\square\)

  3. Fix \(r\in\mathbb{Q}\), to see that \(b^r\) is an upper bound of \(B(r)\), choose any \(t\in\mathbb{Q}, t\leq r\) such that we have \(b^t \in B(r)\). Since \(t \leq r\), \(r-t \geq 0\), choose \(m,n\in\mathbb{Z}^+, n\ne 0\) such that \(\frac{m}{n} = r-t\). Since \(b > 1\), an induction argument on \(m\) shows that \(b^m \geq 1\) with equality holding only when \(m = 0\). Also \((b^m)^{1/n} \geq 1\), for suppose on the contrary that \((b^m)^{1/n} < 1\), then the same argument shows that \(b^m < 1\). Now to show that \(b^t \leq b^r\), we use part (b) to see that \[\begin{align*} b^r &= b^{t + (r-t)} \\ &= b^t\, b^{r-t} \\ &\geq b^t \end{align*}\] and \(b^r\) is indeed an upper bound.

    To see that \(b^r\) is the least upper bound of \(B(r)\), suppose \(c < b^r\) is another upper bound for \(B(r)\). We immediately get a contradiction because \(r \in \mathbb{Q}, r \leq r\) and hence \(b^r \in B(r)\). \(\square\)

To make my way of doing (d) work it might be useful to amend the definition of real exponentiation.

Definition. Define for any \(x\in \mathbb{R}, B'(x) := {\left\{\, b^t: t < x, t\in\mathbb{Q} \,\right\}}\).

Proposition. For any \(x\in\mathbb{R}\), \(\sup B(x) = \sup B'(x)\).

Proof. If \(x\in\mathbb{R}\smallsetminus\mathbb{Q}\) then it is obvious from the definition. So suppose \(x\in\mathbb{Q}\), the proof that \(b^x = \sup B(x)\) is an upper bound of \(B'(x)\) is the same as in part (c), and is skipped. To see that \(b^x\) is the least upper bound, suppose there exists \(0 < c < b^x\) that is also an upper bound for \(B'(x)\) (since \(b>0\) we can consider a positive bound WLOG). Then \(\frac{b^x}{c} > 1\). By Exercise 7 part (c) we can choose sufficiently large \(n\in{\mathbb{N}}\) such that \(b^{1/n} < \frac{b^x}{c}\). Since \(x, \frac1n\) rational by (b) we have \(c < b^{x-\frac1n}\) which is a contradiction.\(\square\)

  1. We start by proving a lemma that if \(t < x + y\) where \(x, y \in\mathbb{R}\), then \(t < a + b\) where \(p,q\in\mathbb{Q}\), \(p < x, q < y\).

    Let \(d = x + y - t\in\mathbb{R}\) and consider the numbers \(x - \frac{d}{2}\) and \(y - \frac{d}{2}\). Use density to choose rational numbers \(p, q\) such that \[\begin{gather*} x - \frac{d}2 < p < x \text{ and} \\ y - \frac{d}2 < q < y \end{gather*}\] then \[t = x + y - d = x - \frac{d}2 + y - \frac{d}2 < p + q.\]

    To answer (d), fix \(x,y\in\mathbb{R}\), we have to show that \(b^x b^y = \sup B'(x + y)\). To see that \(b^x b^y\) is an upper bound, choose \(t \in \mathbb{Q}, t < x + y\). By lemma let \(p,q_0\in\mathbb{Q}\) such that \(p<x, q_0<y, t < p+q_0\). Then \(t = p + q\) where \(q = p + q_0 - t\in\mathbb{Q}\). Then \[b^t = b^{p+q} = b^p\, b^q \leq b^x\,b^q \leq b^x\,b^y. \]

    Now suppose \(0 < c < b^x b^y\) is another upper bound for \(B'(x+y)\). Then \(\frac{c}{\sup B'(x)} < \sup B'(y)\). Choose \(m\in\mathbb{R}\) such that \[ \frac{c}{\sup B'(x)} < m < \sup B'(y) \] Let \(w\in\mathbb{Q}, w < y\) witness \(m < \sup B'(y)\), that is \(m < b^w\). Similarly let \(v\in\mathbb{Q}, v < x\) such that \(\frac{c}{m} < b^v\). Then \[ c = \frac{c}{m}\, m < b^v\,b^w = b^{v+w} \in B'(x+y), \] which is a contradiction. \(\square\)

Homework set 2

Rudin Chapter 1 Q13

Note that \(\left\lvert x \right\rvert - \left\lvert y \right\rvert\) is real, so split into cases.

Rudin Chapter 2 Q7

We use \(N_r(x)\) to denote ball for this question because there are sets named \(B\) and \(B_n\). The proof of (b) also proves the backwards containment in (a) so I shall not write it twice.

  1. Let \(I = {\left\{\, 1,\dots,n \,\right\}}\) for some \(n\in{\mathbb{N}}\), so in particular it’s finite. Proof of (b) already shows the backward inclusion so it remains to prove that \(\overline{B_n} \subset \bigcup_{i=1}^n \overline{A_i}\). So suppose on the contrary that there exists \(x\in \overline{B_n}\) such that \(x\notin \bigcup_{i\in I} \overline{A_i}\). It cannot be the case that \(x\in B_n\) since that will imply \(x\in A_i\) for some \(i\), we just have to consider when \(x\notin B_n\) is a limit point of \(B_n\). Since \(x\) is not in the union, for all \(i\in{\left\{\, 1,\dots,n \,\right\}}\), \(x\notin \overline{A_i}\). In particular it means that for each \(i\), \(x\) is not a limit point of \(A_i\). That is, for each \(i\), \[ \exists r_i>0.~ N_{r_i}(x)\cap A_i = \emptyset. \] Now we take the minimum of the finitely many \(r_i\) that exists, call it \(m\). What we have now is that \[\forall i\in I.~ N_{m}(x) \cap A_i = \emptyset. \] Since \(N_m(x)\) and each \(A_i\) has an empty intersection, \(N_m(x)\cap B = \emptyset\). This means that \(m\) is a witness to \(x\) not being a limit point of \(B_n\), which is a contradiction.

  2. Let \(x \in \overline{A_i}\) for some \(i\), in the case that \(x \in A_i\), then \(x \in B \subset \overline{B}\), so we’re done. In the case that \(x\) is a limit point of \(A_i\), then \[ \forall r>0.~ N_r(x) \cap (A_i\smallsetminus{\left\{\, x \,\right\}}) \ne \emptyset \] since \(A_i\subset B\), we can weaken the condition above to \[ \forall r>0.~ N_r(x) \cap (B\smallsetminus{\left\{\, x \,\right\}}) \ne \emptyset \] which means that \(x\in\overline{B}\). This shows that \(\overline{B} \supset \bigcup_{i\in I} \overline{A_i}\) for any index set \(I\).

For example of proper inclusion in (b), since \(\mathbb{Q}\) is countable, let \({\left\{\, x_1, x_2, \dots \,\right\}}\) be an enumeration. Define for each \(i\in{\mathbb{N}}\), \(A_i := {\left\{\, x_i \,\right\}}\), then \(B = \bigcup_{i=1}^\infty A_i = {\left\{\, x_1, x_2, \dots \,\right\}} = \mathbb{Q}\). Now we see that \(\overline{B} = \overline{\mathbb{Q}} = \mathbb{R}\) while each \(A_i\) is a singleton so \(\overline{A_i} = A_i\), and \(\bigcup_{i=1}^\infty \overline{A_i} = \bigcup_{i=1}^\infty A_i = B = \mathbb{Q}\).

Rudin Chapter 2 Q10

\(X\) is a metric space. It is very clear from the definition that \(d(-,-)\) is positive-definite. It can also be visually verified that the definition is symmetric.

To see the triangle inequality, fix any \(p,q,r \in X\) and we have to show that \[ d(p,q) \leq d(p,r) + d(r,q). \] Case \(p=q\), then LHS is \(0\) so conclusion follows. Case \(p \ne q\), then at least one of \(p\ne r\) or \(q\ne r\) will hold, so \(d(p,r) + d(r,q) \geq 1 = d(p,q)\). \(\square\)

This metric is discrete so there are no limit points, hence every subset is closed. Every subset is open too by complementation. Since \(X\) is infinite, only finite subsets of \(X\) are compact. If \(Y\subset X\) is infinite, define \(G_y := {\left\{\, y \,\right\}}\) for each \(y\in Y\) and the open cover given by \({\left\{\, G_y \,\right\}}_{y\in Y}\) will not have any finite subcover.

Rudin Chapter 2 Q11

  1. \(d_1\) fails the triangle inequality with witness \(d_1(0,2) = 4 > d_1(0,1) + d_1(1,2) = 1 + 1 = 2\).

  2. Positive-definiteness and symmetric is clear from definition. To verify triangle inequality, we want to show that \[ \sqrt{\left\lvert x-y \right\rvert} \leq \sqrt{\left\lvert x-z \right\rvert} + \sqrt{\left\lvert z-y \right\rvert} \] or equivalently \[ \left\lvert x-y \right\rvert \leq \left\lvert x-z \right\rvert + \left\lvert z-y \right\rvert + 2\sqrt{\left\lvert x-z \right\rvert\left\lvert z-y \right\rvert} \] and this holds by the triangle inequality on this metric \(d(x,y) = \left\lvert x-y \right\rvert\).

  3. \(d_3\) fails as \(d_3(-1,1) = 0\).

  4. \(d_4\) fails as \(d_4(2,1) = 0\).

  5. Positive-definiteness is clear from the definition and the expression also looks symmetric in terms of \(x\) and \(y\). To verify triangle inequality we want to show that \[ \frac{\left\lvert x-y \right\rvert}{1 + \left\lvert x-y \right\rvert} \leq \frac{\left\lvert x-z \right\rvert}{1+\left\lvert x-z \right\rvert} + \frac{\left\lvert z-y \right\rvert}{1+\left\lvert z-y \right\rvert}. \] Set \(a = \left\lvert x-y \right\rvert, b = \left\lvert x-z \right\rvert, c = \left\lvert z-y \right\rvert\) and rewrite our target statement as \[ \frac{a}{1+a} \leq \frac{b}{1+b} + \frac{c}{1+c} \] expand everything \[\begin{gather*} a(1+b)(1+c) \stackrel{?}{\leq} b(1+a)(1+c) + c(1+a)(1+b) \\ a + ab + ac + abc \stackrel{?}{\leq} b + ab + bc + abc + c + ac + bc + abc \end{gather*}\] Again from the triangle inequality on the existing metric \(d(x,y) = \left\lvert x-y \right\rvert\) we have \(a \leq b + c\) which implies the equation above. \(\square\)

Homework 3

Rudin Chapter 2 Q14

For each \(i\in{\mathbb{N}}\), define \(G_i := (1/i, 1)\) which is clearly open. To see that \({\left\{\, G_i \,\right\}}_{i\in{\mathbb{N}}}\) is an open cover of \((0,1)\), let \(x\in (0,1)\). By Archimedean property choose \(n\in {\mathbb{N}}\) such that \(x > \frac1n\), then we have \(x \in G_n\). Now suppose on the contrary that there exists indices \(\alpha_1, \alpha_2, \dots, \alpha_n\) such that \[ {\left\{\, G_{\alpha_1}, G_{\alpha_2}, \dots, G_{\alpha_n} \,\right\}} \] still covers \((0,1)\). Let \(\beta = \max(\alpha_1, \alpha_2, \dots, \alpha_n)\). Then we can see that \(\frac1{\beta+1} \in (0,1)\) will not be in any \(G_{\alpha_i}\) for each \(i \in {\left\{\, 1,\dots,n \,\right\}}\).

Rudin Chapter 2 Q16

To see that \(E\) is closed, we show that \(\mathbb{Q}\smallsetminus E\) is open. Let \(x\in \mathbb{Q}, x\notin E\). So we have \(x^2 \leq 2\) or \(x^2 \geq 3\).

Clearly \(E\) is bounded between \(-9123\) and \(9138888888\).

To see that \(E\) is not compact, consider the sequence of open sets defined for \(i\) ranging over \({\mathbb{N}}\), \[ G_i = (\sqrt{2} + 1/i, \sqrt{3})\cap\mathbb{Q}. \] With a similar argument to Q14 it can be shown that no finite subcover of \({\left\{\, G_i \,\right\}}_{i\in{\mathbb{N}}}\) covers \(E\).

Lastly \(E\) is open in \(\mathbb{Q}\). Let \(x\in E\), so \(x\in\mathbb{Q}\) such that \(\sqrt{2} < x < \sqrt{3}\) or \(-\sqrt{3} < x < -\sqrt{2}\). We show the first case as the second argument is analogous but mirrored. Similar to the part on showing \(E\) is closed, use density to find \(a,b\in\mathbb{Q}\) such that \(\sqrt{2} < a < x < b < \sqrt{3}\), and set \(\delta := \min(x-a,b-x)\). Then we have for any \(z\in (x-\delta,x+\delta)\cap\mathbb{Q}\), \(2 < a^2 < y < b^2 < 3\).

Rudin Chapter 2 Q17

First note that the set \({{\left\{\, 4,7 \,\right\}}}^{{\mathbb{N}}}\) has an embedding in \(E\), as every infinite sequence over the set \({\left\{\, 4,7 \,\right\}}\) can be transformed faithfully into a number in \(E\). Since \({\left\{\, 4,7 \,\right\}}^{\mathbb{N}}\) which injects into \(E\) already has cardinality \(2^{\aleph_0}\) we see that \(\left\lvert E \right\rvert \geq 2^{\aleph_0}\) so in particular \(E\) is uncountable.

\(E\) is not dense as \([0.1,0.3] \cap E = \emptyset\) because \(0.4>0.3\) is easily seen as a lower bound for \(E\).

To show \(E\) is compact, we first check that \(E\) is obviously bounded. Now we show the complement of \(E\) is open. Let \(x \in E^c\), if \(x\notin [0,1]\) it’s trivial to find a neighbourhood around \(x\) that lies in \(E^c\), so WLOG assume \(x \in [0,1]\). Let \(x = 0.a_1a_2a_3\dots\) where each \(a_i \in {\left\{\, 0,1,\dots,9 \,\right\}}\), since \(x\notin E\), let \(k\) be the smallest index such that \(a_k \ne 4, a_k \ne 7\). Set \(\delta = \frac1{10^{k+999}}\) and we see that any number in the ball \((x-\delta, x+\delta)\) will still have the same \(k\)-th digit in its decimal expansion, so it will still lie in \(E^c\).

To see that \(E\) is perfect, let \(x \in E\). We want to show that \(x\) is a limit point. Let \(\varepsilon> 0\) be arbitrary, use Archimedean property to find \(n\in{\mathbb{N}}\) such that \(\frac1{10^n} < \varepsilon\). Express \(x\) as its decimal expansion \(x = 0.a_1a_2a_3\dots\), where \(a_i \in {\left\{\, 0,4,7 \,\right\}}\) (treat finite decimal expansions as being right-padded with trailing zeroes). Now set \[ y = 0.a_1a_2\dots a_na_{n+1}f(a_{n+2})a_{n+3}\dots \] where \[ f(0) = 4; f(4) = 7; f(7) = 4. \] Now verify that \(y\in E\), and after that we can check that \(\left\lvert y-x \right\rvert < \frac{1}{10^{n+1}} < \varepsilon\).