0.4 Equivalence relations and partitions

When we say two things are "the same for our purposes", we are using an equivalence relation. It always sorts the set into non-overlapping groups (a partition), and each group can then be treated as a single new object.

In school you were told that $\tfrac12$ and $\tfrac24$ are “the same number”, and that $2$ and $7$ are “the same” when you only care about remainders on dividing by $5$ . Each time, two different-looking objects are treated as one. This chapter says exactly when that is legitimate. A rule for “sameness” must satisfy three conditions, and when it does, the objects fall into non-overlapping groups, and the groups can be used as new objects. The groups are how fractions, clock arithmetic and (later) quotient spaces and quotient groups are built.

Before you start

0.3: sets, ordered pairs, functions, and bijections. 0.1 and 0.2 for negation and direct proof. Three quick checks.

Quick checkHow many ordered pairs are in

\{1, 2\} \times \{a, b, c\}

Quick checkTo DISPROVE 'for all

a

and

b

: if

a

is related to

b

then

b

is related to

a

', what must you give?

Quick checkIs

f: \mathbb Z \to \mathbb Z

f(n) = n + 1

a bijection?

The picture

Sort all the integers by their remainder on division by $3$ . Every integer lands in exactly one row, and no row is empty.

Group	Members
Remainder $0$	$\dots, -6, -3, 0, 3, 6, 9, \dots$
Remainder $1$	$\dots, -5, -2, 1, 4, 7, 10, \dots$
Remainder $2$	$\dots, -4, -1, 2, 5, 8, 11, \dots$

Two integers are in the same row exactly when they differ by a multiple of $3$ . That “differ by a multiple of $3$ ” rule is a notion of sameness, and the three rows are the groups it creates. The same picture works for the plane. Call two vectors “the same” when they have equal length, and the groups are circles centred at the origin: every vector lies on exactly one circle, and circles never overlap.

Where this came from· Gauss and the symbol for 'same up to a multiple'

In 1801, in his Disquisitiones Arithmeticae, Carl Friedrich Gauss introduced the notation $a \equiv b \pmod m$ for ” $m$ divides $a - b$ ”. His problem was to study the remainders of integers on division by a fixed number, and he needed a short way to say that two integers leave the same remainder. He wrote $\equiv$ rather than $=$ because of the analogy between this relation and equality: it can be added, multiplied and substituted like equality. Over the following century mathematicians saw that many other “sameness” rules behave like this one, and the abstract notion of equivalence relation, with its three conditions, is the common core.

The idea, in words

Why· Why we group things at all

Often a question does not care about every detail of an object. A clock shows $14{:}00$ and $2$ pm as the same time. A fraction $\tfrac24$ and $\tfrac12$ name the same quantity. A probability question might only care which of the outcomes of two dice have the same sum. Whenever that happens, we want to replace the many objects with one object per group, and compute with groups instead.

That only works if the sameness rule is well behaved. If $a$ is “the same as” $b$ , then $b$ must be the same as $a$ (otherwise whose view is it?). Everything is the same as itself. And if $a$ is the same as $b$ and $b$ the same as $c$ , then $a$ is the same as $c$ , or the groups would chain and merge. These three conditions are precisely the rules for a group of mutually “same” things to exist.

Definitions and theorems

Definition B

Relation

A relation on a set $A$ is a subset $R \subseteq A \times A$ . We write $a \sim b$ (or $a\,R\,b$ ) when $(a, b) \in R$ , and say ” $a$ is related to $b$ ”. For example, on $\mathbb Z$ the relation " $<$ " is the set of all pairs $(a, b)$ with $a$ less than $b$ .

In one lineA relation on a set $A$ is a rule that says, for each ordered pair $(a, b)$ , whether $a$ is related to $b$ ; formally, a subset of $A \times A$ .

Why it exists'Less than', 'divides', 'is parallel to' and 'has the same remainder as' are all relations; one definition covers them all.

Order matters: $a \sim b$ and $b \sim a$ are different claims. Three properties a relation may have are the whole subject. For a relation $\sim$ on $A$ :

Reflexive: $\forall a \in A:\ a \sim a$ . (Everything is related to itself.)
Symmetric: $\forall a, b \in A:\ a \sim b \Rightarrow b \sim a$ . (Relatedness goes both ways.)
Transitive: $\forall a, b, c \in A:\ (a \sim b \land b \sim c) \Rightarrow a \sim c$ . (Relatedness chains.)

By the negation rules of 0.1, a relation fails to be reflexive when some $a$ has $a \not\sim a$ ; fails to be symmetric when some $a, b$ have $a \sim b$ but $b \not\sim a$ ; and fails to be transitive when some $a, b, c$ have $a \sim b$ and $b \sim c$ but $a \not\sim c$ . Each failure is shown by a single counterexample.

Definition B

Equivalence relation

A relation $\sim$ on $A$ is an equivalence relation if it is reflexive, symmetric and transitive.

In one lineA relation that is reflexive, symmetric and transitive: a valid rule for 'the same for our purposes'.

Why it existsThese three properties are exactly what is needed for things to fall into non-overlapping groups of mutually equivalent objects.

Worked example Hammack 11.2

Which of these relations on

\mathbb Z

are equivalence relations? (i)

a \sim b

iff

a - b

is even. (ii)

a \sim b

iff

\lvert a - b \rvert \le 1

. (iii)

a \sim b

iff

a \le b

