Course Foundation

General Topology · Chapter 1 of 14

Sets, Functions, and Proof

This opening chapter establishes the language and proof discipline used throughout General Topology / Topologie Générale. Sets, functions, direct and inverse images, indexed families, quantifiers, and proof strategies become the working tools for metric spaces, topological spaces, continuity, compactness, and the chapters that follow.

EN · FR · Bilingual

Visual investigations · Before the formal course

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?

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?

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?

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.

\(\mathbb{N}=\{0,1,2,\ldots\}\) - natural numbers in this course

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

Example after Definition 1.1 A function on finite sets Example. Let \(X=\{1,2,3\}\) and \(Y=\{a,b,c\}\). Define \(f:X\to Y\) by \(f(1)=a\), \(f(2)=b\), and \(f(3)=b\). This is a function because every element of the domain \(X\) receives exactly one value in \(Y\). The fact that both \(2\) and \(3\) have the same value does not violate the definition of a function. The domain is \(X=\{1,2,3\}\), the codomain is \(Y=\{a,b,c\}\), and the image is \(f(X)=\{a,b\}\). Notice that \(c\) belongs to the codomain but not to the image. Learning point. A function is determined by the requirement of one output for each input. Different inputs are allowed to have the same output.

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.

Example after Definition 1.2 Recognizing injectivity, surjectivity, and bijectivity Injective but not surjective. Let \(u:\mathbb N\to\mathbb N\) be \(u(n)=n+1\). If \(u(n_1)=u(n_2)\), then \(n_1+1=n_2+1\), so \(n_1=n_2\); hence \(u\) is injective. It is not surjective because \(0\in\mathbb N\) has no preimage. Surjective but not injective. Let \(v:\mathbb R\to[0,\infty)\) be \(v(x)=x^2\). Every \(y\ge 0\) equals \((\sqrt y)^2\), so \(v\) is surjective. It is not injective because \(v(1)=v(-1)=1\) while \(1\ne-1\). Bijective. Let \(w:\mathbb R\to\mathbb R\) be \(w(x)=2x+1\). Equality \(w(x_1)=w(x_2)\) forces \(x_1=x_2\), so \(w\) is injective. Given \(y\in\mathbb R\), choosing \(x=(y-1)/2\) gives \(w(x)=y\), so \(w\) is surjective. Therefore \(w\) is bijective. Learning point. Injectivity asks whether two inputs can collapse to one output. Surjectivity asks whether every codomain value is reached. Bijectivity requires both properties.

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.

Example after Definition 1.3 Direct image and inverse image are different operations Example. Let \(X=\{1,2,3,4\}\), \(Y=\{a,b,c\}\), and define \(f:X\to Y\) by \(f(1)=a\), \(f(2)=b\), \(f(3)=b\), \(f(4)=c\). Take \(A=\{1,3,4\}\subseteq X\). The direct image collects the values of \(f\) on elements of \(A\): \[f(A)=\{f(1),f(3),f(4)\}=\{a,b,c\}.\] Now take \(B=\{b,c\}\subseteq Y\). The inverse image collects all domain points whose values lie in \(B\): \[f^{-1}(B)=\{2,3,4\}.\] Learning point. For \(f(A)\), start with elements of the domain and move forward through \(f\). For \(f^{-1}(B)\), start with a subset of the codomain and ask which domain elements land in it. The notation \(f^{-1}(B)\) does not require \(f\) to have an inverse function.

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 · Complete proof Proof strategy. To prove equality of two sets, it is enough to show that an arbitrary element belongs to the left-hand set if and only if it belongs to the right-hand set. We therefore fix \(x\in X\) and repeatedly unpack the definition of inverse image. 1. Inverse image of a union. Starting from the left-hand side, \[\begin{aligned} x\in f^{-1}(B_1\cup B_2) &\iff f(x)\in B_1\cup B_2\\ &\iff \bigl(f(x)\in B_1\bigr)\text{ or }\bigl(f(x)\in B_2\bigr)\\ &\iff \bigl(x\in f^{-1}(B_1)\bigr)\text{ or }\bigl(x\in f^{-1}(B_2)\bigr)\\ &\iff x\in f^{-1}(B_1)\cup f^{-1}(B_2). \end{aligned}\] Every equivalence is reversible, so the two sets contain exactly the same elements. Hence \[f^{-1}(B_1\cup B_2)=f^{-1}(B_1)\cup f^{-1}(B_2).\] 2. Inverse image of an intersection. Again fix \(x\in X\). Then \[\begin{aligned} x\in f^{-1}(B_1\cap B_2) &\iff f(x)\in B_1\cap B_2\\ &\iff \bigl(f(x)\in B_1\bigr)\text{ and }\bigl(f(x)\in B_2\bigr)\\ &\iff \bigl(x\in f^{-1}(B_1)\bigr)\text{ and }\bigl(x\in f^{-1}(B_2)\bigr)\\ &\iff x\in f^{-1}(B_1)\cap f^{-1}(B_2). \end{aligned}\] Therefore \[f^{-1}(B_1\cap B_2)=f^{-1}(B_1)\cap f^{-1}(B_2).\] 3. Inverse image of a complement. For \(x\in X\), \[\begin{aligned} x\in f^{-1}(Y\setminus B_1) &\iff f(x)\in Y\setminus B_1\\ &\iff f(x)\notin B_1. \end{aligned}\] The condition \(f(x)\in Y\) is automatic because \(f:X\to Y\). Continuing, \[f(x)\notin B_1\iff x\notin f^{-1}(B_1)\iff x\in X\setminus f^{-1}(B_1).\] Hence \[f^{-1}(Y\setminus B_1)=X\setminus f^{-1}(B_1).\] Conclusion. All three identities follow directly from the definition of inverse image. Notice that no injectivity, surjectivity, or bijectivity hypothesis was used. ∎

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. A complete proof is given immediately below. Exercise 1.4 then asks you to reconstruct the indexed-family argument independently, including the empty-index case.

Proof · Generalization 1.1 · Indexed families Proof. Fix an arbitrary \(x\in X\). The indexed union identity follows by translating the existential quantifier hidden in union membership: \[\begin{aligned} x\in f^{-1}\!\left(\bigcup_{i\in I}B_i\right) &\iff f(x)\in\bigcup_{i\in I}B_i\\ &\iff \exists i\in I\text{ such that }f(x)\in B_i\\ &\iff \exists i\in I\text{ such that }x\in f^{-1}(B_i)\\ &\iff x\in\bigcup_{i\in I}f^{-1}(B_i). \end{aligned}\] Because this holds for every \(x\in X\), \[f^{-1}\!\left(\bigcup_{i\in I}B_i\right)=\bigcup_{i\in I}f^{-1}(B_i).\] For intersections, membership contains a universal quantifier: \[\begin{aligned} x\in f^{-1}\!\left(\bigcap_{i\in I}B_i\right) &\iff f(x)\in\bigcap_{i\in I}B_i\\ &\iff \forall i\in I,\ f(x)\in B_i\\ &\iff \forall i\in I,\ x\in f^{-1}(B_i)\\ &\iff x\in\bigcap_{i\in I}f^{-1}(B_i). \end{aligned}\] Therefore \[f^{-1}\!\left(\bigcap_{i\in I}B_i\right)=\bigcap_{i\in I}f^{-1}(B_i).\] Empty-index case. If \(I=\emptyset\), then \(\bigcup_{i\in\emptyset}B_i=\emptyset\) and \(\bigcap_{i\in\emptyset}B_i=Y\). Thus the two formulas reduce respectively to \(f^{-1}(\emptyset)=\emptyset\) and \(f^{-1}(Y)=X\), which are true directly from the definition of inverse image. Why this matters. The proof shows that inverse image translates existential and universal membership statements without changing their logical form. This is the mechanism that later makes inverse images compatible with the union and intersection axioms of topology. ∎

Remark 1.1 - Why this matters for topology In Chapter 6 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. When you reveal a correction, read the goal and reasoning plan first, then compare each line of the complete solution with your own argument.

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

Detailed correction: Exercise 1.1.

1. Goal.
Let \(f : X \to Y\). Prove that \(f^{-1}(Y \setminus B) = X \setminus f^{-1}(B)\) for any \(B \subseteq Y\).

2. Reasoning plan.
Checkpoint 1. Use double inclusion. For (\(\subseteq\)): let \(x \in f^{-1}(Y \setminus B)\) and unpack the definition.
Checkpoint 2. \(x \in f^{-1}(S)\) means exactly \(f(x) \in S\). Apply this in each direction.
Checkpoint 3. \(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)\).

3. Learning check before the full solution.
Do not skip the logical bridge between consecutive formulas. For set equalities, an elementwise equivalence or two inclusions is what turns symbolic manipulation into a proof.

4. Complete step-by-step solution.

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. ∎

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

With \(A_1=\{-1\}\) and \(A_2=\{1\}\), compute \(f(A_1\cap A_2)\) and \(f(A_1)\cap f(A_2)\) separately and state why one is a proper subset of the other.

Detailed correction: Exercise 1.2.

1. Goal.
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)\).

2. Reasoning plan.
Checkpoint 1. 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.
Checkpoint 2. 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\).
Checkpoint 3. With \(A_1=\{-1\}\) and \(A_2=\{1\}\), compute \(f(A_1\cap A_2)\) and \(f(A_1)\cap f(A_2)\) separately and state why one is a proper subset of the other.

3. Learning check before the full solution.
A proposed example is not enough by itself. Compute or verify every property requested, and explicitly show the feature that makes the example work.

4. Complete step-by-step solution.

Step 1 - choose a non-injective function. Let \(f:\mathbb R\to\mathbb R\) be \(f(x)=x^2\). The two distinct points \(-1\) and \(1\) have the same image, since \(f(-1)=f(1)=1\). This is the mechanism that can make the right-hand intersection larger.

Step 2 - choose disjoint input sets. Take \(A_1=\{-1\}\) and \(A_2=\{1\}\). Then \(A_1\cap A_2=\emptyset\), so \[f(A_1\cap A_2)=f(\emptyset)=\emptyset.\]

Step 3 - compute the two direct images. We have \[f(A_1)=\{1\},\qquad f(A_2)=\{1\}.\] Therefore \[f(A_1)\cap f(A_2)=\{1\}.\]

Step 4 - verify strict inclusion. Since \(\emptyset\subseteq\{1\}\) and \(\emptyset\ne\{1\}\), \[f(A_1\cap A_2)=\emptyset\subsetneq\{1\}=f(A_1)\cap f(A_2).\] Thus the requested strict inclusion occurs. \(\square\)

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.

For \(x\in f^{-1}(B_1)\cap f^{-1}(B_2)\), translate membership back to statements about \(f(x)\).

Compress both inclusions into: \(x\in f^{-1}(B_1\cap B_2)\iff f(x)\in B_1\cap B_2\iff x\in f^{-1}(B_1)\cap f^{-1}(B_2)\).

Detailed correction: Exercise 1.3.

1. Goal.
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\).

2. Reasoning plan.
Checkpoint 1. 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.
Checkpoint 2. For \(x\in f^{-1}(B_1)\cap f^{-1}(B_2)\), translate membership back to statements about \(f(x)\).
Checkpoint 3. Compress both inclusions into: \(x\in f^{-1}(B_1\cap B_2)\iff f(x)\in B_1\cap B_2\iff x\in f^{-1}(B_1)\cap f^{-1}(B_2)\).

3. Learning check before the full solution.
Do not skip the logical bridge between consecutive formulas. For set equalities, an elementwise equivalence or two inclusions is what turns symbolic manipulation into a proof.

4. Complete step-by-step solution.

(\(\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)\). ∎

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 condition for \(x\) to belong to the left-hand side with the condition for it to belong to the right-hand side.

Use \(f(x)\in\bigcup_{i\in I}B_i\) iff there exists \(i\in I\) such that \(f(x)\in B_i\), and \(f(x)\in\bigcap_{i\in I}B_i\) iff for every \(i\in I\), \(f(x)\in B_i\).

For every \(i\in I\), use \(f(x)\in B_i\) iff \(x\in f^{-1}(B_i)\), then identify the resulting indexed union or intersection.

Detailed correction: Exercise 1.4.

1. Goal.
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.

2. Reasoning plan.
Checkpoint 1. Fix \(x\in X\). For each equality, compare the condition for \(x\) to belong to the left-hand side with the condition for it to belong to the right-hand side.
Checkpoint 2. Use \(f(x)\in\bigcup_{i\in I}B_i\) iff there exists \(i\in I\) such that \(f(x)\in B_i\), and \(f(x)\in\bigcap_{i\in I}B_i\) iff for every \(i\in I\), \(f(x)\in B_i\).
Checkpoint 3. For every \(i\in I\), use \(f(x)\in B_i\) iff \(x\in f^{-1}(B_i)\), then identify the resulting indexed union or intersection.

3. Learning check before the full solution.
Do not skip the logical bridge between consecutive formulas. For set equalities, an elementwise equivalence or two inclusions is what turns symbolic manipulation into a proof.

4. Complete step-by-step solution.

