22nd Feb 2019

Homework 1

Q1

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.

• Case $$\left\lvert \left\lvert x \right\rvert - \left\lvert y \right\rvert \right\rvert = \left\lvert x \right\rvert - \left\lvert y \right\rvert$$, we can see that \begin{align*} \left\lvert x \right\rvert &= \left\lvert (x - y) + y \right\rvert \\ &\leq \left\lvert x-y \right\rvert + \left\lvert y \right\rvert \end{align*} by triangle inequality which implies the result.

• Case $$\left\lvert \left\lvert x \right\rvert - \left\lvert y \right\rvert \right\rvert = \left\lvert y \right\rvert - \left\lvert x \right\rvert$$ is similar because $$\left\lvert x-y \right\rvert = \left\lvert y-x \right\rvert$$.

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$$.

• Case $$x^2 \leq 2$$, then $$x^2 < 2$$ in fact because $$\sqrt{2} \notin \mathbb{Q}$$.

• Case $$x > 0$$, then $$x < \sqrt{2}$$. Use density to choose rational $$y$$ such that $$x < y < \sqrt{2}$$. Set $$\delta = \min(y-x, x-0)$$ and we consider the ball that is $$(x-\delta, x+\delta)\cap\mathbb{Q}$$. To show that the ball is contained in $$\mathbb{Q}\smallsetminus E$$. Let $$z\in\mathbb{Q}$$ such that $$x-\delta < z < x+\delta$$, then $$0 < z < y$$, so $$0 < z^2 < y^2 < 2$$.

• Case $$x < 0$$, then $$x > -\sqrt{2}$$. Proceed similarly as above argument and choose rational $$y$$ such that $$-\sqrt{2} < y < x$$. Set $$\delta = \min(x-y, -x)$$ and consider the ball $$(x-\delta, x+\delta)\cap\mathbb{Q}$$. Let $$z\in\mathbb{Q}$$ such that $$x-\delta < z < x+\delta$$, then $$y < z < 0$$, so $$0 < z^2 < y^2 < 2$$.

• Case $$x = 0$$, then we can easily see that the ball $$(-1,1)\cap\mathbb{Q}$$ lies in $$\mathbb{Q}\smallsetminus E$$.

• Case $$x^2 \geq 3$$, then similarly $$x^2 > 3$$.

• Case $$x > \sqrt{3}$$, choose rational $$y$$ satisfying $$\sqrt{3} < y < x$$. Set $$\delta = x-y$$ and consider the ball $$(x-\delta,x+\delta)\cap\mathbb{Q}$$. For any $$z\in\mathbb{Q}, x-\delta < z < x+\delta$$, we have $$y < z$$ so $$3 < y^2 < z^2$$.

• Case $$x < -\sqrt{3}$$, the argument is analogous, just mirrored.

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$$.