Course 2 Book 2A: Numbers, Limits and the IntegralChapter 2

Sets, Functions and Equivalence

The language of sets and maps, and quotients: treating different things as the same.

32 min read · Updated Oct 2, 2026

Read with Tao, Analysis I, chapter "Set theory" (fundamentals, Russell's paradox, functions, images and inverse images, Cartesian products). Its last section, on cardinality, is the subject of [[2A.8]].

In this chapter · 6 sections

2.1Sets
2.1.1Which sets exist
2.1.2Operations on sets
2.2Functions
2.2.1Injective, surjective, bijective
2.3Images and preimages
2.4Cartesian products and relations
2.5Equivalence relations and quotients
2.5.1Functions on a quotient must be well defined
2.5.2Equivalence is a strong requirement
2.6Exercises

The previous chapter built the natural numbers and nothing else. Before building any other numbers we need a language for collections of things and for rules that turn one thing into another: sets and functions. Almost every definition from here to Perelman is written in this language. A Riemannian metric is a function, a manifold is a set with extra structure, and the space of all metrics is a set of functions.

This chapter also introduces the idea that does the most work in the next two chapters, and keeps doing work until the end of the route: equivalence relations and quotients. They are the precise way of saying "treat these different things as the same". The integers, the rationals and the real numbers are all built as quotients. So is the circle, the lens spaces of topology, and, at the very end, the space in which Ricci flow really lives: metrics up to a change of coordinates.

By the end of this chapter you will be able to:

work with sets, subsets and the operations on them, and prove set identities;
say exactly what a function is, and when two functions are equal;
decide whether a function is injective, surjective or bijective, and invert a bijection;
compute images and preimages, and explain why preimages behave better;
define an equivalence relation, describe its classes, form the quotient set, and check that a function on a quotient is well defined.

Sets

A set is a collection of objects, called its elements. We write $x \in A$ when $x$ is an element of $A$ , and $x \notin A$ when it isn't. A set is completely determined by its elements: two sets are equal exactly when they have the same elements. So $\{1, 2, 3\}$ , $\{3, 2, 1\}$ and $\{1, 1, 2, 3\}$ are the same set. Order and repetition don't matter, only membership.

Definition 2.1 Subsets

A set $A$ is a subset of a set $B$ , written $A \subseteq B$ , if every element of $A$ is also an element of $B$ . It is a proper subset, written $A \subsetneq B$ , if in addition $A \neq B$ .

Equality of sets is then the same as inclusion both ways: $A = B$ if and only if $A \subseteq B$ and $B \subseteq A$ . This is how almost every set identity is proved. To show two sets are equal, take an arbitrary element of one, show it lies in the other, and then do the same in the other direction.

Which sets exist

To build sets we need some agreed ways of making them. Tao lists them as axioms, and the ones we use constantly are these.1 These are, in slightly informal form, the axioms of Zermelo–Fraenkel set theory, the standard foundation of modern mathematics. You don't need to memorise them; you need to know that every set used in this guidebook is built by them.

There is an empty set $\varnothing$ with no elements.
For any objects $a$ and $b$ there are the sets $\{a\}$ and $\{a, b\}$ .
For any sets $A$ and $B$ there is the union $A \cup B$ , whose elements are those that lie in $A$ or in $B$ (or both).
Specification. For any set $A$ and any property $P(x)$ , there is a set $\{x \in A : P(x)\}$ of the elements of $A$ that have the property.
Replacement. For any set $A$ and any rule assigning an object $f(x)$ to each $x \in A$ , there is a set $\{f(x) : x \in A\}$ .
Infinity. The natural numbers $\mathbb{N}$ form a set.
Power set. For any set $A$ there is the set of all its subsets.

The specification axiom deserves attention because of what it does not allow. It lets you carve a subset out of a set you already have. It does not let you form "the set of all $x$ with property $P$ " with no ambient set, and the reason is one of the most famous arguments in mathematics.

History Russell's paradox

Suppose any property defined a set. Consider the property " $x$ is a set that is not an element of itself", and let $R$ be the set of all such $x$ . Is $R$ an element of itself? If $R \in R$ , then $R$ has the defining property, so $R \notin R$ . If $R \notin R$ , then $R$ has the property, so $R \in R$ . Either way, a contradiction.

Bertrand Russell found this in 1901 and wrote to Gottlob Frege in 1902, just as the second volume of Frege's Grundgesetze der Arithmetik was going to press. Frege's system, an attempt to found arithmetic on logic, allowed exactly this kind of unrestricted set formation, and the paradox showed it was inconsistent. He added an appendix acknowledging the problem. The modern response is the axioms above, which only ever build sets out of sets already in hand.

Operations on sets

Definition 2.2 Union, intersection, difference

Let $A$ and $B$ be sets.

The intersection $A \cap B = \{x \in A : x \in B\}$ consists of the elements in both.
The difference $A \setminus B = \{x \in A : x \notin B\}$ consists of the elements of $A$ not in $B$ .
$A$ and $B$ are disjoint if $A \cap B = \varnothing$ .

When all the sets in a discussion are subsets of one fixed set $X$ , the difference $X \setminus A$ is called the complement of $A$ (in $X$ ), written $A^c$ .

Figure 2.1. The four basic operations. Venn diagrams are good for intuition, but they are not proofs: a proof works with elements.

These operations obey a long list of laws: union and intersection are commutative and associative, each distributes over the other, and so on. They are all proved the same way, element by element. Here is the most useful pair in full.

Proposition 2.3 De Morgan's laws

Let $A$ and $B$ be subsets of a set $X$ . Then

(A \cup B)^c = A^c \cap B^c \qquad\text{and}\qquad (A \cap B)^c = A^c \cup B^c.

More generally, for any family of subsets $A_\alpha$ of $X$ , indexed by $\alpha$ in some set $I$ ,

\Big(\bigcup_{\alpha \in I} A_\alpha\Big)^c = \bigcap_{\alpha \in I} A_\alpha^c \qquad\text{and}\qquad \Big(\bigcap_{\alpha \in I} A_\alpha\Big)^c = \bigcup_{\alpha \in I} A_\alpha^c.

Proof. We prove the first law for a family; the others are the same argument. Let $x \in X$ . Then $x$ lies in the left-hand side exactly when $x$ is not in $\bigcup_\alpha A_\alpha$ , that is, when there is no $\alpha$ with $x \in A_\alpha$ . That says $x \notin A_\alpha$ for every $\alpha$ , which means $x \in A_\alpha^c$ for every $\alpha$ , which is membership of the right-hand side. Each step is an "if and only if", so the two sets have the same elements.

Notice the logic inside the proof: "not (there exists $\alpha$ with …)" became "for every $\alpha$ , not …". De Morgan's laws for sets are the rules for negating "there exists" and "for all". Chapter 2A.5 Quantifiers and the Shape of a Proof makes that rule a central skill.

Functions

Informally, a function from $X$ to $Y$ is a rule that takes each element of $X$ and returns an element of $Y$ . The precise definition makes three things part of the data: where inputs come from, where outputs land, and the rule.

Definition 2.4 Function

Let $X$ and $Y$ be sets. A function $f : X \to Y$ assigns to every $x \in X$ exactly one element $f(x) \in Y$ . The set $X$ is the domain of $f$ , and $Y$ is its codomain. Two functions $f, g : X \to Y$ are equal if $f(x) = g(x)$ for every $x \in X$ .

Three consequences of the definition catch people out.

Every input gets an output. " $f(x) = 1/x$ from $\mathbb{R}$ to $\mathbb{R}$ " is not a function, because $0$ gets nothing. It becomes one if the domain is $\mathbb{R} \setminus \{0\}$ .
Exactly one output. "$f(y) = $ the number whose square is $y$ " is not a function on the positive reals, because $4$ has two square roots. Choosing one ("the positive square root") makes it a function.
Equality is about values, not formulas. $f(x) = x^2 - 1$ and $g(x) = (x - 1)(x + 1)$ are the same function. On the other hand, $x \mapsto x^2$ as a function $\mathbb{R} \to \mathbb{R}$ and as a function $\mathbb{R} \to [0, \infty)$ are, strictly speaking, different functions, because their codomains differ. That distinction matters for surjectivity, below.

One way to make "a rule" precise, using only sets, is through the function's graph, the set of pairs $\{(x, f(x)) : x \in X\}$ . A function is its graph: a set of pairs in which every $x \in X$ appears as a first entry exactly once. Pairs need one more construction, the Cartesian product, which comes later in this chapter.

Composition. If $f : X \to Y$ and $g : Y \to Z$ , the composition $g \circ f : X \to Z$ is $x \mapsto g(f(x))$ . Composition is associative, $h \circ (g \circ f) = (h \circ g) \circ f$ , because both send $x$ to $h(g(f(x)))$ . It is not commutative: putting on socks and then shoes is not the same as shoes then socks.

Injective, surjective, bijective

Definition 2.5 Injective, surjective, bijective

A function $f : X \to Y$ is

injective (one-to-one) if different inputs give different outputs: $x \neq x'$ implies $f(x) \neq f(x')$ ;
surjective (onto) if every element of $Y$ is an output: for every $y \in Y$ there is some $x \in X$ with $f(x) = y$ ;
bijective if it is both.

