Skip to main content

Exercises 1.5 Additional Exercises

1.

If \(A = \{ a, b, c \}\text{,}\) \(B = \{ 1, 2, 3 \}\text{,}\) \(C = \{ x \}\text{,}\) and \(D = \emptyset\text{,}\) list all of the elements in each of the following sets.

  1. \(\displaystyle A \times B\)

  2. \(\displaystyle B \times A\)

  3. \(\displaystyle A \times B \times C\)

  4. \(\displaystyle A \times D\)

Hint.

(a) \(A \times B = \{ (a,1), (a,2), (a,3), (b,1), (b,2), (b,3), (c,1), (c,2), (c,3) \}\text{;}\) (d) \(A \times D = \emptyset\text{.}\)

2.

Find an example of two nonempty sets \(A\) and \(B\) for which \(A \times B = B \times A\) is true.

3.

Prove \(A \cup \emptyset = A\) and \(A \cap \emptyset = \emptyset\text{.}\)

4.

Prove \(A \cup B = B \cup A\) and \(A \cap B = B \cap A\text{.}\)

5.

Prove \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\text{.}\)

Hint.

If \(x \in A \cup (B \cap C)\text{,}\) then either \(x \in A\) or \(x \in B \cap C\text{.}\) Thus, \(x \in A \cup B\) and \(A \cup C\text{.}\) Hence, \(x \in (A \cup B) \cap (A \cup C)\text{.}\) Therefore, \(A \cup (B \cap C) \subset (A \cup B) \cap (A \cup C)\text{.}\) Conversely, if \(x \in (A \cup B) \cap (A \cup C)\text{,}\) then \(x \in A \cup B\) and \(A \cup C\text{.}\) Thus, \(x \in A\) or \(x\) is in both \(B\) and \(C\text{.}\) So \(x \in A \cup (B \cap C)\) and therefore \((A \cup B) \cap (A \cup C) \subset A \cup (B \cap C)\text{.}\) Hence, \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\text{.}\)

6.

Prove \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\text{.}\)

7.

Prove \(A \subset B\) if and only if \(A \cap B = A\text{.}\)

8.