Solution.

(i) Reflexive. $a - a = 0 = 2 \cdot 0$ is even. Every integer differs from itself by $0$ .
(i) Symmetric. If $a - b = 2k$ , then $b - a = 2(-k)$ is even. The negative of an even number is even.
(i) Transitive. If $a - b = 2k$ and $b - c = 2l$ , then $a - c = (a - b) + (b - c) = 2(k + l)$ is even. The telescoping trick: add the two differences. This is a proof for arbitrary $a, b, c$ , not for chosen numbers.
(ii) Not transitive. $0 \sim 1$ and $1 \sim 2$ , but $\lvert 0 - 2 \rvert = 2 > 1$ , so $0 \not\sim 2$ . One counterexample to transitivity is enough. (It is reflexive and symmetric, so only transitivity fails.)
(iii) Not symmetric. $1 \le 2$ but $2 \not\le 1$ . A counterexample to symmetry. It is reflexive and transitive but that is not enough.

Answer. Only (i) is an equivalence relation. The failures in (ii) and (iii) are different, and each needs only one counterexample.

Quick checkOn

\mathbb R

, define

x \sim y

iff

xy \ge 0

. Which property fails?

Quick checkOn

A = \{1, 2, 3\}

let

R = \{(1,1), (2,2), (1,2), (2,1)\}

. Which property fails?

The same remainder, the same length

Worked example Hammack 11.2

Show that

a \sim_n b

iff

n \mid (a - b)

is an equivalence relation on

\mathbb Z

, for a fixed positive integer

n

. Then describe the classes for

n = 5

Here $n \mid m$ (” $n$ divides $m$ ”) means $m = nk$ for some integer $k$ . Chapter 0.5 studies divisibility properly and gives this relation its usual name, congruence mod $n$ .

Solution.

Reflexive. $a - a = 0 = n \cdot 0$ , so $n \mid (a - a)$ . Zero is a multiple of everything.
Symmetric. If $a - b = nk$ then $b - a = n(-k)$ . The negative of a multiple of $n$ is a multiple of $n$ .
Transitive. If $a - b = nk$ and $b - c = nl$ , then $a - c = n(k + l)$ . Add the two equations.
Describe the classes for $n = 5$ . The integers $2, 7, 12, -3, -8, \dots$ all differ from $2$ by multiples of $5$ , so they form one group: all numbers of the form $2 + 5k$ . There are five such groups, one for each possible remainder $0, 1, 2, 3, 4$ . Two integers are related exactly when they leave the same remainder (0.5 proves this using the division algorithm).

Answer. $\sim_n$ is an equivalence relation. For $n = 5$ it sorts $\mathbb Z$ into five groups, for example $\{\dots, -8, -3, 2, 7, 12, \dots\}$ .

Many sameness rules in mathematics have the shape “the same value of some function”. That shape is always an equivalence relation, and we will see that every equivalence relation has it.

Proposition B

Same value is an equivalence relation

Let $f: A \to B$ be a function. Define $a \sim_f b$ to mean $f(a) = f(b)$ . Then $\sim_f$ is an equivalence relation on $A$ .

In one lineFor any function $f: A \to B$ , the relation $a \sim b$ iff $f(a) = f(b)$ is an equivalence relation on $A$ .

Why it is trueIt inherits reflexivity, symmetry and transitivity from equality of values in $B$ .

Proofstandard

The idea: Each property of ~ is the same property of equality, applied to the values f(a), f(b), f(c).

Reflexive:

f(a) = f(a)

, so

a \sim_f a

Equality is reflexive: any value equals itself.

Symmetric: if

f(a) = f(b)

then

f(b) = f(a)

, so

b \sim_f a

Equality is symmetric.

Transitive: if

f(a) = f(b)

and

f(b) = f(c)

, then

f(a) = f(c)

, so

a \sim_f c

Equality is transitive.

Examples: on vectors in the plane, $f(v) = \lVert v \rVert$ gives “same length”, with the circles as groups. On lines in the plane, $f(\ell) =$ the direction of $\ell$ (its angle with the $x$ -axis, at least $0$ and less than $\pi$ ) gives “parallel”, where a line counts as parallel to itself. On $\mathbb Z$ , $f(a) =$ the remainder of $a$ on division by $n$ gives $\sim_n$ .

Equivalence classes

Definition B

Equivalence class

Let $\sim$ be an equivalence relation on $A$ . The equivalence class of $a \in A$ is $[a] = \{x \in A : x \sim a\}$ . An element of a class is called a representative of it. The set of all classes is the quotient set $A / {\sim}$ .

In one lineThe equivalence class $[a]$ of $a$ is the set of everything related to $a$ .

Why it existsIt is the 'group' that $a$ belongs to, and it is the object we compute with when we treat related things as one.

For $\sim_5$ on $\mathbb Z$ : $[2] = \{\dots, -8, -3, 2, 7, 12, \dots\}$ and $[7] = [2]$ : the same class has many names, any of its members. The main fact is that the classes behave as the picture suggests, with no overlaps.

Quick checkFor

\sim_5

\mathbb Z

(differ by a multiple of

5

), which statement is false?

Lemma B

Equal classes

Let $\sim$ be an equivalence relation on $A$ and $a, b \in A$ . The following are equivalent:

$a \sim b$ ;
$[a] = [b]$ ;
$[a] \cap [b] \ne \varnothing$ .

