Chapter 01 · General Topology / Topologie Générale
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.1.
∎
Generalization 1.1 - Indexed families
Theorem 1.1 extends from two sets to arbitrary indexed families. Let \(f:X\to Y\), let \(I\) be any index set, and let \((B_i)_{i\in I}\) be a family of subsets of \(Y\). The identities below also cover \(I=\emptyset\), with the standard conventions for empty unions and intersections.
\[f^{-1}\!\left(\bigcup_{i\in I}B_i\right)=\bigcup_{i\in I}f^{-1}(B_i),\]
\[f^{-1}\!\left(\bigcap_{i\in I}B_i\right)=\bigcap_{i\in I}f^{-1}(B_i).\]
The union identity is especially important because a topology is closed under arbitrary unions. The intersection identity is stronger than the finite-intersection requirement in the topology axioms. The proof follows the same elementwise reasoning as Theorem 1.1 and is assigned in Exercise 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)\). ∎
Exercise 1.4
Let \(f:X\to Y\), let \(I\) be any index set, and let \((B_i)_{i\in I}\) be a family of subsets of \(Y\). Prove that inverse images preserve the indexed union and indexed intersection stated in Generalization 1.1, including the empty-index case.
Expected evidence: two elementwise equivalence proofs, explicit use of existential and universal quantifiers, and a stated conclusion.
LaTeX workspace
Live preview
Your proof will render here.
Fix \(x\in X\). For each equality, compare the membership conditions on both sides.
Translate union membership with an existential quantifier and intersection membership with a universal quantifier.
Use \(f(x)\in B_i\iff x\in f^{-1}(B_i)\) and identify the resulting indexed operation.
View detailed correction - attempt first
For the union, translate membership through the inverse-image definition and the existential quantifier. For the intersection, use the corresponding universal quantifier. Therefore both identities hold. \(\square\)
Exercise 1.5
Let \(f:X\to Y\). Prove that \(f^{-1}(\emptyset)=\emptyset\) and \(f^{-1}(Y)=X\).
Expected evidence: two elementwise arguments using the definition of inverse image and the codomain condition.
LaTeX workspace
Live preview
Your proof will render here.
Translate inverse-image membership.
No element can map into the empty set.
Every value of \(f\) lies in \(Y\).
View detailed correction - attempt first
The empty set has empty inverse image, while every point of \(X\) maps into \(Y\). Therefore \(f^{-1}(\emptyset)=\emptyset\) and \(f^{-1}(Y)=X\). \(\square\)
Exercise 1.6
Let \(B_1,B_2\subseteq Y\). Prove that \(B_1\subseteq B_2\) implies \(f^{-1}(B_1)\subseteq f^{-1}(B_2)\).
Expected evidence: a direct inclusion proof that tracks an arbitrary element through the hypothesis.
LaTeX workspace
Live preview
Your proof will render here.
Start with \(x\in f^{-1}(B_1)\).
Use the hypothesis on \(B_1\) and \(B_2\).
Return to inverse-image notation.
View detailed correction - attempt first
Apply the inclusion to \(f(x)\), then translate back. Thus inverse images are monotone. \(\square\)
Exercise 1.7
For \(B,C\subseteq Y\), prove that \(f^{-1}(B\setminus C)=f^{-1}(B)\setminus f^{-1}(C)\).
Expected evidence: an elementwise chain of equivalences that handles both membership and non-membership.
LaTeX workspace
Live preview
Your proof will render here.
Compare membership on both sides.
Separate the positive and negative membership conditions.
Recognize membership in the difference on the right.
View detailed correction - attempt first
The membership conditions on both sides are equivalent for every \(x\in X\). \(\square\)
Exercise 1.8
For \(B,C\subseteq Y\), prove that inverse images preserve symmetric difference: \(f^{-1}(B\triangle C)=f^{-1}(B)\triangle f^{-1}(C)\).
Expected evidence: correct use of the symmetric-difference decomposition, Theorem 1.1, and Exercise 1.7.
LaTeX workspace
Live preview
Your proof will render here.
Express symmetric difference using unions and differences.
Use the identities already proved.
Identify the symmetric difference on the right.
View detailed correction - attempt first
Rewrite, distribute the inverse image, and recognize the final symmetric difference. \(\square\)
Exercise 1.9
Let \(f:X\to Y\), \(g:Y\to Z\), and \(C\subseteq Z\). Prove that \((g\circ f)^{-1}(C)=f^{-1}(g^{-1}(C))\).
Expected evidence: a type-correct elementwise chain of equivalences and no unnecessary hypotheses.
LaTeX workspace
Live preview
Your proof will render here.
Verify that each inverse image is formed in the correct space.
Write out \((g\circ f)(x)\).
Move backward through \(g\), then through \(f\).
View detailed correction - attempt first
The definitions give the equivalence directly. \(\square\)
Exercise 1.10
For \(y\in f(X)\), let \(F_y=f^{-1}(\{y\})\). Prove that the nonempty fibers form a partition of \(X\), and characterize injectivity using their sizes.
Expected evidence: all partition axioms and both directions of the injectivity characterization.
LaTeX workspace
Live preview
Your proof will render here.
Every point belongs to the fiber of its image.
Distinct fibers cannot share a point.
Injectivity forbids two points in one fiber.
View detailed correction - attempt first
The nonempty fibers cover \(X\), are pairwise disjoint, and encode exactly when two points share an image. \(\square\)
Exercise 1.11
Let \((A_i)_{i\in I}\) be a family of subsets of \(X\). Prove that direct images preserve indexed unions.
Expected evidence: an elementwise proof with explicit existential witnesses in both directions.
LaTeX workspace
Live preview
Your proof will render here.
Use the witness in the definition of direct image.
The union supplies an index.
Use the same witnesses in reverse.
View detailed correction - attempt first
Track the direct-image witness and the union index in both directions. \(\square\)
Exercise 1.12
Prove that \(f\) is injective if and only if direct images preserve every binary intersection.
Expected evidence: both directions, including a singleton argument for the converse.
LaTeX workspace
Live preview
Your proof will render here.
First prove the easy inclusion.
Injectivity merges the two witnesses.
Noninjectivity violates the claimed equality on singleton sets.
View detailed correction - attempt first
Injectivity is exactly what turns the universal inclusion into equality for all intersections. \(\square\)
Exercise 1.13
Write the quantified negations of injectivity and surjectivity, then apply them to \(f(x)=x^2\) on \(\mathbb{R}\).
Expected evidence: correctly ordered quantifiers and explicit witnesses.
LaTeX workspace
Live preview
Your proof will render here.
Use an existential pair of distinct points.
Reverse the quantifiers and negate the equality.
Use \(1,-1\) and a negative target.
View detailed correction - attempt first
The witnesses \(1,-1\) disprove injectivity, and the missing target \(-1\) disproves surjectivity. \(\square\)
Exercise 1.14
Construct finite counterexamples to two false converses, then identify the hypotheses that repair them.
Expected evidence: two explicit finite counterexamples and proof of the repaired statements.
LaTeX workspace
Live preview
Your proof will render here.
Use nonsurjectivity.
Use noninjectivity.
Surjectivity repairs (a), and injectivity repairs (b).
View detailed correction - attempt first
Nonsurjectivity hides codomain points; noninjectivity merges domain points. Surjectivity and injectivity respectively repair the converses. \(\square\)
Exercise 1.15
Use inverse images to construct a topology on \(X\) from a topology on \(Y\).
Expected evidence: a complete verification of the three topology axioms.
LaTeX workspace
Live preview
Your proof will render here.
Verify the first topology axiom.
Use the indexed-union identity.
Use the binary-intersection identity, then iterate for finite intersections.
View detailed correction - attempt first
The inverse-image identities transport all three topology axioms from \(Y\) to \(X\). \(\square\)
Further 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} = 2q-p\) 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 < q_1 < q_0\), and \(q_1 \in \mathbb{N}\). Moreover, \[q_1\sqrt{2}=(p_0-q_0)\sqrt{2}=2q_0-p_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 < q_1 < q_0\), and \(q_1 \in \mathbb{N}\). Moreover, \[q_1\sqrt{2}=(p_0-q_0)\sqrt{2}=2q_0-p_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\)