For the union, let \(x\in X\). Then \(x\in f^{-1}(\bigcup_{i\in I}B_i)\) iff \(f(x)\in\bigcup_{i\in I}B_i\), iff there exists \(i\in I\) such that \(f(x)\in B_i\), iff there exists \(i\in I\) such that \(x\in f^{-1}(B_i)\), iff \(x\in\bigcup_{i\in I}f^{-1}(B_i)\).

For the intersection, \(x\in f^{-1}(\bigcap_{i\in I}B_i)\) iff \(f(x)\in\bigcap_{i\in I}B_i\), iff for every \(i\in I\), \(f(x)\in B_i\), iff for every \(i\in I\), \(x\in f^{-1}(B_i)\), iff \(x\in\bigcap_{i\in I}f^{-1}(B_i)\).

Empty-index case. If \(I=\emptyset\), then \(\bigcup_{i\in\emptyset}B_i=\emptyset\) and \(\bigcap_{i\in\emptyset}B_i=Y\). Hence \(f^{-1}(\emptyset)=\emptyset=\bigcup_{i\in\emptyset}f^{-1}(B_i)\), while \(f^{-1}(Y)=X=\bigcap_{i\in\emptyset}f^{-1}(B_i)\). Thus both identities also hold for the empty family. \(\square\)

Expected evidence: two elementwise arguments using the definition of inverse image and the codomain condition.

LaTeX workspace

Live preview

Your proof will render here.

For \(B\subseteq Y\), \(x\in f^{-1}(B)\) means exactly that \(f(x)\in B\).

No value \(f(x)\) can belong to \(\emptyset\); therefore the first inverse image has no elements.

Because \(f:X\to Y\), every \(x\in X\) satisfies \(f(x)\in Y\).

Detailed correction: Exercise 1.5.

1. Goal.
Let \(f:X\to Y\). Prove that \(f^{-1}(\emptyset)=\emptyset\) and \(f^{-1}(Y)=X\).

2. Reasoning plan.
Checkpoint 1. For \(B\subseteq Y\), \(x\in f^{-1}(B)\) means exactly that \(f(x)\in B\).
Checkpoint 2. No value \(f(x)\) can belong to \(\emptyset\); therefore the first inverse image has no elements.
Checkpoint 3. Because \(f:X\to Y\), every \(x\in X\) satisfies \(f(x)\in Y\).

3. Learning check before the full solution.
Do not skip the logical bridge between consecutive formulas. For set equalities, an elementwise equivalence or two inclusions is what turns symbolic manipulation into a proof.

4. Complete step-by-step solution.

We prove the two identities separately from the definition of inverse image.

1. Preimage of the empty set. Let \(x\in X\). By definition, \[x\in f^{-1}(\emptyset)\iff f(x)\in\emptyset.\] The statement \(f(x)\in\emptyset\) is false for every \(x\), because the empty set has no elements. Hence \(f^{-1}(\emptyset)\) contains no elements, and therefore \[f^{-1}(\emptyset)=\emptyset.\]

2. Preimage of the whole codomain. Again let \(x\in X\). Since \(f:X\to Y\), the value \(f(x)\) belongs to \(Y\) for every \(x\in X\). Thus \[x\in f^{-1}(Y)\iff f(x)\in Y\] is true for every \(x\in X\). Therefore every element of \(X\) belongs to \(f^{-1}(Y)\), and by definition the preimage is already a subset of \(X\). Hence \[f^{-1}(Y)=X.\] No injectivity or surjectivity assumption is needed. \(\square\)

Expected evidence: a direct inclusion proof that tracks an arbitrary element through the hypothesis.

LaTeX workspace

Live preview

Your proof will render here.

Let \(x\in f^{-1}(B_1)\) and translate this membership into a statement about \(f(x)\).

From \(f(x)\in B_1\) and \(B_1\subseteq B_2\), infer \(f(x)\in B_2\).

The condition \(f(x)\in B_2\) is equivalent to \(x\in f^{-1}(B_2)\).

Detailed correction: Exercise 1.6.

1. Goal.
Let \(B_1,B_2\subseteq Y\). Prove that \(B_1\subseteq B_2\) implies \(f^{-1}(B_1)\subseteq f^{-1}(B_2)\).

2. Reasoning plan.
Checkpoint 1. Let \(x\in f^{-1}(B_1)\) and translate this membership into a statement about \(f(x)\).
Checkpoint 2. From \(f(x)\in B_1\) and \(B_1\subseteq B_2\), infer \(f(x)\in B_2\).
Checkpoint 3. The condition \(f(x)\in B_2\) is equivalent to \(x\in f^{-1}(B_2)\).

3. Learning check before the full solution.
Do not skip the logical bridge between consecutive formulas. For set equalities, an elementwise equivalence or two inclusions is what turns symbolic manipulation into a proof.

4. Complete step-by-step solution.

Assume \(B_1\subseteq B_2\). We must prove \(f^{-1}(B_1)\subseteq f^{-1}(B_2)\).

Step 1 - start with an arbitrary element of the smaller preimage. Let \(x\in f^{-1}(B_1)\). By definition of inverse image, this means \[f(x)\in B_1.\]

Step 2 - use the given inclusion in the codomain. Since \(B_1\subseteq B_2\), every element of \(B_1\) is an element of \(B_2\). Therefore \[f(x)\in B_2.\]

Step 3 - translate back through the inverse-image definition. The statement \(f(x)\in B_2\) is equivalent to \[x\in f^{-1}(B_2).\] Thus every \(x\in f^{-1}(B_1)\) also lies in \(f^{-1}(B_2)\). Consequently \[f^{-1}(B_1)\subseteq f^{-1}(B_2).\] This property is often called monotonicity of inverse image. \(\square\)

Expected evidence: an elementwise chain of equivalences that handles both membership and non-membership.

LaTeX workspace

Live preview

Your proof will render here.

Fix \(x\in X\) and begin with \(x\in f^{-1}(B\setminus C)\).

The statement \(f(x)\in B\setminus C\) means \(f(x)\in B\) and \(f(x)\notin C\).

Use \(f(x)\in B\iff x\in f^{-1}(B)\) and \(f(x)\notin C\iff x\notin f^{-1}(C)\).

Detailed correction: Exercise 1.7.

1. Goal.
For \(B,C\subseteq Y\), prove that \(f^{-1}(B\setminus C)=f^{-1}(B)\setminus f^{-1}(C)\).

2. Reasoning plan.
Checkpoint 1. Fix \(x\in X\) and begin with \(x\in f^{-1}(B\setminus C)\).
Checkpoint 2. The statement \(f(x)\in B\setminus C\) means \(f(x)\in B\) and \(f(x)\notin C\).
Checkpoint 3. Use \(f(x)\in B\iff x\in f^{-1}(B)\) and \(f(x)\notin C\iff x\notin f^{-1}(C)\).

3. Learning check before the full solution.
Do not skip the logical bridge between consecutive formulas. For set equalities, an elementwise equivalence or two inclusions is what turns symbolic manipulation into a proof.

4. Complete step-by-step solution.

Let \(x\in X\). Then \(x\in f^{-1}(B\setminus C)\) if and only if \(f(x)\in B\setminus C\), if and only if \(f(x)\in B\) and \(f(x)\notin C\), if and only if \(x\in f^{-1}(B)\) and \(x\notin f^{-1}(C)\), if and only if \(x\in f^{-1}(B)\setminus f^{-1}(C)\). Since this equivalence holds for every \(x\in X\), the two sets are equal. \(\square\)

Expected evidence: correct use of \(B\triangle C=(B\setminus C)\cup(C\setminus B)\), Theorem 1.1, and Exercise 1.7.

LaTeX workspace

Live preview

Your proof will render here.

Use \(B\triangle C=(B\setminus C)\cup(C\setminus B)\).

Apply Theorem 1.1 to the union, then apply Exercise 1.7 to each difference.

The final union is exactly the definition of \(f^{-1}(B)\triangle f^{-1}(C)\).

Detailed correction: Exercise 1.8.

1. Goal.
For \(B,C\subseteq Y\), prove that inverse images preserve symmetric difference: \(f^{-1}(B\triangle C)=f^{-1}(B)\triangle f^{-1}(C)\).

2. Reasoning plan.
Checkpoint 1. Use \(B\triangle C=(B\setminus C)\cup(C\setminus B)\).
Checkpoint 2. Apply Theorem 1.1 to the union, then apply Exercise 1.7 to each difference.
Checkpoint 3. The final union is exactly the definition of \(f^{-1}(B)\triangle f^{-1}(C)\).

3. Learning check before the full solution.
Track the operation one layer at a time. First expand symmetric difference, then move the inverse image through the union, then through each set difference. Every equality should cite the property that justifies it.

4. Complete step-by-step solution.

Step 1 - expand the symmetric difference. By definition, \[B\triangle C=(B\setminus C)\cup(C\setminus B).\] Hence \[f^{-1}(B\triangle C)=f^{-1}((B\setminus C)\cup(C\setminus B)).\]

Step 2 - use preservation of unions. By Theorem 1.1, \[f^{-1}((B\setminus C)\cup(C\setminus B))=f^{-1}(B\setminus C)\cup f^{-1}(C\setminus B).\]

Step 3 - use preservation of set difference. Exercise 1.7 gives \[f^{-1}(B\setminus C)=f^{-1}(B)\setminus f^{-1}(C),\qquad f^{-1}(C\setminus B)=f^{-1}(C)\setminus f^{-1}(B).\] Therefore \[f^{-1}(B\triangle C)=(f^{-1}(B)\setminus f^{-1}(C))\cup(f^{-1}(C)\setminus f^{-1}(B)).\]

Step 4 - recognize the definition. The final expression is exactly \(f^{-1}(B)\triangle f^{-1}(C)\). Thus \[f^{-1}(B\triangle C)=f^{-1}(B)\triangle f^{-1}(C).\] \(\square\)

Expected evidence: a type-correct elementwise chain of equivalences and recognition that no injectivity or surjectivity is required.

LaTeX workspace

Live preview

Your proof will render here.

First \(C\subseteq Z\), then \(g^{-1}(C)\subseteq Y\), and finally \(f^{-1}(g^{-1}(C))\subseteq X\).

For \(x\in X\), \((g\circ f)(x)\in C\) means \(g(f(x))\in C\).

Translate \(g(f(x))\in C\) first into \(f(x)\in g^{-1}(C)\), then into \(x\in f^{-1}(g^{-1}(C))\).

Detailed correction: Exercise 1.9.

1. Goal.
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))\).

2. Reasoning plan.
Checkpoint 1. First \(C\subseteq Z\), then \(g^{-1}(C)\subseteq Y\), and finally \(f^{-1}(g^{-1}(C))\subseteq X\).
Checkpoint 2. For \(x\in X\), \((g\circ f)(x)\in C\) means \(g(f(x))\in C\).
Checkpoint 3. Translate \(g(f(x))\in C\) first into \(f(x)\in g^{-1}(C)\), then into \(x\in f^{-1}(g^{-1}(C))\).

3. Learning check before the full solution.
Do not skip the logical bridge between consecutive formulas. For set equalities, an elementwise equivalence or two inclusions is what turns symbolic manipulation into a proof.

4. Complete step-by-step solution.

Let \(x\in X\). Then \(x\in(g\circ f)^{-1}(C)\) if and only if \((g\circ f)(x)\in C\), if and only if \(g(f(x))\in C\), if and only if \(f(x)\in g^{-1}(C)\), if and only if \(x\in f^{-1}(g^{-1}(C))\). Thus the two subsets of \(X\) have the same elements. No injectivity or surjectivity assumption was used. \(\square\)

Expected evidence: nonemptiness, coverage, pairwise disjointness, and both directions of the injectivity characterization.

LaTeX workspace

Live preview

Your proof will render here.

For any \(x\in X\), take \(y=f(x)\). Then \(y\in f(X)\) and \(x\in F_y\).

If \(x\in F_y\cap F_z\), then \(f(x)=y\) and \(f(x)=z\), so \(y=z\).

Two distinct points lie in the same fiber exactly when they have the same image.

Detailed correction: Exercise 1.10.

1. Goal.
For \(y\in f(X)\), let \(F_y=f^{-1}(\{y\})\). Prove that the nonempty fibers \(\{F_y:y\in f(X)\}\) form a partition of \(X\), and that \(f\) is injective if and only if every fiber contains at most one point.

2. Reasoning plan.
Checkpoint 1. For any \(x\in X\), take \(y=f(x)\). Then \(y\in f(X)\) and \(x\in F_y\).
Checkpoint 2. If \(x\in F_y\cap F_z\), then \(f(x)=y\) and \(f(x)=z\), so \(y=z\).
Checkpoint 3. Two distinct points lie in the same fiber exactly when they have the same image.

3. Learning check before the full solution.
An if-and-only-if statement requires two complete implications. Proving only one direction establishes only a necessary or only a sufficient condition, not equivalence.

4. Complete step-by-step solution.

For each \(y\in f(X)\), some \(x\in X\) satisfies \(f(x)=y\), so \(F_y\neq\emptyset\). Every \(x\in X\) belongs to \(F_{f(x)}\), hence the fibers cover \(X\). If \(F_y\cap F_z\neq\emptyset\), choose \(x\) in the intersection. Then \(f(x)=y\) and \(f(x)=z\), so \(y=z\); the fibers are pairwise disjoint. Thus they form a partition. If \(f\) is injective, two elements of the same fiber have the same image and therefore are equal, so every fiber has at most one point. Conversely, if every fiber has at most one point and \(f(x_1)=f(x_2)=y\), then \(x_1,x_2\in F_y\), hence \(x_1=x_2\). Therefore \(f\) is injective. \(\square\)

