1.2 Equivalence and Quotients · Homology & Cohomology

…mathematics is the art of giving the same name to different things.

— Henri Poincaré, Science and Method (1908), translated by G. B. Halsted

Is $\frac{1}{2}$ the same number as $\frac{2}{4} ?$ Is three o’clock the same time as fifteen o’clock? Is a coffee mug the same shape as a doughnut? Each time the honest answer is “yes — once you decide what to ignore.” Our job is to make that decision precisely, and then to watch what it does: a whole pile of different things, once declared the same, becomes a single new object.

Where this is going

This chapter plants the single most important idea of the book. Declaring things the same and then treating each pile as one object is called taking a quotient, and it is the first of the book’s four recurring ideas (the others are kernels and images, formal sums, and reversed arrows, all coming in Part I). You will meet it again when we build the clock groups $Z / n$ (§1.3 Groups) and quotient groups (§1.4 Abelian Groups and Formal Sums), when we glue the sides of a square into a torus (§2.2 Gluing Spaces Together), and above all in homology itself (§3.3 Homology Groups), where two loops are declared “the same” when together they enclose a region: $H_{n} = Z_{n} / B_{n}$ is literally a quotient. The “well-defined” check of this chapter is what later makes maps between homology groups possible.

Same, up to what?

Mathematicians say “the same” all the time, and they almost never mean “identical.” They mean the same up to something: the same up to a whole number of days, the same up to cancelling a common factor, the same up to stretching and bending. The phrase “up to” names what we have agreed to ignore.

Clocks. A wall clock ignores whole turns of its hand: 3 o’clock and 15 o’clock (and 27 o’clock, if you kept counting) all point the hand at the same place. The clock treats hours that differ by a multiple of 12 as the same.
Fractions. $\frac{1}{2},$ $\frac{2}{4}$ and $\frac{- 3}{- 6}$ are written differently, but every one of them describes the same amount. A fraction ignores common factors of its top and bottom.
Shapes. In §0.1 The Shape of a Question a topologist declared the coffee mug and the doughnut the same, because one can be bent into the other without tearing. Topology ignores bending and stretching.
Parity. For many purposes the only thing that matters about a whole number is whether it is even or odd. Then 2, 8 and −40 are “the same”, and so are 1, 7 and 101.

In every case, many different things get one shared name, which is exactly what Poincaré meant in the epigraph (Poincaré 1908, bk I, ch. II). But “declaring things the same” cannot be done carelessly. Suppose you decided that two numbers are the same whenever they are close, say within $0.1$ of each other. Then $0$ would be the same as $0.1,$ which is the same as $0.2,$ which is the same as $0.3,$ … and after a thousand small steps, $0$ would be “the same” as $100 .$ A notion of sameness that lets every number be the same as every other is useless. So sameness must obey some rules, and finding the right rules is our first job.

We take the idea in five steps:

say precisely what “declaring things the same” means (an equivalence relation);
see what it does to a set: it sorts it into non-overlapping piles (classes, forming a partition);
make a new set whose elements are the piles (the quotient set);
learn the one safety check you need before computing with piles (well-definedness);
use all of this to build shapes by gluing (a preview of §2.2 Gluing Spaces Together).

Relations: a yes-or-no question about pairs

Before we can talk about sameness, we need a way to talk about any connection between elements of a set. Think of a question that can be asked about two things $x$ and $y,$ in that order, and that always has a definite yes-or-no answer:

“Is $x$ less than $y ?”$ (asked about numbers)
“Does $x$ divide $y ?”$ (asked about whole numbers)
“Was $x$ born on the same day of the year as $y ?”$ (asked about people)
“Do $x$ and $y$ leave the same remainder when divided by 3?” (asked about integers)

Such a question is completely described by listing the pairs for which the answer is “yes.” That list is a collection of ordered pairs $(x, y)$ — a subset of the Cartesian product $X \times X$ that you met in §1.1 Sets and Functions. And that is precisely the definition.