In one lineFor an equivalence relation, $a \sim b$ exactly when $[a] = [b]$ , exactly when $[a]$ and $[b]$ share at least one element.

Why it is trueRelatedness lets you move between members of a group without leaving it, so groups that touch are the same group.

ProofHammack Thm 11.1

The idea: Prove 1 implies 2 implies 3 implies 1 in a circle. Each step moves along relations using symmetry and transitivity.

(1 implies 2.) Assume

a \sim b

. Let

x \in [a]

, so

x \sim a

Show

[a] \subseteq [b]

by double inclusion (0.3). Let

x \in [a]

. By the definition of class,

x \sim a

Then

x \sim b

, so

x \in [b]

. Hence

[a] \subseteq [b]

Transitivity applied to

x \sim a

and

a \sim b

Since

b \sim a

by symmetry, the same argument gives

[b] \subseteq [a]

. So

[a] = [b]

Symmetry turns the assumption

a \sim b

into

b \sim a

. Now repeat the argument with the roles swapped.

(2 implies 3.) The element

a

lies in

[a]

and in

[b]

, so

[a] \cap [b] \ne \varnothing

Reflexivity:

a \sim a

, so

a \in [a]

. If

[a] = [b]

, then

a \in [b]

as well.

Assume the classes share an element

z

(3 implies 1.) Pick

z \in [a] \cap [b]

. By the definition of class,

z \sim a

and

z \sim b

Then

a \sim b

Symmetry gives

a \sim z

. Transitivity applied to

a \sim z

and

z \sim b

gives

a \sim b

Definition B

Partition

A partition of a set $A$ is a collection of subsets of $A$ , called blocks, such that:

every block is non-empty;
any two different blocks are disjoint (have no element in common);
every element of $A$ lies in some block.

Equivalently, every element of $A$ lies in exactly one block.

In one lineA way of cutting a set into non-empty, non-overlapping pieces (called blocks) that together cover the whole set.

Why it existsIt is the 'sorted into rows' picture, and it is the same information as an equivalence relation.

Quick checkWhich is a partition of

\{1, 2, 3\}

Now the main theorem. Equivalence relations and partitions are the same thing seen in two ways.

Theorem B Hammack Thm 11.1

Equivalence classes partition the set

If $\sim$ is an equivalence relation on $A$ , then the set of equivalence classes is a partition of $A$ .

In one lineThe equivalence classes of an equivalence relation on $A$ form a partition of $A$ .

Why it is trueEvery element is in its own class, and two classes that touch are equal.

ProofHammack Thm 11.1

The idea: Check the three conditions of a partition. The first two come from reflexivity and the last is the lemma 'touching classes are equal'.

Every class is non-empty, because

a \in [a]

Reflexivity:

a \sim a

for every

a

, so

a \in [a]

Every element of

A

lies in some class.

The same fact: each element

a

belongs to at least one class, namely its own.

Two classes are either equal or disjoint.

Suppose two classes

[a]

and

[b]

are not disjoint, so

[a] \cap [b] \ne \varnothing

. The lemma 'equal classes', direction 3 implies 2, then gives

[a] = [b]

So any two different classes are disjoint, and the three conditions of a partition hold.

'Two different classes are disjoint' is the contrapositive of the previous line.

Proof workshopRebuild: two equivalence classes are equal or disjoint

Tap the lines in the order a proof would write them. Each line can only use what is already above it.

The converse also holds: a partition always comes from an equivalence relation.

Theorem B Hammack Thm 11.2

Partitions give equivalence relations

Let $\mathcal P$ be a partition of $A$ . Define $a \sim b$ to mean that $a$ and $b$ lie in a common block of $\mathcal P$ . Then $\sim$ is an equivalence relation on $A$ , and its equivalence classes are exactly the blocks of $\mathcal P$ .

In one lineGiven a partition of $A$ , 'lying in the same block' is an equivalence relation whose classes are exactly the blocks.

Why it is trueA partition puts each element in exactly one block, and that is what makes 'same block' reflexive, symmetric and transitive.

ProofHammack Thm 11.2

The idea: Reflexivity needs a block for each element, which is the covering condition. Transitivity is where disjointness is used: the middle element b lies in only one block.

Reflexive: for

a \in A

a

and

a

lie in the same block.

Every element lies in some block (condition 3 of a partition), and it lies in that block together with itself.

Symmetric: if

a, b

lie in a block

B

, then

b, a

lie in

B

'Lie in a common block' does not depend on the order of

a

and

b

Transitive: if

a \sim b

and

b \sim c

, the two blocks involved both contain

b

, so they are the same block

B

Say

a, b \in B_1

and

b, c \in B_2

. Then

b \in B_1 \cap B_2

. Blocks are either equal or disjoint (condition 2), and these are not disjoint, so

B_1 = B_2

Hence

a

and

c

lie in a common block, and

a \sim c

Both

a

and

c

lie in that single block

B

The class

[a]

is exactly the block containing

a

, so the classes are the blocks.

Let

B

be the block containing

a

(exactly one exists). Then

x \sim a

iff

x

lies in a block with

a

, and that block must be

B

since

a

is in only one block.

Together these two theorems say that equivalence relations on $A$ and partitions of $A$ correspond exactly: from a relation take its classes, from a partition take ‘same block’, and each undoes the other. (Starting from $\sim$ , the new relation says $a$ and $b$ are in the same class, which by the lemma holds iff $a \sim b$ . Starting from a partition, the classes of the new relation are the original blocks.)