You met injectivity already: 2A.1 The Natural Numbers's Axiom 1.4 says exactly that the successor map $n \mapsto n{+}{+}$ is injective. Together with Axiom 1.3 ( $0$ is not a successor), it says that the successor map from $\mathbb{N}$ to $\mathbb{N}$ is injective but not surjective.

Figure 2.2. The four possibilities. Injective: no two arrows land on the same point. Surjective: every point of

Y

is hit. Bijective: both, so the arrows pair

X

and

Y

off exactly.

Proposition 2.6 Inverses

A function $f : X \to Y$ is bijective if and only if there is a function $g : Y \to X$ with $g(f(x)) = x$ for every $x \in X$ and $f(g(y)) = y$ for every $y \in Y$ . Such a $g$ is unique; it is the inverse of $f$ , written $f^{-1}$ .

Proof. If $f$ is bijective, then for each $y \in Y$ there is some $x$ with $f(x) = y$ (surjectivity), and only one (injectivity). Define $g(y)$ to be that $x$ . Then $f(g(y)) = y$ by construction, and $g(f(x)) = x$ because $x$ is the unique input sent to $f(x)$ .

Conversely, suppose such a $g$ exists. If $f(x) = f(x')$ , apply $g$ : $x = g(f(x)) = g(f(x')) = x'$ , so $f$ is injective. Given $y \in Y$ , the element $x = g(y)$ satisfies $f(x) = y$ , so $f$ is surjective.

