Abstract Algebra: Theory and Applications, Remixed!

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\)

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{.}\)

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{.}\)

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{.}\)

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}\)

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\)

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.

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

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{.}\)

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{.}\)

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{.}\)”

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

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

27.

Prove that

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

28.

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

29.

Prove that

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

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

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

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{.}\)

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,

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

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.