Worked example

List the classes of 'same remainder on division by 4' on

\{1, 2, \dots, 10\}

and count the ordered pairs in the relation.

Solution.

Find each element’s remainder. The remainders of $1, 2, \dots, 10$ on division by $4$ are $1, 2, 3, 0, 1, 2, 3, 0, 1, 2$ . Two numbers are related exactly when their remainders match, so the remainder is the label of the class.
Group by remainder. Remainder $1$ : $\{1, 5, 9\}$ . Remainder $2$ : $\{2, 6, 10\}$ . Remainder $3$ : $\{3, 7\}$ . Remainder $0$ : $\{4, 8\}$ . These four groups are non-empty, disjoint, and cover $\{1, \dots, 10\}$ , so they form a partition, as the theorem promises.
Count the pairs inside each class. A class of size $k$ contributes $k^2$ ordered pairs, because every member is related to every member, including itself. So $3^2 + 3^2 + 2^2 + 2^2 = 26$ . Pairs from different classes are never related, so nothing else is counted.

Answer. Four classes, and $26$ ordered pairs in the relation.

Your answerOn

\{1, 2, \dots, 10\}

, how many ordered pairs

(a, b)

are related by 'same remainder on division by

5

Worked example

List all equivalence relations on

\{1, 2, 3\}

Solution.

Translate to partitions. By the correspondence, counting equivalence relations is counting partitions of $\{1, 2, 3\}$ . Each partition gives exactly one relation, and each relation exactly one partition.
List them by block shapes. One block: $\{1, 2, 3\}$ . A block of two and a block of one: $\{1, 2\} \mid \{3\}$ , $\{1, 3\} \mid \{2\}$ , $\{2, 3\} \mid \{1\}$ . Three blocks of one: $\{1\} \mid \{2\} \mid \{3\}$ . Choosing which element is alone gives the three shapes of type 2 + 1.
Count. $1 + 3 + 1 = 5$ . Sum over the shapes.
Check one relation. The partition $\{1, 2\} \mid \{3\}$ gives the pairs $(1,1), (1,2), (2,1), (2,2), (3,3)$ , which is $2^2 + 1^2 = 5$ pairs. A block of size $k$ contributes $k^2$ ordered pairs, since every element of the block is related to every element of the block.

Answer. There are $5$ equivalence relations on a 3-element set. As a cross-check, there are $2^9 = 512$ relations on $\{1,2,3\}$ (each of the $9$ ordered pairs is in or out), and exactly $5$ of them are reflexive, symmetric and transitive. On a 4-element set there are $15$ .

Your answerHow many equivalence relations on

\{1, 2, 3, 4\}

have exactly two classes?

Worked example

The relation

a \sim b

iff

a^2 = b^2

\mathbb Z

is an equivalence relation. Find its classes. Then find a partition of

\mathbb R

whose relation is

x \sim y

iff

\lfloor x \rfloor = \lfloor y \rfloor

Solution.

Recognise the shape. $a \sim b$ iff $f(a) = f(b)$ for $f(a) = a^2$ , so it is an equivalence relation by ‘same value is an equivalence relation’. No separate check of the three properties is needed.
Find the classes. $[a] = \{b : b^2 = a^2\} = \{a, -a\}$ . So $[0] = \{0\}$ , $[1] = \{1, -1\}$ , $[2] = \{2, -2\}$ , and so on. $b^2 = a^2$ means $b = \pm a$ .
Check it is a partition. Every integer is in exactly one of $\{0\}, \{\pm 1\}, \{\pm 2\}, \dots$ . The classes of an equivalence relation always form a partition.
The second relation. Floor $\lfloor x \rfloor$ is the greatest integer at most $x$ . The classes are the intervals $[n, n + 1)$ for $n \in \mathbb Z$ (for example $\lfloor 2.7 \rfloor = 2 = \lfloor 2.0 \rfloor$ , so $2.7 \sim 2.0$ ). Same floor means the same integer part, so the numbers lie in the same interval $[n, n+1)$ .

Answer. The classes of the first are the pairs $\{a, -a\}$ and $\{0\}$ . The intervals $[n, n+1)$ partition $\mathbb R$ , and they come from “same floor”.

Your answerThe relation

a \sim b

iff

a^2 = b^2

is applied to the integers

-5, -4, \dots, 4, 5

. How many equivalence classes are there?

Worked example

\mathbb R^2

define

(x_1, y_1) \sim (x_2, y_2)

iff

y_1 - 2x_1 = y_2 - 2x_2

. Show it is an equivalence relation and describe its classes.

Solution.

Recognise the shape. Let $f(x, y) = y - 2x$ . Then $(x_1, y_1) \sim (x_2, y_2)$ iff $f(x_1, y_1) = f(x_2, y_2)$ . The relation is “same value of a function”, so the proposition above gives reflexive, symmetric and transitive at once.
Describe one class. The class of $(x_0, y_0)$ is $\{(x, y) : y - 2x = c\}$ where $c = y_0 - 2x_0$ . This is the line $y = 2x + c$ of slope $2$ . A class is everything with the same value of $f$ .
Check the partition picture. Every point $(x, y)$ lies on exactly one such line, the one with $c = y - 2x$ . This is the theorem on classes in action: the lines are non-empty, cover the plane, and never overlap.