Expected evidence: an elementwise proof with the existential witnesses in both directions made explicit.

LaTeX workspace

Live preview

Your proof will render here.

If \(y\in f(\bigcup_i A_i)\), there exists \(x\in\bigcup_i A_i\) such that \(f(x)=y\).

Membership \(x\in\bigcup_i A_i\) gives an index \(i\in I\) with \(x\in A_i\), so \(y\in f(A_i)\).

For the reverse inclusion, take \(y\in f(A_i)\) for some \(i\), choose \(x\in A_i\) with \(f(x)=y\), and note \(x\in\bigcup_i A_i\).

Detailed correction: Exercise 1.11.

1. Goal.
Let \((A_i)_{i\in I}\) be a family of subsets of \(X\). Prove that direct images preserve indexed unions: \(f(\bigcup_{i\in I}A_i)=\bigcup_{i\in I}f(A_i)\).

2. Reasoning plan.
Checkpoint 1. If \(y\in f(\bigcup_i A_i)\), there exists \(x\in\bigcup_i A_i\) such that \(f(x)=y\).
Checkpoint 2. Membership \(x\in\bigcup_i A_i\) gives an index \(i\in I\) with \(x\in A_i\), so \(y\in f(A_i)\).
Checkpoint 3. For the reverse inclusion, take \(y\in f(A_i)\) for some \(i\), choose \(x\in A_i\) with \(f(x)=y\), and note \(x\in\bigcup_i A_i\).

3. Learning check before the full solution.
Do not skip the logical bridge between consecutive formulas. For set equalities, an elementwise equivalence or two inclusions is what turns symbolic manipulation into a proof.

4. Complete step-by-step solution.

Let \(y\in f(\bigcup_{i\in I}A_i)\). There is \(x\in\bigcup_{i\in I}A_i\) with \(f(x)=y\). Hence \(x\in A_i\) for some \(i\in I\), so \(y\in f(A_i)\subseteq\bigcup_{i\in I}f(A_i)\). Conversely, if \(y\in\bigcup_{i\in I}f(A_i)\), then \(y\in f(A_i)\) for some \(i\). Thus there is \(x\in A_i\) with \(f(x)=y\). Since \(x\in\bigcup_{i\in I}A_i\), we have \(y\in f(\bigcup_{i\in I}A_i)\). Both inclusions hold. \(\square\)

Expected evidence: the always-valid inclusion, use of injectivity for the reverse inclusion, and a singleton counterargument for the converse.

LaTeX workspace

Live preview

Your proof will render here.

For every function, \(A\cap B\subseteq A,B\), so \(f(A\cap B)\subseteq f(A)\cap f(B)\).

If \(y\in f(A)\cap f(B)\), choose \(a\in A\) and \(b\in B\) with \(f(a)=y=f(b)\). Injectivity forces \(a=b\).

If \(f(x_1)=f(x_2)\) with \(x_1\neq x_2\), take \(A=\{x_1\}\) and \(B=\{x_2\}\). Their intersection is empty but their images intersect.

Detailed correction: Exercise 1.12.

1. Goal.
Prove that \(f\) is injective if and only if \(f(A\cap B)=f(A)\cap f(B)\) for every pair of subsets \(A,B\subseteq X\).

2. Reasoning plan.
Checkpoint 1. For every function, \(A\cap B\subseteq A,B\), so \(f(A\cap B)\subseteq f(A)\cap f(B)\).
Checkpoint 2. If \(y\in f(A)\cap f(B)\), choose \(a\in A\) and \(b\in B\) with \(f(a)=y=f(b)\). Injectivity forces \(a=b\).
Checkpoint 3. If \(f(x_1)=f(x_2)\) with \(x_1\neq x_2\), take \(A=\{x_1\}\) and \(B=\{x_2\}\). Their intersection is empty but their images intersect.

3. Learning check before the full solution.
An if-and-only-if statement requires two complete implications. Proving only one direction establishes only a necessary or only a sufficient condition, not equivalence.

4. Complete step-by-step solution.

Assume first that \(f\) is injective. The inclusion \(f(A\cap B)\subseteq f(A)\cap f(B)\) holds for every function. For the reverse inclusion, let \(y\in f(A)\cap f(B)\). Choose \(a\in A\) and \(b\in B\) with \(f(a)=y=f(b)\). Injectivity gives \(a=b\), so this common point lies in \(A\cap B\), and \(y\in f(A\cap B)\). Thus equality holds. Conversely, assume the equality holds for all \(A,B\subseteq X\). If \(f\) were not injective, there would be distinct \(x_1,x_2\) with \(f(x_1)=f(x_2)=y\). For \(A=\{x_1\}\) and \(B=\{x_2\}\), \(A\cap B=\emptyset\), so \(f(A\cap B)=\emptyset\), while \(y\in f(A)\cap f(B)\), a contradiction. Therefore \(f\) is injective. \(\square\)

Expected evidence: correctly ordered quantifiers, explicit witnesses, and correct attention to the stated codomain.

LaTeX workspace

Live preview

Your proof will render here.

Not injective means that two distinct points of \(X\) have the same image.

Negating \(\forall y\in Y\,\exists x\in X\) gives \(\exists y\in Y\,\forall x\in X\).

For \(x^2\), compare \(1\) and \(-1\), then choose a negative real number in the codomain.

Detailed correction: Exercise 1.13.

1. Goal.
Write the logical negations of injectivity and surjectivity using quantifiers. Then use them to prove that \(f:\mathbb{R}\to\mathbb{R}\), \(f(x)=x^2\), is neither injective nor surjective.

2. Reasoning plan.
Checkpoint 1. Not injective means that two distinct points of \(X\) have the same image.
Checkpoint 2. Negating \(\forall y\in Y\,\exists x\in X\) gives \(\exists y\in Y\,\forall x\in X\).
Checkpoint 3. For \(x^2\), compare \(1\) and \(-1\), then choose a negative real number in the codomain.

3. Learning check before the full solution.
Keep the domain and codomain visible throughout the argument. Injectivity starts from equality of two outputs; surjectivity starts from an arbitrary target value and constructs or identifies a preimage.

4. Complete step-by-step solution.

The negation of injectivity is \(\exists x_1,x_2\in X\) such that \(x_1\neq x_2\) and \(f(x_1)=f(x_2)\). The negation of surjectivity is \(\exists y\in Y\) such that \(\forall x\in X\), \(f(x)\neq y\). For \(f(x)=x^2\), the distinct points \(1\) and \(-1\) satisfy \(f(1)=1=f(-1)\), so \(f\) is not injective. Also, take \(y=-1\in\mathbb R\). For every \(x\in\mathbb R\), \(x^2\geq0\), hence \(f(x)\neq-1\). Thus \(f\) is not surjective onto \(\mathbb R\). \(\square\)

Expected evidence: two fully specified finite functions and sets, verification of each failed implication, and justification of the repairing hypotheses.

LaTeX workspace

Live preview

Your proof will render here.

For (a), use a function whose image omits a point \(y\). Sets that differ only at \(y\) can have the same inverse image.

For (b), use distinct \(a,b\in X\) with \(f(a)=f(b)\), and compare \(\{a\}\) with \(\{b\}\).

Surjectivity lets you lift every \(y\in B_1\) to \(x\in X\); injectivity lets you identify two domain witnesses with the same image.

Detailed correction: Exercise 1.14.

1. Goal.
Construct finite counterexamples to both false converses: (a) \(f^{-1}(B_1)\subseteq f^{-1}(B_2)\Rightarrow B_1\subseteq B_2\); (b) \(f(A_1)\subseteq f(A_2)\Rightarrow A_1\subseteq A_2\). Identify the additional hypothesis that repairs each implication.

2. Reasoning plan.
Checkpoint 1. For (a), use a function whose image omits a point \(y\). Sets that differ only at \(y\) can have the same inverse image.
Checkpoint 2. For (b), use distinct \(a,b\in X\) with \(f(a)=f(b)\), and compare \(\{a\}\) with \(\{b\}\).
Checkpoint 3. Surjectivity lets you lift every \(y\in B_1\) to \(x\in X\); injectivity lets you identify two domain witnesses with the same image.

3. Learning check before the full solution.
A proposed example is not enough by itself. Compute or verify every property requested, and explicitly show the feature that makes the example work.

4. Complete step-by-step solution.

For (a), let \(X=\{a\}\), \(Y=\{0,1\}\), and \(f(a)=0\). Take \(B_1=\{1\}\) and \(B_2=\emptyset\). Then \(f^{-1}(B_1)=\emptyset=f^{-1}(B_2)\), so the inverse-image inclusion holds, but \(B_1\not\subseteq B_2\). Surjectivity repairs the implication: if \(f\) is surjective and \(y\in B_1\), choose \(x\) with \(f(x)=y\); then \(x\in f^{-1}(B_1)\subseteq f^{-1}(B_2)\), so \(y\in B_2\). For (b), let \(X=\{a,b\}\), \(Y=\{0\}\), and \(f(a)=f(b)=0\). Take \(A_1=\{a\}\) and \(A_2=\{b\}\). Then \(f(A_1)=\{0\}=f(A_2)\), but \(A_1\not\subseteq A_2\). Injectivity repairs this implication: if \(x\in A_1\), then \(f(x)\in f(A_2)\), so \(f(x)=f(a_2)\) for some \(a_2\in A_2\); injectivity gives \(x=a_2\in A_2\). \(\square\)

Forward reference for Exercise 1.15Exercise 1.15 previews Chapter 3. For this exercise only, use the following criterion: a collection \(\mathcal T\subseteq\mathcal P(X)\) is a topology on \(X\) when (i) \(\emptyset,X\in\mathcal T\); (ii) the union of every family of members of \(\mathcal T\) belongs to \(\mathcal T\); and (iii) the intersection of every finite family of members of \(\mathcal T\) belongs to \(\mathcal T\). The formal development of topological spaces comes later in the course.

Expected evidence: verification of \(\emptyset,X\), arbitrary unions, and finite intersections, with exact citations to Exercise 1.5, Generalization 1.1, and Theorem 1.1.

LaTeX workspace

Live preview

Your proof will render here.

Because \(\emptyset,Y\in\mathcal T_Y\), Exercise 1.5 gives \(f^{-1}(\emptyset)=\emptyset\) and \(f^{-1}(Y)=X\).

If \(V_j=f^{-1}(U_j)\) with \(U_j\in\mathcal T_Y\), Generalization 1.1 gives \(\bigcup_jV_j=f^{-1}(\bigcup_jU_j)\).

For \(V_1=f^{-1}(U_1)\) and \(V_2=f^{-1}(U_2)\), Theorem 1.1 gives \(V_1\cap V_2=f^{-1}(U_1\cap U_2)\).

Detailed correction: Exercise 1.15.

1. Goal.
Let \((Y,\mathcal T_Y)\) be a topological space and \(f:X\to Y\) any function. Define \(\mathcal T_f=\{f^{-1}(U):U\in\mathcal T_Y\}\). Prove that \(\mathcal T_f\) is a topology on \(X\).

2. Reasoning plan.
Checkpoint 1. Because \(\emptyset,Y\in\mathcal T_Y\), Exercise 1.5 gives \(f^{-1}(\emptyset)=\emptyset\) and \(f^{-1}(Y)=X\).
Checkpoint 2. If \(V_j=f^{-1}(U_j)\) with \(U_j\in\mathcal T_Y\), Generalization 1.1 gives \(\bigcup_jV_j=f^{-1}(\bigcup_jU_j)\).
Checkpoint 3. For \(V_1=f^{-1}(U_1)\) and \(V_2=f^{-1}(U_2)\), Theorem 1.1 gives \(V_1\cap V_2=f^{-1}(U_1\cap U_2)\).

3. Learning check before the full solution.
To prove a collection is a topology, verify exactly the three topology axioms: \(\emptyset\) and \(X\), arbitrary unions, and finite intersections. Each closure argument should end by identifying an open set of \(Y\) whose inverse image is the set under consideration.

4. Complete step-by-step solution.

Let \(\mathcal T_f=\{f^{-1}(U):U\in\mathcal T_Y\}\). We verify the three topology axioms.

1. Empty set and whole space. Since \(\emptyset,Y\in\mathcal T_Y\), Exercise 1.5 gives \[f^{-1}(\emptyset)=\emptyset,\qquad f^{-1}(Y)=X.\] Hence \(\emptyset,X\in\mathcal T_f\).

2. Arbitrary unions. Let \((V_j)_{j\in J}\) be any family of sets in \(\mathcal T_f\). For each \(j\), choose \(U_j\in\mathcal T_Y\) with \(V_j=f^{-1}(U_j)\). Because \(\mathcal T_Y\) is a topology, \(U=\bigcup_{j\in J}U_j\in\mathcal T_Y\). Generalization 1.1 gives \[\bigcup_{j\in J}V_j=\bigcup_{j\in J}f^{-1}(U_j)=f^{-1}\!\left(\bigcup_{j\in J}U_j\right)=f^{-1}(U).\] Since \(U\in\mathcal T_Y\), the last set belongs to \(\mathcal T_f\).

