6.6: Exercises

EXERCISE 6.1. Let \(f: X \mapsto Y\) and \(g: Y \mapsto Z\). Prove that \[g \circ f: X \rightarrow Z\] is a bijection.

EXERCISE 6.2. Prove that equinumerosity is an equivalence relation.

EXERCISE 6.3. Prove that the relation on sets \(\preceq\) is reflexive and transitive. EXERCISE 6.4. In the proof of the Schröder-Bernstein Theorem, define a function \[G(x)=\left\{\begin{array}{clc} g^{-1}(x) & \text { if } & x \in X_{i} \\ f(x) & \text { if } & x \in X_{e} \\ g^{-1}(x) & \text { if } & X_{o} \end{array}\right.\] Prove that \(G: X \mapsto Y\).

EXERCISE 6.5. Let \(n \in \mathbb{N}\). Prove that \[|P(\ulcorner n\urcorner)|=2^{n} .\] EXERCISE 6.6. Let \(X=\{0,1,2\}\). Write down some function \(f\) : \(X \rightarrow P(X)\). For this particular \(f\), what is the set \(Y\) of Theorem 6.7?

EXERCISE 6.7. Let \(X\) be a set and define a sequence of sets \(\left\langle X_{n} \mid n \in \mathbb{N}\right\rangle\) by \[X_{0}=X\] and \[X_{n+1}=P\left(X_{n}\right) .\] Let \(Y=\bigcup_{n=0}^{\infty} X_{n}\). Prove \[(\forall n \in \mathbb{N})\left|X_{n}\right|<|Y| .\] ExERCISE 6.8. Let \(X\) and \(Y\) be finite sets. Prove that \[\left|X^{Y}\right|=|X|^{|Y|} \text {. }\] EXERCISE 6.9. Prove Proposition 6.8.

EXERCISE 6.10. Let \(f: \mathbb{N} \rightarrow\ulcorner 2\urcorner^{\mathbb{N}}\) and for \(i, j \in N^{+}\) \[a_{i j}=(f(i))_{j} .\] (That is, \(a_{i j}\) is the \(j^{t h}\) term of the \(i^{t h}\) sequence.) Let \(s\) be the "diagonal" sequence \[s=\left\langle 1-a_{n n} \mid n \in N^{+}\right\rangle .\] We know that \(s \notin f[\mathbb{N}]\). If \(F:\ulcorner 2\urcorner^{\mathbb{N}} \mapsto P(\mathbb{N})\) is the bijection in Proposition 6.8, then \(F \circ f: \mathbb{N} \rightarrow P(\mathbb{N})\). Prove that that \(F(s)\) is the "diagonal" set of Theorem \(6.7\) (where \(X=\mathbb{N}\), and \(F \circ f\) is the enumeration of subsets of \(\mathbb{N})\), and hence that \(F(s) \notin(F \circ f)[\mathbb{N}]\). ExERCISE 6.11. Prove that if \(X \subseteq Y\) and \(X\) is uncountable, then \(Y\) is uncountable.

EXERCISE 6.12. Let \(X\) be an uncountable set, \(Y\) be a countable set and \(f: X \rightarrow Y\). Prove that some element of \(Y\) has an uncountable pre-image.

EXERCISE 6.13. Complete the proof of Proposition 6.15.

EXERCISE 6.14. Define an explicit bijection from \(\mathbb{N}\) to \(\mathbb{Z}\).

EXERCISE 6.15. Prove that \(|\mathbb{K} \backslash \mathbb{Q}|=\aleph_{0}\).

EXERCISE 6.16. Prove that \[e=\sum_{n=0}^{\infty} \frac{1}{n !}\] is irrational. (Hint: Argue by contradiction. Assume \(e=\frac{p}{q}\) and multiply both sides by \(q\) !. Rearrange the equation to get an integer equal to an infinite sum of rational numbers that converges to a number in the open interval \((0,1)\).)

Remark: This was also Exercise 3.32. Is it easier now?

EXERCISE 6.17. Suppose that \(a, b, c, d \in \mathbb{R}, a<b\) and \(c<d\). Prove

a) The open interval \((a, b)\) is bijective with the open interval \((c, d)\).

b) The closed interval \([a, b]\) is bijective with the closed interval \([c, d]\).

c) The open interval \((0,1)\) is bijective with the closed interval \([0,1]\).

d) The open interval \((a, b)\) is bijective with the closed interval \([c, d]\).

e) \(|[0,1]|=|\mathbb{R}|\).

EXERCISE 6.18. Construct explicit bijections for each of the pairs of sets in Exercise 6.17.

EXERCISE 6.19. Let \(f(x)\) be a non-zero polynomial with integer coefficients, and suppose \(\alpha \in \mathbb{R}\) is transcendental. Prove that \(f(\alpha)\) is transcendental. EXERCISE 6.20. Let \(F: \mathbb{K} \rightarrow \mathbb{R}\) be defined by: If \(x \in \mathbb{K}, F(x)\) is the lowest degree of a polynomial with integer coefficients for which \(x\) is a root. Is \(F\) well-defined?

EXERCISE \(6.21\). Let \(a \in \mathbb{R}\) be a root of a polynomial with rational coefficients. Prove that \(a\) is a root of a polynomial with integer coefficients, and is therefore an algebraic number.

EXERCISE 6.22. For each of the following sets, state and prove whether it is bijective with \(\mathbb{N}, P(\mathbb{N})\) or is larger than \(P(\mathbb{N})\) (with respect to the relation \(\prec\) ):

a) The set of finite subsets of \(\mathbb{N}\)

b) The set of all permutations of finite sets of natural numbers

c) The set of finite sequences of natural numbers

d) The set of finite sequences of integers

e) The set of finite sequences of algebraic numbers

f) The set of finite sequences of real numbers

g) The set of infinite sequences of natural numbers

h) The set of infinite sequences of real numbers

i) Countable subsets of \(\mathbb{R}\).

h) \(\mathbb{N}^{\mathbb{R}}\)

k) \(\mathbb{R}^{\mathbb{R}}\).

You may use the fact that \(|\mathbb{R}|=2^{\aleph_{0}}\).

EXERCISE 6.23. Prove that \(\left|\mathbb{R}^{\mathbb{R}}\right| \geq|P(\mathbb{R})|\).