Fundamental Structures - Hoang Anh Duc - HUS - VNU

Work 6.

\[\text{Find sets } A \text{ and } B \text{ which satisfy:} \\ \begin{cases} A = \{3, |B|\} \\ B = \{1, |A|, |B|\} \quad \end{cases}\]

Let:

\[\begin{align} |A| = m \\ |B| = n \\ \end{align}\]

We get \(A = \{3, n\}\) and \(B = \{1, m, n\}\), because \(3 \in A\) and \(1 \in B\), by definition:

\[\begin{align} 0 < m \leq 2 \\ 0 < n \leq 3 \\ \end{align}\]

We establish that for every pair of \(m, n\) in the given range, when substituted into \(A, B\), \(\lvert A \lvert = m\) AND \(\lvert B \lvert = n\) needs to be True. We will use Python for this:

# Essentially im proving for 2 x 3 = 6 cases on paper
def find_valid_sets():
    results = []

    for m in range(1, 3):
        for n in range(1, 4):
            A = {3, n}
            B = {1, m, n}

            if len(A) == m and len(B) == n:
                results.append((m, n, A, B))

    return results


valid_pairs = find_valid_sets()

for m, n, A, B in valid_pairs:
    print(f"Valid pair (m, n): ({m}, {n}) with A = {A}, B = {B}")

Results:

Valid pair (m, n): (2, 2) with A = {2, 3}, B = {1, 2}

Conclusion:

\[A = \{2, 3\} \text{ and } B = \{1, 2\} \text{ satisfies the condition.}\]

Work 9.

\[\begin{gather*} \text{Given set } A = \{1, \{2, 3\}\} \text{ and } B = \{4, 5, 6\} \text{ , find: } \\ A \times A\\ B \times B\\ A \times B\\ B \times A\\ \end{gather*}\]

Solution:

\[\begin{gather*} A \times A = \{(1,1),(1,\{2,3\}),(\{2,3\},1),(\{2,3\},\{2,3\})\} \\ B \times B =\{(4,4),(4,5),(4,6),(5,4),(5,5),(5,6),(6,4),(6,5),(6,6)\} \quad \\ A \times B = \{(1,4),(1,5),(1,6),(\{2,3\},4),(\{2,3\},5),(\{2,3\},6)\} \\ B \times A = \{(4,1),(4,\{2,3\}),(5,1),(5,\{2,3\}),(6,1),(6,\{2,3\})\} \end{gather*}\]

Work 16.

\[\begin{gather*} \text{For arbitrary sets A, B, prove:} \\ a, A \cap B = A \setminus (A \setminus B) \\ b, A \cup (B \setminus A) = A \cup B \\ c, A \cap (B \setminus A) = \emptyset \\ d, A \triangle A = \emptyset \\ e, A \triangle \emptyset = A \\ f, A \triangle B = B \triangle A \end{gather*}\]

a, \(A \cap B = A \setminus (A \setminus B)\)

