1.8: Exercises

EXERCISE 1.1. Show that

\(\{n \in \mathbb{N} \mid n\) is odd and \(n=k(k+1)\) for some \(k \in \mathbb{N}\}\)

is empty.

EXERCISE 1.2. Let \(X\) and \(Y\) be subsets of some set \(U\). Prove de Morgan’s laws: \[\begin{aligned} &(X \cup Y)^{c}=X^{c} \cap Y^{c} \\ &(X \cap Y)^{c}=X^{c} \cup Y^{c} \end{aligned}\] ExERCISE 1.3. Let \(X, Y\) and \(Z\) be sets. Prove \[\begin{aligned} &X \cap(Y \cup Z)=(X \cap Y) \cup(X \cap Z) \\ &X \cup(Y \cap Z)=(X \cup Y) \cap(X \cup Z) . \end{aligned}\] EXERCISE 1.4. Let \(X=\ulcorner 2\urcorner, Y=\ulcorner 3\urcorner\), and \(Z=\ulcorner 1\urcorner\). What are the following sets:

(i) \(X \times Y\).

(ii) \(X \times Y \times Z\).

(iii) \(X \times Y \times Z \times \emptyset\).

(iv) \(X \times X\).

(v) \(X^{n}\).

EXERCISE 1.5. Suppose \(X\) is a set with \(m\) elements, and \(Y\) is a set with \(n\) elements. How many elements does \(X \times Y\) have? Is the answer the same if one or both of the sets is empty?

EXERCISE 1.6. How many elements does \(\emptyset \times \mathbb{N}\) have?

EXERCISE 1.7. Describe all possible intervals in \(\mathbb{Z}\).

EXERCISE 1.8. Let \(X\) and \(Y\) be finite non-empty sets, with \(m\) and \(n\) elements, respectively. How many functions are there from \(X\) to \(Y\) ? How many injections? How many surjections? How many bijections?

EXERCISE 1.9. What happens in Exercise \(1.8\) if \(m\) or \(n\) is zero?

EXERCISE 1.10. For each of the following sets, which of the operations addition, subtraction, multiplication, division and exponentiation are operations on the set:

(i) \(\mathbb{N}\)

(ii) \(\mathbb{Z}\)

(iii) \(\mathbb{Q}\)

(iv) \(\mathbb{R}\)

(v) \(\mathbb{R}^{+}\).

EXERCISE 1.11. Let \(f\) and \(g\) be real functions, \(f(x)=3 x+8\), \(g(x)=x^{2}-5 x\). What are \(f \circ g\) and \(g \circ f\) ? Is \((f \circ g) \circ f=f \circ(g \circ f)\) ?

EXERCISE 1.12. Write down all permutations of \(\{a, b, c\}\).

EXERCISE 1.13. What is the natural generalization of Exercise \(1.2\) to an arbitrary number of sets? Verify your generalized laws. ExERCISE 1.14. What is the natural generalization of Exercise \(1.3\) to an arbitrary number of sets? Verify your generalized laws.

EXERCISE 1.15. Let \(X\) be the set of all triangles in the plane, \(Y\) the set of all right-angled triangles, and \(Z\) the set of all non-isosceles triangles. For any triangle \(T\), let \(f(T)\) be the longest side of \(T\), and \(g(T)\) be the maximum of the lengths of the sides of \(T\). On which of the sets \(X, Y, Z\) is \(f\) a function? On which is \(g\) a function?

What is the complement of \(Z\) in \(X\) ? What is \(Y \cap Z^{c}\) ?

EXERCISE 1.16. For each positive real \(t\), let \(X_{t}=(-t, t)\) and \(Y_{t}=\) \([-t, t]\). Describe

(i) \(\bigcup_{t>0} X_{t}\) and \(\bigcup_{t>0} Y_{t}\).

(ii) \(\bigcup_{0<t<10} X_{t}\) and \(\bigcup_{0<t<10} Y_{t}\).

(iii) \(\bigcup_{0<t \leq 10}^{0<t<10} X_{t}\) and \(\bigcup_{0<t \leq 10}^{0<t<10} Y_{t}\).

(iv) \(\bigcap_{t>10}^{0<t \leq 10} X_{t}\) and \(\bigcap_{t>10}^{0<t \leq 10} Y_{t}\).

\((\mathrm{v}) \bigcap_{t>10}^{t \geq 10} X_{t}\) and \(\bigcap_{t>10}^{t \geq 10} Y_{t}\)

(vi) \(\bigcap_{t>0}^{t>10} X_{t}\) and \(\bigcap_{t>0}^{t>10} Y_{t}\).

EXERCISE 1.17. Let \(f\) be the real function cosine, and let \(g\) be the real function \(g(x)=\frac{x^{2}+1}{x^{2}-1}\).

(i) What are \(f \circ g, g \circ f, f \circ f, g \circ g\) and \(g \circ g \circ f\) ?

(ii) What are the domains and ranges of the real functions \(f, g, f \circ g\) and \(g \circ f\) ?

EXERCISE 1.18. Let \(X\) be the set of vertices of a square in the plane. How many permutations of \(X\) are there? How many of these come from rotations? How many come from reflections in lines? How many come from the composition of a rotation and a reflection?

EXERCISE 1.19. Which of the following real functions are injective, and which are surjective:

(i) \(f_{1}(x)=x^{3}-x+2\).

(ii) \(f_{2}(x)=x^{3}+x+2\). (iii) \(f_{3}(x)=\frac{x^{2}+1}{x^{2}-1}\).