For uniqueness, if $g$ and $h$ both work, then for every $y$ , $g(y) = g(f(h(y))) = h(y)$ , using $f(h(y)) = y$ and then $g(f(x)) = x$ with $x = h(y)$ .

In the world In use Hashing: a function that can't be injective

A hash function turns any file, of any length, into a short fixed-length string. SHA-256, for example, outputs 256 bits, and it is used to check downloads, sign software and chain blocks together in cryptocurrencies. There are infinitely many possible inputs and only $2^{256}$ possible outputs, so SHA-256 cannot be injective: some pair of different files must have the same hash (a collision). This is the pigeonhole principle: a function from a larger set into a smaller one can't be injective.

The security of a hash function rests not on injectivity, which is impossible, but on collisions being infeasible to find. When that fails, the function is retired. In 2017 a team from CWI Amsterdam and Google published the first practical collision for the older SHA-1, two different PDF files with the same SHA-1 hash, and SHA-1 has since been phased out of security-critical uses.

In the world In use Ciphers are bijections

An encryption scheme must be decryptable, so encryption with a fixed key must be injective. The simplest example is the Caesar shift on the alphabet, $x \mapsto x + 3$ with letters numbered $0$ to $25$ and wrapping round after $25$ (exactly the clock arithmetic of 2A.1 The Natural Numbers). Its inverse is $x \mapsto x - 3$ . Modern block ciphers such as AES are, for each key, bijections on the set of 128-bit blocks. Decryption is the inverse function.