3. Finite intersections. Let \(V_1,\ldots,V_n\in\mathcal T_f\), with \(V_k=f^{-1}(U_k)\) and \(U_k\in\mathcal T_Y\). Because \(\mathcal T_Y\) is closed under finite intersections, \(U=\bigcap_{k=1}^{n}U_k\in\mathcal T_Y\). Repeated application of Theorem 1.1, or the indexed intersection identity, gives \[\bigcap_{k=1}^{n}V_k=f^{-1}\!\left(\bigcap_{k=1}^{n}U_k\right)=f^{-1}(U)\in\mathcal T_f.\] For the empty finite intersection, the result is \(X\), already shown to lie in \(\mathcal T_f\).

All three topology axioms hold. Therefore \(\mathcal T_f\) is a topology on \(X\). \(\square\)

Further exercises

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

The two classes of subsets are disjoint and each has \(2^n\) elements, so \(|\mathcal P(A)|=2^n+2^n=2^{n+1}\).

Detailed correction: Exercise 1.16.

1. Goal.
Prove by induction that \(|\mathcal{P}(A)| = 2^n\) when \(|A| = n\).

2. Reasoning plan.
Checkpoint 1. 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\).
Checkpoint 2. 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\).
Checkpoint 3. The two classes of subsets are disjoint and each has \(2^n\) elements, so \(|\mathcal P(A)|=2^n+2^n=2^{n+1}\).

3. Learning check before the full solution.
For an induction proof, identify the induction variable, verify the base case, state the induction hypothesis precisely, prove the next case using that hypothesis, and then state the induction conclusion.

4. Complete step-by-step solution.

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

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.

For associativity, an element belongs to \(A\triangle B\) exactly when it belongs to exactly one of \(A,B\). Both \((A\triangle B)\triangle C\) and \(A\triangle(B\triangle C)\) contain precisely the elements belonging to an odd number of \(A,B,C\).

Detailed correction: Exercise 1.17.

1. Goal.
Show that \(A \triangle B = (A \cup B) \setminus (A \cap B)\) and that the symmetric difference \(\triangle\) is associative.

2. Reasoning plan.
Checkpoint 1. 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\).
Checkpoint 2. 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.
Checkpoint 3. For associativity, an element belongs to \(A\triangle B\) exactly when it belongs to exactly one of \(A,B\). Both \((A\triangle B)\triangle C\) and \(A\triangle(B\triangle C)\) contain precisely the elements belonging to an odd number of \(A,B,C\).

3. Learning check before the full solution.
For each set identity, reduce membership to a precise logical condition. For associativity, the invariant is parity: symmetric difference records whether an element belongs to an odd number of the sets involved.

4. Complete step-by-step solution.

First identity. Let \(x\) be arbitrary. Then \[x\in A\triangle B\iff (x\in A\text{ and }x\notin B)\text{ or }(x\in B\text{ and }x\notin A).\] This means exactly that \(x\) belongs to \(A\cup B\) but not to \(A\cap B\). Hence \[x\in A\triangle B\iff x\in (A\cup B)\setminus(A\cap B).\] Since this equivalence holds for every \(x\), \[A\triangle B=(A\cup B)\setminus(A\cap B).\]

Associativity. For the same arbitrary \(x\), let \(a,b,c\in\{0,1\}\) record membership of \(x\) in \(A,B,C\), respectively. Membership in a symmetric difference is addition modulo 2. Thus \[x\in(A\triangle B)\triangle C\iff (a+b)+c\equiv1\pmod2.\] Ordinary integer addition is associative, so \[(a+b)+c\equiv a+(b+c)\pmod2.\] Therefore \[x\in(A\triangle B)\triangle C\iff x\in A\triangle(B\triangle C).\] Because \(x\) was arbitrary, \[(A\triangle B)\triangle C=A\triangle(B\triangle C).\] \(\square\)

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

Because all complements are taken in the same \(U\), the quantifier negations translate directly into membership in \(A_\alpha^c\). This also handles infinite families.

Detailed correction: Exercise 1.18.

1. Goal.
Let \((A_\alpha)_{\alpha\in I}\) be a family of subsets of a fixed ambient set \(U\), and take every complement relative to \(U\). 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\).

2. Reasoning plan.
Checkpoint 1. \(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\).
Checkpoint 2. \(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\).
Checkpoint 3. Because all complements are taken in the same \(U\), the quantifier negations translate directly into membership in \(A_\alpha^c\). This also handles infinite families.

3. Learning check before the full solution.
Do not skip the logical bridge between consecutive formulas. For set equalities, an elementwise equivalence or two inclusions is what turns symbolic manipulation into a proof.

4. Complete step-by-step solution.

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

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

Show that \((a,x)\) belongs to either side exactly when \(a\in A\) and \((x\in B\text{ or }x\in C)\).

Detailed correction: Exercise 1.19.

1. Goal.
Show that \(A \times (B \cup C) = (A \times B) \cup (A \times C)\).

2. Reasoning plan.
Checkpoint 1. 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\).
Checkpoint 2. 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)\).
Checkpoint 3. Show that \((a,x)\) belongs to either side exactly when \(a\in A\) and \((x\in B\text{ or }x\in C)\).

3. Learning check before the full solution.
Do not skip the logical bridge between consecutive formulas. For set equalities, an elementwise equivalence or two inclusions is what turns symbolic manipulation into a proof.

4. Complete step-by-step solution.

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

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

Take \(C\in\mathcal P(A)\). Then \(C\subseteq A\subseteq B\), so \(C\in\mathcal P(B)\).

Detailed correction: Exercise 1.20.

1. Goal.
Prove that if \(A \subseteq B\) then \(\mathcal{P}(A) \subseteq \mathcal{P}(B)\).

2. Reasoning plan.
Checkpoint 1. 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\).
Checkpoint 2. You know \(S \subseteq A\) and \(A \subseteq B\), so by transitivity \(S \subseteq B\).
Checkpoint 3. Take \(C\in\mathcal P(A)\). Then \(C\subseteq A\subseteq B\), so \(C\in\mathcal P(B)\).

3. Learning check before the full solution.
Do not skip the logical bridge between consecutive formulas. For set equalities, an elementwise equivalence or two inclusions is what turns symbolic manipulation into a proof.

4. Complete step-by-step solution.

Assume \(A\subseteq B\). We prove \(\mathcal P(A)\subseteq\mathcal P(B)\).

Step 1 - unpack membership in a power set. Let \(S\in\mathcal P(A)\) be arbitrary. By definition of the power set, \[S\in\mathcal P(A)\iff S\subseteq A.\] Hence \(S\subseteq A\).

Step 2 - use transitivity of inclusion. We are given \(A\subseteq B\). Combining \(S\subseteq A\) with \(A\subseteq B\) gives \[S\subseteq B.\] Indeed, if \(x\in S\), then \(x\in A\), and therefore \(x\in B\).

Step 3 - repack the power-set definition. Since \(S\subseteq B\), we have \(S\in\mathcal P(B)\). Thus every member of \(\mathcal P(A)\) is a member of \(\mathcal P(B)\), and so \[\mathcal P(A)\subseteq\mathcal P(B).\] \(\square\)

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.

For any \(x\), membership in \((A\setminus B)\setminus C\) means \(x\in A\), \(x\notin B\), and \(x\notin C\), which is equivalent to \(x\in A\setminus(B\cup C)\).

Detailed correction: Exercise 1.21.

1. Goal.
Let \(A\), \(B\), \(C\) be sets. Prove \((A \setminus B) \setminus C = A \setminus (B \cup C)\).

2. Reasoning plan.
Checkpoint 1. \(x \in (A \setminus B) \setminus C\) means \(x \in A\), \(x \notin B\), and \(x \notin C\).
Checkpoint 2. \(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.
Checkpoint 3. For any \(x\), membership in \((A\setminus B)\setminus C\) means \(x\in A\), \(x\notin B\), and \(x\notin C\), which is equivalent to \(x\in A\setminus(B\cup C)\).

3. Learning check before the full solution.
Do not skip the logical bridge between consecutive formulas. For set equalities, an elementwise equivalence or two inclusions is what turns symbolic manipulation into a proof.

4. Complete step-by-step solution.

Let \(x\) be arbitrary. We translate membership one condition at a time.

First, \[x\in(A\setminus B)\setminus C\iff x\in A\setminus B\text{ and }x\notin C.\] Expanding the first difference gives \[\iff x\in A,\quad x\notin B,\quad x\notin C.\] The two negative conditions are equivalent to saying that \(x\) belongs to neither \(B\) nor \(C\), which is exactly \(x\notin B\cup C\). Therefore \[x\in(A\setminus B)\setminus C\iff x\in A\text{ and }x\notin B\cup C.\] By the definition of set difference, the last condition is \[x\in A\setminus(B\cup C).\] Thus, for every \(x\), membership in the two sets is equivalent. Hence \[(A\setminus B)\setminus C=A\setminus(B\cup C).\] \(\square\)

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

Inside the fixed set \(A\), membership in \(B\triangle C\) means exactly one of \(B,C\). That is the same as belonging to exactly one of \(A\cap B\) and \(A\cap C\).

Detailed correction: Exercise 1.22.

1. Goal.
Show that \(A \cap (B \triangle C) = (A \cap B) \triangle (A \cap C)\).

2. Reasoning plan.
Checkpoint 1. \(x \in A \cap (B \triangle C)\) iff \(x \in A\) and (\(x \in B\) xor \(x \in C\)).
Checkpoint 2. 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)\).
Checkpoint 3. Inside the fixed set \(A\), membership in \(B\triangle C\) means exactly one of \(B,C\). That is the same as belonging to exactly one of \(A\cap B\) and \(A\cap C\).

3. Learning check before the full solution.
Use direct elementwise reasoning here. The common condition \(x\in A\) is what lets the exclusive choice between \(B\) and \(C\) become an exclusive choice between \(A\cap B\) and \(A\cap C\).

4. Complete step-by-step solution.

Let \(x\) be arbitrary. We compare membership in the two sides. \[\begin{aligned}x\in A\cap(B\triangle C) &\iff x\in A\text{ and }x\in B\triangle C\\ &\iff x\in A\text{ and exactly one of }x\in B,\ x\in C\text{ holds}.\end{aligned}\] Because \(x\in A\) is already required, the last condition is equivalent to saying that exactly one of the statements \(x\in A\cap B\) and \(x\in A\cap C\) holds. Hence \[x\in A\cap(B\triangle C)\iff x\in(A\cap B)\triangle(A\cap C).\] This equivalence holds for every \(x\), so \[A\cap(B\triangle C)=(A\cap B)\triangle(A\cap C).\] \(\square\)

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

For bijectivity, prove injectivity and surjectivity separately using the first two parts; no new argument is needed.

Detailed correction: Exercise 1.23.

1. Goal.
Prove that composition of injective functions is injective, composition of surjective functions is surjective, and composition of bijective functions is bijective.

2. Reasoning plan.
Checkpoint 1. 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\).
Checkpoint 2. 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\).
Checkpoint 3. For bijectivity, prove injectivity and surjectivity separately using the first two parts; no new argument is needed.

3. Learning check before the full solution.
Treat injectivity and surjectivity as two different quantifier patterns. For injectivity, propagate an equality backward through \(g\) and then \(f\). For surjectivity, start with an arbitrary target \(z\) and construct a preimage in two stages.

4. Complete step-by-step solution.

Let \(f:X\to Y\) and \(g:Y\to Z\).

Injective case. Assume both \(f\) and \(g\) are injective. Take \(x_1,x_2\in X\) and suppose \((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)\), and injectivity of \(f\) then gives \(x_1=x_2\). Therefore \(g\circ f\) is injective.

Surjective case. Assume both \(f\) and \(g\) are surjective. Let \(z\in Z\) be arbitrary. Since \(g\) is surjective, choose \(y\in Y\) with \(g(y)=z\). Since \(f\) is surjective, choose \(x\in X\) with \(f(x)=y\). Then \[(g\circ f)(x)=g(f(x))=g(y)=z.\] Thus every \(z\in Z\) has a preimage, so \(g\circ f\) is surjective.

Bijective case. If \(f\) and \(g\) are bijective, each is both injective and surjective. The two arguments above show that \(g\circ f\) is both injective and surjective, hence bijective. \(\square\)

Expected evidence: both equivalences, an explicit left-inverse construction, and a clear indication of where choice is used for a right inverse.

If \(f\) is injective, choose \(x_0\in X\). Define \(g:Y\to X\) by \(g(f(x))=x\) on \(f(X)\), and \(g(y)=x_0\) for \(y\notin f(X)\). Injectivity makes the first rule well-defined.

If \(f\) is surjective, every fiber \(f^{-1}(\{y\})\) is nonempty. Using the axiom of choice, select one element \(h(y)\) from each fiber. Then \(f(h(y))=y\).

A left inverse immediately cancels \(f\) from \(f(x_1)=f(x_2)\). A right inverse immediately writes every \(y\in Y\) as \(f(h(y))\). These directions do not use choice.

Detailed correction: Exercise 1.24.