The symbol $\sim$ is called a tilde. When we use it for a relation, think of it as a fill-in-the-blank: $x \sim y$ is the statement “the answer to our question about $(x, y)$ is yes,” and $x \neq \sim y$ means “the answer is no.”

There are two pictures of a relation that we will use constantly, and the next figure shows both side by side.

The table. Draw the grid $X \times X :$ one row for each $x,$ one column for each $y .$ Mark the cell in row $x$ and column $y$ when $x \sim y .$ The relation is the set of marked cells.
The arrows. Draw each element as a dot and draw an arrow $x \to y$ whenever $x \sim y .$ If $x \sim x,$ the arrow starts and ends at the same dot: a little loop.

Three rules for sameness

Most relations have nothing to do with sameness: “less than” certainly doesn’t. So let us ask: what must be true of a question like “are $x$ and $y$ the same (in the way we care about)?” Three things, which you have known all your life without saying them out loud.

Everything is the same as itself. Whatever we ignore, $x$ never differs from $x .$
Sameness goes both ways. If $x$ is the same as $y,$ then $y$ is the same as $x .$
Sameness can be chained. If $x$ is the same as $y,$ and $y$ is the same as $z,$ then $x$ is the same as $z .$

The third rule is the one that failed for “close to” in the first section. These three rules are the entire definition.

Each rule has a shape in each picture, and once you can see the shapes you can check the rules at a glance.

Reflexive: every cell on the diagonal of the table is marked; in the arrow picture, every dot carries a loop.
Symmetric: the table is a mirror image of itself across the diagonal; in the arrow picture, every arrow has a partner coming back.
Transitive: whenever you can walk $x \to y \to z$ in two steps, there is also a one-step shortcut $x \to z .$

Three rules, checked live Tap cells to add or remove pairs · try the presets

The relation as a table: row

x,

column

y

∼	1	2	3	4
1
2
3
4

The same relation as arrows:

x \to y

when

x \sim y

Reflexive every

x \sim x

Symmetric every arrow has a partner coming back

Transitive

1 \sim 2

and

2 \sim 3,

but not

1 \sim 3

Not an equivalence relation. Try “close it up”: it adds exactly the pairs that the three rules force.

Try:

Figure 1.2.1 A relation on

{1, 2, 3, 4},

drawn as a table and as arrows. The three lights test the rules; when one fails, a witness is highlighted: the gold arrows exist, the dashed rose arrow is the one the rule demands but which is missing. “Close it up” adds exactly the pairs the rules force (shown in violet). Try “

∣ x - y ∣ \leq 1 ”:

it is reflexive and symmetric, yet fails transitivity, just like “close to.”

The star example: same remainder

Fix a whole number $n \geq 1 .$ Two integers are congruent modulo $n$ if they leave the same remainder when divided by $n .$ With $n = 3 :$ $7$ and $13$ are congruent (both leave remainder $1),$ while $7$ and $8$ are not.

There is a neater way to say this that avoids talking about remainders. Two integers leave the same remainder when divided by $n$ exactly when their difference is a multiple of $n :$ $13 - 7 = 6 = 3 \cdot 2 .$ We write $n ∣ m,$ read “ $n$ divides $m,”$ to mean that $m = nk$ for some integer $k .$ (Careful: $n ∣ m$ is a statement, true or false; it is not the fraction $n / m .)$

Each rule needed one everyday fact about the multiples of $n :$ $0$ is one; the negative of one is one; the sum of two is one. Keep that short list in mind. In §1.3 Groups those three facts become the definition of a subgroup, and the proof you have just read then works word for word for “differ by an element of a subgroup” — which is how homology will declare two loops the same.

A little history Gauss and the triple bar

Carl Friedrich Gauss 1777 – 1855