Images and preimages

A function moves sets as well as points. There are two directions, and they behave very differently.

Definition 2.7 Image and preimage

Let $f : X \to Y$ .

For $S \subseteq X$ , the image of $S$ is $f(S) = \{f(x) : x \in S\}$ , the set of outputs of inputs from $S$ .
For $U \subseteq Y$ , the preimage (or inverse image) of $U$ is $f^{-1}(U) = \{x \in X : f(x) \in U\}$ , the set of inputs whose outputs land in $U$ .

The notation $f^{-1}(U)$ does not require $f$ to have an inverse. It makes sense for every function. If $f(x) = x^2$ on $\mathbb{R}$ , then $f^{-1}(\{4\}) = \{-2, 2\}$ , $f^{-1}(\{-1\}) = \varnothing$ , and $f^{-1}([1, 4]) = [-2, -1] \cup [1, 2]$ .

Preimages respect every set operation. Images don't.

Theorem 2.8 Preimages commute with set operations

Let $f : X \to Y$ , and let $U, V$ and $U_\alpha$ (for $\alpha \in I$ ) be subsets of $Y$ . Then

f^{-1}\Big(\bigcup_\alpha U_\alpha\Big) = \bigcup_\alpha f^{-1}(U_\alpha), \qquad f^{-1}\Big(\bigcap_\alpha U_\alpha\Big) = \bigcap_\alpha f^{-1}(U_\alpha), \qquad f^{-1}(Y \setminus U) = X \setminus f^{-1}(U).

Proof. For the union: $x \in f^{-1}(\bigcup_\alpha U_\alpha)$ means $f(x) \in U_\alpha$ for some $\alpha$ , which means $x \in f^{-1}(U_\alpha)$ for some $\alpha$ , which is membership of the right-hand side. The intersection is the same with "some" replaced by "every". For the complement: $x \in f^{-1}(Y \setminus U)$ means $f(x) \notin U$ , which means $x \notin f^{-1}(U)$ .

For images, only the union rule survives: $f(S \cup T) = f(S) \cup f(T)$ always, but in general $f(S \cap T) \subsetneq f(S) \cap f(T)$ can happen.

Example 2.9 Images lose information

Let $f(x) = x^2$ on $\mathbb{R}$ , $S = [-2, -1]$ and $T = [1, 2]$ . Then $S \cap T = \varnothing$ , so $f(S \cap T) = \varnothing$ . But $f(S) = f(T) = [1, 4]$ , so $f(S) \cap f(T) = [1, 4]$ . Points from $S$ and points from $T$ are sent to the same place, so after applying $f$ you can no longer tell them apart. If $f$ is injective this can't happen, and then $f(S \cap T) = f(S) \cap f(T)$ (Exercise 2.20).

Figure 2.3. For

f(x) = x^2

, the disjoint sets

[-2,-1]

and

[1,2]

have the same image

[1,4]

, so the image of their intersection (

\varnothing

) is smaller than the intersection of their images. Read the figure backwards and you see the preimage:

f^{-1}([1,4]) = [-2,-1] \cup [1,2]

Where this goes Why the guidebook keeps using preimages

Theorem 2.8 looks like a technicality, but it decides how two of the central definitions in analysis are written. A function is continuous when the preimage of every open set is open (7A.1 Topological Spaces and Quotients), and measurable when the preimage of every measurable set is measurable (3A.3 The Lebesgue Integral). Both definitions use preimages because preimages respect unions, intersections and complements, which are the operations that define "open set" and "measurable set" in the first place. Images would not work.

In the world In use Thresholding an image is a preimage

A greyscale photograph is a function $b$ from the set of pixels to brightness values $\{0, 1, \dots, 255\}$ . "Select every pixel brighter than $200$ ", the first step in many image-segmentation tools and in counting stars, cells or defects in a picture, is the preimage $b^{-1}(\{201, \dots, 255\})$ . Theorem 2.8 is why combining selections is easy: "bright or red" is the union of two preimages, "bright and red" is the intersection, and "not bright" is the complement.

