8.11: Exercises

EXERCISE 8.1. Let \(S\) be the successor function in Definition 8.1. Prove that \[S(\emptyset) \neq \emptyset .\] Prove that for any set \(X\), \[S(X) \neq X .\] EXERCISE 8.2. Prove that no proper subset of \(\mathbf{N}\) (see equation 8.1) is inductive.

EXERCISE 8.3. Let \(\mathcal{F}=\left\{X_{\alpha} \mid \alpha \in Y\right\}\) be a family of inductive sets indexed by \(Y\). Prove that \[\bigcap_{\alpha \in Y} X_{\alpha}\] is inductive.

EXERCISE 8.4. Prove that addition and multiplication in \(\mathbb{N}\) (as formally defined in Section 8.1) are associative, commutative and distributive.

EXERCISE 8.5. Prove that the relation \(\leq\) defined on \(\mathbb{N}\) in Section \(8.1\) is a linear ordering of \(\mathbb{N}\).

EXERCISE 8.6. Prove that addition and multiplication in \(\mathbb{Z}\) (as formally defined in Section 8.2) are associative, commutative and distributive.

EXERCISE 8.7. Prove that the relation \(\leq\) defined on \(\mathbb{Z}\) in Section \(8.2\) is a linear ordering of \(\mathbb{Z}\).

EXERCISE 8.8. Prove that \(\leq\) is a well ordering of \(\mathbb{N}\) but not of \(\mathbb{Z}\) (using the formal definition of the relation).

EXERCISE 8.9. Prove that addition and multiplication in \(\mathbb{Z}\) and the relation \(\leq\) on \(\mathbb{Z}\) extends the operations and relation on \(\mathbb{N}\). Let \(I: \mathbb{N} \rightarrow \mathbb{Z}\) be defined by \[I(n)=[\langle n, 0\rangle] .\] Prove that \(I\) is an injection and that for all \(m, n \in \mathbb{N}\), \[I(m+n)=I(m)+I(n),\] \[I(m \cdot n)=I(m) \cdot I(n)\] and \[m \leq n \Rightarrow I(m) \leq I(n)\] Note that the operations on the left hand sides of equations \(8.24\) and \(8.25\) are defined in \(\mathbb{N}\) and on the right hand side are defined in \(\mathbb{Z}\). Similarly, the antecedent of statement \(8.26\) is defined in \(\mathbb{N}\) and the consequence is defined in \(\mathbb{Z}\).

EXERCISE 8.10. Prove that addition and multiplication \(\mathbb{Q}\) (as formally defined in Section 8.3) are associative, commutative and distributive.

EXERCISE 8.11. Prove that the relation \(\leq\) defined on \(\mathbb{Q}\) in Section \(8.3\) is a linear ordering of \(\mathbb{Q}\).

EXERCISE 8.12. Prove that addition and multiplication on \(\mathbb{Q}\) and the relation \(\leq\) on \(\mathbb{Q}\) extends the operations and relation on \(\mathbb{Q}\). Let \(I: \mathbb{Z} \rightarrow \mathbb{Q}\) be defined by \[I(a)=[\langle a, 1\rangle] .\] Prove that \(I\) is an injection and that for all \(a, b \in \mathbb{Z}\), \[\begin{gathered} I(a+b)=I(a)+I(b) \\ I(a \cdot b)=I(a) \cdot I(b) \end{gathered}\] and \[a \leq b \Rightarrow I(a) \leq I(b)\] Note that the operations on the left hand sides of equations \(8.27\) and \(8.28\) are defined in \(\mathbb{Z}\) and on the right hand side are defined in \(\mathbb{Q}\). Similarly, the antecedent of statement \(8.29\) is defined in \(\mathbb{Z}\) and the consequence is defined in \(\mathbb{Q}\).

EXERCISE 8.13. Prove that every non-zero element of \(\mathbb{Q}\) has a multiplicative inverse in \(\mathbb{Q}\). ExERCISE 8.14. Prove statements (1), (2) and (3) in Section 8.4.

EXERCISE 8.15. Prove Theorem 8.2.

