Chapter 01 · General Topology
Sets, Functions, and Proof
Establish the language of sets, mappings, inverse images, quantifiers, and proof strategies required throughout General Topology.
EN · FR
Visual investigations · Before the formal course
Investigation 1
What makes a relation a function?
Observe
Look at how each arrow maps domain elements to codomain elements.
Predict
Which diagrams satisfy the definition of a function? Which fail?
Manipulate
Click the canvas to cycle through three scenarios.
Explain
State the precise condition that must hold for every domain element.
Guiding question
Can one input have two distinct outputs? What about an input with no output at all?
Investigation 2
Injective, surjective, or bijective?
Observe
Note which codomain elements receive exactly one arrow, more than one, or none.
Predict
Can the classification change by rerouting a single arrow?
Manipulate
Click to cycle arrow configurations. Watch the classification update.
Explain
Write the quantifier conditions for injectivity and surjectivity separately.
Guiding question
Which condition concerns repeated outputs? Which concerns missing outputs?
Investigation 3
Direct image \(f(A)\) and inverse image \(f^{-1}(B)\)
Observe
Click domain elements to toggle \(A\); click codomain elements to toggle \(B\).
Predict
What happens to \(f^{-1}(B)\) when you enlarge \(B\)? When \(B = Y\)?
Manipulate
Toggle elements. Both \(f(A)\) and \(f^{-1}(B)\) update live.
Explain
Why can \(f^{-1}(B)\) be defined even when \(f\) has no inverse function?
Guiding question
Why can \(f^{-1}(B)\) be defined even when \(f\) is not invertible?
Investigation 4
Building a proof by double inclusion
Observe
Two set expressions are displayed. The goal is to show they are equal.
Predict
Is proving one inclusion enough, or must both directions be established?
Manipulate
Click to step through the double inclusion argument one direction at a time.
Explain
State what must be shown about an arbitrary element \(x\) in each direction.
Guiding question
To establish \(A = B\) by double inclusion, what must be shown in each direction?
Objectives
General objective. Develop the set-theoretic and logical foundations needed to define topological structures and construct rigorous mathematical arguments.
By the end of this chapter, you should be able to:
- distinguish relations from functions;
- identify domains, codomains, and images;
- classify mappings as injective, surjective, or bijective;
- calculate direct images \(f(A)\) and inverse images \(f^{-1}(B)\);
- prove identities involving inverse images under set operations;
- use quantifiers \(\forall\) and \(\exists\) correctly in mathematical statements;
- establish set equality by double inclusion;
- construct counterexamples to disprove universal statements;
- write direct, contrapositive, and contradiction proofs.
Prerequisites
This chapter assumes:
- elementary set notation: \(\in\), \(\subseteq\), \(\cup\), \(\cap\), \(\setminus\), \(\emptyset\);
- basic logical implication and the meaning of a mathematical statement;
- familiarity with symbols \(\forall\), \(\exists\), and \(\Rightarrow\).
Motivating question
Why do inverse images preserve the set operations that later define continuity? This chapter establishes the answer through rigorous definitions, worked examples, and proof.
Notation and terminology
The following symbols are active throughout this chapter.
\(x \in A\) - \(x\) is an element of \(A\)
\(A \subseteq B\) - \(A\) is a subset of \(B\)
\(A \cup B\) - union of \(A\) and \(B\)
\(A \cap B\) - intersection of \(A\) and \(B\)
\(A \setminus B\) - set difference
\(f : X \to Y\) - function from \(X\) to \(Y\)
\(f(A)\) - direct image of \(A \subseteq X\)
\(f^{-1}(B)\) - inverse image of \(B \subseteq Y\)
\(\forall\) - for all (universal quantifier)
\(\exists\) - there exists (existential quantifier)
Definitions
Definition 1.1
Function
Let \(X\) and \(Y\) be sets. A function (or map) from \(X\) to \(Y\), written \(f : X \to Y\), is a rule that assigns to each element \(x \in X\) exactly one element \(f(x) \in Y\).
The set \(X\) is the domain, \(Y\) is the codomain, and \(f(X) = \{f(x) : x \in X\} \subseteq Y\) is the image of \(f\).
Definition 1.2
Injective, surjective, bijective
A function \(f : X \to Y\) is:
injective (one-to-one) if \(\forall\, x_1, x_2 \in X,\ f(x_1) = f(x_2) \Rightarrow x_1 = x_2\);
surjective (onto) if \(\forall\, y \in Y,\ \exists\, x \in X\) such that \(f(x) = y\);
bijective if it is both injective and surjective.
Definition 1.3
Direct image and inverse image
Let \(f : X \to Y\), \(A \subseteq X\), \(B \subseteq Y\).
The direct image of \(A\) under \(f\) is \[f(A) := \{f(x) : x \in A\} \subseteq Y.\]
The inverse image (or preimage) of \(B\) under \(f\) is \[f^{-1}(B) := \{x \in X : f(x) \in B\} \subseteq X.\]
Note: \(f^{-1}(B)\) is defined for any function \(f\) regardless of whether \(f\) is bijective.
Theorems and proofs
Theorem 1.1 - Inverse image preserves set operations
Let \(f : X \to Y\) and \(B_1, B_2 \subseteq Y\). Then:
\[ f^{-1}(B_1 \cup B_2) = f^{-1}(B_1) \cup f^{-1}(B_2), \]
\[ f^{-1}(B_1 \cap B_2) = f^{-1}(B_1) \cap f^{-1}(B_2), \]
\[ f^{-1}(Y \setminus B_1) = X \setminus f^{-1}(B_1). \]
Proof · Theorem 1.1 · First identity
We establish \(f^{-1}(B_1 \cup B_2) = f^{-1}(B_1) \cup f^{-1}(B_2)\) by double inclusion.
(\(\subseteq\)) Let \(x \in f^{-1}(B_1 \cup B_2)\). By definition, \(f(x) \in B_1 \cup B_2\), so either \(f(x) \in B_1\) or \(f(x) \in B_2\). In the first case \(x \in f^{-1}(B_1)\); in the second \(x \in f^{-1}(B_2)\). Hence \(x \in f^{-1}(B_1) \cup f^{-1}(B_2)\).
(\(\supseteq\)) Let \(x \in f^{-1}(B_1) \cup f^{-1}(B_2)\). Then \(f(x) \in B_1\) or \(f(x) \in B_2\), so \(f(x) \in B_1 \cup B_2\), hence \(x \in f^{-1}(B_1 \cup B_2)\).
Both inclusions hold. The proofs of the remaining identities are Exercises 1.3 and 1.4.
∎
Remark 1.1 - Why this matters for topology
In Chapter 3 we define continuity of \(f : X \to Y\) by requiring that \(f^{-1}(U)\) is open in \(X\) whenever \(U\) is open in \(Y\). Theorem 1.1 guarantees that the collection of such preimages is closed under the set operations used to define a topology.
Worked examples
Example 1.1 - Computing direct and inverse images
Let \(f : \mathbb{R} \to \mathbb{R}\) be defined by \(f(x) = x^2\). Let \(A = [-2, 1]\) and \(B = [0, 4]\).
Direct image \(f(A)\). For \(x \in [-2,1]\), the maximum of \(x^2\) is \(f(-2) = 4\) and the minimum is \(f(0) = 0\). Therefore \(f(A) = [0, 4]\).
Inverse image \(f^{-1}(B)\). We want all \(x \in \mathbb{R}\) such that \(x^2 \in [0,4]\), i.e., \(|x| \leq 2\). Hence \(f^{-1}([0,4]) = [-2, 2]\).
Example 1.2 - A counterexample
Direct image does not preserve intersection in general
Let \(f : \mathbb{R} \to \mathbb{R}\), \(f(x) = x^2\), \(A_1 = \{-1\}\), \(A_2 = \{1\}\).
Then \(A_1 \cap A_2 = \emptyset\) so \(f(A_1 \cap A_2) = \emptyset\).
But \(f(A_1) = f(A_2) = \{1\}\), so \(f(A_1) \cap f(A_2) = \{1\} \neq \emptyset\).
Thus \(f(A_1 \cap A_2) \subsetneq f(A_1) \cap f(A_2)\). Contrast with Theorem 1.1: the inverse image does preserve intersection exactly.
Exercises
Work through each exercise in the LaTeX workspace below. Use the progressive hints only after a genuine attempt.
Exercise 1.1
Let \(f : X \to Y\). Prove that \(f^{-1}(Y \setminus B) = X \setminus f^{-1}(B)\) for any \(B \subseteq Y\).
Expected evidence: a proof by double inclusion with explicit set membership arguments, correct use of quantifiers, and a stated conclusion.
LaTeX workspace
Live preview
Your proof will render here.
Use double inclusion. For (\(\subseteq\)): let \(x \in f^{-1}(Y \setminus B)\) and unpack the definition.
\(x \in f^{-1}(S)\) means exactly \(f(x) \in S\). Apply this in each direction.
\(f(x) \in Y \setminus B\) means \(f(x) \in Y\) and \(f(x) \notin B\). Since \(f(x) \in Y\) always holds, this reduces to \(f(x) \notin B\), i.e., \(x \notin f^{-1}(B)\).
View detailed correction - attempt the proof first
Proof.
(\(\subseteq\)) Let \(x \in f^{-1}(Y \setminus B)\). Then \(f(x) \in Y \setminus B\), so \(f(x) \notin B\). Therefore \(x \notin f^{-1}(B)\), i.e., \(x \in X \setminus f^{-1}(B)\).
(\(\supseteq\)) Let \(x \in X \setminus f^{-1}(B)\). Then \(x \notin f^{-1}(B)\), so \(f(x) \notin B\). Since \(f(x) \in Y\) always, we have \(f(x) \in Y \setminus B\), hence \(x \in f^{-1}(Y \setminus B)\).
Both inclusions are established. ∎
(\(\subseteq\)) Let \(x \in f^{-1}(Y \setminus B)\). Then \(f(x) \in Y \setminus B\), so \(f(x) \notin B\). Therefore \(x \notin f^{-1}(B)\), i.e., \(x \in X \setminus f^{-1}(B)\).
(\(\supseteq\)) Let \(x \in X \setminus f^{-1}(B)\). Then \(x \notin f^{-1}(B)\), so \(f(x) \notin B\). Since \(f(x) \in Y\) always, we have \(f(x) \in Y \setminus B\), hence \(x \in f^{-1}(Y \setminus B)\).
Both inclusions are established. ∎
Exercise 1.2
Give an example of \(f : X \to Y\) and \(A_1, A_2 \subseteq X\) such that \(f(A_1 \cap A_2) \subsetneq f(A_1) \cap f(A_2)\).
Expected evidence: explicit sets, an explicit function, computation of both sides, and verification that the inclusion is strict.
LaTeX workspace
Live preview
Your work will render here.
Try \(f(x) = x^2\) on \(\mathbb{R}\). A non-injective function can map distinct elements of \(A_1\) and \(A_2\) to the same image.
Let \(A_1 \cap A_2 = \emptyset\) so that \(f(A_1 \cap A_2) = \emptyset\). Then find \(A_1, A_2\) such that \(f(A_1) \cap f(A_2) \neq \emptyset\).
View detailed correction - attempt first
Let \(f : \mathbb{R} \to \mathbb{R}\), \(f(x) = x^2\), \(A_1 = \{-1\}\), \(A_2 = \{1\}\).
\(A_1 \cap A_2 = \emptyset\), so \(f(A_1 \cap A_2) = \emptyset\).
\(f(A_1) = \{1\}\) and \(f(A_2) = \{1\}\), so \(f(A_1) \cap f(A_2) = \{1\} \neq \emptyset\).
Therefore \(f(A_1 \cap A_2) = \emptyset \subsetneq \{1\} = f(A_1) \cap f(A_2)\). ∎
\(A_1 \cap A_2 = \emptyset\), so \(f(A_1 \cap A_2) = \emptyset\).
\(f(A_1) = \{1\}\) and \(f(A_2) = \{1\}\), so \(f(A_1) \cap f(A_2) = \{1\} \neq \emptyset\).
Therefore \(f(A_1 \cap A_2) = \emptyset \subsetneq \{1\} = f(A_1) \cap f(A_2)\). ∎
Exercise 1.3
Prove \(f^{-1}(B_1 \cap B_2) = f^{-1}(B_1) \cap f^{-1}(B_2)\) for any \(f : X \to Y\) and \(B_1, B_2 \subseteq Y\).
Expected evidence: proof by double inclusion following the pattern of Theorem 1.1.
LaTeX workspace
Live preview
Your proof will render here.
For (\(\subseteq\)): let \(x \in f^{-1}(B_1 \cap B_2)\), unpack to get \(f(x) \in B_1\) and \(f(x) \in B_2\) simultaneously.
View detailed correction - attempt first
(\(\subseteq\)) Let \(x \in f^{-1}(B_1 \cap B_2)\). Then \(f(x) \in B_1 \cap B_2\), so \(f(x) \in B_1\) and \(f(x) \in B_2\). Therefore \(x \in f^{-1}(B_1) \cap f^{-1}(B_2)\).
(\(\supseteq\)) Let \(x \in f^{-1}(B_1) \cap f^{-1}(B_2)\). Then \(f(x) \in B_1\) and \(f(x) \in B_2\), so \(f(x) \in B_1 \cap B_2\), hence \(x \in f^{-1}(B_1 \cap B_2)\). ∎
(\(\supseteq\)) Let \(x \in f^{-1}(B_1) \cap f^{-1}(B_2)\). Then \(f(x) \in B_1\) and \(f(x) \in B_2\), so \(f(x) \in B_1 \cap B_2\), hence \(x \in f^{-1}(B_1 \cap B_2)\). ∎
Exercises 1.4–1.30 continue with compositions of functions, families of sets, indexed inverse images, proof strategies (contrapositive, contradiction, induction), and transfer problems connecting this chapter to Chapter 3.
Final exercises
Exercise 1.16
Prove by induction that \(|\mathcal{P}(A)| = 2^n\) when \(|A| = n\).
Expected evidence: base case, inductive step with explicit bijection or counting argument, and stated conclusion.
Check \(n=0\): \(A=\emptyset\) so \(\mathcal{P}(A)=\{\emptyset\}\) and \(2^0=1\). For the inductive step, write \(A = A' \cup \{a\}\) where \(|A'|=n\).
Every subset of \(A\) either contains \(a\) or does not. Subsets not containing \(a\) biject with \(\mathcal{P}(A')\); subsets containing \(a\) also biject with \(\mathcal{P}(A')\) by removing \(a\).
View detailed correction
Proof by induction on \(n = |A|\).
Base case \(n=0\). \(A = \emptyset\) and \(\mathcal{P}(\emptyset) = \{\emptyset\}\), so \(|\mathcal{P}(A)| = 1 = 2^0\).
Inductive step. Assume the result holds for sets of size \(n\). Let \(|A| = n+1\). Choose any \(a \in A\) and set \(A' = A \setminus \{a\}\), so \(|A'| = n\). Partition \(\mathcal{P}(A)\) into subsets \(S\) with \(a \notin S\) and subsets with \(a \in S\). The first family is \(\mathcal{P}(A')\), which by the inductive hypothesis has \(2^n\) elements. The second family bijects with \(\mathcal{P}(A')\) via \(S \mapsto S \setminus \{a\}\). Hence \(|\mathcal{P}(A)| = 2^n + 2^n = 2^{n+1}\). \(\square\)
Base case \(n=0\). \(A = \emptyset\) and \(\mathcal{P}(\emptyset) = \{\emptyset\}\), so \(|\mathcal{P}(A)| = 1 = 2^0\).
Inductive step. Assume the result holds for sets of size \(n\). Let \(|A| = n+1\). Choose any \(a \in A\) and set \(A' = A \setminus \{a\}\), so \(|A'| = n\). Partition \(\mathcal{P}(A)\) into subsets \(S\) with \(a \notin S\) and subsets with \(a \in S\). The first family is \(\mathcal{P}(A')\), which by the inductive hypothesis has \(2^n\) elements. The second family bijects with \(\mathcal{P}(A')\) via \(S \mapsto S \setminus \{a\}\). Hence \(|\mathcal{P}(A)| = 2^n + 2^n = 2^{n+1}\). \(\square\)
Exercise 1.17
Show that \(A \triangle B = (A \cup B) \setminus (A \cap B)\) and that the symmetric difference \(\triangle\) is associative.
Expected evidence: double inclusion for the first identity; element-chasing for associativity.
Recall \(A \triangle B = (A \setminus B) \cup (B \setminus A)\). An element is in \((A \cup B) \setminus (A \cap B)\) iff it is in exactly one of \(A\), \(B\).
For associativity, consider all eight cases for membership of an element \(x\) in \(A\), \(B\), \(C\) (truth-table style) and verify \((A \triangle B) \triangle C\) and \(A \triangle (B \triangle C)\) agree in each.
View detailed correction
Identity. \(x \in A \triangle B\) iff \(x\) is in exactly one of \(A\), \(B\), iff \(x \in A \cup B\) and \(x \notin A \cap B\), iff \(x \in (A \cup B) \setminus (A \cap B)\). Both inclusions follow immediately.
Associativity. Let \(x\) be arbitrary. Define \(a = \mathbf{1}[x \in A]\), \(b = \mathbf{1}[x \in B]\), \(c = \mathbf{1}[x \in C]\) (indicator values in \(\{0,1\}\)). Then \(x \in A \triangle B\) iff \(a + b \equiv 1 \pmod{2}\). Thus \(x \in (A \triangle B) \triangle C\) iff \((a+b)+c \equiv 1 \pmod{2}\) iff \(a+(b+c) \equiv 1 \pmod{2}\) iff \(x \in A \triangle (B \triangle C)\). Since \(x\) was arbitrary, associativity holds. \(\square\)
Associativity. Let \(x\) be arbitrary. Define \(a = \mathbf{1}[x \in A]\), \(b = \mathbf{1}[x \in B]\), \(c = \mathbf{1}[x \in C]\) (indicator values in \(\{0,1\}\)). Then \(x \in A \triangle B\) iff \(a + b \equiv 1 \pmod{2}\). Thus \(x \in (A \triangle B) \triangle C\) iff \((a+b)+c \equiv 1 \pmod{2}\) iff \(a+(b+c) \equiv 1 \pmod{2}\) iff \(x \in A \triangle (B \triangle C)\). Since \(x\) was arbitrary, associativity holds. \(\square\)
Exercise 1.18
Prove De Morgan's laws for arbitrary (possibly infinite) families: \(\displaystyle\Bigl(\bigcup_{\alpha \in I} A_\alpha\Bigr)^c = \bigcap_{\alpha \in I} A_\alpha^c\) and \(\displaystyle\Bigl(\bigcap_{\alpha \in I} A_\alpha\Bigr)^c = \bigcup_{\alpha \in I} A_\alpha^c\).
Expected evidence: element-wise argument using the negation of quantifiers.
\(x \notin \bigcup_\alpha A_\alpha\) means \(\forall\, \alpha,\, x \notin A_\alpha\), which means \(\forall\,\alpha,\, x \in A_\alpha^c\), which means \(x \in \bigcap_\alpha A_\alpha^c\).
\(x \notin \bigcap_\alpha A_\alpha\) means \(\exists\,\alpha\) such that \(x \notin A_\alpha\), i.e., \(x \in A_\alpha^c\), so \(x \in \bigcup_\alpha A_\alpha^c\).
View detailed correction
First law. \(x \in \Bigl(\bigcup_\alpha A_\alpha\Bigr)^c\) iff \(x \notin \bigcup_\alpha A_\alpha\) iff \(\forall\,\alpha,\,x \notin A_\alpha\) iff \(\forall\,\alpha,\,x \in A_\alpha^c\) iff \(x \in \bigcap_\alpha A_\alpha^c\).
Second law. \(x \in \Bigl(\bigcap_\alpha A_\alpha\Bigr)^c\) iff \(x \notin \bigcap_\alpha A_\alpha\) iff \(\exists\,\alpha,\,x \notin A_\alpha\) iff \(\exists\,\alpha,\,x \in A_\alpha^c\) iff \(x \in \bigcup_\alpha A_\alpha^c\). \(\square\)
Second law. \(x \in \Bigl(\bigcap_\alpha A_\alpha\Bigr)^c\) iff \(x \notin \bigcap_\alpha A_\alpha\) iff \(\exists\,\alpha,\,x \notin A_\alpha\) iff \(\exists\,\alpha,\,x \in A_\alpha^c\) iff \(x \in \bigcup_\alpha A_\alpha^c\). \(\square\)
Exercise 1.19
Show that \(A \times (B \cup C) = (A \times B) \cup (A \times C)\).
Expected evidence: a double-inclusion proof using the definition of Cartesian product.
Elements of \(A \times (B \cup C)\) are ordered pairs \((a, x)\) with \(a \in A\) and \(x \in B \cup C\), i.e., \(x \in B\) or \(x \in C\).
If \(a \in A\) and \(x \in B\) then \((a,x) \in A \times B\); if \(a \in A\) and \(x \in C\) then \((a,x) \in A \times C\). In either case \((a,x) \in (A \times B) \cup (A \times C)\).
View detailed correction
Let \((a,x) \in A \times (B \cup C)\). Then \(a \in A\) and \(x \in B \cup C\). If \(x \in B\) then \((a,x) \in A \times B\); if \(x \in C\) then \((a,x) \in A \times C\). Either way \((a,x) \in (A \times B) \cup (A \times C)\).
Conversely, let \((a,x) \in (A \times B) \cup (A \times C)\). Then \(a \in A\) and either \(x \in B\) or \(x \in C\), so \(x \in B \cup C\) and \((a,x) \in A \times (B \cup C)\). \(\square\)
Conversely, let \((a,x) \in (A \times B) \cup (A \times C)\). Then \(a \in A\) and either \(x \in B\) or \(x \in C\), so \(x \in B \cup C\) and \((a,x) \in A \times (B \cup C)\). \(\square\)
Exercise 1.20
Prove that if \(A \subseteq B\) then \(\mathcal{P}(A) \subseteq \mathcal{P}(B)\).
Expected evidence: a direct proof chasing definitions of power set and subset.
A set \(S \in \mathcal{P}(A)\) means \(S \subseteq A\). You need to show \(S \in \mathcal{P}(B)\), i.e., \(S \subseteq B\).
You know \(S \subseteq A\) and \(A \subseteq B\), so by transitivity \(S \subseteq B\).
View detailed correction
Let \(S \in \mathcal{P}(A)\). By definition \(S \subseteq A\). Since \(A \subseteq B\), every element of \(S\) belongs to \(A\) and hence to \(B\), so \(S \subseteq B\), i.e., \(S \in \mathcal{P}(B)\). Therefore \(\mathcal{P}(A) \subseteq \mathcal{P}(B)\). \(\square\)
Exercise 1.21
Let \(A\), \(B\), \(C\) be sets. Prove \((A \setminus B) \setminus C = A \setminus (B \cup C)\).
Expected evidence: element-chasing double inclusion.
\(x \in (A \setminus B) \setminus C\) means \(x \in A\), \(x \notin B\), and \(x \notin C\).
\(x \in A \setminus (B \cup C)\) means \(x \in A\) and \(x \notin B \cup C\), i.e., \(x \notin B\) and \(x \notin C\). These conditions are identical.
View detailed correction
\(x \in (A \setminus B) \setminus C\) iff \(x \in A \setminus B\) and \(x \notin C\) iff \(x \in A\), \(x \notin B\), and \(x \notin C\) iff \(x \in A\) and \(x \notin B \cup C\) iff \(x \in A \setminus (B \cup C)\). The conditions are equivalent, so the sets are equal. \(\square\)
Exercise 1.22
Show that \(A \cap (B \triangle C) = (A \cap B) \triangle (A \cap C)\).
Expected evidence: element-chasing argument or indicator-function argument.
\(x \in A \cap (B \triangle C)\) iff \(x \in A\) and (\(x \in B\) xor \(x \in C\)).
Since \(x \in A\), saying \(x \in B\) xor \(x \in C\) is the same as saying \(x \in A \cap B\) xor \(x \in A \cap C\), which is exactly \(x \in (A \cap B) \triangle (A \cap C)\).
View detailed correction
Let \(x\) be arbitrary with \(a = \mathbf{1}_{A}(x)\), \(b = \mathbf{1}_{B}(x)\), \(c = \mathbf{1}_{C}(x) \in \{0,1\}\).
\(\mathbf{1}_{A \cap (B \triangle C)}(x) = a \cdot (b \oplus c)\), where \(\oplus\) denotes addition mod 2. On the other hand, \(\mathbf{1}_{(A \cap B) \triangle (A \cap C)}(x) = (ab) \oplus (ac) = a(b \oplus c)\). Since multiplication by \(a \in \{0,1\}\) distributes over \(\oplus\), these are equal for all values of \(a,b,c\). \(\square\)
\(\mathbf{1}_{A \cap (B \triangle C)}(x) = a \cdot (b \oplus c)\), where \(\oplus\) denotes addition mod 2. On the other hand, \(\mathbf{1}_{(A \cap B) \triangle (A \cap C)}(x) = (ab) \oplus (ac) = a(b \oplus c)\). Since multiplication by \(a \in \{0,1\}\) distributes over \(\oplus\), these are equal for all values of \(a,b,c\). \(\square\)
Exercise 1.23
Prove that composition of injective functions is injective, composition of surjective functions is surjective, and composition of bijective functions is bijective.
Expected evidence: three separate direct proofs using the quantifier definitions.
Let \(f: X \to Y\) and \(g: Y \to Z\) both be injective. Suppose \(g(f(x_1)) = g(f(x_2))\). Apply injectivity of \(g\) first, then of \(f\).
Let \(z \in Z\). Surjectivity of \(g\) gives \(y\) with \(g(y) = z\); surjectivity of \(f\) gives \(x\) with \(f(x) = y\). Then \((g \circ f)(x) = z\).
View detailed correction
Let \(f: X \to Y\) and \(g: Y \to Z\).
Injective: Assume \(f\), \(g\) injective. If \((g \circ f)(x_1) = (g \circ f)(x_2)\) then \(g(f(x_1)) = g(f(x_2))\). Injectivity of \(g\) gives \(f(x_1) = f(x_2)\); injectivity of \(f\) then gives \(x_1 = x_2\).
Surjective: Assume \(f\), \(g\) surjective. Let \(z \in Z\). There exists \(y \in Y\) with \(g(y) = z\), and there exists \(x \in X\) with \(f(x) = y\). Then \((g \circ f)(x) = z\).
Bijective: Follows from the two cases above. \(\square\)
Injective: Assume \(f\), \(g\) injective. If \((g \circ f)(x_1) = (g \circ f)(x_2)\) then \(g(f(x_1)) = g(f(x_2))\). Injectivity of \(g\) gives \(f(x_1) = f(x_2)\); injectivity of \(f\) then gives \(x_1 = x_2\).
Surjective: Assume \(f\), \(g\) surjective. Let \(z \in Z\). There exists \(y \in Y\) with \(g(y) = z\), and there exists \(x \in X\) with \(f(x) = y\). Then \((g \circ f)(x) = z\).
Bijective: Follows from the two cases above. \(\square\)
Exercise 1.24
Let \(f: X \to Y\). Prove: \(f\) is injective if and only if it has a left inverse; \(f\) is surjective if and only if it has a right inverse.
Expected evidence: four implications with explicit construction of inverses.
If \(f\) is injective, fix any \(x_0 \in X\). Define \(g: Y \to X\) by \(g(y) = f^{-1}(y)\) if \(y \in f(X)\), and \(g(y) = x_0\) otherwise. Check \(g \circ f = \mathrm{id}_X\).
If \(f\) is surjective, for each \(y \in Y\) choose some \(x_y\) with \(f(x_y) = y\) (axiom of choice). Define \(h(y) = x_y\). Check \(f \circ h = \mathrm{id}_Y\).
View detailed correction
Injective iff left inverse. If \(g \circ f = \mathrm{id}_X\) and \(f(x_1) = f(x_2)\), apply \(g\) to get \(x_1 = x_2\). Conversely, if \(f\) is injective, define \(g(y) = x\) if \(y = f(x)\) (unique), else \(g(y) = x_0\). Then \(g(f(x)) = x\) for all \(x\).
Surjective iff right inverse. If \(f \circ h = \mathrm{id}_Y\), then for any \(y\), \(f(h(y)) = y\), so \(f\) is surjective. Conversely, if \(f\) is surjective, use the axiom of choice to select for each \(y \in Y\) an element \(h(y) \in f^{-1}(\{y\})\). Then \(f(h(y)) = y\). \(\square\)
Surjective iff right inverse. If \(f \circ h = \mathrm{id}_Y\), then for any \(y\), \(f(h(y)) = y\), so \(f\) is surjective. Conversely, if \(f\) is surjective, use the axiom of choice to select for each \(y \in Y\) an element \(h(y) \in f^{-1}(\{y\})\). Then \(f(h(y)) = y\). \(\square\)
Exercise 1.25
Show that \(f^{-1}(A \cap B) = f^{-1}(A) \cap f^{-1}(B)\) for any \(f : X \to Y\) and \(A, B \subseteq Y\).
Expected evidence: a double-inclusion proof mirroring Exercise 1.3.
\(x \in f^{-1}(A \cap B)\) iff \(f(x) \in A \cap B\) iff \(f(x) \in A\) and \(f(x) \in B\).
\(x \in f^{-1}(A) \cap f^{-1}(B)\) iff \(f(x) \in A\) and \(f(x) \in B\). The conditions are identical.
View detailed correction
\(x \in f^{-1}(A \cap B)\) iff \(f(x) \in A \cap B\) iff \(f(x) \in A\) and \(f(x) \in B\) iff \(x \in f^{-1}(A)\) and \(x \in f^{-1}(B)\) iff \(x \in f^{-1}(A) \cap f^{-1}(B)\). \(\square\)
Exercise 1.26
Give an example showing \(f(A \cap B) \neq f(A) \cap f(B)\) in general. Prove that \(f(A \cap B) \subseteq f(A) \cap f(B)\) always holds.
Expected evidence: an explicit counterexample and a direct proof of the inclusion.
Use a non-injective function. Take \(f(x) = x^2\) and disjoint sets \(A = \{-1\}\), \(B = \{1\}\).
If \(y \in f(A \cap B)\) then \(y = f(x)\) for some \(x \in A \cap B\). Since \(x \in A\), \(y \in f(A)\); since \(x \in B\), \(y \in f(B)\).
View detailed correction
Counterexample. Let \(f: \mathbb{R} \to \mathbb{R}\), \(f(x) = x^2\), \(A = \{-1\}\), \(B = \{1\}\). Then \(A \cap B = \emptyset\) so \(f(A \cap B) = \emptyset\), but \(f(A) = \{1\} = f(B)\) so \(f(A) \cap f(B) = \{1\} \neq \emptyset\).
Proof of inclusion. Let \(y \in f(A \cap B)\). Then \(y = f(x)\) for some \(x \in A \cap B\). Since \(x \in A\), \(y \in f(A)\); since \(x \in B\), \(y \in f(B)\). Hence \(y \in f(A) \cap f(B)\). \(\square\)
Proof of inclusion. Let \(y \in f(A \cap B)\). Then \(y = f(x)\) for some \(x \in A \cap B\). Since \(x \in A\), \(y \in f(A)\); since \(x \in B\), \(y \in f(B)\). Hence \(y \in f(A) \cap f(B)\). \(\square\)
Exercise 1.27
Prove that \(f(f^{-1}(B)) \subseteq B\) with equality if and only if \(f\) is surjective.
Expected evidence: proof of the inclusion, then a proof that surjectivity is equivalent to equality for all \(B\).
If \(y \in f(f^{-1}(B))\) then \(y = f(x)\) for some \(x \in f^{-1}(B)\), meaning \(f(x) \in B\), i.e., \(y \in B\).
If \(f\) is surjective and \(b \in B\), there exists \(x\) with \(f(x) = b\), so \(x \in f^{-1}(B)\) and \(b \in f(f^{-1}(B))\). Conversely, if equality holds for all \(B\), take \(B = Y\).
View detailed correction
Inclusion. If \(y \in f(f^{-1}(B))\) then \(y = f(x)\) for some \(x\) with \(f(x) \in B\), so \(y \in B\).
Equality iff surjective. If \(f\) is surjective and \(b \in B\), choose \(x\) with \(f(x) = b\). Then \(x \in f^{-1}(B)\) and \(b = f(x) \in f(f^{-1}(B))\), giving \(B \subseteq f(f^{-1}(B))\).
Conversely, if equality holds for all \(B\), take \(B = Y\): then \(f(f^{-1}(Y)) = Y\), i.e., \(f(X) = Y\), so \(f\) is surjective. \(\square\)
Equality iff surjective. If \(f\) is surjective and \(b \in B\), choose \(x\) with \(f(x) = b\). Then \(x \in f^{-1}(B)\) and \(b = f(x) \in f(f^{-1}(B))\), giving \(B \subseteq f(f^{-1}(B))\).
Conversely, if equality holds for all \(B\), take \(B = Y\): then \(f(f^{-1}(Y)) = Y\), i.e., \(f(X) = Y\), so \(f\) is surjective. \(\square\)
Exercise 1.28
Prove that \(f^{-1}(f(A)) \supseteq A\) with equality if and only if \(f\) is injective.
Expected evidence: proof of the inclusion and a biconditional for equality.
If \(a \in A\) then \(f(a) \in f(A)\), so \(a \in f^{-1}(f(A))\) by definition.
Equality can fail if \(f\) is not injective: take \(f(x) = x^2\), \(A = \{1\}\). Then \(f(A) = \{1\}\) and \(f^{-1}(\{1\}) = \{-1,1\} \supsetneq A\).
View detailed correction
Inclusion. If \(a \in A\), then \(f(a) \in f(A)\), so by definition \(a \in f^{-1}(f(A))\).
Equality iff injective. Suppose \(f\) is injective and \(x \in f^{-1}(f(A))\). Then \(f(x) \in f(A)\), so \(f(x) = f(a)\) for some \(a \in A\). Injectivity gives \(x = a \in A\). Thus \(f^{-1}(f(A)) \subseteq A\).
Conversely, if \(f\) is not injective, there exist \(x_1 \neq x_2\) with \(f(x_1) = f(x_2)\). Take \(A = \{x_1\}\). Then \(x_2 \in f^{-1}(f(A))\) but \(x_2 \notin A\), so equality fails. \(\square\)
Equality iff injective. Suppose \(f\) is injective and \(x \in f^{-1}(f(A))\). Then \(f(x) \in f(A)\), so \(f(x) = f(a)\) for some \(a \in A\). Injectivity gives \(x = a \in A\). Thus \(f^{-1}(f(A)) \subseteq A\).
Conversely, if \(f\) is not injective, there exist \(x_1 \neq x_2\) with \(f(x_1) = f(x_2)\). Take \(A = \{x_1\}\). Then \(x_2 \in f^{-1}(f(A))\) but \(x_2 \notin A\), so equality fails. \(\square\)
Exercise 1.29
Show that the set \(\mathrm{Bij}(X)\) of all bijections from \(X\) to \(X\) forms a group under function composition.
Expected evidence: verification of the four group axioms: closure, associativity, identity, and inverses.
By Exercise 1.23, composition of bijections is a bijection. This gives closure.
If \(f\) is a bijection then \(f^{-1}\) exists and is also a bijection; it is both a left and right inverse of \(f\) under composition.
View detailed correction
We verify the four group axioms for \((\mathrm{Bij}(X), \circ)\).
Closure. If \(f, g \in \mathrm{Bij}(X)\) then \(g \circ f\) is a bijection by Exercise 1.23.
Associativity. Function composition is associative: \((h \circ g) \circ f = h \circ (g \circ f)\).
Identity. The identity map \(\mathrm{id}_X\) is a bijection with \(f \circ \mathrm{id}_X = \mathrm{id}_X \circ f = f\).
Inverses. For any \(f \in \mathrm{Bij}(X)\), the inverse \(f^{-1}: X \to X\) is a bijection with \(f \circ f^{-1} = f^{-1} \circ f = \mathrm{id}_X\). \(\square\)
Closure. If \(f, g \in \mathrm{Bij}(X)\) then \(g \circ f\) is a bijection by Exercise 1.23.
Associativity. Function composition is associative: \((h \circ g) \circ f = h \circ (g \circ f)\).
Identity. The identity map \(\mathrm{id}_X\) is a bijection with \(f \circ \mathrm{id}_X = \mathrm{id}_X \circ f = f\).
Inverses. For any \(f \in \mathrm{Bij}(X)\), the inverse \(f^{-1}: X \to X\) is a bijection with \(f \circ f^{-1} = f^{-1} \circ f = \mathrm{id}_X\). \(\square\)
Exercise 1.30
State the Cantor-Schroder-Bernstein theorem: if there exist injections \(f: A \to B\) and \(g: B \to A\), then \(|A| = |B|\). Outline the proof.
Expected evidence: a clear statement and a proof outline identifying the key construction.
The goal is to construct a bijection \(h: A \to B\). Classify each \(a \in A\) according to the ancestry of \(a\) under repeated applications of \(g \circ f\) and \(g\).
Define \(A_0 = A \setminus g(B)\) and \(A_{n+1} = g(f(A_n))\). Let \(C = \bigcup_{n \geq 0} A_n\). Set \(h(a) = f(a)\) if \(a \in C\), else \(h(a) = g^{-1}(a)\) (valid since \(a \notin C\) implies \(a \in g(B)\)).
View detailed correction
Theorem. If there exist injections \(f: A \to B\) and \(g: B \to A\), then there exists a bijection \(h: A \to B\).
Proof outline. Define \(A_0 = A \setminus g(B)\) and \(A_{n+1} = (g \circ f)(A_n)\) for \(n \geq 0\). Let \(C = \bigcup_{n=0}^\infty A_n \subseteq A\).
Set \(h: A \to B\) by \(h(a) = f(a)\) if \(a \in C\), and \(h(a) = g^{-1}(a)\) if \(a \notin C\) (note: \(a \notin C\) implies \(a \in g(B)\), so \(g^{-1}(a)\) is well-defined since \(g\) is injective).
One verifies that \(h\) is a bijection: injectivity uses the fact that \(C\) and \(A \setminus C\) map into disjoint parts of \(B\) under \(f\) and \(g^{-1}\) respectively; surjectivity follows by checking every \(b \in B\) is hit. \(\square\)
Proof outline. Define \(A_0 = A \setminus g(B)\) and \(A_{n+1} = (g \circ f)(A_n)\) for \(n \geq 0\). Let \(C = \bigcup_{n=0}^\infty A_n \subseteq A\).
Set \(h: A \to B\) by \(h(a) = f(a)\) if \(a \in C\), and \(h(a) = g^{-1}(a)\) if \(a \notin C\) (note: \(a \notin C\) implies \(a \in g(B)\), so \(g^{-1}(a)\) is well-defined since \(g\) is injective).
One verifies that \(h\) is a bijection: injectivity uses the fact that \(C\) and \(A \setminus C\) map into disjoint parts of \(B\) under \(f\) and \(g^{-1}\) respectively; surjectivity follows by checking every \(b \in B\) is hit. \(\square\)
Exercise 1.31
Prove by contradiction: there is no rational number whose square is 2.
Expected evidence: the classic parity argument, clearly structured as a proof by contradiction.
Assume \(\sqrt{2} = p/q\) with \(p, q \in \mathbb{Z}\), \(q \neq 0\), and \(\gcd(p,q) = 1\). Then \(p^2 = 2q^2\).
\(p^2 = 2q^2\) is even, so \(p\) is even; write \(p = 2k\). Then \(4k^2 = 2q^2\), so \(q^2 = 2k^2\) is even, so \(q\) is even. This contradicts \(\gcd(p,q) = 1\).
View detailed correction
Proof. Suppose for contradiction that \(\sqrt{2} \in \mathbb{Q}\). Write \(\sqrt{2} = p/q\) with \(p, q \in \mathbb{Z}\), \(q \neq 0\), and \(\gcd(p, q) = 1\). Squaring, \(p^2 = 2q^2\). Thus \(p^2\) is even, so \(p\) is even. Write \(p = 2k\); then \(4k^2 = 2q^2\), giving \(q^2 = 2k^2\). Thus \(q^2\) is even, so \(q\) is even. But then \(2 \mid \gcd(p,q)\), contradicting \(\gcd(p,q) = 1\). Therefore no such rational exists. \(\square\)
Exercise 1.32
Prove by contrapositive: if \(n^2\) is even then \(n\) is even.
Expected evidence: explicit statement of the contrapositive and a direct proof of it.
The contrapositive is: if \(n\) is odd then \(n^2\) is odd.
If \(n = 2k+1\), then \(n^2 = 4k^2 + 4k + 1 = 2(2k^2+2k)+1\), which is odd.
View detailed correction
We prove the contrapositive: if \(n\) is odd, then \(n^2\) is odd. Suppose \(n = 2k+1\) for some integer \(k\). Then \(n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2+2k)+1\), which has the form \(2m+1\). Hence \(n^2\) is odd. The original statement follows by contrapositive. \(\square\)
Exercise 1.33
Prove by strong induction: every integer \(n \geq 2\) has a prime factorisation.
Expected evidence: correct strong induction hypothesis and two-case analysis (prime vs. composite).
Assume every integer \(k\) with \(2 \leq k < n\) has a prime factorisation. Consider \(n\): either \(n\) is prime, or \(n\) is composite.
If \(n\) is composite, write \(n = ab\) with \(2 \leq a, b < n\). Apply the inductive hypothesis to both \(a\) and \(b\).
View detailed correction
Proof by strong induction. Base case: \(n = 2\) is prime, so it is its own factorisation.
Inductive step: Let \(n \geq 3\) and assume every integer \(k\) with \(2 \leq k < n\) has a prime factorisation. If \(n\) is prime, it is its own factorisation. If \(n\) is composite, write \(n = ab\) with integers \(2 \leq a, b < n\). By hypothesis, both \(a\) and \(b\) have prime factorisations; concatenating them gives a prime factorisation of \(n\). By strong induction the result holds for all \(n \geq 2\). \(\square\)
Inductive step: Let \(n \geq 3\) and assume every integer \(k\) with \(2 \leq k < n\) has a prime factorisation. If \(n\) is prime, it is its own factorisation. If \(n\) is composite, write \(n = ab\) with integers \(2 \leq a, b < n\). By hypothesis, both \(a\) and \(b\) have prime factorisations; concatenating them gives a prime factorisation of \(n\). By strong induction the result holds for all \(n \geq 2\). \(\square\)
Exercise 1.34
Prove that the sum of the first \(n\) odd natural numbers equals \(n^2\), i.e., \(\displaystyle\sum_{k=1}^{n}(2k-1) = n^2\).
Expected evidence: a clean induction proof with explicit base case and inductive step.
For \(n=1\): the sum is \(2(1)-1 = 1 = 1^2\). Check.
Assume \(\sum_{k=1}^n (2k-1) = n^2\). Then \(\sum_{k=1}^{n+1}(2k-1) = n^2 + (2(n+1)-1) = n^2 + 2n+1 = (n+1)^2\).
View detailed correction
Proof by induction. Base case \(n=1\): \(\sum_{k=1}^1(2k-1) = 1 = 1^2\). Verified.
Inductive step: Assume \(\sum_{k=1}^n(2k-1) = n^2\). Then \[\sum_{k=1}^{n+1}(2k-1) = \sum_{k=1}^n(2k-1) + (2(n+1)-1) = n^2 + 2n+1 = (n+1)^2.\] By induction the formula holds for all \(n \geq 1\). \(\square\)
Inductive step: Assume \(\sum_{k=1}^n(2k-1) = n^2\). Then \[\sum_{k=1}^{n+1}(2k-1) = \sum_{k=1}^n(2k-1) + (2(n+1)-1) = n^2 + 2n+1 = (n+1)^2.\] By induction the formula holds for all \(n \geq 1\). \(\square\)
Exercise 1.35
A set \(S \subseteq \mathbb{N}\) satisfies: \(1 \in S\), and \(n \in S \Rightarrow n+2 \in S\). What can you conclude? What additional condition forces \(S = \mathbb{N}\)?
Expected evidence: identification of the exact subset implied and the extra condition needed.
Starting from \(1 \in S\) and adding 2 each time gives \(1, 3, 5, 7, \ldots\), all odd positive integers. So \(S\) must contain all odd naturals.
A second seed condition \(2 \in S\) together with closure under \(n \mapsto n+2\) yields all even integers. Together these give \(S = \mathbb{N}\).
View detailed correction
The given conditions guarantee that \(S\) contains all odd positive integers: from \(1 \in S\), repeated application of \(n \mapsto n+2\) yields \(1, 3, 5, 7, \ldots \in S\). No information is given about even integers, so the most we can conclude is \(\{1, 3, 5, 7, \ldots\} \subseteq S\).
To force \(S = \mathbb{N}\), one sufficient additional condition is \(2 \in S\): together with closure under \(n \mapsto n+2\), this yields all even naturals, and combined with the odd case gives \(S = \mathbb{N}\). Alternatively, adding the ordinary induction step \(n \in S \Rightarrow n+1 \in S\) immediately gives \(S = \mathbb{N}\). \(\square\)
To force \(S = \mathbb{N}\), one sufficient additional condition is \(2 \in S\): together with closure under \(n \mapsto n+2\), this yields all even naturals, and combined with the odd case gives \(S = \mathbb{N}\). Alternatively, adding the ordinary induction step \(n \in S \Rightarrow n+1 \in S\) immediately gives \(S = \mathbb{N}\). \(\square\)
Exercise 1.36
Use the well-ordering principle to prove that \(\sqrt{2}\) is irrational, without the parity argument of Exercise 1.31.
Expected evidence: the argument using the minimal positive integer denominator.
Suppose \(\sqrt{2} = p/q\) with \(p, q \in \mathbb{N}\). By the well-ordering principle, there is a least such \(q\). Now derive a smaller valid denominator.
From \(\sqrt{2} = p/q\), set \(q_1 = p - q\). Then \(q_1 \sqrt{2} = p\sqrt{2} - q \cdot 2\) and \(0 < q_1 < q\), giving a strictly smaller element of the same set.
View detailed correction
Suppose for contradiction that \(\sqrt{2} \in \mathbb{Q}\). Let \(S = \{q \in \mathbb{N} : q\sqrt{2} \in \mathbb{N}\}\). Since \(\sqrt{2} = p/q\) for some positive integers \(p, q\), we have \(q \in S\), so \(S \neq \emptyset\). By the well-ordering principle, \(S\) has a least element \(q_0\), with \(q_0\sqrt{2} = p_0 \in \mathbb{N}\).
Set \(q_1 = p_0 - q_0 = q_0(\sqrt{2}-1)\). Since \(1 < \sqrt{2} < 2\), we have \(0 < \sqrt{2}-1 < 1\), so \(0 < q_1 < q_0\), and \(q_1 \in \mathbb{N}\) since \(q_1 = p_0 - q_0\). Also \(q_1 \sqrt{2} = p_0\sqrt{2} - 2q_0\). Now \(p_0\sqrt{2} = 2q_0 + q_0(\sqrt{2}-1)^2 \cdot (\sqrt{2}+1) \ldots\) more directly: \(q_1 \sqrt{2} = (p_0 - q_0)\sqrt{2} = p_0\sqrt{2} - q_0\sqrt{2} \cdot \sqrt{2}/\sqrt{2}\). Simpler: \(q_1\sqrt{2} = p_0\sqrt{2} - q_0 \cdot 2\). Since \(p_0\sqrt{2} = (q_0\sqrt{2})\cdot\sqrt{2} = p_0\sqrt{2}\) and \(q_0\sqrt{2} = p_0 \in \mathbb{N}\), we get \(q_1\sqrt{2} = p_0\sqrt{2} - 2q_0 \in \mathbb{N}\). Thus \(q_1 \in S\) with \(q_1 < q_0\), contradicting minimality. Therefore \(\sqrt{2} \notin \mathbb{Q}\). \(\square\)
Set \(q_1 = p_0 - q_0 = q_0(\sqrt{2}-1)\). Since \(1 < \sqrt{2} < 2\), we have \(0 < \sqrt{2}-1 < 1\), so \(0 < q_1 < q_0\), and \(q_1 \in \mathbb{N}\) since \(q_1 = p_0 - q_0\). Also \(q_1 \sqrt{2} = p_0\sqrt{2} - 2q_0\). Now \(p_0\sqrt{2} = 2q_0 + q_0(\sqrt{2}-1)^2 \cdot (\sqrt{2}+1) \ldots\) more directly: \(q_1 \sqrt{2} = (p_0 - q_0)\sqrt{2} = p_0\sqrt{2} - q_0\sqrt{2} \cdot \sqrt{2}/\sqrt{2}\). Simpler: \(q_1\sqrt{2} = p_0\sqrt{2} - q_0 \cdot 2\). Since \(p_0\sqrt{2} = (q_0\sqrt{2})\cdot\sqrt{2} = p_0\sqrt{2}\) and \(q_0\sqrt{2} = p_0 \in \mathbb{N}\), we get \(q_1\sqrt{2} = p_0\sqrt{2} - 2q_0 \in \mathbb{N}\). Thus \(q_1 \in S\) with \(q_1 < q_0\), contradicting minimality. Therefore \(\sqrt{2} \notin \mathbb{Q}\). \(\square\)
Exercise 1.37
Prove Bernoulli's inequality: for \(x > -1\) and \(n \in \mathbb{N}\), \((1+x)^n \geq 1 + nx\).
Expected evidence: a complete proof by induction with clear base case and inductive step.
Base case \(n=0\): \((1+x)^0 = 1 \geq 1 + 0 \cdot x = 1\). Inductive step: assume \((1+x)^n \geq 1+nx\); multiply both sides by \((1+x) > 0\).
\((1+x)^{n+1} \geq (1+nx)(1+x) = 1 + (n+1)x + nx^2 \geq 1 + (n+1)x\) since \(nx^2 \geq 0\).
View detailed correction
Proof by induction on \(n\). Base case \(n=0\): \(1 \geq 1\). True.
Inductive step: assume \((1+x)^n \geq 1+nx\) for some \(n \geq 0\). Since \(1+x > 0\):
\[(1+x)^{n+1} = (1+x)^n \cdot (1+x) \geq (1+nx)(1+x) = 1 + x + nx + nx^2 = 1 + (n+1)x + nx^2.\] Since \(nx^2 \geq 0\), we get \((1+x)^{n+1} \geq 1 + (n+1)x\). By induction the inequality holds for all \(n \in \mathbb{N}\). \(\square\)
Inductive step: assume \((1+x)^n \geq 1+nx\) for some \(n \geq 0\). Since \(1+x > 0\):
\[(1+x)^{n+1} = (1+x)^n \cdot (1+x) \geq (1+nx)(1+x) = 1 + x + nx + nx^2 = 1 + (n+1)x + nx^2.\] Since \(nx^2 \geq 0\), we get \((1+x)^{n+1} \geq 1 + (n+1)x\). By induction the inequality holds for all \(n \in \mathbb{N}\). \(\square\)
Exercise 1.38
Prove that the intersection of any two equivalence relations on a set \(X\) is an equivalence relation.
Expected evidence: verification of reflexivity, symmetry, and transitivity for the intersection relation.
If \(R\) and \(S\) are equivalence relations on \(X\), their intersection \(R \cap S\) (as subsets of \(X \times X\)) satisfies: \(x(R \cap S)y\) iff \(xRy\) and \(xSy\).
For reflexivity: \(xRx\) and \(xSx\), so \(x(R \cap S)x\). Apply the same "and" logic for symmetry and transitivity.
View detailed correction
Let \(R\) and \(S\) be equivalence relations on \(X\), and \(T = R \cap S\).
Reflexivity. For any \(x \in X\): \(xRx\) and \(xSx\), so \(xTx\).
Symmetry. If \(xTy\), then \(xRy\) and \(xSy\). By symmetry of \(R\) and \(S\), \(yRx\) and \(ySx\), so \(yTx\).
Transitivity. If \(xTy\) and \(yTz\), then \(xRy\), \(yRz\), \(xSy\), \(ySz\). By transitivity of \(R\) and \(S\), \(xRz\) and \(xSz\), so \(xTz\). Hence \(T\) is an equivalence relation. \(\square\)
Reflexivity. For any \(x \in X\): \(xRx\) and \(xSx\), so \(xTx\).
Symmetry. If \(xTy\), then \(xRy\) and \(xSy\). By symmetry of \(R\) and \(S\), \(yRx\) and \(ySx\), so \(yTx\).
Transitivity. If \(xTy\) and \(yTz\), then \(xRy\), \(yRz\), \(xSy\), \(ySz\). By transitivity of \(R\) and \(S\), \(xRz\) and \(xSz\), so \(xTz\). Hence \(T\) is an equivalence relation. \(\square\)
Exercise 1.39
Let \(f: X \to Y\). Define \(x \sim y\) iff \(f(x) = f(y)\). Show that \(\sim\) is an equivalence relation and describe the equivalence classes.
Expected evidence: verification of the three axioms and an explicit description of the equivalence classes.
Reflexivity: \(f(x) = f(x)\). Symmetry: if \(f(x) = f(y)\) then \(f(y) = f(x)\). Transitivity: if \(f(x)=f(y)\) and \(f(y)=f(z)\) then \(f(x)=f(z)\).
The equivalence class of \(x\) is \([x] = \{x' \in X : f(x') = f(x)\} = f^{-1}(\{f(x)\})\). These are the fibres of \(f\).
View detailed correction
Reflexivity: \(f(x)=f(x)\), so \(x \sim x\). Symmetry: if \(x \sim y\) then \(f(x)=f(y)\), so \(f(y)=f(x)\), i.e., \(y \sim x\). Transitivity: if \(x \sim y\) and \(y \sim z\) then \(f(x)=f(y)=f(z)\), so \(x \sim z\).
The equivalence class of \(x\) is \([x] = \{x' \in X : f(x') = f(x)\} = f^{-1}(\{f(x)\})\), the fibre of \(f\) over \(f(x)\). The quotient \(X/{\sim}\) is in bijection with the image \(f(X) \subseteq Y\). \(\square\)
The equivalence class of \(x\) is \([x] = \{x' \in X : f(x') = f(x)\} = f^{-1}(\{f(x)\})\), the fibre of \(f\) over \(f(x)\). The quotient \(X/{\sim}\) is in bijection with the image \(f(X) \subseteq Y\). \(\square\)
Exercise 1.40
Show that the usual order \(\leq\) on \(\mathbb{R}\) is a total order. Give an example of a partial order that is not total.
Expected evidence: verification of the partial order axioms and totality for \(\mathbb{R}\), plus a concrete non-total example.
A partial order is reflexive, antisymmetric, and transitive. A total order additionally satisfies: for all \(a, b\), either \(a \leq b\) or \(b \leq a\).
The subset relation \(\subseteq\) on \(\mathcal{P}(\{1,2\})\) is a partial order: \(\{1\}\) and \(\{2\}\) are not comparable.
View detailed correction
Total order on \(\mathbb{R}\). The relation \(\leq\) on \(\mathbb{R}\) is reflexive (\(a \leq a\)), antisymmetric (\(a \leq b\) and \(b \leq a\) implies \(a = b\)), transitive (\(a \leq b\) and \(b \leq c\) implies \(a \leq c\)), and total (for any \(a, b \in \mathbb{R}\), either \(a \leq b\) or \(b \leq a\)). Hence \(\leq\) is a total order.
Non-total example. Consider \(\mathcal{P}(\{1,2\})\) with the subset order \(\subseteq\). This is a partial order, but \(\{1\}\) and \(\{2\}\) are incomparable since neither \(\{1\} \subseteq \{2\}\) nor \(\{2\} \subseteq \{1\}\). \(\square\)
Non-total example. Consider \(\mathcal{P}(\{1,2\})\) with the subset order \(\subseteq\). This is a partial order, but \(\{1\}\) and \(\{2\}\) are incomparable since neither \(\{1\} \subseteq \{2\}\) nor \(\{2\} \subseteq \{1\}\). \(\square\)
Exercise 1.41
Prove that every finite non-empty totally ordered set has a maximum and a minimum.
Expected evidence: a proof by induction on the size of the set.
Base case: a set of size 1 has a single element that is both max and min. Inductive step: remove one element, apply the hypothesis to the remaining set, then compare.
Let \(a \in S\) and let \(M\) be the max of \(S \setminus \{a\}\). Since the order is total, either \(a \leq M\) or \(M \leq a\), giving the max of \(S\).
View detailed correction
Proof by induction on \(|S|\). Base case \(|S|=1\): the unique element is both maximum and minimum.
Inductive step: let \(|S| = n+1\) and pick any \(a \in S\). By the inductive hypothesis, \(S' = S \setminus \{a\}\) has a maximum \(M\) and minimum \(m\). By totality, compare \(a\) with \(M\) and with \(m\): the maximum of \(S\) is \(\max(a, M)\) and the minimum is \(\min(a, m)\). By induction the result holds for all finite non-empty totally ordered sets. \(\square\)
Inductive step: let \(|S| = n+1\) and pick any \(a \in S\). By the inductive hypothesis, \(S' = S \setminus \{a\}\) has a maximum \(M\) and minimum \(m\). By totality, compare \(a\) with \(M\) and with \(m\): the maximum of \(S\) is \(\max(a, M)\) and the minimum is \(\min(a, m)\). By induction the result holds for all finite non-empty totally ordered sets. \(\square\)
Exercise 1.42
Define the lexicographic order on \(\mathbb{N} \times \mathbb{N}\) and prove it is a total order.
Expected evidence: explicit definition plus verification of reflexivity, antisymmetry, transitivity, and totality.
Define \((a,b) \leq_{\mathrm{lex}} (c,d)\) iff \(a < c\), or \(a = c\) and \(b \leq d\).
Given \((a,b)\) and \((c,d)\): since \(\leq\) on \(\mathbb{N}\) is total, either \(a < c\), \(a = c\), or \(a > c\). Each case determines the comparison lexicographically.
View detailed correction
Definition. \((a,b) \leq_{\mathrm{lex}} (c,d)\) iff \(a < c\), or \(a = c\) and \(b \leq d\).
Reflexivity. \((a,b) \leq_{\mathrm{lex}} (a,b)\) since \(a = a\) and \(b \leq b\).
Antisymmetry. If \((a,b) \leq_{\mathrm{lex}} (c,d)\) and \((c,d) \leq_{\mathrm{lex}} (a,b)\), we cannot have \(a < c\) and \(c < a\) simultaneously; hence \(a = c\), and then \(b \leq d\) and \(d \leq b\) give \(b = d\).
Transitivity. Follows by case analysis on whether the first coordinates agree or not.
Totality. Given \((a,b)\) and \((c,d)\): by totality of \(\mathbb{N}\), either \(a < c\), \(a > c\), or \(a = c\) (in which case compare \(b\) and \(d\)). \(\square\)
Reflexivity. \((a,b) \leq_{\mathrm{lex}} (a,b)\) since \(a = a\) and \(b \leq b\).
Antisymmetry. If \((a,b) \leq_{\mathrm{lex}} (c,d)\) and \((c,d) \leq_{\mathrm{lex}} (a,b)\), we cannot have \(a < c\) and \(c < a\) simultaneously; hence \(a = c\), and then \(b \leq d\) and \(d \leq b\) give \(b = d\).
Transitivity. Follows by case analysis on whether the first coordinates agree or not.
Totality. Given \((a,b)\) and \((c,d)\): by totality of \(\mathbb{N}\), either \(a < c\), \(a > c\), or \(a = c\) (in which case compare \(b\) and \(d\)). \(\square\)
Exercise 1.43
Show that \(\mathbb{N}\), \(\mathbb{Z}\), and \(\mathbb{Q}\) are all countably infinite by constructing explicit bijections with \(\mathbb{N}\).
Expected evidence: an explicit bijection for each of \(\mathbb{Z}\) and \(\mathbb{Q}\), with justification.
Interleave positives and negatives: \(0 \mapsto 0,\, 1 \mapsto 1,\, 2 \mapsto -1,\, 3 \mapsto 2,\, 4 \mapsto -2, \ldots\). Formally: \(f(2k) = k\), \(f(2k+1) = -(k+1)\) for \(k \geq 0\).
Arrange all fractions \(p/q\) (in lowest terms, \(q > 0\)) in the grid \(\mathbb{Z} \times \mathbb{N}\) and enumerate by diagonals.
View detailed correction
N is countably infinite by definition.
Z is countably infinite. Define \(f: \mathbb{N} \to \mathbb{Z}\) by \(f(0)=0\), \(f(2k-1)=k\), \(f(2k)=-k\) for \(k \geq 1\). This maps \(\mathbb{N}\) bijectively onto \(\mathbb{Z}\).
Q is countably infinite. Since \(\mathbb{Z} \times (\mathbb{N} \setminus \{0\})\) is countable (as a product of two countable sets), the map \((p,q) \mapsto p/q\) restricted to coprime pairs gives a bijection onto \(\mathbb{Q}\), showing \(\mathbb{Q}\) is countable. Since \(\mathbb{Q} \supseteq \mathbb{N}\) is infinite, it is countably infinite. \(\square\)
Z is countably infinite. Define \(f: \mathbb{N} \to \mathbb{Z}\) by \(f(0)=0\), \(f(2k-1)=k\), \(f(2k)=-k\) for \(k \geq 1\). This maps \(\mathbb{N}\) bijectively onto \(\mathbb{Z}\).
Q is countably infinite. Since \(\mathbb{Z} \times (\mathbb{N} \setminus \{0\})\) is countable (as a product of two countable sets), the map \((p,q) \mapsto p/q\) restricted to coprime pairs gives a bijection onto \(\mathbb{Q}\), showing \(\mathbb{Q}\) is countable. Since \(\mathbb{Q} \supseteq \mathbb{N}\) is infinite, it is countably infinite. \(\square\)
Exercise 1.44
Prove that the interval \((0,1)\) is uncountable using Cantor's diagonal argument.
Expected evidence: a clear presentation of the diagonal argument with explicit construction of the missing real number.
Suppose \((0,1)\) is countable. List its elements as \(x_1, x_2, x_3, \ldots\) where each \(x_n = 0.d_{n1}d_{n2}d_{n3}\cdots\) in decimal. Construct a number \(y\) that differs from each \(x_n\).
Define \(y = 0.e_1e_2e_3\cdots\) where \(e_n = 5\) if \(d_{nn} \neq 5\), and \(e_n = 6\) if \(d_{nn} = 5\). Then \(y \neq x_n\) for every \(n\).
View detailed correction
Suppose for contradiction that \((0,1)\) is countable. List its elements as \(x_1, x_2, x_3, \ldots\) and write each in decimal: \(x_n = 0.d_{n1}d_{n2}d_{n3}\cdots\) (using non-terminating expansions).
Define \(y = 0.e_1e_2e_3\cdots\) where \(e_n = 5\) if \(d_{nn} \neq 5\) and \(e_n = 6\) if \(d_{nn} = 5\). Then \(y \in (0,1)\) and \(y \neq x_n\) for every \(n\) (since \(y\) and \(x_n\) differ in the \(n\)-th decimal digit). This contradicts the assumption that the list contains every element of \((0,1)\). Therefore \((0,1)\) is uncountable. \(\square\)
Define \(y = 0.e_1e_2e_3\cdots\) where \(e_n = 5\) if \(d_{nn} \neq 5\) and \(e_n = 6\) if \(d_{nn} = 5\). Then \(y \in (0,1)\) and \(y \neq x_n\) for every \(n\) (since \(y\) and \(x_n\) differ in the \(n\)-th decimal digit). This contradicts the assumption that the list contains every element of \((0,1)\). Therefore \((0,1)\) is uncountable. \(\square\)
Exercise 1.45
Prove Cantor's theorem: for any set \(A\), \(|A| < |\mathcal{P}(A)|\). Conclude that \(\mathcal{P}(\mathbb{N})\) is uncountable.
Expected evidence: the diagonal/Russell-style proof that no surjection from \(A\) to \(\mathcal{P}(A)\) exists.
There is always an injection \(a \mapsto \{a\}\) from \(A\) into \(\mathcal{P}(A)\), so \(|A| \leq |\mathcal{P}(A)|\). It remains to show there is no surjection.
Let \(f: A \to \mathcal{P}(A)\) be any function. Define \(D = \{a \in A : a \notin f(a)\}\). If \(D = f(c)\) for some \(c\), then \(c \in D\) iff \(c \notin D\), a contradiction.
View detailed correction
Proof. There is an injection \(i: A \to \mathcal{P}(A)\) given by \(i(a) = \{a\}\), so \(|A| \leq |\mathcal{P}(A)|\). It suffices to show no surjection \(f: A \to \mathcal{P}(A)\) exists.
Let \(f: A \to \mathcal{P}(A)\) be any function. Define \(D = \{a \in A : a \notin f(a)\} \subseteq A\), so \(D \in \mathcal{P}(A)\). Suppose for contradiction that \(D = f(c)\) for some \(c \in A\). Then: \(c \in D \Leftrightarrow c \notin f(c) = D\), a contradiction. Therefore \(D \notin \mathrm{im}(f)\), so \(f\) is not surjective.
Since no bijection \(A \to \mathcal{P}(A)\) exists but an injection does, we conclude \(|A| < |\mathcal{P}(A)|\).
Corollary. Taking \(A = \mathbb{N}\), since \(|\mathbb{N}| < |\mathcal{P}(\mathbb{N})|\), it follows that \(\mathcal{P}(\mathbb{N})\) is uncountable. \(\square\)
Let \(f: A \to \mathcal{P}(A)\) be any function. Define \(D = \{a \in A : a \notin f(a)\} \subseteq A\), so \(D \in \mathcal{P}(A)\). Suppose for contradiction that \(D = f(c)\) for some \(c \in A\). Then: \(c \in D \Leftrightarrow c \notin f(c) = D\), a contradiction. Therefore \(D \notin \mathrm{im}(f)\), so \(f\) is not surjective.
Since no bijection \(A \to \mathcal{P}(A)\) exists but an injection does, we conclude \(|A| < |\mathcal{P}(A)|\).
Corollary. Taking \(A = \mathbb{N}\), since \(|\mathbb{N}| < |\mathcal{P}(\mathbb{N})|\), it follows that \(\mathcal{P}(\mathbb{N})\) is uncountable. \(\square\)