Cartesian products and relations

Definition 2.10 Cartesian product

An ordered pair $(x, y)$ consists of a first entry $x$ and a second entry $y$ ; two pairs are equal exactly when their first entries are equal and their second entries are equal. The Cartesian product of sets $X$ and $Y$ is the set of all ordered pairs $X \times Y = \{(x, y) : x \in X, y \in Y\}$ . Products of more sets, $X_1 \times \dots \times X_n$ , consist of ordered $n$ -tuples.

So $\mathbb{R}^2 = \mathbb{R} \times \mathbb{R}$ is the plane, and a function $f : X \to Y$ can be identified with its graph, a subset of $X \times Y$ . If $X$ has $m$ elements and $Y$ has $n$ , then $X \times Y$ has $m \times n$ , which is where the word "product" comes from.

Definition 2.11 Relation

A relation on a set $X$ is a subset $R \subseteq X \times X$ . We write $x \sim y$ for $(x, y) \in R$ .

"Less than" on $\mathbb{N}$ is a relation: the set of pairs $(m, n)$ with $m < n$ . So is "has the same birthday as" on the set of people.

In the world In use Relational databases store relations

Most of the world's business data sits in relational databases, a design proposed by Edgar F. Codd in 1970. A database table is literally a relation in the sense of Definition 2.10, generalised to more columns: a set of tuples. A CROSS JOIN of two tables is their Cartesian product, and an ordinary join is a subset of that product picked out by a condition, which is the specification axiom in action. Codd built his model directly on this set-theoretic language, which is why queries can be reasoned about mathematically and optimised automatically.

Equivalence relations and quotients

Some relations behave like equality. "Has the same remainder after division by $12$ " is one: it treats $3$ , $15$ and $27$ as the same as far as a clock is concerned. Three properties capture what "behaves like equality" means.

Definition 2.12 Equivalence relation

A relation $\sim$ on a set $X$ is an equivalence relation if it is

reflexive: $x \sim x$ for every $x$ ;
symmetric: if $x \sim y$ then $y \sim x$ ;
transitive: if $x \sim y$ and $y \sim z$ then $x \sim z$ .

The equivalence class of $x$ is $[x] = \{y \in X : y \sim x\}$ , everything equivalent to $x$ .

Example 2.13 Congruence modulo

n

Fix a positive natural number $n$ . For integers $a$ and $b$ , say $a \equiv b \pmod n$ if $a - b$ is a multiple of $n$ . (We use the integers informally here; they are built properly in 2A.3 Integers and Rationals.) This is an equivalence relation: $a - a = 0 = 0 \cdot n$ ; if $a - b = kn$ then $b - a = (-k)n$ ; and if $a - b = kn$ and $b - c = ln$ then $a - c = (k + l)n$ . There are exactly $n$ classes, $[0], [1], \dots, [n-1]$ , one for each possible remainder, by Euclidean division (2A.1 The Natural Numbers).

The key fact about equivalence classes is that they cut $X$ into non-overlapping pieces.

Theorem 2.14 Equivalence classes partition the set

Let $\sim$ be an equivalence relation on $X$ . Then every element of $X$ lies in exactly one equivalence class. In particular, two classes $[x]$ and $[y]$ are either equal (when $x \sim y$ ) or disjoint (when $x \not\sim y$ ).

Conversely, any way of cutting $X$ into non-empty, pairwise disjoint pieces whose union is $X$ (a partition) comes from exactly one equivalence relation: " $x \sim y$ when $x$ and $y$ are in the same piece".

Proof. Each $x$ lies in its own class, by reflexivity. Suppose $[x]$ and $[y]$ share an element $z$ , so $z \sim x$ and $z \sim y$ . By symmetry $x \sim z$ , and with transitivity $x \sim y$ . Now if $w \in [x]$ , then $w \sim x$ and $x \sim y$ give $w \sim y$ , so $w \in [y]$ ; thus $[x] \subseteq [y]$ , and by the same argument $[y] \subseteq [x]$ . So two classes that meet are equal, which is the first claim. The converse is a direct check of the three properties (Exercise 2.22).