The symbol $\equiv$ for congruence was introduced by Gauss, aged twenty-four, in his Disquisitiones Arithmeticae of 1801, the book that made arithmetic modulo $n$ a systematic theory. A stipend from the Duke of Brunswick freed him to write it, and its last section held the discovery he had made as a student: a regular 17-sided polygon can be drawn with ruler and compasses. A footnote explains the choice of symbol: “We have adopted this sign because of the great analogy that is found between equality and congruence.” Adrien-Marie Legendre, Gauss adds, had for the same reason simply used the equals sign itself, which Gauss “hesitated to imitate, lest ambiguity arise” (Gauss 1801, art. 2). (The translations from Gauss’s Latin are ours.) So the third bar says: equal, in the one respect we care about.

More examples

Equality, $x \sim y ⟺ x = y,$ is an equivalence relation. It is the strictest one: it declares nothing the same except a thing and itself.
“Everything is related to everything” is also an equivalence relation, the most generous one: it declares all elements the same.
Same colour on a bag of marbles; same birthday on a set of people; same number of letters on a set of words. Any relation of the form “ $x$ and $y$ give the same answer to a fixed question” is an equivalence relation, and the three rules hold for three small reasons: an answer equals itself, equality goes both ways, and equalities chain.
Same distance from the origin, for points of the plane: $(x, y) \sim (x^{'}, y^{'})$ when $x^{2} + y^{2} = x^{'2} + y^{'2} .$ This is again “same answer to a question” — the question being “how far are you from $0 ?”$

That last pattern is so useful that it deserves to be said in general. If $f : X \to Y$ is any function, then

x \sim x^{'} ⟺ f (x) = f (x^{'})

is an equivalence relation on $X :$ “same output.” Every function quietly sorts its inputs into groups, one group for each output it actually produces. Remember this; it comes back at the end of the chapter.

Non-examples, each failing exactly one rule

The best way to understand a definition with several conditions is to look at examples that satisfy all but one of them. Each of the following fails exactly one rule. (The first two are presets in Figure 1.2.1, on four numbers.)

Relation	Reflexive?	Symmetric?	Transitive?
$x \leq y$ on $Z$	yes	no: $1 \leq 2$ but $2 \neq \leq 1$	yes
$∣ x - y ∣ \leq 1$ on $Z$ (“close to”)	yes	yes	no: $1 \sim 2,$ $2 \sim 3,$ but $1 \neq \sim 3$
$x y > 0$ on $R$ (“same strict sign”)	no: $0 \cdot 0 = 0,$ so $0 \neq \sim 0$	yes	yes

The third row is the subtle one. For nonzero numbers, $x y > 0$ says “ $x$ and $y$ have the same sign,” which is a perfectly good sameness. It fails reflexivity at a single point, $0,$ which is related to nothing at all — not even itself. And that single point is enough to disqualify it.

Classes and partitions

Sort the integers by their remainder on division by $3$ and they fall into three piles: the multiples of $3,$ the numbers one more than a multiple, and the numbers two more. Every equivalence relation sorts its set like this. Each element has a pile — everything equivalent to it — and from here on the piles, rather than the elements, take centre stage.

(The notation ${y \in X ∣ y \sim x}$ is the set-builder notation of §1.1 Sets and Functions: “the set of all $y$ in $X$ such that $y \sim x .”)$

Two facts keep classes tidy. The first says that “same class” and “equivalent” are the same thing; the second says that classes never partly overlap.

A way of chopping a set into non-overlapping pieces has a name, and the theorem says that the classes are such a chopping.

So every equivalence relation gives a partition (its classes). The surprise is that it also works backwards, so that equivalence relations and partitions are really the same thing in two costumes (Hammack 2018, §11.4).

The next figure lets you choose a relation and paints each element with the colour of its class. Ignore the “Collapse” button for a moment; it is the subject of the next section.

The partition painter Choose a relation · tap a point to see its class · then collapse

x \sim y

exactly when

x

and

y

leave the same remainder on division by

3 .

Tap a number to see its class.

Z /3 = {[0], [1], [2]}

has 3 elements.

n 3

Figure 1.2.2 Three equivalence relations, each painting its set by classes: integers with the same remainder modulo

n

(try several

n),

marbles of the same colour, and lattice points at the same distance from

0 .

Tap any element to light up its whole class. Then press Collapse: each class flies together into a single point, and the arrows show where every element went — the projection