(iv) \(f_{4}(x)= \begin{cases}-x^{2} & x \leq 0 \\ 2 x+3 & x>0\end{cases}\)

EXERCISE 1.20. Suppose \(f: X \rightarrow Y\) and \(g: Y \rightarrow Z\). Prove that if \(g \circ f\) is injective, then \(f\) is injective.

Give an example to show that \(g\) need not be injective.

EXERCISE 1.21. Suppose \(f: X \rightarrow Y\) and \(g: Y \rightarrow Z\).

(i) Show that if \(f\) and \(g\) are surjective, so is \(g \circ f\).

(ii) Show that if \(g \circ f\) is surjective, then one of the two functions \(f, g\) must be surjective (which one?). Give an example to show that the other function need not be surjective.

EXERCISE 1.22. For what \(n \in \mathbb{N}\) is the function \(f(x)=x^{n}\) an injection.

EXERCISE 1.23. Let \(f: \mathbb{R} \rightarrow \mathbb{R}\) be a polynomial of degree \(n \in \mathbb{N}\). For what values of \(n\) must \(f\) be a surjection, and for what values is it not a surjection?

EXERCISE 1.24. Write down a bijection from \((X \times Y)\) times \(Z\) to \(X \times(Y\) times \(Z)\). Prove that it is one-to-one and onto.

ExERCISE 1.25. Let \(X\) be a set with \(n\) elements. How many permutations of \(X\) are there?

EXERCISE 1.26. Let \(f: \mathbb{R} \rightarrow \mathbb{R}\) be a function built using only natural numbers and addition, multiplication and exponentiation (for instance \(f\) could be defined as \(\left.x \mapsto(x+3)^{x^{2}}\right)\). What can you say about \(f[\mathbb{N}] ?\) What can you say if we include subtraction or division?

EXERCISE 1.27. Let \(f(x)=x^{3}-x .\) Find sets \(X\) and \(Y\) such that \(f: X \rightarrow Y\) is a bijection. Is there a maximal choice of \(X ?\) If there is, is it unique? Is there a maximal choice of \(y\) ? If there is, is it unique?

EXERCISE 1.28. Let \(f(x)=\tan (x)\). Use set notation to define the domain and range of \(f\). What is \(f^{-1}(1)\) ? What is \(f^{-1}\left[\mathbb{R}^{+}\right] ?\) EXERCISE 1.29. For each of the following real functions, find an interval \(X\) that contains more than one point and such that the function is a bijection from \(X\) to \(f[X]\). Find a formula for the inverse function.

(i) \(f_{1}(x)=x^{2}+5 x+6\).

(ii) \(f_{2}(x)=x^{3}-x+2\).

(iii) \(f_{3}(x)=\frac{x^{2}+1}{x^{2}-1}\).

(iv) \(f_{4}(x)= \begin{cases}-x^{2} & x \leq 0 \\ 2 x+3 & x>0\end{cases}\)

EXERCISE 1.30. Find formulas for the following sequences:

(i) \(\langle 1,2,9,28,65,126, \ldots\rangle\).

(ii) \(\langle 1,-1,1,-1,1,-1, \ldots\rangle\).

(iii) \(\langle 2,1,10,27,66,125,218, \ldots\rangle\).

(iv) \(\langle 1,1,2,3,5,8,13,21, \ldots\rangle\).

EXERCISE 1.31. Let the real function \(f\) be strictly increasing. Show that for any \(b \in \mathbb{R}, f^{-1}(b)\) is either empty or consists of a single element, and that \(f\) is therefore an injection. If \(f\) is also a bijection, is the inverse function of \(f\) also strictly increasing?

EXERCISE 1.32. Let \(f\) be a real function that is a bijection. Show that the graph of \(f^{-1}\) is the reflection of the graph of \(f\) in the line \(y=x\).

EXERCISE 1.33. Let \(X_{n}=\{n+1, n+2, \ldots, 2 n\}\) for each \(n \in \mathbb{N}^{+}\) as in Example 1.43. What are

(i) \(\cup_{n=1}^{5} X_{n}\).

(ii) \(\cap_{n=4}^{6} X_{n}\).

(iii) \(\cap_{k=1}^{5}\left[\cup_{n=1}^{k} X_{n}\right]\).

(iv) \(\cap_{k=5}^{\infty}\left[\cup_{n=3}^{k} X_{n}\right]\).

EXERCISE 1.34. Verify the assertions of Example 1.44.

EXERCISE 1.35. Let \(f: X \rightarrow Y\), and assume that \(U_{\alpha} \subseteq X\) for every \(\alpha \in A\), and \(V_{\beta} \subseteq Y\) for every \(\beta \in B\). Prove: \[\begin{aligned} & \text { (i) } f\left(\bigcup_{\alpha \in A} U_{\alpha}\right)=\bigcup_{\alpha \in A} f\left(U_{\alpha}\right) \\ & \text { (ii) } f\left(\bigcap_{\alpha \in A} U_{\alpha}\right) \subseteq \bigcap_{\alpha \in A} f\left(U_{\alpha}\right) \\ & \text { (iii) } f^{-1}\left(\bigcup_{\beta \in B} V_{\beta}\right)=\bigcup_{\beta \in B} f^{-1}\left(V_{\beta}\right) \\ & \text { (iv) } f^{-1}\left(\bigcap_{\beta \in B} V_{\beta}\right)=\bigcap_{\beta \in B} f^{-1}\left(V_{\beta}\right) \text {. } \end{aligned}\] Note that (ii) has containment instead of equality. Give an example of proper containment in part (ii). Find a condition on \(f\) that would ensure equality in (ii).