1. Goal.
Let \(f:X\to Y\) and assume \(X\neq\emptyset\). Prove that \(f\) is injective if and only if it has a left inverse. Assuming the axiom of choice for arbitrary fibers, prove that \(f\) is surjective if and only if it has a right inverse.

2. Reasoning plan.
Checkpoint 1. If \(f\) is injective, choose \(x_0\in X\). Define \(g:Y\to X\) by \(g(f(x))=x\) on \(f(X)\), and \(g(y)=x_0\) for \(y\notin f(X)\). Injectivity makes the first rule well-defined.
Checkpoint 2. If \(f\) is surjective, every fiber \(f^{-1}(\{y\})\) is nonempty. Using the axiom of choice, select one element \(h(y)\) from each fiber. Then \(f(h(y))=y\).
Checkpoint 3. A left inverse immediately cancels \(f\) from \(f(x_1)=f(x_2)\). A right inverse immediately writes every \(y\in Y\) as \(f(h(y))\). These directions do not use choice.

3. Learning check before the full solution.
An if-and-only-if statement requires two complete implications. Proving only one direction establishes only a necessary or only a sufficient condition, not equivalence.

4. Complete step-by-step solution.

Injective iff left inverse. Suppose \(g:Y\to X\) satisfies \(g\circ f=\mathrm{id}_X\). If \(f(x_1)=f(x_2)\), applying \(g\) gives \(x_1=x_2\), so \(f\) is injective. Conversely, assume \(f\) is injective. Because \(X\neq\emptyset\), choose \(x_0\in X\). Define \(g:Y\to X\) by \(g(f(x))=x\) for \(f(x)\in f(X)\), and \(g(y)=x_0\) for \(y\notin f(X)\). Injectivity makes \(g\) well-defined on \(f(X)\), and \(g(f(x))=x\) for every \(x\in X\). Thus \(g\circ f=\mathrm{id}_X\).

Surjective iff right inverse. If \(h:Y\to X\) satisfies \(f\circ h=\mathrm{id}_Y\), then every \(y\in Y\) equals \(f(h(y))\), so \(f\) is surjective. Conversely, assume \(f\) is surjective. Every fiber \(f^{-1}(\{y\})\) is nonempty. By the axiom of choice, choose \(h(y)\in f^{-1}(\{y\})\) for each \(y\in Y\). Then \(f(h(y))=y\), so \(f\circ h=\mathrm{id}_Y\). \(\square\)

Expected evidence: the general inclusion, the injective equality proof, and one strict counterexample.

If \(y\in f(\bigcap_i A_i)\), write \(y=f(x)\) with \(x\in A_i\) for every \(i\). Then \(y\in f(A_i)\) for every \(i\).

Assume \(f\) injective and \(y\in\bigcap_i f(A_i)\). Since \(I\neq\emptyset\), choose \(i_0\in I\) and \(x_0\in A_{i_0}\) with \(f(x_0)=y\). For any \(i\), a witness \(x_i\in A_i\) with \(f(x_i)=y\) must equal \(x_0\).

Use two distinct points \(a,b\) with \(f(a)=f(b)\), and take the two-set family \(A_1=\{a\}\), \(A_2=\{b\}\).

Detailed correction: Exercise 1.25.

1. Goal.
Let \(I\neq\emptyset\) and let \((A_i)_{i\in I}\) be a family of subsets of \(X\). Prove that \(f\bigl(\bigcap_{i\in I}A_i\bigr)\subseteq\bigcap_{i\in I}f(A_i)\). Show that equality holds whenever \(f\) is injective, and give a non-injective example where the inclusion is strict.

2. Reasoning plan.
Checkpoint 1. If \(y\in f(\bigcap_i A_i)\), write \(y=f(x)\) with \(x\in A_i\) for every \(i\). Then \(y\in f(A_i)\) for every \(i\).
Checkpoint 2. Assume \(f\) injective and \(y\in\bigcap_i f(A_i)\). Since \(I\neq\emptyset\), choose \(i_0\in I\) and \(x_0\in A_{i_0}\) with \(f(x_0)=y\). For any \(i\), a witness \(x_i\in A_i\) with \(f(x_i)=y\) must equal \(x_0\).
Checkpoint 3. Use two distinct points \(a,b\) with \(f(a)=f(b)\), and take the two-set family \(A_1=\{a\}\), \(A_2=\{b\}\).

3. Learning check before the full solution.
Keep the domain and codomain visible throughout the argument. Injectivity starts from equality of two outputs; surjectivity starts from an arbitrary target value and constructs or identifies a preimage.

4. Complete step-by-step solution.

Let \(y\in f(\bigcap_{i\in I}A_i)\). Then \(y=f(x)\) for some \(x\in\bigcap_{i\in I}A_i\). Hence \(x\in A_i\) for every \(i\), so \(y\in f(A_i)\) for every \(i\). Therefore \(y\in\bigcap_{i\in I}f(A_i)\), proving the inclusion.

Now suppose \(f\) is injective and let \(y\in\bigcap_{i\in I}f(A_i)\). Since \(I\neq\emptyset\), choose \(i_0\in I\) and \(x_0\in A_{i_0}\) with \(f(x_0)=y\). For any \(i\in I\), because \(y\in f(A_i)\), there exists \(x_i\in A_i\) with \(f(x_i)=y=f(x_0)\). Injectivity gives \(x_i=x_0\). Thus \(x_0\in A_i\) for every \(i\), so \(x_0\in\bigcap_iA_i\) and \(y\in f(\bigcap_iA_i)\). Equality follows.

For strictness, let \(f:\{-1,1\}\to\{1\}\) be given by \(f(-1)=f(1)=1\), with \(A_1=\{-1\}\) and \(A_2=\{1\}\). Then \(A_1\cap A_2=\emptyset\), so \(f(A_1\cap A_2)=\emptyset\), while \(f(A_1)\cap f(A_2)=\{1\}\). \(\square\)

Expected evidence: the universal inclusion, the injective equality proof, and a collision-based converse.

Take \(y\in f(A)\setminus f(B)\). Write \(y=f(a)\) with \(a\in A\). Why must \(a\notin B\)?

If \(f\) is injective and \(y=f(a)\) with \(a\in A\setminus B\), show that \(y\notin f(B)\); otherwise \(f(a)=f(b)\) for some \(b\in B\).

If \(f(a)=f(b)\) for distinct \(a,b\), take \(A=\{a\}\) and \(B=\{b\}\). Compare the two sides.

Detailed correction: Exercise 1.26.

1. Goal.
Let \(A,B\subseteq X\). Prove that \(f(A)\setminus f(B)\subseteq f(A\setminus B)\). Show that equality holds for all \(A,B\subseteq X\) if and only if \(f\) is injective.

2. Reasoning plan.
Checkpoint 1. Take \(y\in f(A)\setminus f(B)\). Write \(y=f(a)\) with \(a\in A\). Why must \(a\notin B\)?
Checkpoint 2. If \(f\) is injective and \(y=f(a)\) with \(a\in A\setminus B\), show that \(y\notin f(B)\); otherwise \(f(a)=f(b)\) for some \(b\in B\).
Checkpoint 3. If \(f(a)=f(b)\) for distinct \(a,b\), take \(A=\{a\}\) and \(B=\{b\}\). Compare the two sides.

3. Learning check before the full solution.
An if-and-only-if statement requires two complete implications. Proving only one direction establishes only a necessary or only a sufficient condition, not equivalence.

4. Complete step-by-step solution.

Let \(y\in f(A)\setminus f(B)\). Then \(y=f(a)\) for some \(a\in A\). If \(a\in B\), then \(y=f(a)\in f(B)\), a contradiction. Hence \(a\in A\setminus B\), so \(y\in f(A\setminus B)\). Thus \(f(A)\setminus f(B)\subseteq f(A\setminus B)\).

Assume \(f\) is injective. If \(y\in f(A\setminus B)\), write \(y=f(a)\) with \(a\in A\setminus B\). Then \(y\in f(A)\). If \(y\in f(B)\), there is \(b\in B\) with \(f(b)=f(a)\), and injectivity gives \(b=a\), contradicting \(a\notin B\). Therefore \(y\in f(A)\setminus f(B)\), proving equality.

Conversely, suppose equality holds for every \(A,B\subseteq X\). If \(f\) were not injective, choose \(a\neq b\) with \(f(a)=f(b)\), and set \(A=\{a\}\), \(B=\{b\}\). Then \(f(A)\setminus f(B)=\emptyset\), but \(A\setminus B=\{a\}\), so \(f(A\setminus B)=\{f(a)\}\neq\emptyset\), a contradiction. Hence \(f\) is injective. \(\square\)

Expected evidence: the exact identity, followed by the correctly quantified surjectivity criterion.

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

After proving \(f(f^{-1}(B))=B\cap f(X)\), the criterion is immediate: equality with \(B\) for every \(B\) is equivalent to \(f(X)=Y\).

Detailed correction: Exercise 1.27.

1. Goal.
Let \(f:X\to Y\) and \(B\subseteq Y\). Prove the exact identity \(f(f^{-1}(B))=B\cap f(X)\). Deduce that \(f(f^{-1}(B))=B\) for every \(B\subseteq Y\) if and only if \(f\) is surjective.

2. Reasoning plan.
Checkpoint 1. 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\).
Checkpoint 2. 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\).
Checkpoint 3. After proving \(f(f^{-1}(B))=B\cap f(X)\), the criterion is immediate: equality with \(B\) for every \(B\) is equivalent to \(f(X)=Y\).

3. Learning check before the full solution.
An if-and-only-if statement requires two complete implications. Proving only one direction establishes only a necessary or only a sufficient condition, not equivalence.

4. Complete step-by-step solution.

Let \(y\in Y\). Then \(y\in f(f^{-1}(B))\) iff there exists \(x\in X\) such that \(f(x)=y\) and \(x\in f^{-1}(B)\). The second condition means \(f(x)\in B\), so this is equivalent to \(y\in f(X)\) and \(y\in B\). Hence \(f(f^{-1}(B))=B\cap f(X)\).

If \(f\) is surjective, then \(f(X)=Y\), so for every \(B\subseteq Y\), \(B\cap f(X)=B\), giving \(f(f^{-1}(B))=B\). Conversely, if \(f(f^{-1}(B))=B\) for every \(B\subseteq Y\), take \(B=Y\). Then \(f(X)=f(f^{-1}(Y))=Y\), so \(f\) is surjective. \(\square\)

Expected evidence: the universal inclusion, the injective reverse inclusion, and a singleton test for the converse.

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

If equality holds for every \(A\), take \(A=\{x_1\}\). Whenever \(f(x_1)=f(x_2)\), the point \(x_2\) lies in \(f^{-1}(f(A))=A\).

Detailed correction: Exercise 1.28.

1. Goal.
Let \(f:X\to Y\) and \(A\subseteq X\). Prove \(A\subseteq f^{-1}(f(A))\). Deduce that \(f^{-1}(f(A))=A\) for every \(A\subseteq X\) if and only if \(f\) is injective.

2. Reasoning plan.
Checkpoint 1. If \(a \in A\) then \(f(a) \in f(A)\), so \(a \in f^{-1}(f(A))\) by definition.
Checkpoint 2. 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\).
Checkpoint 3. If equality holds for every \(A\), take \(A=\{x_1\}\). Whenever \(f(x_1)=f(x_2)\), the point \(x_2\) lies in \(f^{-1}(f(A))=A\).

3. Learning check before the full solution.
An if-and-only-if statement requires two complete implications. Proving only one direction establishes only a necessary or only a sufficient condition, not equivalence.

4. Complete step-by-step solution.

If \(a\in A\), then \(f(a)\in f(A)\), so \(a\in f^{-1}(f(A))\). Thus \(A\subseteq f^{-1}(f(A))\).

Assume \(f\) is injective and let \(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\), proving \(f^{-1}(f(A))\subseteq A\), hence equality for every \(A\).

Conversely, suppose \(f^{-1}(f(A))=A\) for every \(A\subseteq X\). If \(f(x_1)=f(x_2)\), take \(A=\{x_1\}\). Then \(x_2\in f^{-1}(f(A))=A\), so \(x_2=x_1\). Therefore \(f\) is injective. \(\square\)

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.

The identity map \(\mathrm{id}_X\) is the neutral element, and every bijection \(f:X\to X\) has a bijective inverse \(f^{-1}\) with \(f^{-1}\circ f=f\circ f^{-1}=\mathrm{id}_X\).

Detailed correction: Exercise 1.29.

1. Goal.
Show that the set \(\mathrm{Bij}(X)\) of all bijections from \(X\) to \(X\) forms a group under function composition.

2. Reasoning plan.
Checkpoint 1. By Exercise 1.23, composition of bijections is a bijection. This gives closure.
Checkpoint 2. 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.
Checkpoint 3. The identity map \(\mathrm{id}_X\) is the neutral element, and every bijection \(f:X\to X\) has a bijective inverse \(f^{-1}\) with \(f^{-1}\circ f=f\circ f^{-1}=\mathrm{id}_X\).

3. Learning check before the full solution.
A group proof is an axiom-by-axiom verification. Check closure, associativity, an identity element, and an inverse for every element; also state why the inverse remains inside \(\mathrm{Bij}(X)\).

4. Complete step-by-step solution.