q

onto the quotient set

X / \sim .

The quotient set: one point per class

Here is the bold step. We have sorted $X$ into piles. Now we build a brand-new set whose elements are the piles themselves.

Two properties of $q$ follow at once, and between them they sum up everything so far.

$q$ is surjective: every class is the class of something (namely of any of its representatives).
$q (x) = q (y)$ exactly when $x \sim y .$ That is the lemma above, rewritten: the projection “forgets” precisely the differences we declared unimportant, and nothing else.

Look back at the partition painter and press Collapse. Each pile shrinks to a single point; the arrows that remain are $q .$ In the first mode you get $Z / n,$ sitting on a clock face. In the third mode the collapse has a geometric meaning: every lattice point swings round its circle to the positive $x$ -axis, so points at the same distance land on the same spot, and the quotient becomes a row of points on a ray, one per distance.

The hardest step, and how to take it

Researchers who study how people learn this material keep finding the same sticking point: students can compute a class as a list, but find it hard to treat the whole class as a single object that can itself be an element of a set, be added, or be fed into a function (Dubinsky et al. 1994). If that feels strange to you, you are in good company. Here are three ways to make it feel natural.

Sealed envelopes. Put each pile into an envelope and seal it. The quotient set is the set of envelopes. You can count envelopes, line them up, or hand one to a friend, without opening any of them — even if one contains infinitely many slips of paper.
Names on the outside. To refer to an envelope you write a name on it, and any slip inside will do: $[1],$ $[4]$ and $[- 2]$ are three labels for the same envelope. A label is not the envelope.
Positions on a clock. $Z /12$ is the set of 12 positions of a clock hand. The position “3 o’clock” is one thing, even though infinitely many hour-counts (3, 15, 27, −9, …) put the hand there.

Which picture is “right”? All of them, and good mathematicians switch between them constantly. What matters is knowing which operations are safe in which picture. Counting envelopes is always safe. Reading what is written on the label is not, because the same envelope carries many labels — and that danger is the subject of the well-definedness check below.

Fractions are classes

Here is an example you have used since childhood without knowing it was a quotient. A fraction is written with an integer on top and a nonzero integer on the bottom, so it is described by a pair $(a, b)$ with $b \neq = 0 .$ But different pairs describe the same fraction: $(1, 2),$ $(2, 4)$ and $(- 3, - 6)$ all describe one half. When do $(a, b)$ and $(c, d)$ describe the same fraction? When $\frac{a}{b} = \frac{c}{d},$ which — multiplying both sides by $b d$ — says $a d = b c .$ That condition involves no division at all, so we can use it as a definition.

The same up to rotation

For a final example, colour each corner of a square gold or violet. There are $2 \times 2 \times 2 \times 2 = 16$ colourings. But suppose the square is a necklace of four beads that can be turned: then a colouring and its rotations should count as the same necklace. “Can be turned into each other by a rotation” is an equivalence relation (turning by nothing is a rotation; a rotation can be undone by turning back; two rotations in a row make a rotation). How many different necklaces are there?

Same up to rotation Switch stages · tap a necklace to light up its class

Each corner is gold or violet: two choices at each of four corners make $2^{4} = 16$ colourings. Declare two colourings the same when a rotation turns one into the other.

Figure 1.2.3 The 16 colourings of a square’s corners, sorted into classes of colourings that differ by a rotation. The class sizes are

1, 4, 4, 2, 4, 1 :

a necklace with all beads alike has only itself in its class, and the alternating necklace has just two members. Collapsing each class to one point gives the quotient set: exactly 6 necklaces.

Notice that the classes have different sizes. Nothing in the definition requires classes to be the same size — only that they don’t overlap and that together they cover everything.

There is a way to get the answer 6 without drawing a single necklace. For each of the four rotations, count the colourings it leaves unchanged: turning by nothing fixes all $16,$ a quarter turn either way fixes only the $2$ one-colour necklaces, and a half turn fixes $4$ (opposite corners must match). The average, $(16 + 2 + 4 + 2) /4,$ is exactly $6 .$ That this always works is Burnside’s counting theorem, one of the first rewards of group theory, though this book will not need it (Judson 2025, §14.3).