EXERCISE 8.16. Let \(X \subseteq \mathbb{R}, Y \subseteq \mathbb{R}\) and let every element of \(X\) be less than every element of \(Y\). Prove that there is \(a \in \mathbb{R}\) satisfying \[(\forall x \in X)(\forall y \in Y) x \leq a \leq y .\] EXERCISE 8.17. Let \(X \subseteq \mathbb{R}\) be bounded above. Prove that the least upper bound of \(X\) is unique.

EXERCISE 8.18. Let \(X \subseteq \mathbb{R}\) be bounded below. Prove that \(X\) has a greatest lower bound.

EXERCISE 8.19. Only the special case of the Bolzano-Weierstrass Theorem (Theorem 8.6) was proved (where \([b, c]\) is the closed unit interval, \([0,1])\). Generalize the proof to arbitrary \(b, c \in \mathbb{R}\) where \(b \leq c\).

EXERCISE 8.20. Let \(X \subseteq \mathbb{R}\). We say that \(X\) is dense in \(\mathbb{R}\) if given any \(a, b \in \mathbb{R}\) with \(a<b\), there is \(x \in X\) such that \[a \leq x \leq b .\] a) Prove that \(\mathbb{Q}\) is dense in \(\mathbb{R}\).

b) Prove that \(\mathbb{R} \backslash \mathbb{Q}\) is dense in \(\mathbb{R}\).

EXERCISE 8.21. Let \(\left\langle a_{n}\right\rangle\) be an injective sequence. What is the cardinality of the set of all subsequences of \(\left\langle a_{n}\right\rangle\) ? What can you say about the set of subsequences of a non-injective sequence?

EXERCISE 8.22. Let \(s\) be an infinite decimal expansion, and for any \(n \in \mathbb{N}^{+}\), let \(s_{n}\) be the truncation of \(s\) to the \(n^{t h}\) decimal place. Prove that the sequence \(\left\langle s_{n}\right\rangle\) is a Cauchy sequence.

EXERCISE 8.23. Let \(\left\langle a_{n}\right\rangle\) be a convergent sequence and \(\left\langle a_{f(n)}\right\rangle\) be a subsequence of \(\left\langle a_{n}\right\rangle\). Prove that \[\lim _{n \rightarrow \infty} a_{n}=\lim _{n \rightarrow \infty} a_{f(n)} .\] ExERCISE 8.24. Prove the following generalization of the triangle inequality: if the series \(\sum_{n=0}^{\infty} a_{n}\) converges, then \[\left|\sum_{n=0}^{\infty} a_{n}\right| \leq \sum_{n=0}^{\infty}\left|a_{n}\right| .\] EXERCISE 8.25. Let \(f\) be a real function continuous at \(a\), and let \(\left\langle a_{n}\right\rangle\) be a sequence converging to \(a\). Prove that \[\lim _{n \rightarrow \infty} f\left(a_{n}\right)=f(a) .\] ExERCISE 8.26. Give an example of a continuous function on an open interval that achieves its extreme values on the interval. Give an example of a continuous function defined on an open interval that does not achieve its extreme values on the interval.

EXERCISE 8.27. Complete the proof of Theorem \(8.12\) - that is, prove the result for \(f(c)\) a minimum value of \(f\) on \((a, b)\).

EXERCISE 8.28. Prove Corollary 8.15.

EXERCISE 8.29. Prove that any continuous injective real function on an interval is monotonic on that interval.

EXERCISE 8.30. Prove that there is no continuous bijection from \((0,1)\) to \([0,1]\).

EXERCISE 8.31. Prove that every polynomial in \(\mathbb{R}[x]\) of odd degree has at least one real root.

EXERCISE 8.32. Prove that if you have a square table, with legs of equal length, and a continuous floor, you can always rotate the table so that all 4 legs are simultaneously in contact with the floor. (Hint: Apply the Intermediate value theorem to an appropriately chosen function). This is one of the earliest applications of mathematics to coffee-houses.

EXERCISE 8.33. The proof of Proposition 8.16 requires that nonzero real numbers have reciprocals (and hence quotients of real numbers are well-defined). Prove that non-zero real numbers have reciprocals. ExERCISE 8.34. Show that there are exactly 4 order-complete extensions of \(\mathbb{Q}\) in which \(\mathbb{Q}\) is dense.