We verify the four group axioms for \((\mathrm{Bij}(X),\circ)\).

1. Closure. Let \(f,g\in\mathrm{Bij}(X)\). By Exercise 1.23, the composition \(g\circ f:X\to X\) is bijective. Hence \(g\circ f\in\mathrm{Bij}(X)\).

2. Associativity. For \(f,g,h\in\mathrm{Bij}(X)\) and every \(x\in X\), \[((h\circ g)\circ f)(x)=h(g(f(x)))=(h\circ(g\circ f))(x).\] Since the two functions agree at every \(x\), \((h\circ g)\circ f=h\circ(g\circ f)\).

3. Identity. The identity map \(\mathrm{id}_X:X\to X\), \(\mathrm{id}_X(x)=x\), is bijective. For every \(f\in\mathrm{Bij}(X)\), \[f\circ\mathrm{id}_X=f=\mathrm{id}_X\circ f.\]

4. Inverses. If \(f\in\mathrm{Bij}(X)\), bijectivity gives a well-defined inverse function \(f^{-1}:X\to X\). The inverse is itself bijective, and \[f^{-1}\circ f=\mathrm{id}_X,\qquad f\circ f^{-1}=\mathrm{id}_X.\] Thus every group axiom holds, so \((\mathrm{Bij}(X),\circ)\) is a group. \(\square\)

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

A standard proof partitions \(A\) into the points that can be matched forward through the alternating chains generated by \(f\) and \(g\), and matches the remaining points backward using \(g^{-1}\). State this construction clearly even if you omit technical details.

Detailed correction: Exercise 1.30.

1. Goal.
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.

2. Reasoning plan.
Checkpoint 1. 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\).
Checkpoint 2. 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)\)).
Checkpoint 3. A standard proof partitions \(A\) into the points that can be matched forward through the alternating chains generated by \(f\) and \(g\), and matches the remaining points backward using \(g^{-1}\). State this construction clearly even if you omit technical details.

3. Learning check before the full solution.
This is a construction proof, not a contradiction proof. After defining \(h\), verify separately that the second branch is well-defined, that \(h\) is injective, and that \(h\) is surjective. The cross-case is the step most often omitted.

4. Complete step-by-step solution.

Theorem. If there are injections \(f:A\to B\) and \(g:B\to A\), then there is a bijection \(h:A\to B\).

Step 1 - build the forward region. Put \[A_0=A\setminus g(B),\qquad A_{n+1}=g(f(A_n)),\qquad C=\bigcup_{n\ge0}A_n.\] Because \(f\) and \(g\) are injective, the restriction of \(g\) to \(B\) has a well-defined inverse \(g^{-1}:g(B)\to B\).

Step 2 - define the candidate bijection. Set \[h(a)=\begin{cases}f(a),&a\in C,\\g^{-1}(a),&a\notin C.\end{cases}\] If \(a\notin C\), then in particular \(a\notin A_0=A\setminus g(B)\), so \(a\in g(B)\). Thus the second branch is well-defined.

Step 3 - prove injectivity. Suppose \(h(a_1)=h(a_2)\). If both points lie in \(C\), injectivity of \(f\) gives \(a_1=a_2\). If both lie outside \(C\), injectivity of \(g^{-1}\) gives \(a_1=a_2\). A cross-case is impossible. Indeed, if \(a_1\in C\), \(a_2\notin C\), and \(f(a_1)=g^{-1}(a_2)\), then \(a_2=g(f(a_1))\). Since \(a_1\in A_n\) for some \(n\), this gives \(a_2\in A_{n+1}\subseteq C\), contradicting \(a_2\notin C\). Hence \(h\) is injective.

Step 4 - prove surjectivity. Let \(b\in B\). If \(g(b)\notin C\), then \(h(g(b))=g^{-1}(g(b))=b\). If \(g(b)\in C\), then \(g(b)\notin A_0\), so \(g(b)\in A_{n+1}=g(f(A_n))\) for some \(n\). Thus \(g(b)=g(f(a))\) for some \(a\in A_n\subseteq C\). Injectivity of \(g\) gives \(b=f(a)=h(a)\). In either case \(b\) is hit by \(h\). Therefore \(h\) is surjective.

The map \(h\) is both injective and surjective, so it is a bijection. Hence \(|A|=|B|\). \(\square\)

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

Write \(\sqrt2=p/q\) in lowest terms. From \(p^2=2q^2\), deduce \(p\) is even; substituting \(p=2r\) then forces \(q\) even, contradicting coprimality.

Detailed correction: Exercise 1.31.

1. Goal.
Prove by contradiction: there is no rational number whose square is 2.

2. Reasoning plan.
Checkpoint 1. Assume \(\sqrt{2} = p/q\) with \(p, q \in \mathbb{Z}\), \(q \neq 0\), and \(\gcd(p,q) = 1\). Then \(p^2 = 2q^2\).
Checkpoint 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\).
Checkpoint 3. Write \(\sqrt2=p/q\) in lowest terms. From \(p^2=2q^2\), deduce \(p\) is even; substituting \(p=2r\) then forces \(q\) even, contradicting coprimality.

3. Learning check before the full solution.
The crucial number-theoretic fact is: if an integer has even square, then the integer itself is even. Make that implication explicit; one short proof is that an odd integer \(2k+1\) has odd square.

4. Complete step-by-step solution.

Step 1 - assume the negation. Suppose, for contradiction, that there is a rational number whose square is 2. Then we may write \(r=p/q\) with \(p,q\in\mathbb Z\), \(q\ne0\), \(\gcd(p,q)=1\), and \(r^2=2\). Hence \[p^2=2q^2.\]

Step 2 - justify the parity implication. If an integer \(m\) were odd, \(m=2k+1\), then \[m^2=4k^2+4k+1=2(2k^2+2k)+1,\] which is odd. Therefore, by contrapositive, an integer whose square is even must be even.

Step 3 - force both numerator and denominator to be even. Since \(p^2=2q^2\), the number \(p^2\) is even, so \(p\) is even. Write \(p=2k\). Substitution gives \[4k^2=2q^2,\qquad q^2=2k^2.\] Thus \(q^2\) is even, so the same parity fact implies that \(q\) is even.

Step 4 - identify the contradiction. Both \(p\) and \(q\) are divisible by 2, contradicting \(\gcd(p,q)=1\). Hence no rational number has square 2; equivalently, \(\sqrt2\notin\mathbb Q\). \(\square\)

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.

Once the contrapositive has been proved for every integer \(n\), use the logical equivalence \(P\Rightarrow Q\iff \neg Q\Rightarrow\neg P\): proving “\(n\) odd \(\Rightarrow n^2\) odd” proves “\(n^2\) even \(\Rightarrow n\) even.”

Detailed correction: Exercise 1.32.

1. Goal.
Prove by contrapositive: if \(n^2\) is even then \(n\) is even.

2. Reasoning plan.
Checkpoint 1. The contrapositive is: if \(n\) is odd then \(n^2\) is odd.
Checkpoint 2. If \(n = 2k+1\), then \(n^2 = 4k^2 + 4k + 1 = 2(2k^2+2k)+1\), which is odd.
Checkpoint 3. The contrapositive is: if \(n\) is odd, then \(n^2\) is odd. Write \(n=2k+1\) and expand.

3. Learning check before the full solution.
Check that every conclusion follows from a stated definition, hypothesis, or previously established result. A complete correction should make the dependency of each step visible.

4. Complete step-by-step solution.

We prove the statement by proving its contrapositive. Let \(P\) be “\(n^2\) is even” and \(Q\) be “\(n\) is even.” The contrapositive of \(P\Rightarrow Q\) is \(\neg Q\Rightarrow\neg P\): if \(n\) is odd, then \(n^2\) is odd.

Assume \(n\) is odd. By definition, there exists \(k\in\mathbb Z\) such that \[n=2k+1.\] Squaring gives \[n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1.\] Since \(2k^2+2k\in\mathbb Z\), the last expression has the form \(2m+1\) for an integer \(m\). Therefore \(n^2\) is odd.

We have proved “\(n\) odd \(\Rightarrow n^2\) odd,” the contrapositive of the original statement. A statement and its contrapositive are logically equivalent. Hence, if \(n^2\) is even, then \(n\) is even. \(\square\)

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

In the composite case \(n=ab\), justify \(2\le a,b<n\), apply the strong-induction hypothesis to both factors, substitute their prime factorizations into \(n=ab\), and then state the induction conclusion.

Detailed correction: Exercise 1.33.

1. Goal.
Prove by strong induction: every integer \(n \geq 2\) has a prime factorisation.

2. Reasoning plan.
Checkpoint 1. Assume every integer \(k\) with \(2 \leq k < n\) has a prime factorisation. Consider \(n\): either \(n\) is prime, or \(n\) is composite.
Checkpoint 2. If \(n\) is composite, write \(n = ab\) with \(2 \leq a, b < n\). Apply the inductive hypothesis to both \(a\) and \(b\).
Checkpoint 3. For the strong-induction step, if \(n\) is prime you are done. If \(n=ab\) with \(2\le a,b<n\), apply the induction hypothesis to both \(a\) and \(b\) and concatenate their prime factorizations.

3. Learning check before the full solution.
For an induction proof, identify the induction variable, verify the base case, state the induction hypothesis precisely, prove the next case using that hypothesis, and then state the induction conclusion.

4. Complete step-by-step solution.

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

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

From the induction hypothesis \(1+3+\cdots+(2n-1)=n^2\), add \(2(n+1)-1=2n+1\) and simplify \(n^2+2n+1\).

Detailed correction: Exercise 1.34.

1. Goal.
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\).

2. Reasoning plan.
Checkpoint 1. For \(n=1\): the sum is \(2(1)-1 = 1 = 1^2\). Check.
Checkpoint 2. 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\).
Checkpoint 3. From the induction hypothesis \(1+3+\cdots+(2n-1)=n^2\), add \(2(n+1)-1=2n+1\) and simplify \(n^2+2n+1\).

3. Learning check before the full solution.
In an induction proof, identify exactly where the induction hypothesis is used. Here it replaces the first \(n\) odd-number sum by \(n^2\); the only new term is \(2(n+1)-1=2n+1\).

4. Complete step-by-step solution.

We prove \(P(n):\sum_{k=1}^{n}(2k-1)=n^2\) for every \(n\ge1\).

Base case. For \(n=1\), \[\sum_{k=1}^{1}(2k-1)=1=1^2,\] so \(P(1)\) is true.

Induction hypothesis. Fix \(n\ge1\) and assume \[\sum_{k=1}^{n}(2k-1)=n^2.\]

Induction step. The sum for \(n+1\) contains the first \(n\) terms plus one new odd number: \[\begin{aligned}\sum_{k=1}^{n+1}(2k-1)&=\sum_{k=1}^{n}(2k-1)+(2(n+1)-1)\\&=n^2+(2n+1)\\&=n^2+2n+1\\&=(n+1)^2.\end{aligned}\] The second line is exactly where the induction hypothesis is used. Thus \(P(n)\Rightarrow P(n+1)\).

By mathematical induction, \(\sum_{k=1}^{n}(2k-1)=n^2\) for every \(n\ge1\). \(\square\)

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.

Because \(0\in\mathbb N\), the right additional seed is \(0\in S\). Then repeated addition of 2 gives \(0,2,4,\ldots\), while the original seed \(1\) gives \(1,3,5,\ldots\).

The seed \(1\) generates every positive odd natural; the added seed \(0\) generates every even natural. Their union is exactly \(\mathbb N\).

Detailed correction: Exercise 1.35.

1. Goal.
Recall that \(\mathbb N=\{0,1,2,\ldots\}\) in this course. 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 seed condition is sufficient to force \(S=\mathbb N\)?

2. Reasoning plan.
Checkpoint 1. 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.
Checkpoint 2. Because \(0\in\mathbb N\), the right additional seed is \(0\in S\). Then repeated addition of 2 gives \(0,2,4,\ldots\), while the original seed \(1\) gives \(1,3,5,\ldots\).
Checkpoint 3. The seed \(1\) generates every positive odd natural; the added seed \(0\) generates every even natural. Their union is exactly \(\mathbb N\).

3. Learning check before the full solution.
The step size is 2, so the closure rule preserves parity. One seed controls only one parity class. To obtain all of \(\mathbb N\), a seed of the opposite parity is needed; \(0\in S\) is the natural sufficient condition under this course's convention.

4. Complete step-by-step solution.

What the original hypotheses force. Since \(1\in S\) and \(n\in S\Rightarrow n+2\in S\), repeated application gives \[1,3,5,7,\ldots\in S.\] Formally, induction on \(k\) proves \(2k+1\in S\) for every \(k\ge0\). Thus every positive odd natural belongs to \(S\).

What they do not force. Adding 2 never changes parity, so the seed 1 can never generate an even number. For example, the set of all positive odd natural numbers satisfies the two stated hypotheses but is not \(\mathbb N\). Therefore the original assumptions alone do not imply \(S=\mathbb N\).

A sufficient additional seed. Add \(0\in S\). The same induction now gives \(2k\in S\) for every \(k\ge0\). The original seed gives every \(2k+1\), while the new seed gives every \(2k\). Every natural number is either even or odd, so every element of \(\mathbb N\) lies in \(S\). Since \(S\subseteq\mathbb N\), we conclude \(S=\mathbb N\). \(\square\)