Functions on classes: the well-definedness check

We now want to compute with classes, and the natural way is through representatives: to tell what a function does to a class, say what it does to a member of the class. But a class has many members. The rule had better give the same answer no matter which member you ask.

The name is a little misleading: “well-defined” does not mean “defined nicely.” It means “actually defined” — that the recipe, which secretly depended on a choice of representative, turns out not to depend on that choice. Whenever a mathematician defines something on classes using representatives, the very next sentence of the proof is the well-definedness check. (You met the word as a proof shape in §0.2 How to Read Mathematics.)

Ask every representative Pick a rule · change n · look for rose clashes

The rule

[x] \mapsto x mod 4

Z /6

[0]

−6 ↦

2

0 ↦

0

6 ↦

2

12 ↦

0

[1]

−5 ↦

3

1 ↦

1

7 ↦

3

13 ↦

1

[2]

−4 ↦

0

2 ↦

2

8 ↦

0

14 ↦

2

[3]

−3 ↦

1

3 ↦

3

9 ↦

1

15 ↦

3

[4]

−2 ↦

2

4 ↦

0

10 ↦

2

16 ↦

0

[5]

−1 ↦

3

5 ↦

1

11 ↦

3

17 ↦

1

Not well defined: $[0] = [- 6]$ in $Z /6,$ yet the representative $0$ gives $0$ while $- 6$ gives $2 .$

n (we work in ℤ/n) 6

Figure 1.2.4 A rule on

Z / n

given by a formula in a representative

x .

For each class we ask four representatives,

k - n, k, k + n, k + 2 n;

if they disagree, the class turns rose. Discover the pattern: “remainder mod

m ”

is well defined on

Z / n

exactly when

m

divides

n,

while

[x] \mapsto [2 x]

and

[x] \mapsto [x^{2}]

always work.

More checks

Fractions, badly. “The numerator of a fraction” is not well defined: $\frac{1}{2} = \frac{2}{4},$ but the numerators are $1$ and $2 .$ Neither is “add the top and the bottom”: $1 + 2 \neq = 2 + 4 .$ Both rules secretly depend on how the fraction is written.
Fractions, well. “The decimal value $a \div b ”$ is well defined: if $a d = b c$ then $a \div b = c \div d .$ So is the usual addition $\frac{a}{b} + \frac{c}{d} = \frac{a d + b c}{b d},$ although proving it takes a few lines (see the exercise “Adding fractions is well defined”).
Clock addition. On $Z / n$ define $[x] + [y] = [x + y] .$ If we change representatives, $x^{'} = x + k n$ and $y^{'} = y + ℓ n,$ then $x^{'} + y^{'} = (x + y) + (k + ℓ) n,$ which is congruent to $x + y .$ So the answer does not depend on the representatives: clock addition is well defined. This tiny check is what makes $Z / n$ into a number system with its own arithmetic, the subject of §1.3 Groups.

There is a tidy way to package the whole idea. A function $F : X \to Y$ that gives equal answers on equivalent elements is said to be constant on classes. Such a function “factors through” the quotient:

Read the theorem as a recipe for building functions on a quotient: find a function on the original set that ignores exactly the differences you declared unimportant, and it automatically becomes a function on the classes. This is how almost every function on a quotient in this book will be built, including the maps between homology groups in §3.5 Maps, Invariance, and First Triumphs.

Gluing: making shapes by declaring points the same

So far our quotients have been sets of numbers or necklaces. Now apply the same idea to the points of a shape, and something visual happens: declaring points the same glues them together.

An interval becomes a circle

Take the interval $I = [0, 1],$ all real numbers from $0$ to $1 .$ Declare the two endpoints the same, $0 \sim 1,$ and declare nothing else (every point is, of course, still the same as itself). The classes are

{0, 1} and {x} for each 0 < x < 1.