Prove \((A \cap B)' = A' \cup B'\text{.}\)

9.

Prove \(A \cup B = (A \cap B) \cup (A \setminus B) \cup (B \setminus A)\text{.}\)

Hint.

\((A \cap B) \cup (A \setminus B) \cup (B \setminus A) = (A \cap B) \cup (A \cap B') \cup (B \cap A') = [A \cap (B \cup B')] \cup (B \cap A') = A \cup (B \cap A') = (A \cup B) \cap (A \cup A') = A \cup B\text{.}\)

10.

Prove \((A \cup B) \times C = (A \times C ) \cup (B \times C)\text{.}\)

11.

Prove \((A \cap B) \setminus B = \emptyset\text{.}\)

12.

Prove \((A \cup B) \setminus B = A \setminus B\text{.}\)

13.

Prove \(A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)\text{.}\)

Hint.

\(A \setminus (B \cup C) = A \cap (B \cup C)' = (A \cap A) \cap (B' \cap C') = (A \cap B') \cap (A \cap C') = (A \setminus B) \cap (A \setminus C)\text{.}\)

14.

Prove \(A \cap (B \setminus C) = (A \cap B) \setminus (A \cap C)\text{.}\)

15.

Prove \((A \setminus B) \cup (B \setminus A) = (A \cup B) \setminus (A \cap B)\text{.}\)

16.

Which of the following relations \(f: {\mathbb Q} \rightarrow {\mathbb Q}\) define a mapping? In each case, supply a reason why \(f\) is or is not a mapping.

  1. \(\displaystyle \displaystyle f(p/q) = \frac{p+ 1}{p - 2}\)

  2. \(\displaystyle \displaystyle f(p/q) = \frac{3p}{3q}\)

  3. \(\displaystyle \displaystyle f(p/q) = \frac{p+q}{q^2}\)

  4. \(\displaystyle \displaystyle f(p/q) = \frac{3 p^2}{7 q^2} - \frac{p}{q}\)

Hint.

(a) Not a map since \(f(2/3)\) is undefined; (b) this is a map; (c) not a map, since \(f(1/2) = 3/4\) but \(f(2/4)=3/8\text{;}\) (d) this is a map.

17.

Determine which of the following functions are one-to-one and which are onto. If the function is not onto, determine its range.

  1. \(f: {\mathbb R} \rightarrow {\mathbb R}\) defined by \(f(x) = e^x\)

  2. \(f: {\mathbb Z} \rightarrow {\mathbb Z}\) defined by \(f(n) = n^2 + 3\)

  3. \(f: {\mathbb R} \rightarrow {\mathbb R}\) defined by \(f(x) = \sin x\)

  4. \(f: {\mathbb Z} \rightarrow {\mathbb Z}\) defined by \(f(x) = x^2\)

Hint.

(a) \(f\) is one-to-one but not onto. \(f({\mathbb R} ) = \{ x \in {\mathbb R} : x \gt 0 \}\text{.}\) (c) \(f\) is neither one-to-one nor onto. \(f(\mathbb R) = \{ x : -1 \leq x \leq 1 \}\text{.}\)

18.

Let \(f :A \rightarrow B\) and \(g : B \rightarrow C\) be invertible mappings; that is, mappings such that \(f^{-1}\) and \(g^{-1}\) exist. Show that \((g \circ f)^{-1} =f^{-1} \circ g^{-1}\text{.}\)

19.
  1. Define a function \(f: {\mathbb N} \rightarrow {\mathbb N}\) that is one-to-one but not onto.

  2. Define a function \(f: {\mathbb N} \rightarrow {\mathbb N}\) that is onto but not one-to-one.

Hint.

(a) \(f(n) = n + 1\text{.}\)

20.

Prove the relation defined on \({\mathbb R}^2\) by \((x_1, y_1 ) \sim (x_2, y_2)\) if \(x_1^2 + y_1^2 = x_2^2 + y_2^2\) is an equivalence relation.

21.

Define a function on the real numbers by

\begin{equation*} f(x) = \frac{x + 1}{x - 1}\text{.} \end{equation*}

What are the domain and range of \(f\text{?}\) What is the inverse of \(f\text{?}\) Compute \(f \circ f^{-1}\) and \(f^{-1} \circ f\text{.}\)

Hint.

\(f^{-1}(x) = (x+1)/(x-1)\text{.}\)

22.

Let \(f: X \rightarrow Y\) be a map with \(A_1, A_2 \subset X\) and \(B_1, B_2 \subset Y\text{.}\)

  1. Prove \(f( A_1 \cup A_2 ) = f( A_1) \cup f( A_2 )\text{.}\)

  2. Prove \(f( A_1 \cap A_2 ) \subset f( A_1) \cap f( A_2 )\text{.}\) Give an example in which equality fails.

  3. Prove \(f^{-1}( B_1 \cup B_2 ) = f^{-1}( B_1) \cup f^{-1}(B_2 )\text{,}\) where

    \begin{equation*} f^{-1}(B) = \{ x \in X : f(x) \in B \}\text{.} \end{equation*}
  4. Prove \(f^{-1}( B_1 \cap B_2 ) = f^{-1}( B_1) \cap f^{-1}( B_2 )\text{.}\)

  5. Prove \(f^{-1}( Y \setminus B_1 ) = X \setminus f^{-1}( B_1)\text{.}\)

Hint.

(a) Let \(y \in f(A_1 \cup A_2)\text{.}\) Then there exists an \(x \in A_1 \cup A_2\) such that \(f(x) = y\text{.}\) Hence, \(y \in f(A_1)\) or \(f(A_2) \text{.}\) Therefore, \(y \in f(A_1) \cup f(A_2)\text{.}\) Consequently, \(f(A_1 \cup A_2) \subset f(A_1) \cup f(A_2)\text{.}\) Conversely, if \(y \in f(A_1) \cup f(A_2)\text{,}\) then \(y \in f(A_1)\) or \(f(A_2)\text{.}\) Hence, there exists an \(x\) in \(A_1\) or \(A_2\) such that \(f(x) = y\text{.}\) Thus, there exists an \(x \in A_1 \cup A_2\) such that \(f(x) = y\text{.}\) Therefore, \(f(A_1) \cup f(A_2) \subset f(A_1 \cup A_2)\text{,}\) and \(f(A_1 \cup A_2) = f(A_1) \cup f(A_2)\text{.}\)

23.

Show that an \(m \times n\) matrix gives rise to a well-defined map from \({\mathbb R}^n\) to \({\mathbb R}^m\text{.}\)

24.

Find the error in the following argument by providing a counterexample. “The reflexive property is redundant in the axioms for an equivalence relation. If \(x \sim y\text{,}\) then \(y \sim x\) by the symmetric property. Using the transitive property, we can deduce that \(x \sim x\text{.}\)”

Hint.

Let \(X = {\mathbb N} \cup \{ \sqrt{2}\, \}\) and define \(x \sim y\) if \(x + y \in {\mathbb N}\text{.}\)

25. Projective Real Line.

Define a relation on \({\mathbb R}^2 \setminus \{ (0,0) \}\) by letting \((x_1, y_1) \sim (x_2, y_2)\) if there exists a nonzero real number \(\lambda\) such that \((x_1, y_1) = ( \lambda x_2, \lambda y_2)\text{.}\) Prove that \(\sim\) defines an equivalence relation on \({\mathbb R}^2 \setminus (0,0)\text{.}\) What are the corresponding equivalence classes? This equivalence relation defines the projective line, denoted by \({\mathbb P}({\mathbb R}) \text{,}\) which is very important in geometry.

26.

Prove that

\begin{equation*} 1^2 + 2^2 + \cdots + n^2 = \frac{n(n + 1)(2n + 1)}{6} \end{equation*}

for \(n \in {\mathbb N}\text{.}\)

Hint.

The base case, \(S(1): [1(1 + 1)(2(1) + 1)]/6 = 1 = 1^2\) is true. Assume that \(S(k): 1^2 + 2^2 + \cdots + k^2 = [k(k + 1)(2k + 1)]/6\) is true. Then

\begin{align*} 1^2 + 2^2 + \cdots + k^2 + (k + 1)^2 & = [k(k + 1)(2k + 1)]/6 + (k + 1)^2\\ & = [(k + 1)((k + 1) + 1)(2(k + 1) + 1)]/6\text{,} \end{align*}

and so \(S(k + 1)\) is true. Thus, \(S(n)\) is true for all positive integers \(n\text{.}\)

27.

Prove that

\begin{equation*} 1^3 + 2^3 + \cdots + n^3 = \frac{n^2(n + 1)^2}{4} \end{equation*}

for \(n \in {\mathbb N}\text{.}\)

28.

Prove that \(n! \gt 2^n\) for \(n \geq 4\text{.}\)

Hint.

The base case, \(S(4): 4! = 24 \gt 16 =2^4\) is true. Assume \(S(k): k! \gt 2^k\) is true. Then \((k + 1)! = k! (k + 1) \gt 2^k \cdot 2 = 2^{k + 1}\text{,}\) so \(S(k + 1)\) is true. Thus, \(S(n)\) is true for all positive integers \(n\text{.}\)

29.

Prove that

\begin{equation*} x + 4x + 7x + \cdots + (3n - 2)x = \frac{n(3n - 1)x}{2} \end{equation*}

for \(n \in {\mathbb N}\text{.}\)

30.

Prove that \(10^{n + 1} + 10^n + 1\) is divisible by \(3\) for \(n \in {\mathbb N}\text{.}\)

31.

Prove that \(4 \cdot 10^{2n} + 9 \cdot 10^{2n - 1} + 5\) is divisible by \(99\) for \(n \in {\mathbb N}\text{.}\)

32.

Show that

\begin{equation*} \sqrt[n]{a_1 a_2 \cdots a_n} \leq \frac{1}{n} \sum_{k = 1}^{n} a_k\text{.} \end{equation*}
33.

Prove the Leibniz rule for \(f^{(n)} (x)\text{,}\) where \(f^{(n)}\) is the \(n\)th derivative of \(f\text{;}\) that is, show that

\begin{equation*} (fg)^{(n)}(x) = \sum_{k = 0}^{n} \binom{n}{k} f^{(k)}(x) g^{(n - k)}(x)\text{.} \end{equation*}
Hint.

Follow the proof in Example 1.34 .

34.

Use induction to prove that \(1 + 2 + 2^2 + \cdots + 2^n = 2^{n + 1} - 1\) for \(n \in {\mathbb N}\text{.}\)

35.

Prove that

\begin{equation*} \frac{1}{2}+ \frac{1}{6} + \cdots + \frac{1}{n(n + 1)} = \frac{n}{n + 1} \end{equation*}

for \(n \in {\mathbb N}\text{.}\)

36.

If \(x\) is a nonnegative real number, then show that \((1 + x)^n - 1 \geq nx\) for \(n = 0, 1, 2, \ldots\text{.}\)

Hint.

The base case, \(S(0): (1 + x)^0 - 1 = 0 \geq 0 = 0 \cdot x\) is true. Assume \(S(k): (1 + x)^k -1 \geq kx\) is true. Then

\begin{align*} (1 + x)^{k + 1} - 1 & = (1 + x)(1 + x)^k -1\\ & = (1 + x)^k + x(1 + x)^k - 1\\ & \geq kx + x(1 + x)^k\\ & \geq kx + x\\ & = (k + 1)x\text{,} \end{align*}

so \(S(k + 1)\) is true. Therefore, \(S(n)\) is true for all positive integers \(n\text{.}\)

37. Power Sets.

Let \(X\) be a set. Define the power set of \(X\text{,}\) denoted \({\mathcal P}(X)\text{,}\) to be the set of all subsets of \(X\text{.}\) For example,

\begin{equation*} {\mathcal P}( \{a, b\} ) = \{ \emptyset, \{a\}, \{b\}, \{a, b\} \}\text{.} \end{equation*}

For every positive integer \(n\text{,}\) show that a set with exactly \(n\) elements has a power set with exactly \(2^n\) elements.

38.

Prove that the two principles of mathematical induction stated in Section 1.4 are equivalent.

39.

Show that the Principle of Well-Ordering for the natural numbers implies that 1 is the smallest natural number. Use this result to show that the Principle of Well-Ordering implies the Principle of Mathematical Induction; that is, show that if \(S \subset {\mathbb N}\) such that \(1 \in S\) and \(n + 1 \in S\) whenever \(n \in S\text{,}\) then \(S = {\mathbb N}\text{.}\)

40. Fibonacci Numbers.

The Fibonacci numbers are

\begin{equation*} 1, 1, 2, 3, 5, 8, 13, 21, \ldots\text{.} \end{equation*}

We can define them inductively by \(f_1 = 1\text{,}\) \(f_2 = 1\text{,}\) and \(f_{n + 2} = f_{n + 1} + f_n\) for \(n \in {\mathbb N}\text{.}\)

  1. Prove that \(f_n \lt 2^n\text{.}\)

  2. Prove that \(f_{n + 1} f_{n - 1} = f^2_n + (-1)^n\text{,}\) \(n \geq 2\text{.}\)

  3. Prove that \(f_n = [(1 + \sqrt{5}\, )^n - (1 - \sqrt{5}\, )^n]/ 2^n \sqrt{5}\text{.}\)

  4. Show that \(\lim_{n \rightarrow \infty} f_n / f_{n + 1} = (\sqrt{5} - 1)/2\text{.}\)

  5. Prove that \(f_n\) and \(f_{n + 1}\) are relatively prime.

Hint.

For (a) and (b) use mathematical induction. (c) Show that \(f_1 = 1\text{,}\) \(f_2 = 1\text{,}\) and \(f_{n + 2} = f_{n + 1} + f_n\text{.}\) (d) Use part (c). (e) Use part (b) and Exercise 6.1.5.2 .