Expected evidence: the argument using the minimal positive integer denominator.

Suppose \(\sqrt{2}=p/q\) with \(p,q\in\mathbb N_{\gt 0}\). Consider the set \[S=\{q\in\mathbb N_{\gt 0}:q\sqrt{2}\in\mathbb N_{\gt 0}\}.\] Choose its least element \(q_0\).

From \(\sqrt{2}=p/q\), set \(q_1=p-q\). Then \[\begin{aligned} q_1\sqrt{2} &= 2q-p,\\[2pt] 0 &\lt q_1\lt q. \end{aligned}\] Thus \(q_1\) is a strictly smaller positive element of the same set.

With \(p_0=q_0\sqrt{2}\), set \(q_1=p_0-q_0\). Verify the two facts \[0\lt q_1\lt q_0,\] and \[q_1\sqrt{2}=2q_0-p_0\in\mathbb N_{\gt 0}.\]

Detailed correction: Exercise 1.36.

1. Goal.
Use the well-ordering principle to prove that \(\sqrt{2}\) is irrational, without the parity argument of Exercise 1.31.

2. Reasoning plan.
Checkpoint 1. Suppose \(\sqrt{2}=p/q\) with \(p,q\in\mathbb N_{\gt 0}\). Consider the set \[S=\{q\in\mathbb N_{\gt 0}:q\sqrt{2}\in\mathbb N_{\gt 0}\}.\] Choose its least element \(q_0\).
Checkpoint 2. From \(\sqrt{2}=p/q\), set \(q_1=p-q\). Then \[\begin{aligned} q_1\sqrt{2} &= 2q-p,\\[2pt] 0 &\lt q_1\lt q. \end{aligned}\] Thus \(q_1\) is a strictly smaller positive element of the same set.
Checkpoint 3. With \(p_0=q_0\sqrt{2}\), set \(q_1=p_0-q_0\). Verify the two facts \[0\lt q_1\lt q_0,\] and \[q_1\sqrt{2}=2q_0-p_0\in\mathbb N_{\gt 0}.\]

3. Learning check before the full solution.
In a contradiction argument, state the assumption being negated and identify the exact contradiction obtained. This makes clear which hypothesis has failed.

4. Complete step-by-step solution.

Suppose for contradiction that \(\sqrt2\in\mathbb Q\). Because \(\sqrt2>0\), write \(\sqrt2=p/q\) with positive integers \(p,q\). Define \[S=\{q\in\mathbb N_{>0}:q\sqrt2\in\mathbb N_{>0}\}.\] The chosen denominator \(q\) belongs to \(S\), so \(S\ne\emptyset\). By the well-ordering principle, \(S\) has a least element; call it \(q_0\). Put \[p_0=q_0\sqrt2\in\mathbb N_{>0}.\]

We use the elementary estimate \(1<\sqrt2<2\). It follows because all three numbers are positive and \(1^2<2<2^2\). Define \[q_1=p_0-q_0=q_0(\sqrt2-1).\] Since \(1<\sqrt2<2\), \(0<\sqrt2-1<1\), so \[0<q_1<q_0.\] Also \(q_1\) is an integer because \(p_0\) and \(q_0\) are integers.

It remains to prove that \(q_1\in S\). Compute \[q_1\sqrt2=(p_0-q_0)\sqrt2=p_0\sqrt2-q_0\sqrt2.\] Since \(p_0=q_0\sqrt2\), we have \(p_0\sqrt2=2q_0\) and \(q_0\sqrt2=p_0\). Therefore \[q_1\sqrt2=2q_0-p_0=q_0(2-\sqrt2).\] The inequality \(1<\sqrt2<2\) gives \(0<2-\sqrt2<1\), hence \[0<q_1\sqrt2<q_0.\] Moreover \(2q_0-p_0\) is an integer, so \(q_1\sqrt2\in\mathbb N_{>0}\). Thus \(q_1\in S\).

We have constructed \(q_1\in S\) with \(0<q_1<q_0\), contradicting the minimality of \(q_0\). Therefore the assumption \(\sqrt2\in\mathbb Q\) is false, so \(\sqrt2\) is irrational. \(\square\)

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

Because \(x>-1\), \(1+x>0\). Multiply the induction hypothesis by \(1+x\), then use \((1+nx)(1+x)=1+(n+1)x+nx^2\ge1+(n+1)x\).

Detailed correction: Exercise 1.37.

1. Goal.
Prove Bernoulli's inequality: for \(x > -1\) and \(n \in \mathbb{N}\), \((1+x)^n \geq 1 + nx\).

2. Reasoning plan.
Checkpoint 1. 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\).
Checkpoint 2. \((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\).
Checkpoint 3. Because \(x>-1\), \(1+x>0\). Multiply the induction hypothesis by \(1+x\), then use \((1+nx)(1+x)=1+(n+1)x+nx^2\ge1+(n+1)x\).

3. Learning check before the full solution.
Check that every conclusion follows from a stated definition, hypothesis, or previously established result. A complete correction should make the dependency of each step visible.

4. Complete step-by-step solution.

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

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.

If \(R\) and \(S\) are equivalence relations, then a pair in \(R\cap S\) inherits reflexivity, symmetry, and transitivity because each property holds simultaneously in both relations.

Detailed correction: Exercise 1.38.

1. Goal.
Prove that the intersection of any two equivalence relations on a set \(X\) is an equivalence relation.

2. Reasoning plan.
Checkpoint 1. 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\).
Checkpoint 2. For reflexivity: \(xRx\) and \(xSx\), so \(x(R \cap S)x\). Apply the same "and" logic for symmetry and transitivity.
Checkpoint 3. If \(R\) and \(S\) are equivalence relations, then a pair in \(R\cap S\) inherits reflexivity, symmetry, and transitivity because each property holds simultaneously in both relations.

3. Learning check before the full solution.
When a structure is defined by several axioms, each axiom must be checked separately. Do not infer an omitted axiom merely because the others hold.

4. Complete step-by-step solution.

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

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

Go one step further: the map \([x]\mapsto f(x)\) from \(X/{\sim}\) to \(f(X)\) is well-defined and bijective. This shows that the equivalence classes are exactly the non-empty fibres of \(f\).

Detailed correction: Exercise 1.39.

1. Goal.
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.

2. Reasoning plan.
Checkpoint 1. 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)\).
Checkpoint 2. The equivalence class of \(x\) is \([x] = \{x' \in X : f(x') = f(x)\} = f^{-1}(\{f(x)\})\). These are the fibres of \(f\).
Checkpoint 3. For \(x\in X\), the equivalence class \([x]\) is \(\{y\in X:f(y)=f(x)\}=f^{-1}(\{f(x)\})\).

3. Learning check before the full solution.
An if-and-only-if statement requires two complete implications. Proving only one direction establishes only a necessary or only a sufficient condition, not equivalence.

4. Complete step-by-step solution.

Reflexivity. For every \(x\in X\), \(f(x)=f(x)\), so \(x\sim x\).

Symmetry. If \(x\sim y\), then \(f(x)=f(y)\). Equality is symmetric, so \(f(y)=f(x)\), hence \(y\sim x\).

Transitivity. If \(x\sim y\) and \(y\sim z\), then \(f(x)=f(y)\) and \(f(y)=f(z)\). Therefore \(f(x)=f(z)\), so \(x\sim z\). Thus \(\sim\) is an equivalence relation.

Equivalence classes. For \(x\in X\), \[[x]=\{x'\in X:x'\sim x\}=\{x'\in X:f(x')=f(x)\}=f^{-1}(\{f(x)\}).\] Hence each equivalence class is exactly a non-empty fibre of \(f\), and two points are equivalent precisely when they lie in the same fibre.

Connection with the image. Define \(\Phi:X/{\sim}\to f(X)\) by \(\Phi([x])=f(x)\). It is well-defined because if \([x]=[y]\), then \(x\sim y\) and hence \(f(x)=f(y)\). It is surjective because every element of \(f(X)\) equals \(f(x)\) for some \(x\). It is injective because \(\Phi([x])=\Phi([y])\) implies \(f(x)=f(y)\), hence \(x\sim y\) and \([x]=[y]\). Therefore \(X/{\sim}\) is in bijection with \(f(X)\). \(\square\)

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.

To certify the example, verify that inclusion is reflexive, antisymmetric, and transitive on \(\mathcal P(\{1,2\})\). Only then use \(\{1\}\) and \(\{2\}\) to show that totality fails.

Detailed correction: Exercise 1.40.

1. Goal.
Show that the usual order \(\leq\) on \(\mathbb{R}\) is a total order. Give an example of a partial order that is not total.

2. Reasoning plan.
Checkpoint 1. 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\).
Checkpoint 2. The subset relation \(\subseteq\) on \(\mathcal{P}(\{1,2\})\) is a partial order: \(\{1\}\) and \(\{2\}\) are not comparable.
Checkpoint 3. On \(\mathcal P(\{1,2\})\), inclusion is a partial order, but \(\{1\}\) and \(\{2\}\) are incomparable. This proves it is not total.

3. Learning check before the full solution.
A proposed example is not enough by itself. Compute or verify every property requested, and explicitly show the feature that makes the example work.

4. Complete step-by-step solution.

1. The usual order on \(\mathbb R\). We check all four requirements. Reflexivity: \(a\le a\) for every real \(a\). Antisymmetry: if \(a\le b\) and \(b\le a\), then \(a=b\). Transitivity: if \(a\le b\) and \(b\le c\), then \(a\le c\). Totality: for any \(a,b\in\mathbb R\), either \(a\le b\) or \(b\le a\). Hence the usual relation \(\le\) is a total order on \(\mathbb R\).

2. A partial order that is not total. Let \(P=\mathcal P(\{1,2\})\) and order \(P\) by inclusion \(\subseteq\). We first verify that inclusion is a partial order.

Reflexivity. Every subset \(S\in P\) satisfies \(S\subseteq S\).

Antisymmetry. If \(S\subseteq T\) and \(T\subseteq S\), then the two sets have exactly the same elements, so \(S=T\).

Transitivity. If \(S\subseteq T\) and \(T\subseteq U\), then every element of \(S\) belongs to \(T\) and therefore to \(U\); hence \(S\subseteq U\). Thus \(\subseteq\) is a partial order on \(P\).

Failure of totality. The two elements \(\{1\}\) and \(\{2\}\) of \(P\) are incomparable: \(\{1\}\not\subseteq\{2\}\) and \(\{2\}\not\subseteq\{1\}\). Therefore this partial order is not total. \(\square\)

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

Remove one element \(a\). By induction the remaining finite set has a maximum \(M\) and minimum \(m\); totality lets you compare \(a\) with \(M\) and with \(m\) to obtain the new extrema.

Detailed correction: Exercise 1.41.

1. Goal.
Prove that every finite non-empty totally ordered set has a maximum and a minimum.

2. Reasoning plan.
Checkpoint 1. 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.
Checkpoint 2. 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\).
Checkpoint 3. Remove one element \(a\). By induction the remaining finite set has a maximum \(M\) and minimum \(m\); totality lets you compare \(a\) with \(M\) and with \(m\) to obtain the new extrema.

3. Learning check before the full solution.
Induction is on the number of elements, not on the order values. In the induction step, use totality to define the new maximum and minimum by cases, then verify explicitly that they bound every element of the enlarged set.

4. Complete step-by-step solution.

We use induction on \(n=|S|\).

Base case \(n=1\). If \(S=\{a\}\), then every element of \(S\) is \(a\), so \(a\) is both a maximum and a minimum.

Induction hypothesis. Assume every non-empty totally ordered set with \(n\) elements has both a maximum and a minimum.