So the quotient $I / \sim$ has one point for the pair of endpoints and one point for each interior point. Picture a piece of string whose two ends are tied together: a loop. The quotient of an interval by “its ends are the same” is a circle.

Gluing the ends Play or scrub the gluing

The interval $[0, 1] .$ Every point is alone in its class: $0$ and $1$ are different points.

interval circle

Figure 1.2.5 Bending the interval changes nothing about which points are the same; only when the ends meet do

0

and

1

become a single point, and the interval becomes a circle. The marks

\frac{1}{4}, \frac{1}{2}, \frac{3}{4}

show that the points in between are untouched.

Winding the real line

Here is a second road to the circle. On the whole real line $R,$ declare two numbers the same when they differ by a whole number:

s \sim t ⟺ s - t \in Z .

(This is an equivalence relation for the same reasons as congruence: $0$ is a whole number, the negative of a whole number is a whole number, and so is the sum of two.) The class of $0.3$ is ${\dots, - 1.7, - 0.7, 0.3, 1.3, 2.3, \dots},$ often written $0.3 + Z .$ Every class has exactly one representative in $[0, 1),$ so you might think the quotient $R / Z$ “is” the interval $[0, 1) .$ But walk along $R$ from $0$ to $1 :$ when you reach $1,$ you are back in the class of $0 .$ The quotient closes up into a circle, just like the glued interval.

The figure below makes this visible by winding the line around a cylinder, one unit per turn, like a spring. Numbers in the same class sit directly above one another, on one vertical line. The projection $q$ drops every point straight down onto the floor, where its shadow traces a circle. The integers wound the same way, with $n$ points per turn, give $Z / n :$ exactly the clock face of the partition painter.

Winding the line Drag to rotate · change n or t · press Project

Integers $k$ and $k + 5$ sit on the same vertical line: they are one class of $Z /5 .$ Dropping every point straight down is the projection $q : Z \to Z /5 .$

n (points per turn) 5

Figure 1.2.6 The integers (or the real numbers) wound into a helix. Every class is a vertical “fibre”: in

Z

with

n = 5,

the integers

- 5, 0, 5

sit on one line above

[0] .

Pressing Project squashes the spring flat; what survives is one point per class — the circle

R / Z,

or the

n

points of

Z / n .

A square becomes a torus

Now take a filled square and glue its left side to its right side, point by point at the same height, and its bottom to its top, point by point at the same horizontal position. The left–right gluing alone rolls the square into a tube (a cylinder); the bottom–top gluing then joins the two ends of the tube into a doughnut surface — a torus. We will carry this out carefully, with pictures in three dimensions, in §2.2 Gluing Spaces Together. For now there is one subtle point that only equivalence relations can settle.

Our gluing instructions — “each left point is the same as the right point at the same height,” and so on — are a relation, but not an equivalence relation: they do not say that a point is the same as itself, and they are not transitive. We use the smallest equivalence relation that contains them, the one you get by adding everything the three rules force. (The “close it up” button in Figure 1.2.1 does exactly this.) Formally:

Now watch the corners. The bottom-left corner is glued to the bottom-right corner (left side to right side, at the bottom). It is also glued to the top-left corner (bottom to top, at the left). And the top-left corner is glued to the top-right corner. By transitivity, all four corners become a single point. A common mistake is to say the corners give two points, or four; the chain of gluings says one. Play Figure 1.2.7 and watch the corner count: four, then two once the sides $b$ are glued, then one.

A square becomes a torus Press play or drag the slider · drag the picture to turn it

The square. Points of the same colour will become one point.

corners: 4 points

p

: 2 points

q

: 2 points

square torus

Figure 1.2.7 Gluing the sides marked

a

to each other and the sides marked

b

to each other, matching the arrows. Rolling the sheet glues the

b

-sides together and bending it glues the

a

-sides; points of the same colour close in on each other and meet. The counts underneath are the classes, measured as the sheet moves: the two

p ’s

become one point, the two

q ’s

become one point, and the four corners become two points and then one, the point

v

of the torus where the loops

a

and

b