Figure 2.4. Congruence modulo

3

\{0, \dots, 11\}

. Its three equivalence classes are the three remainders, and they partition the set: every number lies in exactly one class.

Now the central construction.

Definition 2.15 Quotient set

Let $\sim$ be an equivalence relation on $X$ . The quotient set $X/{\sim}$ is the set of equivalence classes, $\{[x] : x \in X\}$ . The map $\pi : X \to X/{\sim}$ , $\pi(x) = [x]$ , is the quotient map.

The quotient is a new set whose elements are whole classes. Each class is treated as a single object. The quotient map is always surjective, and it is injective only when $\sim$ is plain equality. It forgets exactly the differences that $\sim$ declares unimportant.

Figure 2.5. The quotient

\mathbb{R}/\mathbb{Z}

, where

x \sim y

when

x - y

is an integer. Each class, such as

\{\dots, 0.25, 1.25, 2.25, \dots\}

, becomes one point, and the quotient is naturally pictured as a circle: going once round it means moving one unit along the line.

In the world In use The antimeridian: a quotient that breaks software

Longitude is an angle: $-180°$ and $+180°$ name the same meridian, and so do $10°$ and $370°$ . Mathematically, longitude is a point of the quotient $\mathbb{R}/360\mathbb{Z}$ , a circle, not a point of the interval $[-180, 180]$ . Software that forgets this breaks at the antimeridian, the line of $\pm 180°$ through the Pacific. A rectangle that runs from $170°$ E across to $170°$ W (that is, to $-170°$ ) is only $20°$ wide. Stored naively as "from $170$ to $-170$ ", it is drawn as a band $340°$ wide stretching the wrong way round the whole globe. The GeoJSON format, a standard for exchanging map data (IETF RFC 7946, 2016), addresses this explicitly. Its section 3.1.9, Antimeridian Cutting, says that a geometry crossing the antimeridian should be cut in two, so that no piece's coordinates cross it.

Figure 2.6. The same 20°-wide region near the antimeridian, stored naively (top) and cut in two as RFC 7946 recommends (bottom). The underlying mistake is treating a quotient (a circle of longitudes) as if it were an interval.

Functions on a quotient must be well defined

To define a function on a quotient set $X/{\sim}$ , it is natural to give a formula in terms of a representative: "$F([x]) = $ something computed from $x$ ". That defines a function only if the answer doesn't depend on which representative of the class you used. This condition is called being well defined.

Proposition 2.16 Defining functions on quotients

Let $\sim$ be an equivalence relation on $X$ , and let $f : X \to Y$ be a function that is constant on each class: $x \sim x'$ implies $f(x) = f(x')$ . Then there is exactly one function $F : X/{\sim} \to Y$ with $F([x]) = f(x)$ for every $x$ , that is, with $F \circ \pi = f$ .