Induction step. Let \(S\) have \(n+1\) elements. Choose \(a\in S\) and put \(S'=S\setminus\{a\}\). Then \(|S'|=n\), so by the induction hypothesis \(S'\) has a maximum \(M\) and a minimum \(m\).

Because the order is total, either \(a\le M\) or \(M\le a\). Define \(M'=M\) in the first case and \(M'=a\) in the second. Every \(x\in S'\) satisfies \(x\le M\); checking the two cases shows \(x\le M'\), and also \(a\le M'\). Hence \(M'\) is a maximum of \(S\).

Similarly, totality gives either \(a\le m\) or \(m\le a\). Define \(m'=a\) in the first case and \(m'=m\) in the second. Every \(x\in S'\) satisfies \(m\le x\); in either case \(m'\le x\), and also \(m'\le a\). Hence \(m'\) is a minimum of \(S\).

Therefore every finite non-empty totally ordered set has a maximum and a minimum. \(\square\)

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.

For transitivity, analyze whether the first-coordinate inequalities are strict or equal. If the first coordinates tie, transitivity reduces to the usual order on the second coordinates.

Detailed correction: Exercise 1.42.

1. Goal.
Define the lexicographic order on \(\mathbb{N} \times \mathbb{N}\) and prove it is a total order.

2. Reasoning plan.
Checkpoint 1. Define \((a,b) \leq_{\mathrm{lex}} (c,d)\) iff \(a < c\), or \(a = c\) and \(b \leq d\).
Checkpoint 2. 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.
Checkpoint 3. For transitivity, analyze whether the first-coordinate inequalities are strict or equal. If the first coordinates tie, transitivity reduces to the usual order on the second coordinates.

3. Learning check before the full solution.
For a total-order proof, check reflexivity, antisymmetry, transitivity, and totality separately. The transitivity step needs an explicit case analysis; writing only 'by cases' leaves the main logical work unstated.

4. Complete step-by-step solution.

Define \((a,b)\le_{\mathrm{lex}}(c,d)\) when either \(a<c\), or \(a=c\) and \(b\le d\).

Reflexivity. For every \((a,b)\), we have \(a=a\) and \(b\le b\), so \((a,b)\le_{\mathrm{lex}}(a,b)\).

Antisymmetry. Suppose \((a,b)\le_{\mathrm{lex}}(c,d)\) and \((c,d)\le_{\mathrm{lex}}(a,b)\). If \(a<c\), the second inequality would require \(c<a\) or \(c=a\), both impossible. Similarly \(c<a\) is impossible. Therefore \(a=c\). The two lexicographic inequalities then give \(b\le d\) and \(d\le b\), so \(b=d\). Hence the ordered pairs are equal.

Transitivity. Suppose \((a,b)\le_{\mathrm{lex}}(c,d)\) and \((c,d)\le_{\mathrm{lex}}(e,r)\). If \(a<c\), then the second relation gives either \(c<e\) or \(c=e\); in both cases \(a<e\), hence \((a,b)\le_{\mathrm{lex}}(e,r)\). If instead \(a=c\) and \(b\le d\), then either \(c<e\), which again gives \(a<e\), or \(c=e\) and \(d\le r\). In the latter case \(a=e\) and \(b\le d\le r\), so \(b\le r\). Thus transitivity holds in every case.

Totality. Given \((a,b)\) and \((c,d)\), exactly one of \(a<c\), \(a>c\), or \(a=c\) holds. The first two cases decide the lexicographic comparison. If \(a=c\), totality of the usual order on \(\mathbb N\) gives \(b\le d\) or \(d\le b\). Therefore the two pairs are always comparable.

The lexicographic relation is reflexive, antisymmetric, transitive, and total, so it is a total order on \(\mathbb N\times\mathbb N\). \(\square\)

Expected evidence: a formula for the bijection with \(\mathbb Z\), and a repetition-free rule that lists every rational exactly once.

Use \(z(0)=0\), \(z(2k-1)=k\), and \(z(2k)=-k\) for \(k\ge1\). This produces \(0,1,-1,2,-2,\ldots\).

Represent each rational uniquely as \(p/q\) with \(q\ge1\) and \(\gcd(|p|,q)=1\). Then order these pairs by increasing height \(|p|+q\).

For each \(m\ge1\), only finitely many reduced pairs satisfy \(|p|+q=m\). Listing these finite levels in increasing \(m\), and sorting by \(p\) inside each level, gives a concrete sequence with no repetitions.

Detailed correction: Exercise 1.43.

1. Goal.
Using \(\mathbb N=\{0,1,2,\ldots\}\), construct an explicit bijection \(\mathbb N\to\mathbb Z\) and an explicit enumeration of \(\mathbb Q\) without repetition. Conclude that \(\mathbb N\), \(\mathbb Z\), and \(\mathbb Q\) are countably infinite.

2. Reasoning plan.
Checkpoint 1. Use \(z(0)=0\), \(z(2k-1)=k\), and \(z(2k)=-k\) for \(k\ge1\). This produces \(0,1,-1,2,-2,\ldots\).
Checkpoint 2. Represent each rational uniquely as \(p/q\) with \(q\ge1\) and \(\gcd(|p|,q)=1\). Then order these pairs by increasing height \(|p|+q\).
Checkpoint 3. For each \(m\ge1\), only finitely many reduced pairs satisfy \(|p|+q=m\). Listing these finite levels in increasing \(m\), and sorting by \(p\) inside each level, gives a concrete sequence with no repetitions.

3. Learning check before the full solution.
To prove that an enumeration is a bijection, verify both exhaustiveness and uniqueness. For \(\mathbb Q\), reduced fractions provide uniqueness, while the finite-height construction guarantees that every reduced fraction eventually appears.

4. Complete step-by-step solution.

1. Enumerating \(\mathbb Z\). Define \(z:\mathbb N\to\mathbb Z\) by \[z(0)=0,\qquad z(2k-1)=k,\qquad z(2k)=-k\quad(k\ge1).\] The values are \(0,1,-1,2,-2,\ldots\). To see surjectivity, let \(m\in\mathbb Z\): if \(m=0\), use \(0\); if \(m>0\), then \(m=z(2m-1)\); if \(m<0\), writing \(m=-k\) with \(k>0\) gives \(m=z(2k)\). These three cases also show uniqueness of the index, so \(z\) is injective. Hence \(z\) is a bijection.

2. Canonical representatives for \(\mathbb Q\). Every rational number can be written uniquely as \(p/q\) with \(p\in\mathbb Z\), \(q\in\mathbb N_{>0}\), and \(\gcd(|p|,q)=1\). Let \[R=\{(p,q):q\ge1,\ \gcd(|p|,q)=1\}.\]

3. Enumerate the representatives. Give \((p,q)\in R\) the height \(h(p,q)=|p|+q\). For a fixed height \(m\), the conditions \(|p|+q=m\) and \(q\ge1\) leave only finitely many possible pairs. List first all reduced pairs of height 1, then height 2, then height 3, and so on; within a level, order by \(p\). Every pair has one finite height, so it appears at a finite stage. No pair is repeated because it belongs to exactly one height level and is listed once within that level.

4. Transfer the enumeration to rationals. If the resulting sequence is \((p_n,q_n)\), define \(r(n)=p_n/q_n\). Every rational has a reduced representative, so \(r\) is surjective. Uniqueness of reduced representations shows that \(r(n)=r(m)\) implies \((p_n,q_n)=(p_m,q_m)\), hence \(n=m\); therefore \(r\) is injective.

Thus both \(\mathbb Z\) and \(\mathbb Q\) are in bijection with \(\mathbb N\). They are countably infinite. \(\square\)

Expected evidence: a clear presentation of the diagonal argument with explicit construction of the missing real number.

Suppose \((0,1)\) is countable and list its elements as \(x_1,x_2,\ldots\). For every \(x_n\), choose the decimal expansion that is not eventually all 9s. Then diagonal digit comparison is unambiguous.

Construct \(y=0.e_1e_2e_3\cdots\) using only digits 1 and 2: set \(e_n=1\) if the \(n\)-th digit of \(x_n\) is not 1, and \(e_n=2\) otherwise. Then \(y\) differs from \(x_n\) in digit \(n\).

Resolve the decimal-expansion issue explicitly: use for every listed number its expansion that is not eventually all 9s, and construct \(y\) only with digits 1 and 2. Then differing in the \(n\)-th canonical digit guarantees \(y\ne x_n\).

Detailed correction: Exercise 1.44.

1. Goal.
Prove that the interval \((0,1)\) is uncountable using Cantor's diagonal argument.

2. Reasoning plan.
Checkpoint 1. Suppose \((0,1)\) is countable and list its elements as \(x_1,x_2,\ldots\). For every \(x_n\), choose the decimal expansion that is not eventually all 9s. Then diagonal digit comparison is unambiguous.
Checkpoint 2. Construct \(y=0.e_1e_2e_3\cdots\) using only digits 1 and 2: set \(e_n=1\) if the \(n\)-th digit of \(x_n\) is not 1, and \(e_n=2\) otherwise. Then \(y\) differs from \(x_n\) in digit \(n\).
Checkpoint 3. Assume \((0,1)=\{x_1,x_2,\ldots\}\) and choose decimal expansions not ending in repeating 9s. Build \(y=0.d_1d_2\ldots\) with \(d_n=1\) if the \(n\)-th digit of \(x_n\) is not 1, and \(d_n=2\) otherwise. Then \(y\) differs from \(x_n\) in digit \(n\).

3. Learning check before the full solution.
Diagonalization has two technical obligations: construct a number that really lies in \((0,1)\), and remove the ambiguity of decimal representations such as terminating decimals versus repeating 9s. Handle both explicitly before claiming the new number differs from every listed number.

4. Complete step-by-step solution.

Step 1 - assume a complete list exists. Suppose, for contradiction, that \((0,1)\) is countable. Then its elements can be listed as \(x_1,x_2,x_3,\ldots\). For each \(x_n\), choose the decimal expansion that is not eventually all 9s and write \[x_n=0.d_{n1}d_{n2}d_{n3}\cdots.\] This convention selects one representation when a number has two decimal representations.

Step 2 - construct the diagonal number. Define digits \[e_n=\begin{cases}1,&d_{nn}\ne1,\\2,&d_{nn}=1.\end{cases}\] and let \(y=0.e_1e_2e_3\cdots\). Every digit of \(y\) is 1 or 2. Hence \(0<y<1\), and its expansion is certainly not eventually all 9s.

Step 3 - compare with every entry. Fix \(n\). By construction, \(e_n\ne d_{nn}\). Thus the chosen decimal expansion of \(y\) differs from the chosen decimal expansion of \(x_n\) at the \(n\)-th digit. Because both are represented using the convention 'not eventually all 9s', unequal digit strings cannot be two alternative representations of the same real number. Therefore \(y\ne x_n\).

Step 4 - contradiction. The argument holds for every \(n\), so \(y\) is an element of \((0,1)\) missing from the supposedly complete list. This contradicts the assumption that the list contains every element of \((0,1)\). Therefore \((0,1)\) is uncountable. \(\square\)

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.

The diagonal set \(D\) is itself an element of \(\mathcal P(A)\). Showing that \(D\ne f(c)\) for every \(c\in A\) proves that every proposed \(f:A\to\mathcal P(A)\) misses at least one subset and therefore cannot be surjective.

Detailed correction: Exercise 1.45.

1. Goal.
Prove Cantor's theorem: for any set \(A\), \(|A| < |\mathcal{P}(A)|\). Conclude that \(\mathcal{P}(\mathbb{N})\) is uncountable.

2. Reasoning plan.
Checkpoint 1. 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.
Checkpoint 2. 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.
Checkpoint 3. Given any proposed map \(F:A\to\mathcal P(A)\), define \(D=\{a\in A:a\notin F(a)\}\). If \(D=F(d)\), then \(d\in D\iff d\notin D\), impossible.

3. Learning check before the full solution.
Keep the two parts of the cardinal comparison separate. First exhibit an injection \(A\to\mathcal P(A)\). Then prove that every proposed map \(A\to\mathcal P(A)\) fails to be surjective by constructing a subset outside its image.

4. Complete step-by-step solution.

Step 1 - show that \(A\) injects into its power set. Define \(i:A\to\mathcal P(A)\) by \(i(a)=\{a\}\). If \(i(a)=i(b)\), then \(\{a\}=\{b\}\), hence \(a=b\). Thus \(i\) is injective and \(|A|\le|\mathcal P(A)|\).

Step 2 - take an arbitrary proposed surjection. Let \(f:A\to\mathcal P(A)\) be any function and define the diagonal subset \[D=\{a\in A:a\notin f(a)\}.\] By construction \(D\subseteq A\), so \(D\in\mathcal P(A)\).

Step 3 - prove that \(D\) is missing from the image. Suppose there were \(c\in A\) with \(f(c)=D\). Then, using the definition of \(D\), \[c\in D\iff c\notin f(c).\] Substituting \(f(c)=D\) gives \[c\in D\iff c\notin D,\] which is impossible. Therefore no \(c\in A\) satisfies \(f(c)=D\). The subset \(D\) is not in the image of \(f\), so \(f\) is not surjective.

Step 4 - conclude the strict inequality. Since an injection \(A\to\mathcal P(A)\) exists but no surjection \(A\to\mathcal P(A)\) exists, there can be no bijection between the two sets. Hence \[|A|<|\mathcal P(A)|.\]

Corollary. Taking \(A=\mathbb N\), if \(\mathcal P(\mathbb N)\) were countable then it would have the same cardinality as \(\mathbb N\), contradicting Cantor's theorem. Therefore \(\mathcal P(\mathbb N)\) is uncountable. \(\square\)

Course Foundation Where Topology Begins This opening chapter launches General Topology / Topologie Générale by establishing the language used everywhere else in the course. Sets, subsets, indexed families, functions, direct and inverse images, complements, and quantifiers become the common grammar for metric spaces, topological spaces, continuity, compactness, connectedness, and the chapters that follow. The proof habits introduced here - implication, equivalence, contradiction, counterexample, and careful control of assumptions - are not preliminary decoration. They are the working discipline of the whole course. Chapter 2 turns this foundation into geometry by introducing metric spaces, where distance provides the first concrete model of topological structure.

Foundation established ✓ Ch 2 · Metric Spaces

\(x \in A\)	\(x\) is an element of \(A\)
\(A \subseteq B\)	\(A\) is a subset of \(B\)
\(A \cup B\)	union
\(A \cap B\)	intersection
\(A \setminus B\)	set difference
\(f(A)\)	direct image
\(f^{-1}(B)\)	inverse image
\(\forall\)	for all
\(\exists\)	there exists
\(\Rightarrow\)	implies
\(\Leftrightarrow\)	iff