cross. (A preview of §2.2 Gluing Spaces Together.)

Why this is the most important idea in the book

One recipe has done all the work: declare some things the same, then treat each pile as a single new thing. Applied to numbers it gave clocks and fractions; to beads, necklaces; to the points of a square, a torus. Along the way we learned the one precaution it demands — check that nothing depends on which representative you picked. This recipe is the first of the four ideas that run through the whole book, and it returns in every part of it:

Arithmetic (§1.3 Groups and §1.4 Abelian Groups and Formal Sums): $Z / n$ gets its addition from the well-defined rule $[x] + [y] = [x + y],$ and every abelian group can be divided by a subgroup in the same way.
Shapes (§2.2 Gluing Spaces Together): cylinders, Möbius bands, tori, Klein bottles and projective planes are all quotients of a square by different gluing instructions.
Homology (§3.3 Homology Groups): a loop on a surface may or may not enclose a region. Two loops are declared the same when together they form the edge of a region between them. Set this beside congruence, where $x \equiv y (mod n)$ when $x - y$ is a multiple of $n :$ homology plays the same game with loops, and “differ by a multiple of $n ”$ becomes “differ by the edge of a region.” The piles of loops that result are the elements of the first homology group, and each pile — like $[1] \in Z /3$ — is one object with infinitely many names. The formula $H_{n} = Z_{n} / B_{n}$ at the centre of the book is this chapter’s $X / \sim$ with new letters.

When you get there, you will already know the moves: choose a representative, do the computation, and check that the answer does not depend on the choice.

One thing the recipe never provides is a way to decide whether two given things lie in the same pile. For remainders it is easy: divide and compare. For shapes it is the whole difficulty of topology, and the rest of the book builds tools for it. Even for finite, completely explicit objects it can be surprisingly hard.

Open problem Graph isomorphism in polynomial time

Open since the 1970s Asked since the 1970s

Is there an algorithm that decides whether two networks of $n$ dots are the same network with the dots relabelled, in a number of steps bounded by a fixed power of $n ?$

A network of dots and lines is the same as another “up to relabelling” if renaming the dots turns one into the other, and this is an equivalence relation. Counting the lines, or how many neighbours each dot has, can prove that two networks are different, but never that they are the same. That is exactly the position homology will be in for shapes.

What is known. In 2015 László Babai announced an algorithm that runs in quasi-polynomial time, roughly $n^{(l o g n)^{c}}$ steps: far faster than anything before, but not a fixed power of $n .$ In 2017 Harald Helfgott found a gap in one step; Babai repaired it within days, and Helfgott checked the repair. Graph isomorphism is believed not to be among the hardest problems in NP, which puts it in a rare middle ground.

A way in. Try colour refinement: colour all dots alike, then repeatedly recolour each dot by its old colour together with the list of its neighbours’ colours. If the two networks ever show different numbers of dots of some colour, they are different. Then find two different networks it cannot tell apart, such as a hexagon and a pair of triangles: an invariant can prove that two things differ, but never that they are the same.

(Babai 2016; Helfgott 2017) Status as of October 2026 All open problems

Exercises

Exercise Which are equivalence relations?

For each relation, decide whether it is an equivalence relation. If it is, describe its classes; if not, name a rule that fails and give a witness.

On English words: “has the same number of letters as.”
On $Z :$ $x \sim y$ if $x - y$ is even.
On $Z :$ $x \sim y$ if $x - y$ is odd.
On the positive integers: $x \sim y$ if $x$ divides $y .$
On $R :$ $x \sim y$ if $x^{2} = y^{2} .$

Hint

Look for “same answer to a question” relations: those are automatically equivalence relations.

Solution

Yes (“same answer to: how many letters?”). One class for each word length: all three-letter words form one class, and so on.
Yes; it is congruence modulo 2. Two classes: the even integers and the odd integers.
No. Not reflexive: $0 - 0 = 0$ is even, so $0 \neq \sim 0 .$ (Not transitive either: $0 \sim 1$ and $1 \sim 2,$ but $0 \neq \sim 2 .)$
No. Reflexive and transitive, but not symmetric: $1$ divides $2,$ but $2$ does not divide $1 .$
Yes (“same answer to: what is your square?”). The classes are ${0}$ and the pairs ${x, - x}$ for $x > 0 .$