Proof. Define $F$ on a class $C$ by choosing any $x \in C$ and setting $F(C) = f(x)$ . Any other choice $x' \in C$ satisfies $x' \sim x$ , so $f(x') = f(x)$ : the value doesn't depend on the choice, and $F$ is a function. It satisfies $F([x]) = f(x)$ by construction, and any function with that property must agree with $F$ on every class.

Example 2.17 A formula that isn't a function

On the clock $\mathbb{Z}/12$ , " $F([a]) = a$ " is not a function into the integers, because $[3] = [15]$ but $3 \neq 15$ . On the other hand, " $G([a]) = [a + 5]$ " is a well-defined function $\mathbb{Z}/12 \to \mathbb{Z}/12$ ("five hours later"): if $a \equiv a' \pmod{12}$ then $a + 5 \equiv a' + 5 \pmod{12}$ .

This is exactly why a clock can tell you what time it will be in five hours, but not how many hours have passed since a given moment. That last quantity isn't a function of the clock reading, which was the recursion problem of 2A.1 The Natural Numbers seen from a new angle.

Where this goes Quotients from here to Ricci flow

The pattern "build a set of representatives, declare an equivalence, check that operations are well defined" is how the next two chapters build numbers. The integers are pairs of naturals modulo an equivalence, and so are the rationals (2A.3 Integers and Rationals); the reals are Cauchy sequences modulo another (2A.4 The Real Numbers). Much later, the circle, tori and lens spaces are quotients of familiar spaces (7A.1 Topological Spaces and Quotients, 7A.6 Covering Spaces), and the 3-manifolds left behind by Ricci flow with surgery are quotients $S^3/\Gamma$ of the sphere. Most striking of all, Ricci flow itself is diffeomorphism-invariant: changing coordinates turns a solution into a solution. So the flow really acts on the quotient set "metrics modulo diffeomorphisms", and much of its theory (DeTurck's trick, 11A.3 Short-Time Existence and Uniqueness; solitons, 11B.1 Ricci Solitons) is about working in that quotient.

Equivalence is a strong requirement

Transitivity is the property most often violated by relations that "feel like" sameness.

In the world In use "Similar enough" is not an equivalence relation

Merging duplicate records, such as customers entered twice under slightly different spellings, is a routine and expensive data-cleaning task. A natural rule is "two names are duplicates if they differ by at most one letter". This relation is reflexive and symmetric but not transitive. "cat" and "cot" differ in one letter, "cot" and "dot" in one, "dot" and "dog" in one, but "cat" and "dog" differ in all three. Merge along the rule and the chain cat–cot–dot–dog collapses into one record, though its two ends have nothing in common. Practical deduplication systems therefore either cluster with a careful threshold or make a final decision for each cluster. Either way, they must turn a non-transitive similarity into a genuine equivalence relation before they can form classes.

Figure 2.7. Each adjacent pair differs in one letter, but the ends differ in three. "Differs in at most one letter" is reflexive and symmetric, not transitive, so it can't be used to form classes. Chapter 2B.1 Metric Spaces studies such distances properly: the edit distance is a metric, and the issue here is that "distance at most 1" isn't transitive.

Recall Where we stand

We have the language of sets and functions, the four kinds of maps (injective, surjective, bijective, neither), images and preimages and why preimages behave better, products and relations, and the central tool of the next two chapters: equivalence relations, quotients and well-definedness. Chapter 2A.3 Integers and Rationals uses all of it to build the integers and the rationals from the natural numbers.

Exercises

Exercise 2.18 A distributive law

Prove that $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ for any sets $A$ , $B$ , $C$ , by showing each side is a subset of the other.

Solution

If $x \in A \cap (B \cup C)$ then $x \in A$ , and $x \in B$ or $x \in C$ . In the first case $x \in A \cap B$ , in the second $x \in A \cap C$ ; either way $x$ is in the right-hand side. Conversely, if $x \in A \cap B$ then $x \in A$ and $x \in B \subseteq B \cup C$ , so $x$ is in the left-hand side; the case $x \in A \cap C$ is the same.

Exercise 2.19 Composition and the kinds of maps

Let $f : X \to Y$ and $g : Y \to Z$ . Prove: (a) if $f$ and $g$ are injective, so is $g \circ f$ ; (b) if $f$ and $g$ are surjective, so is $g \circ f$ ; (c) if $g \circ f$ is injective, then $f$ is injective, but $g$ need not be.

Hint

For (c), a counterexample: let $X$ have one element, and let $g$ send two different points of $Y$ to the same point.

Exercise 2.20 When images behave

Show that if $f$ is injective then $f(S \cap T) = f(S) \cap f(T)$ for all $S, T \subseteq X$ . Then find the exact place in your proof where injectivity is used, and check that Example 2.9 fails at that place.

Exercise 2.21 Going there and back

Let $f : X \to Y$ , $S \subseteq X$ and $U \subseteq Y$ . Prove that $S \subseteq f^{-1}(f(S))$ and $f(f^{-1}(U)) \subseteq U$ . Show that the first inclusion is an equality for every $S$ exactly when $f$ is injective, and the second for every $U$ exactly when $f$ is surjective.

Exercise 2.22 Partitions give equivalence relations

Complete the proof of Theorem 2.14: given a partition of $X$ , show that " $x \sim y$ if $x$ and $y$ lie in the same piece" is an equivalence relation whose classes are exactly the pieces.

Exercise 2.23 Which are equivalence relations?

For each relation, decide whether it is reflexive, symmetric and transitive: (a) $m \leq n$ on $\mathbb{N}$ ; (b) " $x - y$ is an even integer" on $\mathbb{Z}$ ; (c) " $|x - y| < 1$ " on $\mathbb{R}$ ; (d) "lives within 10 km of" on the set of people; (e) " $x$ and $y$ have the same last digit" on $\mathbb{N}$ .

Solution

(a) Reflexive and transitive, not symmetric. (b) An equivalence relation, with two classes, the even and odd integers. (c) Reflexive and symmetric, not transitive ( $0 \sim 0.6 \sim 1.2$ but $|0 - 1.2| > 1$ ): the real-number version of "similar enough". (d) Same as (c). (e) An equivalence relation with ten classes; it is congruence modulo $10$ .

Exercise 2.24 Well defined or not?

On $\mathbb{Z}/12$ (clock arithmetic), decide which of these formulas define functions: (a) $[a] \mapsto [2a]$ into $\mathbb{Z}/12$ ; (b) $[a] \mapsto [a]$ into $\mathbb{Z}/6$ ; (c) $[a] \mapsto [a]$ into $\mathbb{Z}/5$ ; (d) $[a] \mapsto$ the remainder of $a$ on division by $12$ , into $\{0, \dots, 11\}$ .

Solution

(a) Yes: $a \equiv a' \pmod{12}$ gives $2a \equiv 2a' \pmod{12}$ . (b) Yes: a multiple of $12$ is a multiple of $6$ , so congruent mod $12$ implies congruent mod $6$ . (c) No: $[0] = [12]$ in $\mathbb{Z}/12$ , but $0 \not\equiv 12 \pmod 5$ . (d) Yes, and it is a bijection: it chooses one canonical representative for each class.

Exercise 2.25 Rehearsal: a distance on a circle

Longitudes live in $\mathbb{R}/360\mathbb{Z}$ . Show that $d([a], [b]) = \min\{|a - b - 360k| : k \in \mathbb{Z}\}$ is well defined, that is, independent of the representatives $a$ and $b$ , and compute $d([170], [-170])$ . This is the first appearance of a recurring idea: a quotient often inherits a distance from the space above it, by taking the shortest distance between classes. Riemannian quotients such as lens spaces get their geometry the same way (7A.6 Covering Spaces, 9A.1 Riemannian Metrics and Model Spaces).

Solution

Replacing $a$ by $a + 360j$ changes the set $\{|a - b - 360k| : k \in \mathbb{Z}\}$ only by renaming $k$ to $k - j$ , so the minimum is unchanged; the same holds for $b$ . For $a = 170$ , $b = -170$ : $a - b = 340$ , and $|340 - 360| = 20$ is the smallest value, so the distance is $20°$ , as the map in Figure 2.6 says it should be.

© 2026 NeckPinch (www.neckpinch.com). All content in the guidebook (text, mathematics, figures and exercises) is protected by copyright. All rights reserved. No part may be copied, republished or redistributed without written permission.

2.1Sets

2.1.1Which sets exist

2.1.2Operations on sets

2.2Functions

2.2.1Injective, surjective, bijective

2.3Images and preimages

2.4Cartesian products and relations

2.5Equivalence relations and quotients

2.5.1Functions on a quotient must be well defined

2.5.2Equivalence is a strong requirement

2.6Exercises

Sets

Which sets exist

Operations on sets

Functions

Injective, surjective, bijective

Images and preimages

Cartesian products and relations

Equivalence relations and quotients

Functions on a quotient must be well defined

Equivalence is a strong requirement

Exercises