Answer. An equivalence relation whose classes are all the lines of slope $2$ , one for each real number $c$ .

Worked example

Prove: if

\sim

and

\approx

are equivalence relations on

A

, then so is

\mathrel{R}

, defined by

a \mathrel R b

iff (

a \sim b

and

a \approx b

Solution. The plan: check the three properties, using the same property of each of the two relations.

Reflexive. For $a \in A$ : $a \sim a$ and $a \approx a$ , so $a \mathrel R a$ . Both relations are reflexive.
Symmetric. If $a \mathrel R b$ then $a \sim b$ and $a \approx b$ . So $b \sim a$ and $b \approx a$ , that is $b \mathrel R a$ . Both relations are symmetric, and we apply that to each half of the “and”.
Transitive. If $a \mathrel R b$ and $b \mathrel R c$ , then $a \sim b$ , $b \sim c$ , $a \approx b$ , $b \approx c$ . So $a \sim c$ and $a \approx c$ , that is $a \mathrel R c$ . Transitivity of $\sim$ gives the first, and transitivity of $\approx$ gives the second.

Answer. $\mathrel R$ is an equivalence relation. The same argument fails for “or” in place of “and”, because transitivity needs the chain $a \sim b$ , $b \approx c$ to give something.

A function is a bijection from its classes to its range

Every equivalence relation is a “same value” relation: the function $\pi: A \to A / {\sim}$ , $\pi(a) = [a]$ , has $\pi(a) = \pi(b)$ iff $[a] = [b]$ iff $a \sim b$ by the lemma. The reverse is the next theorem, and it is the set-level shadow of three results later in the book: rank–nullity (2.3), isomorphism theorems (541), and quotient topology (551).

Theorem B

A function is a bijection from its classes onto its range

Let $f: A \to B$ and let $\sim$ be ‘same value’. Then $\bar f: A / {\sim} \to f(A)$ , $\bar f([a]) = f(a)$ , is a well-defined bijection.

In one lineFor $f: A \to B$ with $a \sim b$ iff $f(a) = f(b)$ , the rule $[a] \mapsto f(a)$ is a well-defined bijection from $A / {\sim}$ onto the range $f(A)$ .

Why it is trueGrouping the inputs that $f$ cannot tell apart leaves exactly one group per output.

Proofstandard

The idea: Well-defined: the output must not depend on which representative you use. Injective and surjective are both quick.

Well-defined: if

[a] = [a']

, then

a \sim a'

by the lemma, so

f(a) = f(a')

. The value

\bar f([a])

does not depend on the representative.

A rule defined using a representative is a legitimate function only if a different representative of the same class gives the same answer. This is the check that matters whenever we define something on classes.

Injective: if

\bar f([a]) = \bar f([a'])

, then

f(a) = f(a')

Template for injective: assume equal outputs.

a \sim a'

, hence

[a] = [a']

That says

a \sim a'

, and then the lemma gives equal classes.

Surjective: if

y \in f(A)

, then

y = f(a)

for some

a

, and

y = \bar f([a])

Template for surjective onto the range: every element of

f(A)

has the form

f(a)

Fractions as classes

Here is the example the whole chapter was building toward, and it answers the question “why is $\tfrac12 = \tfrac24$ ?” The answer is a definition that we choose, and no fact about numbers is discovered.

Start with the set $A = \mathbb Z \times (\mathbb Z \setminus \{0\})$ of pairs $(a, b)$ (“the numerator $a$ over the denominator $b$ ”). We want $(1, 2)$ and $(2, 4)$ to count as the same. The school rule says $\tfrac ab = \tfrac cd$ when $ad = bc$ (cross-multiplication). Define

(a, b) \sim (c, d) \quad\text{iff}\quad ad = bc.

Worked example Hammack 11.2

Show that

(a, b) \sim (c, d)

iff

ad = bc

is an equivalence relation on

\mathbb Z \times (\mathbb Z \setminus \{0\})

, and explain why

\tfrac12 = \tfrac24

Solution.

Reflexive. $(a, b) \sim (a, b)$ because $ab = ba$ . Multiplication of integers is commutative.
Symmetric. If $ad = bc$ , then $cb = da$ , which says $(c, d) \sim (a, b)$ . Swap the sides of the equation and reorder the products.
Transitive, setting up. Suppose $(a, b) \sim (c, d)$ and $(c, d) \sim (e, f)$ , so $ad = bc$ and $cf = de$ . We must show $af = be$ . That is what $(a, b) \sim (e, f)$ means.
Transitive, the algebra. Multiply the first equation by $f$ to get $adf = bcf$ . Now $bcf = b(cf) = b(de)$ by the second equation. So $d(af) = d(be)$ . Two substitutions chain the equations together. The middle pair $(c, d)$ drops out.
Cancel. Since $d \ne 0$ , we may cancel $d$ and get $af = be$ . In $\mathbb Z$ , a product $dx = dy$ with $d \ne 0$ forces $x = y$ . This is where “denominator not zero” is used, and why transitivity would fail if $(0, 0)$ were allowed.
The meaning. $(1, 2) \sim (2, 4)$ because $1 \cdot 4 = 2 \cdot 2$ . By the lemma on equal classes, $[(1, 2)] = [(2, 4)]$ . The lemma says related pairs have equal classes.

Answer. $\sim$ is an equivalence relation. A rational number $\tfrac ab$ is, by definition, the class $[(a, b)]$ , so $\tfrac12$ and $\tfrac24$ are two names for one class. The statement " $\tfrac12 = \tfrac24$ " is the statement $(1,2) \sim (2,4)$ , which is true.

Proof workshopRebuild: transitivity of the fraction relation

Tap the lines in the order a proof would write them. Each line can only use what is already above it.

Your answerUnder the rule

(a, b) \sim (c, d)

iff

ad = bc

, the pair

(3, 5)

is related to

(x, 20)

. What is

x

Once rational numbers are classes, arithmetic on them must be defined using representatives, and then we must check the result does not depend on which representatives we picked. This is exactly the well-definedness check of the previous theorem.

Worked example

Define

[(a, b)] + [(c, d)] = [(ad + bc,\ bd)]

. Show that the sum does not depend on the representatives.

Solution.

State what must be shown. Suppose $(a, b) \sim (a', b')$ , that is $ab' = a'b$ . We must show $(ad + bc,\ bd) \sim (a'd + b'c,\ b'd)$ . If we replace one summand by another name for the same class, the answer must name the same class.
Write out what the relation requires. We need $(ad + bc)(b'd) = (a'd + b'c)(bd)$ . This is the cross-multiplication rule for the two answers. Denominators $bd$ and $b'd$ are nonzero since a product of nonzero integers is nonzero.
Expand the left side. $(ad + bc)(b'd) = ab'd^2 + bb'cd$ . Distribute.
Expand the right side. $(a'd + b'c)(bd) = a'bd^2 + bb'cd$ . Distribute.
Compare. The terms $bb'cd$ are identical, and $ab'd^2 = a'bd^2$ because $ab' = a'b$ . This is the only place the hypothesis is used.

Answer. The sum is well defined in the first summand. The formula is symmetric in the two summands (swapping them gives $(cb + da,\ db)$ , which is the same pair because addition and multiplication of integers are commutative), so it is well defined in the second summand too. Multiplication $[(a,b)][(c,d)] = [(ac, bd)]$ is checked the same way, and is shorter: $ab' = a'b$ gives $(ac)(b'd) = (a'c)(bd)$ by multiplying both sides by $cd$ .

Why· The picture behind 'well-defined'

A class is a room with many doors (its representatives). A rule on classes that is stated using a door must give the same answer whichever door you use. If you define $g([a])$ as “the number of letters in the word the fraction is written with”, the rule is nonsense, because $\tfrac12$ and $\tfrac24$ are the same class with different numbers of digits. The check in the previous example is the proof that addition is not like that.

Quick checkDefine

g: \mathbb Q \to \mathbb Z

g(\tfrac ab) = a + b

. Is

g

well defined?

Where it is used

Used inside maths· Inside maths: quotient objects, and building number systems

Declaring things equivalent and passing to classes is one of the main constructions in mathematics. The integers can be built from pairs of counting numbers $(a, b)$ meaning " $a - b$ ", with $(a, b) \sim (c, d)$ iff $a + d = b + c$ . The real numbers can be built as classes of sequences of rationals that get arbitrarily close, where two sequences are equivalent when their difference tends to $0$ . The next chapter turns the relation $\sim_n$ into the number system $\mathbb Z_n$ . In linear algebra (chapter 3.7) a subspace $W$ of $V$ defines $v \sim w$ iff $v - w \in W$ , and the classes form the quotient space $V / W$ . The theorem above, with $f$ a linear map and $W$ its null space, becomes $V / N(T) \cong T(V)$ , which is rank–nullity in disguise. Quotient groups $G / H$ (MATH 541) use the same recipe with a subgroup $H$ .

A preview· Preview: a plane modulo a line

In $\mathbb R^2$ let $W$ be the line $y = 0$ (the $x$ -axis), and say $v \sim w$ iff $v - w$ lies on $W$ . Two vectors are related when they have the same $y$ -coordinate, so the classes are the horizontal lines, and the quotient $\mathbb R^2 / W$ is “the set of horizontal lines”, which can be labelled by one number, the height. The plane has dimension $2$ , the line has dimension $1$ , and the quotient has dimension $2 - 1 = 1$ . This is the picture behind chapter 3.7.

Used in the real world· Computer science: union-find, state minimisation, normalisation

The data structure union-find (disjoint sets) maintains a partition of $\{1, \dots, N\}$ under two operations, “merge the classes of $i$ and $j$ ” and “are $i$ and $j$ in the same class?”. Start with 8 elements, each alone: eight classes. After merging $1,2$ , then $3,4$ , then $2,4$ , then $5,6$ , the classes are $\{1,2,3,4\}$ , $\{5,6\}$ , $\{7\}$ , $\{8\}$ : four classes of sizes $4, 2, 1, 1$ , and $4^2 + 2^2 + 1 + 1 = 22$ related ordered pairs. Kruskal’s algorithm for a minimum spanning tree adds an edge only if its endpoints are in different classes, which stops it from creating a cycle. Type inference in compilers uses the same structure to merge type variables that must be equal. The minimal automaton of a regular language is built by merging states that no input string can tell apart, which is an equivalence relation on states (the Myhill and Nerode theorem describes these classes). Even email follows the pattern: Gmail ignores dots in the part before the @, so first.last and firstlast at gmail.com are equivalent addresses and name one inbox.

Traps

Watch out· Symmetric and transitive do not give reflexive

The tempting “proof” is: if $a \sim b$ then $b \sim a$ , and then $a \sim b$ with $b \sim a$ gives $a \sim a$ . It assumes $a$ has some $b$ to be related to. On $A = \{1, 2\}$ take only the pair $(1, 1)$ : it is symmetric and transitive, but $2 \not\sim 2$ . Always check reflexivity separately.

Watch out· Classes never partly overlap

Two equivalence classes are equal or disjoint. If you find a relation where two groups share some elements but not all, then it is not transitive (or not symmetric), and it is not an equivalence relation. The relation $|a - b| \le 1$ in the first example is exactly like that.

Watch out· A rule on classes must be checked for well-definedness

Whenever you define a function on classes using a representative, show the answer does not depend on the choice. The sum of fractions passes. “Numerator plus denominator” does not.

Watch out· Many names for one class

$[2] = [7] = [-3]$ for $\sim_5$ . Writing $[2] \ne [7]$ is a mistake. The fraction $\tfrac12$ is not “the” pair $(1, 2)$ but the whole class, and $(2, 4)$ is another name for it.

Watch out· 'Parallel' needs a definition that includes equal lines

If “parallel” means “never meets”, a line is not parallel to itself, so reflexivity fails. Define $\ell \parallel m$ as “equal, or never meeting” (equivalently “same direction”) and it becomes an equivalence relation.

Problems

check

Is ” $a$ divides $b$ ” an equivalence relation on the positive integers? Prove or give a counterexample for each property.

Solution

Reflexive: $a = a \cdot 1$ , so $a \mid a$ . Transitive: if $b = ak$ and $c = bl$ then $c = a(kl)$ . Not symmetric: $2 \mid 4$ but $4 \nmid 2$ . So it is not an equivalence relation.

check

On $\mathbb R$ let $x \sim y$ iff $x - y \in \mathbb Z$ . Is it an equivalence relation? Describe $[0.3]$ .

Solution

Reflexive: $x - x = 0 \in \mathbb Z$ . Symmetric: if $x - y \in \mathbb Z$ then $y - x \in \mathbb Z$ . Transitive: $(x - y) + (y - z) = x - z$ , a sum of integers. Yes. $[0.3] = \{0.3 + k : k \in \mathbb Z\} = \{\dots, -1.7, -0.7, 0.3, 1.3, 2.3, \dots\}$ . Each class has exactly one member in $[0, 1)$ .

check

Which of these are partitions of $\{1, 2, 3, 4\}$ ? (a) $\{1, 3\}, \{2, 4\}$ . (b) $\{1, 2, 3\}, \{3, 4\}$ . (c) $\{1\}, \{2\}, \{3\}$ .

Solution

(a) Yes. (b) No: $3$ lies in two blocks. (c) No: $4$ lies in no block.

use

List the classes of “same remainder on division by $4$ ” on $\{1, 2, \dots, 10\}$ , and count the ordered pairs in the relation.

Solution

Classes: $\{1, 5, 9\}$ , $\{2, 6, 10\}$ , $\{3, 7\}$ , $\{4, 8\}$ . A block of size $k$ gives $k^2$ ordered pairs, so $9 + 9 + 4 + 4 = 26$ pairs.

use

On $\mathbb R^2$ define $(x_1, y_1) \sim (x_2, y_2)$ iff $x_1 + y_1 = x_2 + y_2$ . Show it is an equivalence relation and describe the classes geometrically.

Solution

It is “same value” for $f(x, y) = x + y$ , so it is an equivalence relation by the proposition. The class of $(x_0, y_0)$ is the line $x + y = x_0 + y_0$ , a line of slope $-1$ . The classes are all the lines of slope $-1$ , one for each value of $x + y$ , and they partition the plane.

use

Show that multiplication $[(a,b)] \cdot [(c,d)] = [(ac, bd)]$ of fractions is well defined in the first factor.

Solution

Suppose $(a, b) \sim (a', b')$ , so $ab' = a'b$ . We need $(ac, bd) \sim (a'c, b'd)$ , that is $(ac)(b'd) = (a'c)(bd)$ . The left side is $(ab')cd$ and the right side is $(a'b)cd$ , equal because $ab' = a'b$ . Also $bd \ne 0$ and $b'd \ne 0$ since the integers are nonzero.

prove

Let $\sim$ and $\approx$ be equivalence relations on $A$ , and let $a \mathrel{R} b$ mean ( $a \sim b$ and $a \approx b$ ), an equivalence relation by the worked example. Prove that $[a]_R = [a]_\sim \cap [a]_\approx$ . Then deduce: if $\sim$ has $3$ classes and $\approx$ has $2$ classes, then $R$ has at most $6$ classes.

Solution

For the classes: $x \in [a]_R$ iff $x \mathrel R a$ iff ( $x \sim a$ and $x \approx a$ ) iff ( $x \in [a]_\sim$ and $x \in [a]_\approx$ ) iff $x \in [a]_\sim \cap [a]_\approx$ . For the count, every class of $R$ is $C \cap D$ for one of the $3$ classes $C$ of $\sim$ and one of the $2$ classes $D$ of $\approx$ , and there are only $3 \cdot 2 = 6$ such choices. Some of the intersections may be empty, which is why the number of classes can be smaller than $6$ .

prove

Give an example of two equivalence relations whose union is not an equivalence relation.

Solution

On $\{1, 2, 3\}$ take $\sim$ with the single nontrivial pair $1 \sim 2$ (blocks $\{1,2\}, \{3\}$ ) and $\approx$ with $2 \approx 3$ (blocks $\{1\}, \{2,3\}$ ). The union contains $1 \sim 2$ and $2 \approx 3$ but not $(1, 3)$ , so it is not transitive. Intersections (the worked example above) are safe, unions are not.

prove

Let $A$ be a finite set and $\sim$ an equivalence relation in which every class has exactly $k$ elements. Prove that $\lvert A \rvert = k \cdot m$ , where $m$ is the number of classes.

Solution

The $m$ classes form a partition of $A$ , so each element lies in exactly one class. Counting the elements of $A$ class by class counts each element once, and each class contributes $k$ . So $\lvert A \rvert = k + k + \dots + k = km$ . The disjointness of the classes is what prevents double counting, and covering is what prevents missing elements. (This is the idea behind Lagrange’s theorem in MATH 541.)

prove

Prove that $(a, b) \sim (c, d)$ iff $a + d = b + c$ is an equivalence relation on $\mathbb N \times \mathbb N$ (the relation used to build the integers). Which pairs are related to $(1, 3)$ , and what integer should $[(1, 3)]$ be?

Solution

Reflexive: $a + b = b + a$ . Symmetric: if $a + d = b + c$ then $c + b = d + a$ , which says $(c, d) \sim (a, b)$ . Transitive: if $a + d = b + c$ and $c + f = d + e$ , add: $a + d + c + f = b + c + d + e$ ; cancel $c + d$ to get $a + f = b + e$ . The pairs related to $(1, 3)$ are those with $1 + d = 3 + c$ , that is $d = c + 2$ : $(1, 3), (2, 4), (3, 5), \dots$ . The class should be the integer $1 - 3 = -2$ , since $a - b$ is the same for every pair in it.

stretch

Count the equivalence relations on a set with $4$ elements by listing partitions by block sizes. Check with your answer for $3$ elements.

Solution

Block shapes: $4$ : $1$ way. $3 + 1$ : choose the single element, $4$ ways. $2 + 2$ : split into two pairs, $3$ ways ( $\{12|34\}$ , $\{13|24\}$ , $\{14|23\}$ ). $2 + 1 + 1$ : choose the pair, $\binom42 = 6$ ways. $1 + 1 + 1 + 1$ : $1$ way. Total $1 + 4 + 3 + 6 + 1 = 15$ . For $3$ elements the shapes are $3$ (1 way), $2 + 1$ (3 ways), $1 + 1 + 1$ (1 way): $5$ , matching the earlier example.

stretch

On $\mathbb R$ define $x \sim y$ iff $x - y \in \mathbb Q$ . Show it is an equivalence relation, show every class is countable, and use the uncountability of $\mathbb R$ to show there are uncountably many classes.

Solution

Equivalence: $x - x = 0 \in \mathbb Q$ ; if $x - y \in \mathbb Q$ so is $y - x$ ; and $x - z = (x - y) + (y - z)$ is a sum of rationals. The class of $x$ is $x + \mathbb Q = \{x + q : q \in \mathbb Q\}$ , and the function $q \mapsto x + q$ is a bijection from $\mathbb Q$ onto it, so the class is countable. Suppose there were only countably many classes. Choose one representative $r_k$ from the $k$ th class of a list of the classes, and list $\mathbb Q$ as $q_1, q_2, \dots$ . Every real number lies in some class, so it equals $r_k + q_n$ for some $k, n$ . So $(k, n) \mapsto r_k + q_n$ is a function from the countable set $\mathbb N \times \mathbb N$ onto $\mathbb R$ , and $\mathbb R$ would be countable by closure property 2 of chapter 0.3. That is false, so there are uncountably many classes. (This relation is the starting point of the Vitali set in measure theory.)

Summary

A relation on $A$ is a subset of $A \times A$ . It is an equivalence relation if it is reflexive, symmetric and transitive. Each property is disproved by one counterexample.
The equivalence class $[a]$ is everything related to $a$ . The lemma: $a \sim b$ iff $[a] = [b]$ iff the classes share an element.
Therefore the classes are non-empty, cover $A$ , and are equal or disjoint: they form a partition. Conversely, “same block” for any partition is an equivalence relation. The two notions are the same information.
“Same value of a function” is always an equivalence relation, and $[a] \mapsto f(a)$ is a bijection from the classes onto the range.
A rule defined on classes using a representative must be checked to be well defined. Addition of fractions passes.
A fraction $\tfrac ab$ is the class of the pair $(a, b)$ under $ad = bc$ , so $\tfrac12 = \tfrac24$ is a definition, not a discovery.
Seeds: $\mathbb Z_n$ (0.5), quotient spaces (3.7), quotient groups (541).

Watch and read

The same ideas explained by someone else. Use these when an explanation here does not land.

0.4 Equivalence relations and partitions

The picture

The idea, in words

Definitions and theorems

Relation

Equivalence relation

The same remainder, the same length

Same value is an equivalence relation

Equivalence classes

Equivalence class

Equal classes

Partition

Equivalence classes partition the set

Partitions give equivalence relations

A function is a bijection from its classes to its range

A function is a bijection from its classes onto its range

Fractions as classes

Where it is used

Traps

Problems

Summary

Watch and read

Where this sits

Comes from

Leads to

Same idea elsewhere