\[\begin{gather*} \text{RHS: } A \setminus (A \setminus B) \\ \rightarrow A \setminus (A \cap B^\complement) \\ \rightarrow A \cap (A \cap B^\complement)^\complement \\ \rightarrow A \cap (A^\complement \cup B) \text{ (De Morgan's Laws)}\\ \rightarrow (A \cap A^\complement) \cup (A \cap B) \text{ (Distributive Laws)}\\ \rightarrow A \cap B = \text{ LHS} \\ \end{gather*}\]

b, \(A \cup (B \setminus A) = A \cup B \\\)

\[\begin{gather*} \text{LHS: } A \cup (B \setminus A) \\ \rightarrow A \cup (B \cap A^\complement) \\ \rightarrow (A \cup B) \cap (A \cup A^\complement) \text{ (Distributive Laws)} \\ \rightarrow A \cup B = \text{ RHS}\\ \end{gather*}\]

c, \(A \cap (B \setminus A) = \emptyset\)

\[\begin{gather*} \text{LHS: } A \cap (B \setminus A) \\ \rightarrow A \cap (B \cap A^\complement) \\ \rightarrow (A \cap A^\complement) \cap B \text{ (Associative Laws)} \\ \rightarrow \emptyset \cap B \text{ (Associative Laws)} \\ \rightarrow \emptyset = \text{ RHS (Domination Laws)} \\ \end{gather*}\]

d, \(A \triangle A = \emptyset\)

\[\begin{gather*} \text{LHS: } A \triangle A \\ \rightarrow (A \setminus A) \cup (A \setminus A) \\ \rightarrow \emptyset \cup \emptyset \\ \rightarrow \emptyset = \text{ RHS} \\ \end{gather*}\]

e, \(A \triangle \emptyset = A \\\)

\[\begin{gather*} \text{LHS: } A \triangle A \\ \rightarrow (A \setminus \emptyset) \cup (\emptyset \setminus A) \\ \rightarrow A \cup \emptyset = \text{ RHS} \\ \end{gather*}\]

f, \(A \triangle B = B \triangle A\)

\[\begin{gather*} \text{LHS: } A \triangle B \\ \rightarrow (A \setminus B) \cup (B \setminus A) \\ \rightarrow (B \setminus A) \cup (A \setminus B) \text{ (Commutative Laws)}\\ \rightarrow B \triangle A = \text{ RHS} \\ \end{gather*}\]

Work 17.

\[\begin{gather*} \text{For arbitrary sets A, B, C, can you prove A = B with:} \quad \\ a, A \cup C = B \cup C \\ b, A \cap C = B \cap C \\ c, A \cup C = B \cup C \text{ AND } A \cap C = B \cap C \\ \end{gather*}\]

a, \(A \cup C = B \cup C\)

\[\begin{gather*} \text{Let: } x \in A \\ \rightarrow x \in A \cup C \\ \rightarrow x \in B \cup C \quad (A \cup C = B \cup C) \\ \rightarrow (x \in B) \vee (x \in C) = T \\ \text{Assume: } x \notin C \rightarrow x \in B \\ \rightarrow x \in B \rightarrow x \in A \rightarrow A \subseteq B (1)\\[20pt] \text{Let: } y \in B \\ \rightarrow y \in B \cup C \\ \rightarrow y \in A \cup C \quad (A \cup C = B \cup C) \\ \rightarrow (y \in A) \vee (y \in C) = T \\ \text{Assume: } y \notin C \rightarrow y \in A \\ \rightarrow y \in A \rightarrow y \in B \rightarrow B \subseteq A (2)\\[20pt] \text{From (1), (2), we conclude: } A = B \\ \end{gather*}\]

b, \(A \cap C = B \cap C\)

\[\begin{gather*} \text{Let: } x \in A \\ \rightarrow x \in A \cap C \leftrightarrow x \notin C \\ \rightarrow x \in B \cap C \quad (A \cap C = B \cap C) \\ \rightarrow (x \in B) \wedge (x \notin C) = T \\ \rightarrow x \in B \rightarrow x \in A \rightarrow A \subseteq B (1)\\[20pt] \text{Let: } y \in B \\ \rightarrow y \in B \cap C \leftrightarrow x \notin C \\ \rightarrow y \in A \cup C \quad (A \cup C = B \cup C) \\ \rightarrow (y \in A) \wedge (y \notin C) = T \\ \rightarrow y \in A \rightarrow y \in B \rightarrow B \subseteq A (2)\\[20pt] \text{From (1), (2), we conclude: } A = B \\ \end{gather*}\]

c, \((A \cup C = B \cup C) \wedge (A \cap C = B \cap C)\)

\[\begin{gather*} \text{From (a), (b), trivially, we conclude: } A = B \\ \end{gather*}\]

Work. 25

\[\begin{gather*} \text{In each cases, is } \mathcal{R} \text{ an equivalence relation?} \\[5pt] (1) \mathcal{R} = \{(p, q) \lvert p \equiv q\} \text{ p, q are Statements} \\[5pt] (2) \mathcal{R} = \{(A, B) \lvert A \subseteq B\} \text{ A, B are Sets} \\[5pt] (3) \mathcal{R} = \{(A, B) \lvert A = B\} \text{ A, B are Sets} \\ (4) \mathcal{R} = \{(a, b) \lvert a\ \vdots\ b\} \text{ a, b are Positive Integers} \\ \end{gather*}\]

\((1) \mathcal{R} = \{(p, q) \mid p \equiv q\} (\text{ where } p \text{ and } q \text{ are statements})\)

\[\begin{gather*} \text{Reflexivity: A statement } p \text{ is equivalent to itself } (p \equiv p). \\ \text{ Thus, } (p, p) \in \mathcal{R} \text{ for all statements } p. \\ \text{Symmetry: If } (p \equiv q), \text{ then } (q \equiv p). \\ \text{ Therefore, if } (p, q) \in \mathcal{R}, \text{ it follows that } (q, p) \in \mathcal{R}. \\ \text{Transitivity: If } (p \equiv q) \text{ and } (q \equiv r), \text{ then } (p \equiv r). \\ \text{ Hence, if } (p, q) \in \mathcal{R} \text{ and } (q, r) \in \mathcal{R}, \text{ it follows that } (p, r) \in \mathcal{R}. \quad\\ \text{Conclusion: } \mathcal{R} \text{ is an equivalence relation. } \end{gather*}\]

\((2) \mathcal{R} = \{(A, B) \mid A \subseteq B\} (\text{ where } A \text{ and } B \text{ are sets})\)

\[\begin{gather*} \text{Reflexivity: For any set } A, \text{ it holds that } A \subseteq A. \\ \text{ Thus, } (A, A) \in \mathcal{R}. \\ \text{Symmetry: If } A \subseteq B, \text{ it does not imply that } B \subseteq A \text{ unless } A = B.\\ \text{ Therefore, } (A, B) \in \mathcal{R} \text{ does not guarantee } (B, A) \in \mathcal{R}. \\ \text{Transitivity: If } A \subseteq B \text{ and } B \subseteq C, \text{ then } A \subseteq C.\\ \text{ Hence, if } (A, B) \in \mathcal{R} \text{ and } (B, C) \in \mathcal{R}, \text{ it follows that } (A, C) \in \mathcal{R}. \\ \text{Conclusion: } \mathcal{R} \text{ is not an equivalence relation because it fails symmetry. } \quad \end{gather*}\]

\((3) \mathcal{R} = \{(A, B) \mid A = B\} (\text{ where } A \text{ and } B \text{ are sets})\)

\[\begin{gather*} \text{Reflexivity: For any set } A, \text{ it holds that } A = A. \text{ Thus, } (A, A) \in \mathcal{R}. \quad \\ \text{Symmetry: If } A = B, \text{ then } B = A.\\ \text{ Therefore, if } (A, B) \in \mathcal{R}, \text{ it follows that } (B, A) \in \mathcal{R}. \\ \text{Transitivity: If } A = B \text{ and } B = C, \text{ then } A = C. \\ \text{ Hence, if } (A, B) \in \mathcal{R} \text{ and } (B, C) \in \mathcal{R}, \text{ it follows that } (A, C) \in \mathcal{R}. \\ \text{Conclusion: } \mathcal{R} \text{ is an equivalence relation. } \end{gather*}\]

\((4) \mathcal{R} = \{(a, b) \mid a\ \vdots\ b\} (\text{ where } a \text{ and } b \text{ are positive integers})\)

\[\begin{gather*} \text{Reflexivity: For any positive integer } a, \text{ it holds that } a \vdots a. \text{ Thus, } (a, a) \in \mathcal{R}. \quad \\ \text{Symmetry: If } a \vdots b, \text{ it does not imply that } b \vdots a \text{ unless } a = b. \\ \text{ Therefore, } (a, b) \in \mathcal{R} \text{ does not guarantee } (b, a) \in \mathcal{R}. \\ \text{Transitivity: If } a \vdots b \text{ and } b \vdots c, \text{ then } a \vdots c \text{ holds true.}\\ \text{Hence, if } (a, b) \in \mathcal{R} \text{ and } (b, c) \in \mathcal{R}, \text{ it follows that } (a, c) \in \mathcal{R}. \\ \text{Conclusion: } \mathcal{R} \text{ is not an equivalence relation because it fails symmetry. } \end{gather*}\]

Work 33.

\[\begin{gather*} \text{ is } \mathcal{f} : \mathbb{R} \rightarrow \mathbb{R} \text{ a bijection in these cases:} \\ \mathcal{f}(x) = -3x + 4 \\ \mathcal{f}(x) = -3x^2 + 7 \\ \mathcal{f}(x) = \frac{x + 1}{x + 2} \\ \mathcal{f}(x) = x^5 + 1 \\ \mathcal{f}(x) = 2x + 1 \\ \mathcal{f}(x) = x^2 + 1 \\ \mathcal{f}(x) = x^3 \\ \mathcal{f}(x) = \frac{x^2 + 1}{x^2} + 2 \\ \end{gather*}\]

\(\text{(1) } \mathcal{f}(x) = -3x + 4\)

\[\begin{gather*} \text{Injectivity: Let } \mathcal{f}(x_1) = \mathcal{f}(x_2). \\ \Rightarrow -3x_1 + 4 = -3x_2 + 4 \\ \Rightarrow -3x_1 = -3x_2 \\ \Rightarrow x_1 = x_2. \\ \text{Thus, } \mathcal{f} \text{ is injective.} \\ \text{Surjectivity: For any } y \in \mathbb{R}, \text{ let } y = -3x + 4. \\ \Rightarrow x = \frac{4 - y}{3}. \\ \text{Since } y \text{ can take any value in } \mathbb{R}, \mathcal{f} \text{ is surjective.} \\ \text{Conclusion: } \mathcal{f} \text{ is a bijection.} \end{gather*}\]

\(\text{(2) } \mathcal{f}(x) = -3x^2 + 7 \\\)

\[\begin{gather*} \text{Injectivity: Let } \mathcal{f}(x_1) = \mathcal{f}(x_2). \\ \Rightarrow -3x_1^2 + 7 = -3x_2^2 + 7 \\ \Rightarrow -3x_1^2 = -3x_2^2 \\ \Rightarrow x_1^2 = x_2^2 \\ \Rightarrow x_1 = x_2 \text{ or } x_1 = -x_2. \\ \text{Thus, } \mathcal{f} \text{ is not injective.} \\ \text{Conclusion: } \mathcal{f} \text{ is not a bijection.} \end{gather*}\]

\(\text{(3) } \mathcal{f}(x) = \frac{x + 1}{x + 2}\)

\[\begin{gather*} \text{Injectivity: Let } \mathcal{f}(x_1) = \mathcal{f}(x_2). \\ \Rightarrow \frac{x_1 + 1}{x_1 + 2} = \frac{x_2 + 1}{x_2 + 2} \\ \Rightarrow (x_1 + 1)(x_2 + 2) = (x_2 + 1)(x_1 + 2) \\ \Rightarrow x_1x_2 + 2x_1 + x_2 + 2 = x_2x_1 + 2x_2 + x_1 + 2 \\ \Rightarrow 2x_1 = 2x_2 \\ \Rightarrow x_1 = x_2. \\ \text{Thus, } \mathcal{f} \text{ is injective.} \\ \text{Surjectivity: For any } y \in \mathbb{R}, \\ \Rightarrow y(x + 2) = x + 1 \\ \Rightarrow yx + 2y = x + 1 \\ \Rightarrow x(y - 1) = 1 - 2y \\ \Rightarrow x = \frac{1 - 2y}{y - 1}. \\ \text{Since } y \text{ can take any value in } \mathbb{R} \text{ except } 1, \mathcal{f} \text{ is not surjective.} \quad \\ \text{Conclusion: } \mathcal{f} \text{ is not a bijection.} \end{gather*}\]

\(\text{(4) } \mathcal{f}(x) = x^5 + 1\)

\[\begin{gather*} \text{Injectivity: Let } \mathcal{f}(x_1) = \mathcal{f}(x_2). \\ \Rightarrow x_1^5 + 1 = x_2^5 + 1 \\ \Rightarrow x_1^5 = x_2^5 \\ \Rightarrow x_1 = x_2. \\ \text{Thus, } \mathcal{f} \text{ is injective.} \\ \text{Surjectivity: For any } y \in \mathbb{R}, \\ \Rightarrow y = x^5 + 1 \\ \Rightarrow x^5 = y - 1 \\ \Rightarrow x = (y - 1)^{1/5}. \\ \text{Since } y \text{ can take any value in } \mathbb{R}, \mathcal{f} \text{ is surjective.} \\ \text{Conclusion: } \mathcal{f} \text{ is a bijection.} \end{gather*}\]

\(\text{(5) } \mathcal{f}(x) = 2x + 1\)

\[\begin{gather*} \text{Injectivity: Let } \mathcal{f}(x_1) = \mathcal{f}(x_2). \\ \Rightarrow 2x_1 + 1 = 2x_2 + 1 \\ \Rightarrow 2x_1 = 2x_2 \\ \Rightarrow x_1 = x_2. \\ \text{Thus, } \mathcal{f} \text{ is injective.} \\ \text{Surjectivity: For any } y \in \mathbb{R}, \\ \Rightarrow y = 2x + 1 \\ \Rightarrow 2x = y - 1 \\ \Rightarrow x = \frac{y - 1}{2}. \\ \text{Since } y \text{ can take any value in } \mathbb{R}, \mathcal{f} \text{ is surjective.} \\ \text{Conclusion: } \mathcal{f} \text{ is a bijection.} \end{gather*}\]

\(\text{(6) } \mathcal{f}(x) = x^2 + 1\)

\[\begin{gather*} \text{Injectivity: Let } \mathcal{f}(x_1) = \mathcal{f}(x_2). \\ \Rightarrow x_1^2 + 1 = x_2^2 + 1 \\ \Rightarrow x_1^2 = x_2^2 \\ \Rightarrow x_1 = x_2 \text{ or } x_1 = -x_2. \\ \text{Thus, } \mathcal{f} \text{ is not injective.} \\ \text{Conclusion: } \mathcal{f} \text{ is not a bijection.} \end{gather*}\]

\(\text{(7) } \mathcal{f}(x) = x^3\)

\[\begin{gather*} \text{Injectivity: Let } \mathcal{f}(x_1) = \mathcal{f}(x_2). \\ \Rightarrow x_1^3 = x_2^3 \\ \Rightarrow x_1 = x_2. \\ \text{Thus, } \mathcal{f} \text{ is injective.} \\ \text{Surjectivity: For any } y \in \mathbb{R}, \\ \Rightarrow y = x^3 \\ \Rightarrow x = y^{1/3}. \\ \text{Since } y \text{ can take any value in } \mathbb{R}, \mathcal{f} \text{ is surjective.} \\ \text{Conclusion: } \mathcal{f} \text{ is a bijection.} \end{gather*}\]

\(\text{(8) } \mathcal{f}(x) = \frac{x^2 + 1}{x^2} + 2\)

\[\begin{gather*} \text{Injectivity: Let } \mathcal{f}(x_1) = \mathcal{f}(x_2). \\ \Rightarrow \frac{x_1^2 + 1}{x_1^2} + 2 = \frac{x_2^2 + 1}{x_2^2} + 2 \\ \Rightarrow \frac{x_1^2 + 1}{x_1^2} = \frac{x_2^2 + 1}{x_2^2} \\ \Rightarrow 1 + \frac{1}{x_1^2} = 1 + \frac{1}{x_2^2} \\ \Rightarrow \frac{1}{x_1^2} = \frac{1}{x_2^2} \\ \Rightarrow x_1^2 = x_2^2 \\ \Rightarrow x_1 = x_2 \text{ or } x_1 = -x_2. \\ \text{Thus, } \mathcal{f} \text{ is not injective.} \\ \text{Surjectivity: For any } y \in \mathbb{R}, \\ \Rightarrow y = \frac{x^2 + 1}{x^2} + 2 \\ \Rightarrow y - 2 = \frac{x^2 + 1}{x^2} \\ \Rightarrow y - 2 = 1 + \frac{1}{x^2} \\ \Rightarrow y - 3 = \frac{1}{x^2} \\ \Rightarrow x^2 = \frac{1}{y - 3}. \\ \text{For } y > 3, \text{ we get valid values for } x, \text{ so } \mathcal{f} \text{ is surjective over } (3, \infty). \quad \\ \text{Conclusion: } \mathcal{f} \text{ is not a bijection over } \mathbb{R}. \end{gather*}\]

Work 37.

\[\begin{gather*} \text{ Given functions: } \mathcal{g} : \mathbb{A} \rightarrow \mathbb{B} \text{ and } \mathcal{f} : \mathbb{B} \rightarrow \mathbb{C} \text{ prove that:} \\ \text{(a) } \text{If } \mathcal{g} \text{ and } \mathcal{f} \text{ are injective, then } \mathcal{f} \circ \mathcal{g} \text{ is injective.} \\ \text{(b) } \text{If } \mathcal{g} \text{ and } \mathcal{f} \text{ are surjective, then } \mathcal{f} \circ \mathcal{g} \text{ is surjective.} \\ \text{(c) } \text{If } \mathcal{f} \circ \mathcal{g} \text{ is surjective, then } \mathcal{f} \text{ is surjective.} \\ \text{(d) } \text{If } \mathcal{f} \circ \mathcal{g} \text{ is injective, then } \mathcal{g} \text{ is injective.} \\ \text{(e) } \mathcal{f} \circ \mathcal{g} \text{ is bijective} \iff (\mathcal{g} \text{ is surjective} \iff \mathcal{f} \text{ is injective}). \quad \end{gather*}\]

\(\text{(a) } \text{If } \mathcal{g} \text{ and } \mathcal{f} \text{ are injective, then } \mathcal{f} \circ \mathcal{g} \text{ is injective.}\)

\[\begin{gather*} \text{Let } x_1, x_2 \in \mathbb{A} \text{ and assume that } (\mathcal{f} \circ \mathcal{g})(x_1) = (\mathcal{f} \circ \mathcal{g})(x_2). \quad\\ \Rightarrow \mathcal{f}(\mathcal{g}(x_1)) = \mathcal{f}(\mathcal{g}(x_2)). \\ \text{Since } \mathcal{f} \text{ is injective, we have } \mathcal{g}(x_1) = \mathcal{g}(x_2). \\ \text{Since } \mathcal{g} \text{ is injective, we conclude that } x_1 = x_2. \\ \text{Thus, } \mathcal{f} \circ \mathcal{g} \text{ is injective.} \end{gather*}\]

\(\text{(b) } \text{If } \mathcal{g} \text{ and } \mathcal{f} \text{ are surjective, then } \mathcal{f} \circ \mathcal{g} \text{ is surjective.}\)

\[\begin{gather*} \text{Let } z \in \mathbb{C}. \\ \text{Since } \mathcal{f} \text{ is surjective, there exists some } y \in \mathbb{B} \text{ such that } \mathcal{f}(y) = z. \quad\\ \text{Since } \mathcal{g} \text{ is surjective, there exists some } x \in \mathbb{A} \text{ such that } \mathcal{g}(x) = y. \quad\\ \Rightarrow \mathcal{f}(\mathcal{g}(x)) = z. \\ \text{Thus, for every } z \in \mathbb{C}, \text{ we have } (\mathcal{f} \circ \mathcal{g})(x) = z. \\ \text{Therefore, } \mathcal{f} \circ \mathcal{g} \text{ is surjective.} \end{gather*}\]

\(\text{(c) } \text{If } \mathcal{f} \circ \mathcal{g} \text{ is surjective, then } \mathcal{f} \text{ is surjective.}\)

\[\begin{gather*} \text{Let } z \in \mathbb{C}. \\ \text{Since } \mathcal{f} \circ \mathcal{g} \text{ is surjective, there exists some } x \in \mathbb{A} \text{ such that } (\mathcal{f} \circ \mathcal{g})(x) = z. \quad\\ \Rightarrow \mathcal{f}(\mathcal{g}(x)) = z. \\ \text{Thus, for every } z \in \mathbb{C}, \text{ there is some } y = \mathcal{g}(x) \in \mathbb{B} \text{ such that } \mathcal{f}(y) = z. \\ \text{Therefore, } \mathcal{f} \text{ is surjective.} \end{gather*}\]

\(\text{(d) } \text{If } \mathcal{f} \circ \mathcal{g} \text{ is injective, then } \mathcal{g} \text{ is injective.}\)

\[\begin{gather*} \text{Let } x_1, x_2 \in \mathbb{A} \text{ and assume that } \mathcal{g}(x_1) = \mathcal{g}(x_2). \\ \Rightarrow (\mathcal{f} \circ \mathcal{g})(x_1) = \mathcal{f}(\mathcal{g}(x_1)) = \mathcal{f}(\mathcal{g}(x_2)) = (\mathcal{f} \circ \mathcal{g})(x_2). \quad\\ \text{Since } \mathcal{f} \circ \mathcal{g} \text{ is injective, we conclude that } x_1 = x_2. \\ \text{Therefore, } \mathcal{g} \text{ is injective.} \end{gather*}\]

\(\text{(e) } \mathcal{f} \circ \mathcal{g} \text{ is bijective} \iff (\mathcal{g} \text{ is surjective} \iff \mathcal{f} \text{ is injective}).\)

\[\begin{gather*} \text{} \Rightarrow \text{}: \text{Suppose } \mathcal{f} \circ \mathcal{g} \text{ is bijective.} \\ \text{Since } \mathcal{f} \circ \mathcal{g} \text{ is injective, by (d), we know that } \mathcal{g} \text{ is injective.} \\ \text{Since } \mathcal{f} \circ \mathcal{g} \text{ is surjective, by (c), we know that } \mathcal{f} \text{ is surjective.} \\ \Rightarrow \mathcal{g} \text{ is surjective } \iff \mathcal{f} \text{ is injective.} \\[10pt] \text{} \Leftarrow \text{}: \text{If } \mathcal{g} \text{ is surjective and } \mathcal{f} \text{ is injective, then by (a) and (b), } \mathcal{f} \circ \mathcal{g} \text{ is bijective.} \quad \end{gather*}\]

Work 44.

\[\begin{gather*} \text{For each of the following integer sequences, find a simple formula} \\ \text{or a method to find the next terms of the sequence. Assuming the} \\ \text{formula you find is correct, find the next three terms of the sequence.} \quad\\[10pt] (1) 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, ... \\ (2) 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, ... \\ (3) 1, 0, 2, 0, 4, 0, 8, 0, 16, 0, ... \\ (4) 3, 6, 12, 24, 48, 96, 192, ... \\ (5) 15, 8, 1, −6, −13, −20, −27, ... \\ (6) 3, 5, 8, 12, 17, 23, 30, 38, 47, ... \\ (7) 2, 16, 54, 128, 250, 432, 686, ... \\ (8) 2, 3, 7, 25, 121, 721, 5041, 40321, ... \\ \end{gather*}\]

• (1) 1, 1, 1.
• (2) 9, 10, 10.
• (3) 32, 0, 64.
• (4) 384, 768, 1536.
• (5) −34, −41, −48.
• (6) 57, 68, 80.
• (7) 1016, 1450, 1974.
• (8) 362881, 3628801, 39916801.

Work 49.

\[\begin{gather*} \text{Calculate these sums} \\ (1) \sum_{k=100}^{200} k \\ (2) \sum_{k=99}^{200} k^3 \\ (3) \sum_{k=10}^{20} k^2(k-3) \\ \end{gather*}\]

• (1) 20100 - 4950 = 15150
• (2) 404010000 - 23532201 = 380477799
• (3) 35490 - 1170 = 34320

References:

• “Duplicates does not change cardinality”.
• “Cardinality: Comparing the size of sets”.
• Winfried K. Grassman & Jean-Paul Tremblay, Logic and Discrete Mathematics: A Computer Science Perspective.
• Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 4th ed.
• Richard Johnsonbaugh, Discrete Mathematics, 4th ed.
• Bernard Kolman, Robert C. Busby, & Sharon Ross, Discrete Mathematical Structures for Computer Science, 3rd ed.
• Edward Scheinerman, Mathematics: A Discrete Introduction, 2nd ed.