Every set is due at 11:59pm on Gradescope on the date listed.
Let \(E\) be a nonempty subset of an ordered set \(S\). Suppose \(\alpha\) is a lower bound of \(E\) and \(\beta\) is an upper bound of \(E\). Prove that \(\alpha \le \beta\).
The solution is on this page of Roger Cooke’s solutions manual to Rudin.
Let \(A\) be a nonempty set of real numbers which is bounded below, and let \(-A\) be the set of all numbers \(-x\) with \(x \in A\). Prove that
\[\inf A = -\sup(-A).\]The solution is on this page of Roger Cooke’s solutions manual to Rudin.
A nonempty subset of an ordered set is called bounded if it is bounded above and bounded below.
Show that a nonempty \(A \subseteq \R\) is bounded if and only if there exists \(M \ge 0\) such that \(\lvert x \rvert \le M\) for every \(x \in A\).
Prove that if \(A, B \subseteq \R\) are nonempty and bounded, then
\[A + B = \{a + b \;;\; a \in A,\, b \in B\} \quad\text{and}\quad A \cdot B = \{ab \;;\; a \in A,\, b \in B\}\]are both bounded.
If \(A\) is bounded, there exist \(K_1, K_2\) with \(K_2 \le x \le K_1\) for every \(x \in A\). Let \(M = \max\{\lvert K_1 \rvert, \lvert K_2 \rvert\}\). Then
\[-M \le K_2 \le x \le K_1 \le M\]for every \(x \in A\), so \(\lvert x \rvert \le M\).
Conversely, if there is \(M \ge 0\) with \(\lvert x \rvert \le M\) for every \(x \in A\), then \(-M \le x \le M\), so \(A\) is bounded below by \(-M\) and above by \(M\).
Let \(A\) and \(B\) be nonempty and bounded. By part 1 there are \(M_1, M_2 \ge 0\) with \(\lvert a \rvert \le M_1\) for all \(a \in A\) and \(\lvert b \rvert \le M_2\) for all \(b \in B\).
If \(x \in A + B\) then \(x = a + b\) for some \(a \in A\) and \(b \in B\), so
\[\lvert x \rvert = \lvert a + b \rvert \le \lvert a \rvert + \lvert b \rvert \le M_1 + M_2 .\]Since \(M_1 + M_2 \ge 0\), part 1 shows that \(A + B\) is bounded.
If \(y \in A \cdot B\) then \(y = ab\) for some \(a \in A\) and \(b \in B\), so \(\lvert y \rvert = \lvert a \rvert \lvert b \rvert \le M_1 M_2\), and part 1 shows that \(A \cdot B\) is bounded.
Prove that if \(A \subseteq \R\) is nonempty and bounded then
\[\sup_{x \in A} \lvert x \rvert = \max\{\lvert \sup A \rvert, \lvert \inf A \rvert\}.\]Write \(a = \inf A\), \(b = \sup A\), \(m = \max\{\lvert a \rvert, \lvert b \rvert\}\) and \(A' = \{\lvert x \rvert \;;\; x \in A\}\). The goal is \(m = \sup A'\).
First, \(m\) is an upper bound of \(A'\). Let \(x \in A\), so \(a \le x \le b\). If \(x \ge 0\) then \(0 \le x \le b\), hence \(\lvert x \rvert \le \lvert b \rvert \le m\). If \(x \le 0\) then \(a \le x \le 0\), hence \(\lvert x \rvert \le \lvert a \rvert \le m\). So \(\lvert x \rvert \le m\) for every \(x \in A\).
Suppose \(m \neq \sup A'\), and put \(\varepsilon = m - \sup A' > 0\). Since \(b = \sup A\), there is \(x \in A\) with
\[0 \le b - x = \lvert b - x \rvert < \varepsilon .\]By the triangle inequality,
\[\lvert x \rvert \ge \lvert b \rvert - \lvert b - x \rvert > \lvert b \rvert - \varepsilon .\]If \(m = \lvert b \rvert\) this gives \(\lvert x \rvert > m - \varepsilon = \sup A'\), a contradiction, so \(m \neq \lvert b \rvert\). The same argument at the infimum gives \(m \neq \lvert a \rvert\). Together these contradict the definition of \(m\), so \(m = \sup A'\).
Let \(A, B \subseteq \R\) be nonempty sets such that
\[a \le b \qquad \text{for every } (a,b) \in A \times B,\]and such that for every \(\varepsilon > 0\) there exists \((a,b) \in A \times B\) with \(\lvert a - b \rvert < \varepsilon\). Show that \(A\) is bounded above, that \(B\) is bounded below, and that \(\sup A = \inf B\).
By the first hypothesis, every element of \(A\) is a lower bound for \(B\) and every element of \(B\) is an upper bound for \(A\). So \(A\) is bounded above, \(B\) is bounded below, both \(\sup A\) and \(\inf B\) exist, and
\[a \le \inf B \quad (a \in A), \qquad \sup A \le b \quad (b \in B).\]These give \(\sup A \le \inf B\). It remains to show \(\sup A \ge \inf B\).
Let \(\varepsilon > 0\). By the second hypothesis there are \(a \in A\) and \(b \in B\) with \(0 \le b - a < \varepsilon\). Hence
\[\inf B \le b < a + \varepsilon \le \sup A + \varepsilon ,\]and since \(\varepsilon > 0\) was arbitrary, \(\inf B \le \sup A\).
Prove that if \(A, B \subseteq \R\) are nonempty and bounded above, then
\[\min\{\sup A, \sup B\} = \sup\{\min\{a,b\} \;;\; (a,b) \in A \times B\}.\]The statement is symmetric in \(A\) and \(B\), so assume without loss of generality that \(\sup A \ge \sup B\).
For every \((a,b) \in A \times B\),
\[\min\{a,b\} \le b \le \sup B = \min\{\sup A, \sup B\},\]so \(\sup\{\min\{a,b\} \;;\; (a,b) \in A \times B\} \le \min\{\sup A, \sup B\}\).
Let \(\varepsilon > 0\). By definition of supremum there are \(c \in A\) and \(d \in B\) with \(\sup A - \varepsilon < c\) and \(\sup B - \varepsilon < d\). Hence
\[\begin{aligned} \sup\{\min\{a,b\} \;;\; (a,b) \in A \times B\} &\ge \min\{c,d\} \\ &> \min\{\sup A - \varepsilon,\, \sup B - \varepsilon\} \\ &= \min\{\sup A, \sup B\} - \varepsilon . \end{aligned}\]As \(\varepsilon > 0\) was arbitrary, the reverse inequality follows.
If \(r\) is rational, \(r \neq 0\), and \(x\) is irrational, prove that \(r + x\) and \(rx\) are irrational.
Prove that there is no rational number whose square is \(12\). You can prove this directly or use 1.
The solution is on this page of Roger Cooke’s solutions manual to Rudin.
Prove that if \((a,b,c) \in \Q^3\) then
\[a + b \sqrt[3]{2} + c \sqrt[3]{4} = 0\]if and only if \(a = b = c = 0\). Hint: Try multiplying the equation by \(\theta = 2^{1/3}\), and solving a linear system of equations for $\theta$ and $\theta^2$.
An argument like the one for \(\sqrt{2}\) (Rudin, page 2) shows that \(\sqrt[3]{2}\) and \(\sqrt[3]{4}\) are both irrational. Hence if \(x\) and \(y\) are rational and any one of
\[x + y\sqrt[3]{2} = 0, \qquad x + y\sqrt[3]{4} = 0, \qquad x\sqrt[3]{2} + y\sqrt[3]{4} = 0\]holds, then \(x = y = 0\). In particular, if \((a,b,c) \in \Q^3\) satisfies \(a + b\sqrt[3]{2} + c\sqrt[3]{4} = 0\) and one of \(a, b, c\) is zero, then all three are.
Suppose some \((a,b,c) \in \Q^3\) satisfies the equation with at least one of them nonzero. By the previous paragraph none of \(a, b, c\) is zero. Multiplying by \(b - c\sqrt[3]{2}\) gives
\[(ab - 2c^2) + (b^2 - ac)\sqrt[3]{2} = \bigl(a + b\sqrt[3]{2} + c\sqrt[3]{4}\bigr) \bigl(b - c\sqrt[3]{2}\bigr) = 0 .\]Both \(ab - 2c^2\) and \(b^2 - ac\) are rational, so by the first paragraph
\[ab - 2c^2 = 0, \qquad b^2 - ac = 0 .\]Then \(a = b^2/c\), and substituting into \(ab = 2c^2\) gives \(b^3 = 2c^3\), so \(\sqrt[3]{2} = b/c \in \Q\), a contradiction.
Let
\[C = \{\sqrt{n} - \lfloor \sqrt{n} \rfloor \;;\; n \in \N\},\]where \(x \mapsto \lfloor x \rfloor\) is the floor function and \(\N = \Z_{\geq 0}\) is the set of natural numbers. Show that \(C\) is a bounded subset of \(\R\), and find with proof \(\inf C\) and \(\sup C\).
By definition of the floor function \(\lfloor x \rfloor \le x < \lfloor x \rfloor + 1\), so
\[0 \le \sqrt{n} - \lfloor \sqrt{n} \rfloor < 1 \qquad \text{for every } n \in \N,\]which gives \(0 \le \inf C \le \sup C \le 1\).
Since \(\sqrt{1} - \lfloor \sqrt{1} \rfloor = 1 - 1 = 0\), we get \(\inf C = 0\).
For the supremum, let \(\varepsilon > 0\); we produce \(x \in C\) with \(x > 1 - \varepsilon\). For every \(n \in \N\),
\[n - 1 \le \sqrt{n^2 - 1} < n,\]so \(\lfloor \sqrt{n^2 - 1} \rfloor = n - 1\) and
\[\sqrt{n^2 - 1} - \lfloor \sqrt{n^2 - 1} \rfloor = \sqrt{n^2 - 1} - n + 1 = 1 - \frac{1}{\sqrt{n^2 - 1} + n} \ge 1 - \frac{1}{2n - 1} .\]By the Archimedean property there is a positive integer \(m\) with \(1/(2m - 1) < \varepsilon\). Then
\[\sqrt{m^2 - 1} - \lfloor \sqrt{m^2 - 1} \rfloor > 1 - \varepsilon,\]and this number lies in \(C\). Hence \(\sup C = 1\).
A nonempty subset of \(\R\) is called an interval if it has the property that any number lying between two numbers in the subset also belongs to the subset. Assume that \(B\) is a bounded interval and that \(A \subseteq \R\) is nonempty and satisfies
\[\lvert x - y \rvert < \sup\{u - v \;;\; u, v \in B,\, u \ge v\} \qquad \text{for every } x, y \in A.\]Show that \(A + B\), defined as in Problem 3, is an interval.
\(A\) and \(B\) are nonempty, so \(A + B\) is nonempty. Note first that \(\{a\} + B\) is an interval for every \(a \in A\), being a translate of \(B\).
Let \(x, z \in A + B\) and let \(y \in \R\) with \(x \le y \le z\); we show \(y \in A + B\). Write \(x = a_1 + b_1\) and \(z = a_2 + b_2\) with \(a_1, a_2 \in A\) and \(b_1, b_2 \in B\).
If there is \(b \in B\) with \(y \le a_1 + b\), then \(y\) lies between \(a_1 + b_1\) and \(a_1 + b\), both of which are in \(\{a_1\} + B\), so \(y \in \{a_1\} + B \subseteq A + B\) and we are done.
Otherwise \(a_1 + b < y\) for every \(b \in B\). In particular \(a_1 + b_2 < y \le a_2 + b_2\), so \(a_1 < a_2\). By hypothesis
\[a_2 - a_1 < \sup\{u - v \;;\; u, v \in B,\, u \ge v\},\]so there are \(u, v \in B\) with \(u - v > a_2 - a_1\). Then
\[a_2 + v < a_1 + u < y \le a_2 + b_2 ,\]and \(a_2 + v\) and \(a_2 + b_2\) both lie in \(\{a_2\} + B\), which is an interval. Hence \(y \in \{a_2\} + B \subseteq A + B\).
Using the least upper bound property of \(\R\), show that every nonempty, upper bounded set of integers has a maximum.
Prove that no order can be defined on the complex field that turns it into an ordered field. Hint: \(-1\) is a square.
Suppose \(z = a + bi\) and \(w = c + di\). Define \(z < w\) if \(a < c\), and also if \(a = c\) but \(b < d\). Prove that this turns \(\C\) into an ordered set. (This kind of order relation is called a dictionary order, or lexicographic order, for obvious reasons.) Does this ordered set have the least upper bound property?
If \(z, w \in \C\), prove that
\[\bigl\lvert \lvert z \rvert - \lvert w \rvert \bigr\rvert \le \lvert z - w \rvert.\]If \(z \in \C\) and \(\lvert z \rvert = 1\), compute
\[\lvert 1 + z \rvert^2 + \lvert 1 - z \rvert^2.\]Prove that
\[\lvert x + y \rvert^2 + \lvert x - y \rvert^2 = 2 \lvert x \rvert^2 + 2 \lvert y \rvert^2\]for all \(x, y \in \R^k\). Interpret this geometrically, as a statement about parallelograms.
Prove that if \(k \ge 2\), then for every \(x \in \R^k\) there is a \(y \in \R^k\) with \(y \neq 0\) and \(x \cdot y = 0\). Is this also true when \(k = 1\)?
Recall the construction sketched in class (well it will be sketched in class this week). A cut is a set \(\alpha \subseteq \Q\) with the following three properties.
Prove the two consequences of (II) that we used without comment: if \(p \in \alpha\) and \(q \notin \alpha\) then \(p < q\); and if \(r \notin \alpha\) and \(r < s\) then \(s \notin \alpha\).
For \(r \in \Q\), let \(r^* = \{p \in \Q \;;\; p < r\}\). Prove that \(r^*\) is a cut.
Prove that
\[\alpha = \{p \in \Q \;;\; p < 0 \text{ or } p^2 < 2\}\]is a cut, and that \(\alpha \neq r^*\) for every \(r \in \Q\).
Write \(0^* = \{q \in \Q \;;\; q < 0\}\) and \(1^* = \{q \in \Q \;;\; q < 1\}\), and let \(\R^+\) be the set of cuts \(\alpha\) with \(\alpha > 0^*\). For \(\alpha, \beta \in \R^+\), define
\[\alpha\beta = \{p \in \Q \;;\; p \le rs \text{ for some } r \in \alpha,\ s \in \beta \text{ with } r > 0,\ s > 0\}.\]Prove that \(\alpha\beta\) is a cut, and that \(\alpha\beta \in \R^+\).
Prove that \(\alpha\beta = \beta\alpha\).
Prove that \(1^* \alpha = \alpha\).
Suppose property (III) were omitted from the definition of a cut. Keep the same definition of order, and define addition by
\[\alpha + \beta = \{r + s \;;\; r \in \alpha,\, s \in \beta\}\]as before. Show that the resulting ordered set still has the least upper bound property, and that addition still satisfies the axioms (A1) through (A4) (closure, commutativity, associativity, and an additive identity, though with a slightly different zero element), but that (A5), the existence of additive inverses, fails.
Fix \(b > 1\).
If \(m, n, p, q\) are integers with \(n > 0\), \(q > 0\), and \(r = m/n = p/q\), prove that
\[(b^m)^{1/n} = (b^p)^{1/q}.\]Hence it makes sense to define \(b^r = (b^m)^{1/n}\) for rational \(r\).
Prove that \(b^{r+s} = b^r b^s\) for all rational \(r\) and \(s\).
For real \(x\), let \(B(x)\) be the set of all \(b^t\) where \(t\) is rational and \(t \le x\). Prove that
\[b^r = \sup B(r)\]when \(r\) is rational. Hence it makes sense to define \(b^x = \sup B(x)\) for every real \(x\).
Fix \(b > 1\). On the previous set you defined \(b^x = \sup B(x)\) for every real \(x\), where \(B(x)\) is the set of all \(b^t\) with \(t\) rational and \(t \le x\). Prove that
\[b^{x+y} = b^x b^y\]for all real \(x\) and \(y\).
Throughout \(b > 1\) is fixed. For real \(x\) put
\[\begin{aligned} B(x) & = \{ t \in \Q,\ t < x \},\\ b^x & = \sup_{t \in B(x)} b^t. \end{aligned}\]Note the strict inequality \(t < x\). The previous set used \(t \le x\), and the first thing to check is that the change makes no difference.
Step 0: the two definitions agree. If \(x\) is irrational there is nothing to prove, since no rational \(t\) equals \(x\) and the two sets of exponents are literally the same set. So let \(r\) be rational, and let us check that
\[\sup \{ b^t \;;\; t \in \Q,\ t < r \} = b^r ,\]where on the right \(b^r\) is the rational power from the previous set. (With \(t \le r\) this was immediate, because \(b^r\) belongs to the set. With \(t < r\) it does not, and there is something to prove.)
Rational powers of \(b > 1\) are increasing, so \(b^t \le b^r\) for every rational \(t < r\), and \(b^r\) is an upper bound. For the other direction let \(u < b^r\); we produce a rational \(t < r\) with \(b^t > u\), which shows that no number below \(b^r\) is an upper bound. We may assume \(u > 0\), since every \(b^t\) is positive. For a positive integer \(n\) put \(c = b^{1/n} - 1\), which is positive because \(b > 1\). By the binomial theorem,
\[b = (1 + c)^n \ge 1 + nc , \qquad \text{so} \qquad 0 < b^{1/n} - 1 \le \frac{b - 1}{n} .\]Since \(b^r / u > 1\), the archimedean property gives an \(n\) with
\[\frac{b - 1}{n} < \frac{b^r}{u} - 1 ,\]and then \(b^{1/n} < b^r / u\). Take \(t = r - 1/n\), which is rational and less than \(r\). Then
\[b^t = \frac{b^r}{b^{1/n}} > u ,\]as required. So the supremum is exactly \(b^r\), and the two definitions of \(b^x\) agree for every real \(x\).
Everything below uses only the definition above and the laws of rational exponents from the previous set.
Step 1: \(b^{x+y} \le b^x b^y\). For any \(t \in \Q \cap (-\infty, x+y)\), find an \(s \in \Q\) such that
\[t - x < s < y .\]That this can be done is in Theorem 1.20(b) in Rudin.
This shows that \(t - s < x\) and thus \(t - s \in B(x)\) and \(s \in B(y)\). By what we’ve shown previously about rational exponents,
\[b^{t} = b^{t - s} b^s \leq b^{x} b^{y}\]by definition. Take a sup over \(t\) to get
\[b^{x + y} \leq b^x b^y .\]Step 2: \(b^x b^y \le b^{x+y}\). Take \(s \in B(x)\) and \(t \in B(y)\). Obviously, \(s + t \in B(x + y)\). Then we have
\[b^{s} b^{t} = b^{s + t} \leq b^{x + y} .\]Take a sup over \(s \in B(x)\) to get \(b^{x} b^t \leq b^{x + y}\). Then take another sup to get \(b^{x} b^{y} \leq b^{x + y}\). There are a couple of steps I’ve glossed over here: you may identify \(b^{x + y} b^{-t}\) as an upper bound for \(\{ b^s \colon s \in B(x)\}\), and thus the sup must be smaller than or equal to the upper bound.
Let \(f \colon X \to Y\) be an arbitrary function. Show that the following two statements are equivalent.
\(f\) is bijective.
There exists \(g \colon Y \to X\) such that \(g(f(x)) = x\) for every \(x \in X\), and \(f(g(y)) = y\) for every \(y \in Y\).
(1) implies (2). Since \(f\) is onto, for each \(y \in Y\) there is at least one \(x \in X\) with \(f(x) = y\); since \(f\) is one-to-one there is at most one. So for each \(y\) there is a unique such \(x\), and setting \(g(y) = x\) defines a function \(g \colon Y \to X\). If \(x \in X\) and \(y = f(x)\), then \(x\) is the unique preimage of \(y\), so \(g(f(x)) = x\); and if \(y \in Y\) then \(f(g(y)) = f(x) = y\).
(2) implies (1). The hypothesis says that \(g \circ f = 1_X\) and \(f \circ g = 1_Y\), the identity maps.
If \(f(x) = f(x')\) then \(x = g(f(x)) = g(f(x')) = x'\), so \(f\) is one-to-one. If \(y \in Y\) then \(y = f(g(y))\), so \(y\) is in the range of \(f\) and \(f\) is onto. Hence \(f\) is bijective.
Construct, with proof, an onto function \(f \colon \N \to \N\) such that \(f^{-1}(\{n\})\) is infinite for every \(n \in \N\). Here \(\N = \Z_{\ge 0}\) is the set of natural numbers.
There are many such functions. Let us find $g = f^{-1}$ instead. For $n=0$, let $g$ map to the even integers. We are left with the odd integers $A_0 = {1,3,\ldots}$. At stage $n$, we are given a countable, infinite subset $A_n = {x_0,\ldots}$ of the positive integers that has not been mapped to any of the previous integers $0,\ldots,n$. Let $g(n+1) = {x_0,x_2,\ldots}$, and let $A_{n+1} = {x_1,x_3,\ldots}$. Define $f = n$ on $g(n)$. This completes the inductive construction.
Here is another construction.
Define \(f \colon \N \to \N\) by
\[f(n) = n - \lfloor \sqrt{n} \rfloor^2 ,\]where \(\lfloor t \rfloor\) is the largest integer \(\le t\).
This is well defined: \(\lfloor \sqrt n \rfloor\) is an integer, so \(f(n)\) is an integer, and \(\lfloor \sqrt n \rfloor \le \sqrt n\) gives \(\lfloor \sqrt n \rfloor^2 \le n\), so \(f(n) \ge 0\).
Fix \(k \in \N\). For every integer \(n \ge k\),
\[n^2 \le n^2 + k < n^2 + 2n + 1 = (n+1)^2 ,\]so \(n \le \sqrt{n^2 + k} < n+1\), that is \(\lfloor \sqrt{n^2+k} \rfloor = n\). Therefore
\[f(n^2 + k) = n^2 + k - n^2 = k ,\]and so \(\{ n^2 + k \;;\; n \ge k \} \subseteq f^{-1}(\{k\})\). The set on the left is infinite, hence so is \(f^{-1}(\{k\})\). In particular it is nonempty for every \(k\), so \(f\) is onto.
Recall that two sets \(A\) and \(B\) are equivalent, written \(A \sim B\), if there is a one-to-one map of \(A\) onto \(B\). Show that a set is finite if and only if it is not equivalent to any of its proper subsets.
Suppose first that \(A\) is finite, with \(n\) elements, and let \(B \subsetneq A\). Then \(B\) has \(k\) elements for some \(k < n\), and two finite sets with different numbers of elements are not equivalent. So \(A\) is not equivalent to any of its proper subsets.
For the converse we prove the contrapositive: if \(A\) is infinite, then it is equivalent to a proper subset of itself.
Since \(A\) is infinite we may choose \(y_1 \in A\), and having chosen \(y_1, \dots, y_n\) we may choose
\[y_{n+1} \in A \setminus \{y_1, \dots, y_n\} ,\]which is nonempty because \(A\) is infinite. This produces a sequence of pairwise distinct points of \(A\); put \(B = \{ y_n \;;\; n \ge 1 \}\), a countable subset of \(A\). Define \(f \colon A \to A \setminus \{y_1\}\) by
\[f(x) = \begin{cases} x, & x \notin B, \\ y_{n+1}, & x = y_n . \end{cases}\]This is well defined because the \(y_n\) are distinct, so each \(x \in B\) equals \(y_n\) for exactly one \(n\). Directly from the definition,
\[f(A \setminus B) = A \setminus B, \qquad f(B) = B \setminus \{y_1\} .\]\(f\) is one-to-one. The two identities show that no point of \(B\) and point of \(A \setminus B\) have the same image, so it is enough to check the two cases separately. If \(x, x' \notin B\) and \(f(x) = f(x')\), then \(x = x'\). If \(x = y_i\) and \(x' = y_j\) and \(y_{i+1} = y_{j+1}\), then \(i = j\), again because the \(y_n\) are distinct.
\(f\) is onto \(A \setminus \{y_1\}\), since the two identities give
\[f(A) = (A \setminus B) \cup (B \setminus \{y_1\}) = A \setminus \{y_1\} .\]So \(A \sim A \setminus \{y_1\}\), and \(A \setminus \{y_1\}\) is a proper subset of \(A\).
Remark. Extracting the sequence \((y_n)\) makes infinitely many independent choices and cannot be carried out in ZF alone; it is an application of the axiom of countable choice. Rudin uses the same step without comment in the proof of Theorem 2.12.
A complex number \(z\) is said to be algebraic if there are integers \(a_0, \dots, a_n\), not all zero, such that
\[a_0 z^n + a_1 z^{n-1} + \dots + a_{n-1} z + a_n = 0.\]Prove that the set of all algebraic numbers is countable. Hint: for every positive integer \(N\) there are only finitely many equations with
\[n + \lvert a_0 \rvert + \lvert a_1 \rvert + \dots + \lvert a_n \rvert = N.\]Prove that there exist real numbers which are not algebraic.
Is the set of all irrational real numbers countable?
For me the solution is direct, and I don’t really understand why Rudin does it the way he does. Given any algebraic equation
\[a_0 z^n + a_1 z^{n-1} + \dots + a_{n-1} z + a_n = 0,\]the number of solutions is finite. The set of $n+1$ tuples
\[\{ (a_0,\ldots,a_n) \colon a_i \in \Z \}\]is countable since we have proved this in class (Theorem 2.13 of Rudin). The subsets where $a_0$ is non-zero is a subset of a countable set, and must be countable as well. Thus, algebraic numbers that solve a degree $n$ equation is countable since it is countable union of finite sets. Then take a union of degree $n$, and since this is a countable union of countable sets, we’re done. Also note that the rationals are solutions to $n z - m = 0$.
If you want to use the hint, we can do the following.
1. For an integer \(N \ge 1\), let \(A_N\) be the set of all complex \(z\) satisfying some equation
\[a_0 z^n + a_1 z^{n-1} + \dots + a_{n-1} z + a_n = 0, \qquad n + \lvert a_0 \rvert + \dots + \lvert a_n \rvert = N,\]with \(a_0, \dots, a_n\) integers, not all zero.
Each \(A_N\) is finite. The constraint forces \(n \le N\) and \(\lvert a_i \rvert \le N\) for every \(i\), so there are at most \(N (2N+1)^{N+1}\) such equations, and in particular finitely many. In each of them the left side is not the zero polynomial, so it has at most \(n \le N\) roots. A finite union of finite sets is finite.
Every algebraic number lies in some \(A_N\). If $z$ is algebraic, it must satisfy an equation of the above form. Set
\[N = n + \lvert a_0 \rvert + \dots + \lvert a_n \rvert,\]a positive integer. Then $z \in A_N$.
So the set of algebraic numbers is \(\bigcup_{N \ge 1} A_N\), a countable union of finite sets, hence at most countable by the corollary to Theorem 2.12. It is not finite, because every rational \(q\) is algebraic (it solves \(z - q = 0\)). So it is countable.
Why the hint carries an \(n\). The integer \(N\) has to bound the degree and the size of the coefficients at the same time. Drop the \(n\) and the equations \(z = 0\), \(z^2 = 0\), \(z^3 = 0, \dots\) all have coefficient sum \(1\), so the level sets are no longer finite.
2. The real algebraic numbers are a subset of the algebraic numbers, hence at most countable. If every real number were algebraic, then \(\R\) would be at most countable, contradicting the statements after Theorem 2.14 in Rudin. So some real number is not algebraic. (Such numbers are called transcendental.)
3. No. If \(\R \setminus \Q\) were countable, then \(\R = \Q \cup (\R \setminus \Q)\) would be a union of two countable sets and therefore countable by Theorem 2.12, contradicting the corollary to Theorem 2.14.
For \(x, y \in \R\), define
\[\begin{aligned} d_1(x,y) &= (x - y)^2, \\ d_2(x,y) &= \sqrt{\lvert x - y \rvert}, \\ d_3(x,y) &= \lvert x^2 - y^2 \rvert, \\ d_4(x,y) &= \lvert x - 2y \rvert, \\ d_5(x,y) &= \frac{\lvert x - y \rvert}{1 + \lvert x - y \rvert}. \end{aligned}\]Determine, for each of these, whether it is a metric on \(\R\).
This problem is Rudin 2.11. The solution is on this page.
For each of the following subsets of \(\R\), find, with proof, its limit points and its interior points.
\[\left\{ \frac{1}{n} \;;\; n \in \Z,\, n \ge 1 \right\}, \qquad (0,1) \cap \Q, \qquad \left\{ (-1)^n + \frac{1}{n} \;;\; n \in \Z,\, n \ge 1 \right\}.\]First, any nonempty open interval \((a,b)\) is uncountable: the function
\[f \colon (a,b) \to \R, \qquad f(y) = \tan\left( \frac{\pi(2y - a - b)}{2(b-a)} \right), \qquad \forall\, y \in (a,b),\]is easily seen to be bijective. In particular this implies that any open ball \(B(x,r) = (x-r, x+r)\) contains irrational numbers. Given that all three subsets are also subsets of \(\Q\), it follows that none of them has interior points.
Next, we claim that the first subset, which we denote by \(A\), has \(0\) as its unique limit point. For all \(r > 0\) the Archimedean property ensures the existence of a positive integer \(n\) such that \(r > 1/n\). It follows that
\[\frac1n \in (0,r) \cap A = \big(B(0,r) \setminus \{0\}\big) \cap A,\]which leads to \(\big(B(0,r) \setminus \{0\}\big) \cap A \ne \emptyset\), thus proving that \(0 \in A'\). In arguing that any \(x \ne 0\) is not a limit point for \(A\), one can check easily that \(\big(B(x,r) \setminus \{x\}\big) \cap A = \emptyset\) if
For the second subset, labeled \(B\), the claim is that \(B' = [0,1]\). In arguing that \(x \notin B'\) when either \(x < 0\) or \(x > 1\), we can work with exactly the same radii used for the subset \(A\). On the other hand, if \(0 \le x \le 1\) and \(r > 0\) then
\[\begin{aligned} \big(B(x,r) \setminus \{x\}\big) \cap B &= \big( (x-r,x) \cup (x,x+r) \big) \cap \big( (0,1) \cap \Q \big) \\ &= \Big( \big(\max\{x-r,0\},\, x\big) \cup \big(x,\, \min\{x+r,1\}\big) \Big) \cap \Q \;\ne\; \emptyset, \end{aligned}\]due to Theorem 1.20(b) and the fact that at least one of the two intervals in the last line is nonempty.
For the third set, denoted \(C\), the only limit points are \(-1\) and \(1\). The argument is very similar to the one for \(A\) and this is why we only sketch it. If \(r > 0\), then, for a positive integer \(n > 1/r\), we have
\[1 + \frac{1}{2n} \in \big(B(1,r) \setminus \{1\}\big) \cap C \qquad \text{and} \qquad -1 + \frac{1}{2n+1} \in \big(B(-1,r) \setminus \{-1\}\big) \cap C.\]For $x$ which is neither $1$ nor $-1$, we write
\(C = \{0,-1 + 1/3, -1 + 1/5,\ldots\} \cup \{1+1/2,1 + 1/4, \ldots\}\).
So for \(x < -1\), choose \(r = \vert x + 1\vert\). For \(-1 < x < 0\), there are \(u,v \in C\) such that \((u,v) \cap C = \emptyset\). So we can take \(r = \min\{x - u, v - x\}\) here. For \(0 < x < 1\), we can take \(r = \min(x,1-x)\), etc. In all of these cases, with \(r\) appropriately chosen we see that
\[\big(B(x,r) \setminus \{x\}\big) \cap C = \emptyset\]which implies that $x$ is not an accumulation point.
Let \(n\) be a positive integer and let \(A\) be a set with \(n\) elements. Prove that there are exactly \(3^n\) ordered pairs of sets \((X, Y)\) satisfying
\[X \cup Y = A.\]In order to identify a solution \((X,Y)\) to \(X \cup Y = A\), we have to make a decision for each \(a \in A\) as to which of the following three scenarios takes place:
\[\big( a \in X \setminus Y \big) \qquad \text{or} \qquad \big( a \in X \cap Y \big) \qquad \text{or} \qquad \big( a \in Y \setminus X \big).\]Given that these decisions are independent from one \(a\) to another, and that there are \(n\) of them, the multiplication principle of combinatorics yields that the number of solutions is \(3^n\).
Assume \(0 < m < M\) and that \(a_1, \dots, a_n \in [m, M]\). Show that
\[\left( \sum_{i=1}^{n} a_i \right) \left( \sum_{i=1}^{n} \frac{1}{a_i} \right) \le n^2 \, \frac{(M + m)^2}{4Mm}.\]This is called Kantorovich’s inequality.
Again, we give two solutions. Note first that for $a,b > 0$
\[2 \sqrt{a b} \geq a + b\](square both sides or use AM/GM).
\[\begin{align*} 2 \sqrt{\left( \sum_{i=1}^{n} a_i \right) \left( \sum_{i=1}^{n} \frac{1}{a_i} \right) } & \leq \sum_{i=1}^{n} a_i + \sum_{i=1}^{n} a_i^{-1} \end{align*}\]Now, we use the trick discussed in class and introduce a new parameter $s > 0$.
\[\begin{align*} 2 \sqrt{ \left( \sum_{i=1}^{n} a_i \right) \left( \sum_{i=1}^{n} \frac{1}{a_i} \right) } & \leq \sum_{i=1}^{n} s a_i + \sum_{i=1}^{n} (s a_i)^{-1}\\ & \leq n \max_{1 \leq i \leq n} \left( s a_i + (s a_i)^{-1} \right) \end{align*}\]Now, we have to choose $s > 0$ correctly. The function $f(c) = s c + 1 / (s c)$ has a minimum at $c = 1/s$, and taking derivatives we see that it is convex. For us, $c$ varies in $[m,M]$. Then clearly $\left( s a_i + (s a_i)^{-1} \right)$ must take its maximum values at either $m$ or $M$. So it makes sense to choose $s$ such that
\[s m + (s m)^{-1} = s M + (s M)^{-1}\]which gives $s = 1/\sqrt{m M}$. Plugging this into the above, we get
\[4 \left( \sum_{i=1}^{n} a_i \right) \left( \sum_{i=1}^{n} \frac{1}{a_i} \right) \leq \frac{ (M + m)^2 }{M m}\]Another solution
Each \(a_i\) lies in \([m,M]\), so \((a_i - m)(M - a_i) \ge 0\), which expands to
\[a_i^2 + mM \le (m+M)\, a_i .\]Divide by \(a_i > 0\) and sum over \(i\):
\[\sum_{i=1}^{n} a_i + mM \sum_{i=1}^{n} \frac{1}{a_i} \le n(m+M).\]Write \(S = \sum_{i=1}^n a_i\) and \(T = \sum_{i=1}^n 1/a_i\), both positive. The inequality \(u + v \ge 2\sqrt{uv}\) for \(u, v \ge 0\) (which is just \((\sqrt u - \sqrt v)^2 \ge 0\)), applied to \(u = S\) and \(v = mM\,T\), gives
\[2\sqrt{mM \, S T} \;\le\; S + mM \, T \;\le\; n(m+M).\]Both sides are nonnegative, so squaring is legitimate and yields \(4mM \, ST \le n^2 (m+M)^2\), that is
\[\left( \sum_{i=1}^{n} a_i \right) \left( \sum_{i=1}^{n} \frac{1}{a_i} \right) \le n^2 \, \frac{(M+m)^2}{4Mm}.\]Prove that for any \(n\) distinct positive integers \(x_1, \dots, x_n\),
\[\left( \sum_{i=1}^{n} x_i \right)^2 \le \sum_{i=1}^{n} x_i^3.\]Hint: try the case \(x_k = k\) first, and show that
\[(1 + 2 + \dots + n)^2 = 1^3 + 2^3 + \dots + n^3.\]Again two solutions. Let us first use the hint. Let
\[T_n = 1 + \cdots + n\]Then,
\[\begin{align*} T_n^2 - T_{n-1}^2 & = (T_n - T_{n-1} ) (T_n + T_{n-1} )\\ & = (n) (2 T_{n-1} + n )\\ & = (n) (n (n-1) + n )\\ & = n^3. \end{align*}\]which is exactly what we needed to prove (the rest follows by telescoping). So in general, assume that the list is sorted $x_1 < \cdots < x_n$ with
\[T_n = x_1 + \cdots + x_n\]we have
\[\begin{align*} T_n^2 - T_{n-1}^2 & = (x_n) (2 T_{n-1} + x_n )\\ & \leq (x_n) (x_n ( x_n - 1) + x_n )\\ & = x_n^3 \end{align*}\]which would be true if
\[2 T_{n-1} \leq x_n (x_n - 1)\]Now we use distinctness! If we summed all the numbers from $1,\ldots,x_{n} - 1$, then we would get exactly the sum $x_n(x_n - 1)/2$. But there could be some of these missing in the set ${x_1,\ldots,x_{n-1}}$. Therefore the upper bound for $2 T_{n-1}$ holds and after telescoping, we are done:
\[T_n^2 \leq x_1^3 + \cdots + x_n^3.\]Another way of writing the proof (due to Dan Geba):
We prove the statement by simple induction. The base case (i.e. \(n = 1\)) reads as \(x_1^2 \le x_1^3\), which is equivalent to \(x_1^3 - x_1^2 = x_1^2(x_1 - 1) \ge 0\). However, this holds true since \(x_1 \ge 1\), which is due to \(x_1\) being a positive integer.
For the inductive step, we assume that the result is valid for \(n = k\) and we show that it is also valid for \(n = k+1\). Due to the hypothesis and the symmetry of the estimate in all the variables, we can assume, without loss of generality, that
\[x_1 < x_2 < \dots < x_k < x_{k+1} .\]Since all \(x_i\) are integers, it follows that
\[\sum_{i=1}^{k} x_i \le 1 + 2 + \dots + (x_{k+1} - 2) + (x_{k+1} - 1) = \frac{x_{k+1}^2 - x_{k+1}}{2},\]which can be rewritten as
\[2 x_{k+1} \sum_{i=1}^{k} x_i + x_{k+1}^2 \le x_{k+1}^3 .\]By the inductive hypothesis we have
\[\left( \sum_{i=1}^{k} x_i \right)^2 \le \sum_{i=1}^{k} x_i^3 .\]Adding up the two inequalities term by term, we deduce
\[\left( \sum_{i=1}^{k+1} x_i \right)^2 = \left( \sum_{i=1}^{k} x_i \right)^2 + 2 x_{k+1} \sum_{i=1}^{k} x_i + x_{k+1}^2 \le \sum_{i=1}^{k+1} x_i^3 ,\]which is the desired conclusion.
Let \(E\) be a subset of a metric space \(X\), and let \(E'\) be the set of all limit points of \(E\).
Prove that \(E'\) is closed.
Prove that \(E\) and \(\overline{E}\) have the same limit points. Recall that \(\overline{E} = E \cup E'\).
Do \(E\) and \(E'\) always have the same limit points?
This problem is Rudin 2.6. The solution is on this page.
Let \(A_1, A_2, A_3, \dots\) be subsets of a metric space.
If \(B_n = \bigcup_{i=1}^{n} A_i\), prove that
\[\overline{B_n} = \bigcup_{i=1}^{n} \overline{A_i} \qquad (n = 1, 2, 3, \dots).\]If \(B = \bigcup_{i=1}^{\infty} A_i\), prove that
\[\overline{B} \supseteq \bigcup_{i=1}^{\infty} \overline{A_i}.\]Show, by an example, that this inclusion can be proper.
This problem is Rudin 2.7. The solution is on these pages.
Is every point of every open set \(E \subseteq \R^2\) a limit point of \(E\)? Answer the same question for closed sets in \(\R^2\).
This problem is Rudin 2.8. The solution is on this page.
Let \(E^{\circ}\) denote the set of all interior points of a set \(E\) in a metric space \(X\). It is called the interior of \(E\).
Prove that \(E^{\circ}\) is always open.
Prove that \(E\) is open if and only if \(E^{\circ} = E\).
If \(G \subseteq E\) and \(G\) is open, prove that \(G \subseteq E^{\circ}\).
Prove that the complement of \(E^{\circ}\) is the closure of the complement of \(E\).
Do \(E\) and \(\overline{E}\) always have the same interiors?
Do \(E\) and \(E^{\circ}\) always have the same closures?
This problem is Rudin 2.9. The solution is on these pages.
Let \(A \subseteq \R\) be arbitrary and let \(D \subseteq \R\) be open. Prove that
\[\overline{A} \cap D \subseteq \overline{A \cap D} \qquad \text{and} \qquad A^{\circ} \cap D \subseteq (A \cap D)^{\circ}.\]Show by an example that the first inclusion can fail if \(D\) is not open.
First, we argue based on Definition 2.26 that the first inclusion holds true if \(A' \cap D \subseteq (A \cap D)'\) is valid. Indeed,
\[\overline{A} \cap D = (A \cup A') \cap D = (A \cap D) \cup (A' \cap D) \subseteq (A \cap D) \cup (A \cap D)' = \overline{A \cap D}.\]If \(A' \cap D = \emptyset\), the inclusion \(A' \cap D \subseteq (A \cap D)'\) is obvious. Otherwise, let \(x \in A' \cap D\) be arbitrary. The goal is to show that \(x \in (A \cap D)'\), which is equivalent to
\[\big(B(x,r) \setminus \{x\}\big) \cap (A \cap D) \neq \emptyset, \qquad \forall\, r > 0.\]Since \(x \in D\) and \(D\) is open, there exists \(\bar r > 0\) such that \(B(x,\bar r) \subseteq D\). This implies, also factoring in \(x \in A'\),
\[\begin{aligned} \emptyset \neq \big(B(x,\min\{r,\bar r\}) \setminus \{x\}\big) \cap A &= \Big( \big(B(x,\min\{r,\bar r\}) \setminus \{x\}\big) \cap D \Big) \cap A \\ &= \big(B(x,\min\{r,\bar r\}) \setminus \{x\}\big) \cap (A \cap D) \subseteq \big(B(x,r) \setminus \{x\}\big) \cap (A \cap D). \end{aligned}\]This finishes the proof of the first inclusion.
For the second inclusion, let \(x \in A^{\circ} \cap D\). Since \(x \in A^{\circ}\), there is \(r_1 > 0\) with \(B(x,r_1) \subseteq A\), and since \(x \in D\) and \(D\) is open, there is \(r_2 > 0\) with \(B(x,r_2) \subseteq D\). With \(r = \min\{r_1, r_2\}\),
\[B(x,r) \subseteq A \cap D,\]so \(x\) is an interior point of \(A \cap D\), that is \(x \in (A \cap D)^{\circ}\).
For the example, take \(A = \Q\) and \(D = \Q + \sqrt{2} = \{q + \sqrt{2} \;;\; q \in \Q\}\), which is not open. Every \(q + \sqrt{2}\) is irrational (HW 1, problem 7), so \(A \cap D = \emptyset\) and \(\overline{A \cap D} = \emptyset\). On the other hand \(\overline{\Q} = \R\), so
\[\overline{A} \cap D = \R \cap (\Q + \sqrt{2}) = \Q + \sqrt{2} \neq \emptyset,\]and the first inclusion fails.
Let \(B \subseteq \R\) be at most countable. Show that
\[(\R \setminus B)' = \R,\]where \(E'\) denotes the set of limit points of \(E\).
The argument is by contradiction. Assuming that \((\R \setminus B)' \neq \R\), it follows that there exists \(x \in \R\) which is not a limit point for \(\R \setminus B\). According to Definition 2.18, there exists \(r > 0\) such that
\[\big(B(x,r) \setminus \{x\}\big) \cap (\R \setminus B) = \emptyset.\]This implies that \(B(x,r) \setminus \{x\} \subseteq B\) and, since \(B\) is at most countable, the same is true about \(B(x,r) \setminus \{x\}\).
However, the function
\[f \colon B(x,r) \setminus \{x\} \to \R \setminus \{0\}, \qquad f(y) = \tan\left( \frac{\pi(y - x)}{2r} \right), \qquad \forall\, y \in B(x,r) \setminus \{x\},\]is easily seen to be bijective. Hence, \(B(x,r) \setminus \{x\}\) and \(\R \setminus \{0\}\) are equivalent. As \(\R \setminus \{0\}\) is obviously uncountable, we derive that \(B(x,r) \setminus \{x\}\) is also uncountable, thus arriving at a contradiction.
Find, with proof, the limit points of the set
\[\left\{ \frac{1}{n} + \frac{1}{m} \;;\; n, m \in \Z,\, n \ge 1,\, 1 \le m \le 2^n - 1 \right\}.\]We claim that for the set in question, labeled \(A\), the limit points are
\[\left\{ \frac{1}{n} \;;\; n \in \Z,\, n \ge 1 \right\} \cup \{0\}.\]First, we show that
\[A = \left\{ \frac{1}{n} + \frac{1}{m} \;;\; n, m \in \Z,\, 1 \le m \le n \right\},\]which is a more friendly-working version than the original one. If we denote by \(B\) the set on the right, one has immediately that \(B \subseteq A\), since an easy inductive argument yields that \(n \le 2^n - 1\) for all \(n \ge 1\). On the other hand, by relabeling the indices \(m\) and \(n\), we observe that
\[B = \left\{ \frac{1}{n} + \frac{1}{m} \;;\; n, m \in \Z,\, n, m \ge 1 \right\}\]and, hence, \(A \subseteq B\).
Next, if \(r > 0\), \(m \ge 1\), and \(n\) is a positive integer satisfying \(n > \max\{1/r, m\}\), then
\[\frac{1}{2n} + \frac{1}{2n} \in \big(B(0,r) \setminus \{0\}\big) \cap A \qquad \text{and} \qquad \frac{1}{n} + \frac{1}{m} \in \left( B\left(\frac{1}{m}, r\right) \setminus \left\{\frac{1}{m}\right\} \right) \cap A.\]This proves that
\[\left\{ \frac{1}{n} \;;\; n \in \Z,\, n \ge 1 \right\} \cup \{0\} \subseteq A'.\]For the opposite inclusion, if \(x < 0\) then
\[\big(B(x,-x) \setminus \{x\}\big) \cap A = \emptyset.\]If \(x > 0\) and \(x \neq \frac{1}{n}\) for any \(n \ge 1\), we argue first that there exists a nonnegative integer \(k\) such that
\[\frac{1}{k+1} < x < \frac{1}{k},\]with the convention that \(1/0 = \infty\). Further, we can find nonnegative integer \(j\) such that
\[\frac{1}{k+1} + \frac{1}{j+1} \le x < \frac{1}{k+1} + \frac{1}{j} \le \frac{1}{k}.\]Finally, a direct argument yields that there are only finitely many pairs of positive integers \((m,n)\) satisfying
\[\frac{1}{k+1} < \frac{1}{m} + \frac{1}{n} < \frac{1}{k} \qquad \text{and} \qquad k + 1 < m \le n.\]All these facts allow us to infer that we can choose \(r > 0\) such that
\[\big(B(x,r) \setminus \{x\}\big) \cap A = \emptyset.\]Let \(K \subseteq \R\) consist of \(0\) together with the numbers \(1/n\) for \(n = 1, 2, 3, \dots\). Prove that \(K\) is compact directly from the definition, without using the Heine-Borel theorem.
This problem is Rudin 2.12. The solution is on this page.
Give an example of an open cover of the segment \((0,1)\) which has no finite subcover.
This problem is Rudin 2.14. The solution is on this page.
Regard \(\Q\), the set of all rational numbers, as a metric space with \(d(p,q) = \lvert p - q \rvert\). Let \(E\) be the set of all \(p \in \Q\) such that \(2 < p^2 < 3\).
Show that \(E\) is closed and bounded in \(\Q\), but that \(E\) is not compact. Is \(E\) open in \(\Q\)?
This problem is Rudin 2.16. The solution is on these pages.
Recall the construction of the Cantor set. Put \(E_0 = [0,1]\), and let \(E_n\) be obtained from \(E_{n-1}\) by deleting the open middle third of each of the intervals making up \(E_{n-1}\), so that \(E_n\) is a union of \(2^n\) closed intervals of length \(3^{-n}\). The Cantor set is
\[P = \bigcap_{n=1}^{\infty} E_n .\]Show that each \(E_n\) is compact and that \(E_1 \supseteq E_2 \supseteq E_3 \supseteq \dots\), and conclude that \(P\) is nonempty and compact.
Show that \(P\) contains no segment.
Prove that \(P\) is perfect: every point of \(P\) is a limit point of \(P\).
Let \(S\) be the set of all sequences \(a = (\alpha_1, \alpha_2, \dots)\) in which every \(\alpha_n\) is either \(0\) or \(2\). For \(a \in S\) put
\[s_N(a) = \sum_{n=1}^{N} \frac{\alpha_n}{3^{n}}, \qquad x(a) = \sup_{N \ge 1} s_N(a) .\]Show that \(s_N(a)\) is increasing in \(N\) and bounded above by \(1\), so that \(x(a)\) is a well defined element of \([0,1]\). (Once we have series, \(x(a)\) will be the sum \(\sum_{n \ge 1} \alpha_n 3^{-n}\); for now the supremum is all we need.)
Prove that \(\{ x(a) \;;\; a \in S \}\) is exactly the Cantor set \(P\) of the previous problem.
Prove that \(a \mapsto x(a)\) is one-to-one, and deduce from the diagonal argument that \(P\) is uncountable.
So \(P\) is an uncountable set (of measure zero as you’ll see in MATH 471), a set with as many points as \([0,1]\) and no segment inside it.
Theorem 2.36 says that if \(\{K_\alpha\}\) is a collection of compact sets with the finite intersection property, then \(\bigcap K_\alpha\) is nonempty; its corollary is the nested version for \(K_1 \supseteq K_2 \supseteq \dots\).
Show that the corollary fails in \(\R\) if “compact” is weakened to “closed”, and that it also fails if “compact” is weakened to “bounded”. That is, produce
nonempty closed sets \(F_1 \supseteq F_2 \supseteq \dots\) in \(\R\) with \(\bigcap_{n} F_n = \emptyset\), and
nonempty bounded sets \(B_1 \supseteq B_2 \supseteq \dots\) in \(\R\) with \(\bigcap_{n} B_n = \emptyset\).
Let \(K \subseteq \R\) be nonempty and compact. Prove that there exist \(a, b \in K\) such that
\[\lvert x - y \rvert \le \lvert a - b \rvert \qquad \text{for all } x, y \in K .\]In other words, a compact set attains its diameter.
Let \(C \subseteq \R\) be an infinite compact set. Show that there exists \(c \in C\) such that \(C \setminus \{c\}\) is not compact.
Which points \(c\) work, and what does the answer say about perfect sets?
Is there a nonempty perfect set in \(\R\) which contains no rational number? Prove your answer.
Let \(X\) be a metric space.
If \(A\) and \(B\) are disjoint closed subsets of \(X\), prove that they are separated.
Prove the same for disjoint open subsets of \(X\).
Fix \(p \in X\) and \(\delta > 0\). Let \(A\) be the set of \(q \in X\) with \(d(p,q) < \delta\) and let \(B\) be the set of \(q \in X\) with \(d(p,q) > \delta\). Prove that \(A\) and \(B\) are separated.
Prove that every connected metric space with at least two points is uncountable. Use part 3.
Let \((A_i)_{i \in I}\) be a family of connected subsets of \(\R\) such that \(A_i \cap A_j \ne \emptyset\) for every pair of indices \((i,j) \in I \times I\). Show that
\[\bigcup_{i \in I} A_i\]is a connected subset of \(\R\).
Let \((x_n)_{n \ge 1}\) be a sequence of real numbers for which the three subsequences
\[(x_{2n})_{n \ge 1}, \qquad (x_{2n+1})_{n \ge 1}, \qquad (x_{3n})_{n \ge 1}\]all have a limit. Prove that \((x_n)_{n \ge 1}\) has a limit.
Let \((x_n)_{n \ge 1}\) be a sequence of rational numbers which converges to an irrational number. Write each term in lowest terms,
\[x_n = \frac{p_n}{q_n}, \qquad p_n, q_n \in \Z,\ q_n \ge 1,\ \gcd(p_n, q_n) = 1 .\]Prove that \(q_n \to \infty\).
Let \(\{s_n\}\) be a sequence of real numbers, and recall that Rudin defines \(\limsup s_n\) as the supremum, in the extended real numbers, of the set of subsequential limits of \(\{s_n\}\) (Definition 3.16). For \(n \ge 1\) put
\[\sigma_n = \sup_{k \ge n} s_k, \qquad \iota_n = \inf_{k \ge n} s_k,\]where \(\sigma_n = +\infty\) if \(\{s_n\}\) is not bounded above and \(\iota_n = -\infty\) if it is not bounded below.
Show that \(\{\sigma_n\}\) is nonincreasing and \(\{\iota_n\}\) is nondecreasing.
Prove that
\[\limsup_{n \to \infty} s_n = \inf_{n \ge 1} \sigma_n \qquad \text{and} \qquad \liminf_{n \to \infty} s_n = \sup_{n \ge 1} \iota_n .\]Hint: Theorem 3.17.
Use part 2 to give a one-line proof of Theorem 3.19: if \(s_n \le t_n\) for \(n \ge N\), where \(N\) is fixed, then \(\liminf s_n \le \liminf t_n\) and \(\limsup s_n \le \limsup t_n\).
Prove that convergence of \(\{s_n\}\) implies convergence of \(\{\lvert s_n \rvert\}\). Is the converse true?
Calculate
\[\lim_{n \to \infty} \left( \sqrt{n^2 + n} - n \right).\]If \(s_1 = \sqrt{2}\) and
\[s_{n+1} = \sqrt{2 + \sqrt{s_n}} \qquad (n = 1, 2, 3, \dots),\]prove that \(\{s_n\}\) converges, and that \(s_n < 2\) for \(n = 1, 2, 3, \dots\).
Let \((x_n)_{n \ge 1}\) be the sequence of real numbers given by
\[x_1 = a \in \R, \qquad x_{n+1} = \frac{x_n}{\sqrt{1 + x_n^2}} \qquad (n \ge 1).\]Show that \((x_n)_{n \ge 1}\) converges to \(0\).
Let \((x_n)_{n \ge 1}\) be given by \(x_1 > -1\) and
\[x_{n+1} = \frac{2}{1 + x_n} \qquad (n \ge 1).\]Decide, with proof, whether \((x_n)_{n \ge 1}\) converges or diverges.
Fix a positive number \(\alpha\). Choose \(x_1 > \sqrt{\alpha}\), and define \(x_2, x_3, x_4, \dots\) by the recursion formula
\[x_{n+1} = \frac{1}{2} \left( x_n + \frac{\alpha}{x_n} \right).\]Prove that \(\{x_n\}\) decreases monotonically and that \(\lim x_n = \sqrt{\alpha}\).
Put \(\varepsilon_n = x_n - \sqrt{\alpha}\), and show that
\[\varepsilon_{n+1} = \frac{\varepsilon_n^2}{2 x_n} < \frac{\varepsilon_n^2}{2\sqrt{\alpha}},\]so that, setting \(\beta = 2\sqrt{\alpha}\),
\[\varepsilon_{n+1} < \beta \left( \frac{\varepsilon_1}{\beta} \right)^{2^n} \qquad (n = 1, 2, 3, \dots).\]This is a good algorithm for computing square roots, since the recursion formula is simple and the convergence is extremely rapid. For example, if \(\alpha = 3\) and \(x_1 = 2\), show that \(\varepsilon_1 / \beta < \frac{1}{10}\) and that therefore
\[\varepsilon_5 < 4 \cdot 10^{-16}, \qquad \varepsilon_6 < 4 \cdot 10^{-32}.\]Suppose \(\{p_n\}\) is a Cauchy sequence in a metric space \(X\), and some subsequence \(\{p_{n_i}\}\) converges to a point \(p \in X\). Prove that the full sequence \(\{p_n\}\) converges to \(p\).
Prove the following analogue of Theorem 3.10(b): if \(\{E_n\}\) is a sequence of closed nonempty and bounded sets in a complete metric space \(X\), if \(E_n \supseteq E_{n+1}\), and if
\[\lim_{n \to \infty} \operatorname{diam} E_n = 0,\]then \(\bigcap_{n=1}^{\infty} E_n\) consists of exactly one point.
Find the upper and lower limits of the sequence \(\{s_n\}\) defined by
\[s_1 = 0; \qquad s_{2m} = \frac{s_{2m-1}}{2}; \qquad s_{2m+1} = \frac{1}{2} + s_{2m}.\]For any two real sequences \(\{a_n\}\), \(\{b_n\}\), prove that
\[\limsup_{n \to \infty} (a_n + b_n) \le \limsup_{n \to \infty} a_n + \limsup_{n \to \infty} b_n,\]provided the sum on the right is not of the form \(\infty - \infty\).
Let \((x_n)_{n \ge 1}\) be a sequence of real numbers and \(\lambda \in (-1, 1)\) such that
\[\lim_{n \to \infty} (x_{n+1} - \lambda x_n) = 0.\]Show that \((x_n)_{n \ge 1}\) converges to \(0\).
Show that the series
\[\sum_{n \ge 2} \ln\left( 1 - \frac{1}{n^2} \right)\]is convergent, and compute its sum.
Investigate the behavior (convergence or divergence) of
\[\sum_{n \ge 1} \frac{1}{1 + z^{n}}\]for complex values of \(z\). Your answer should cover every \(z\) for which the terms are defined.
Let \((x_n)_{n \ge 1}\) be a sequence of real numbers such that
\[\sum_{n \ge 2} \lvert x_n - x_{n-1} \rvert\]is convergent. Prove that \((x_n)_{n \ge 1}\) is convergent. Give an example showing that the converse is false.
Investigate the nature of the series
\[\sum_{n \ge 1} \frac{1}{n + x^{n}},\]where \(x\) is an arbitrary nonnegative number.
Investigate the nature of the series
\[\sum_{n \ge 1} \frac{1}{n \left( 1 + x + \dots + x^{n} \right)},\]where \(x\) is an arbitrary nonnegative number.
Let \((x_n)_{n \ge 1}\) be a non-increasing sequence of real numbers, that is \(x_n \ge x_{n+1}\) for every \(n \ge 1\), and suppose \(\sum_{n \ge 1} x_n\) is convergent. Show that
\[\lim_{n \to \infty} n x_n = 0 .\]Prove that if \((x_n)_{n \ge 1}\) is a strictly increasing, divergent sequence of real numbers, then the series
\[\sum_{n \ge 1} \frac{x_{n+1} - x_n}{x_{n+1}}\]is divergent.
Let \((x_n)_{n \ge 1}\) have positive terms. Argue that \(\sum_{n \ge 1} x_n\) is convergent if and only if there exists a strictly increasing, divergent sequence \((z_n)_{n \ge 1}\) of positive numbers such that
\[x_n = \frac{1}{z_n} - \frac{1}{z_{n+1}} \qquad \text{for every } n \ge 1 .\]Let \((x_n)_{n \ge 1}\) be a sequence of real numbers for which \(\sum_{n \ge 1} x_n^{2}\) is convergent. Argue that
\[\lim_{n \to \infty} \frac{x_1 + x_2 + \dots + x_n}{n} = 0 .\]Suppose \(a_n > 0\), put \(s_n = a_1 + \dots + a_n\), and suppose \(\sum a_n\) diverges.
Prove that \(\displaystyle \sum \frac{a_n}{1 + a_n}\) diverges.
Prove that
\[\frac{a_{N+1}}{s_{N+1}} + \dots + \frac{a_{N+k}}{s_{N+k}} \ge 1 - \frac{s_N}{s_{N+k}},\]and deduce that \(\displaystyle \sum \frac{a_n}{s_n}\) diverges.
Prove that
\[\frac{a_n}{s_n^{2}} \le \frac{1}{s_{n-1}} - \frac{1}{s_n},\]and deduce that \(\displaystyle \sum \frac{a_n}{s_n^{2}}\) converges.