Exercise The plane, wrapped twice

On $R^{2}$ declare $(x, y) \sim (x^{'}, y^{'})$ when $x - x^{'} \in Z$ and $y - y^{'} \in Z .$ Show that every class has exactly one representative in the half-open square $[0, 1) \times [0, 1) .$ Which points of the closed square $[0, 1] \times [0, 1]$ are equivalent to each other, and what does that suggest the quotient $R^{2} / \sim$ looks like?

Solution

Every real number $x$ can be written uniquely as $x = m + r$ with $m \in Z$ and $0 \leq r < 1$ (take $m$ to be the largest integer not exceeding $x).$ Doing this to both coordinates gives the unique representative $(r, s) \in [0, 1)^{2}$ of the class of $(x, y) .$ In the closed square, a point $(0, y)$ on the left side is equivalent to $(1, y)$ on the right side, a point $(x, 0)$ on the bottom to $(x, 1)$ on the top, and all four corners to each other. That is exactly the gluing of Figure 1.2.7: the quotient is a torus.

Exercise Every function is a quotient in disguise

Let $f : X \to Y$ be any function, and let $x \sim x^{'}$ mean $f (x) = f (x^{'}) .$ Show that the rule $f ˉ ([x]) = f (x)$ defines a well-defined function $f ˉ : X / \sim \to f (X),$ and that $f ˉ$ is a bijection onto the image $f (X) .$

Hint

Well-definedness is immediate from the definition of $\sim .$ For injectivity, use the lemma $[x] = [x^{'}] ⟺ x \sim x^{'} .$

Solution

Well defined: if $x \sim x^{'}$ then $f (x) = f (x^{'})$ by the very definition of $\sim .$ Surjective onto $f (X) :$ any element of $f (X)$ is $f (x) = f ˉ ([x])$ for some $x .$ Injective: if $f ˉ ([x]) = f ˉ ([x^{'}])$ then $f (x) = f (x^{'}),$ so $x \sim x^{'},$ so $[x] = [x^{'}] .$ Hence the quotient of $X$ by “same output” is in perfect one-to-one correspondence with the set of outputs. This little fact grows up into the First Isomorphism Theorem of §1.4 Abelian Groups and Formal Sums.

Summary

Recap

A relation on $X$ is a set of ordered pairs, $R \subseteq X \times X;$ we write $x \sim y$ for $(x, y) \in R .$
An equivalence relation is reflexive, symmetric and transitive — the three rules every notion of “the same” must obey. “Same answer to a question” relations, such as congruence modulo $n,$ are always equivalence relations.
The class $[x]$ collects everything equivalent to $x .$ Classes are equal or disjoint and cover $X :$ they form a partition, and partitions and equivalence relations are the same thing.
The quotient set $X / \sim$ has one element per class; the projection $q (x) = [x]$ is surjective and $q (x) = q (y) ⟺ x \sim y .$ A class is one element of the quotient, however many members it has.
A rule on classes given through representatives is well defined when equivalent representatives give equal answers; then it factors through $q .$
Gluing is taking a quotient of a shape: $[0, 1]$ with $0 \sim 1$ and $R / Z$ are circles, and a square with opposite sides glued is a torus (with all four corners becoming one point).

Equivalence and Quotients

Same, up to what?

Relations: a yes-or-no question about pairs

Three rules for sameness

The star example: same remainder

More examples

Non-examples, each failing exactly one rule

Classes and partitions

The quotient set: one point per class

The hardest step, and how to take it

Fractions are classes

The same up to rotation

Functions on classes: the well-definedness check

More checks

Gluing: making shapes by declaring points the same

An interval becomes a circle

Winding the real line

A square becomes a torus

Why this is the most important idea in the book

Exercises

Summary

Further reading

References