Lecture 24 — Equivalence Relations

lecture
discrete-math
set-theory
relations
proof

Equivalence relations, their classes, and why the classes cut the set into a partition. Pre-work: Video 031 (Equivalence Relations). The definition and how to prove or disprove it are collected in equivalence-relations, and classes, partitions and the two-way link between them in equivalence-classes-and-partitions. The three properties come from reflexive-symmetric-and-transitive-relations.

Goals

  1. Know how to prove or disprove that a relation is an equivalence relation.
  2. Understand equivalence classes.
  3. Understand the connection between equivalence relations and partitions.

All three in one sentence:

If \(R\) is an equivalence relation on a set \(A\), then the equivalence classes of \(R\) partition \(A\).

Figure 1: A set \(A\) cut into the equivalence classes of a relation on it. Every element of \(A\) lies in exactly one region. Each region is named after one of the elements in it, written in square brackets: \([a]\) is the region that \(a\) is in. The regions cover \(A\) and no two overlap, and that is what a partition is.

Three questions to start with

Are there any equivalence relations apart from congruence mod \(n\) and equality? Yes. Fractions are one. Take pairs of positive integers and relate

\[(a,b) \sim (c,d) \quad\text{if and only if}\quad ad = bc,\]

which is the condition \(\dfrac{a}{b} = \dfrac{c}{d}\) written without division. Then \(\frac12 = \frac24 = \frac36 = \cdots\) says that \((1,2)\), \((2,4)\) and \((3,6)\) are all related: three pairs in one class. A positive rational number is a whole class of pairs. The relation is worked through in equivalence-relations.

What exactly is the equivalence class \([a]\)? The set of everything related to \(a\). See Equivalence classes.

Why does the set of equivalence classes form a partition, and given a partition, how do we get an equivalence relation? The first is Two classes are equal or disjoint, and the second is From a partition to an equivalence relation.

The definition

For a relation \(\rho\) on a set \(A\) (reflexive-symmetric-and-transitive-relations):

Property Condition
reflexive \(\forall x \in A,\ x \mathrel{\rho} x\)
symmetric \(\forall x, y \in A,\ x \mathrel{\rho} y \to y \mathrel{\rho} x\)
transitive \(\forall x, y, z \in A,\ (x \mathrel{\rho} y \text{ and } y \mathrel{\rho} z) \to x \mathrel{\rho} z\)

A relation is an equivalence relation if and only if it is reflexive, symmetric and transitive.

Worked: the sum is rational

Let \(\rho\) be the relation on \(\mathbb{R}\) defined by: for all \(x, y \in \mathbb{R}\), \(x \mathrel{\rho} y\) if and only if \(x + y \in \mathbb{Q}\). Is \(\rho\) an equivalence relation?

No. \(\rho\) is not reflexive.

Take \(x = \sqrt2 \in \mathbb{R}\). Then \(x + x = \sqrt2 + \sqrt2 = 2\sqrt2 \notin \mathbb{Q}\), so \(\sqrt2 \mathrel{\not\rho} \sqrt2\). \(\therefore \rho\) is not an equivalence relation.

Reflexive is a “for all” statement, \(\forall x \in A,\ x \mathrel{\rho} x\), so a single \(x\) that fails disproves it. An equivalence relation needs all three properties, so one failed property, shown by one witness, settles the question. There is no need to look at the other two.

For the record, \(\rho\) is symmetric, because \(x + y = y + x\). It is not transitive: \(\sqrt2 \mathrel{\rho} {-\sqrt2}\) and \(-\sqrt2 \mathrel{\rho} \sqrt2\), since both sums are \(0\), but \(\sqrt2 \mathrel{\not\rho} \sqrt2\). That is the forced loop of reflexive-symmetric-and-transitive-relations again.

Worked: the difference is rational

Let \(\tau\) be the relation on \(\mathbb{R}\) defined by: for all \(x, y \in \mathbb{R}\), \(x \mathrel{\tau} y\) if and only if \(x - y \in \mathbb{Q}\). Is \(\tau\) an equivalence relation?

Yes. The proof has three parts, one for each property.

(1) Reflexive. Let \(x \in \mathbb{R}\). (Think: is \(x \mathrel{\tau} x\)?) \(x - x = 0 \in \mathbb{Q}\), since \(0 = \frac01\). So \(\tau\) is reflexive.

(2) Symmetric. Let \(x, y \in \mathbb{R}\) and suppose \(x \mathrel{\tau} y\). Then \(x - y \in \mathbb{Q}\), so \(x - y = \dfrac{a}{b}\) for some \(a, b \in \mathbb{Z}\), \(b \neq 0\). \[y - x = -(x - y) = -\left(\frac{a}{b}\right) = \frac{-a}{b}.\] Since \(-a \in \mathbb{Z}\) we have \(y - x \in \mathbb{Q}\), so \(y \mathrel{\tau} x\). \(\therefore \tau\) is symmetric.

(3) Transitive. Let \(x, y, z \in \mathbb{R}\) and suppose \(x \mathrel{\tau} y\) and \(y \mathrel{\tau} z\). Thus \(x - y = \dfrac{a}{b}\) and \(y - z = \dfrac{c}{d}\) for some \(a, b, c, d \in \mathbb{Z}\), \(b \neq 0\), \(d \neq 0\). \[\text{Now } x - z = (x - y) + (y - z) = \frac{a}{b} + \frac{c}{d} = \frac{ad + bc}{bd}.\] Since \(a, b, c, d \in \mathbb{Z}\), \(ad + bc,\ bd \in \mathbb{Z}\). Also \(bd \neq 0\). \(\therefore x - z \in \mathbb{Q}\), so \(x \mathrel{\tau} z\). \(\therefore \tau\) is transitive.

Three things to copy from this proof:

  • Start each part by asking what the property says for this relation. For reflexive that is “is \(x \mathrel{\tau} x\)?”, which is “is \(x - x \in \mathbb{Q}\)?”.
  • Each part unfolds the definition. “\(x - y \in \mathbb{Q}\)” is turned into \(x - y = \frac{a}{b}\) with \(a, b \in \mathbb{Z}\), \(b \neq 0\) (rational-and-irrational-numbers), worked on, and folded back up into “\(\in \mathbb{Q}\)”.
  • New letters for the second fraction. Part (3) uses \(\frac{c}{d}\) for \(y - z\). Writing \(\frac{a}{b}\) again would claim the two differences are equal.

The step that makes part (3) work is \(x - z = (x - y) + (y - z)\): the middle term cancels. For sums there is no such identity, which is where \(\rho\) goes wrong.

Figure 2: The same five real numbers under the two relations. Left, \(x \mathrel{\rho} y \leftrightarrow x + y \in \mathbb{Q}\). Only 0 and 1 have loops. There is none at \(\sqrt2\) because \(\sqrt2 + \sqrt2\) is irrational, so \(\rho\) is not reflexive, and the three missing loops are dashed. Right, \(x \mathrel{\tau} y \leftrightarrow x - y \in \mathbb{Q}\). Every number has a loop because \(x - x = 0\), and the numbers fall into three separate clusters with every arrow present inside a cluster and none between clusters. That clustered shape is what an equivalence relation looks like.

Partitions

Two sets \(X\) and \(Y\) are disjoint if and only if \(X \cap Y = \emptyset\).
A collection of sets is mutually disjoint if each pair of distinct sets in the collection is disjoint.

A partition of a set \(S\) is a collection of non-empty and mutually disjoint subsets of \(S\) whose union is \(S\).
The subsets in a partition are sometimes called parts.

This is the definition from sets-and-set-notation with two new words, mutually disjoint and parts. Three conditions: the pieces are non-empty, no two overlap, and together they cover \(S\).

The positive integers by remainder. \[\big\{\{1,4,7,\dots\},\ \{2,5,8,\dots\},\ \{3,6,9,\dots\}\big\} \text{ is a partition of } \mathbb{Z}^{+}.\] The three parts are the positive integers sorted by remainder on division by 3. A partition is always a partition of some set, here \(\mathbb{Z}^{+}\), and naming that set is part of the statement.

One set, two partitions. Let \(S = \{x_1, x_2, x_3, x_4, x_5, x_6, x_7, x_8, x_9\}\).

  • \(\big\{\{x_1, x_2, x_3\},\ \{x_4, x_5\},\ \{x_6, x_7, x_8, x_9\}\big\}\) is a partition of \(S\) with 3 parts.
  • \(\big\{\{x_1, x_2\},\ \{x_3, x_4\},\ \{x_5, x_8, x_9\},\ \{x_6, x_7\}\big\}\) is another partition of \(S\), with 4 parts.

One set has many partitions. The parts need not be the same size, and their elements need not be next to each other in any listing: \(\{x_5, x_8, x_9\}\) is a part.

Mutually disjoint, and not. Let \(W = \{1,2,3\}\), \(X = \{4,5,6\}\), \(Y = \{6,7,8\}\), \(Z = \{7,8,9,10\}\).

  • \(W\), \(X\) and \(Z\) are mutually disjoint.
  • \(W\), \(X\) and \(Y\) are not mutually disjoint, because \(X \cap Y = \{6\}\). One overlapping pair is enough, even though \(W\) is disjoint from both of the others.
  • \(\{W, X, Z\}\) is a partition of \(\{1,2,3,4,5,6,7,8,9,10\}\) with 3 parts.

Figure 3: The four sets \(W\), \(X\), \(Y\) and \(Z\) on the numbers 1 to 10. \(W\), \(X\) and \(Z\) sit side by side and share no number, so they are mutually disjoint, and between them they use every number from 1 to 10, so \({W, X, Z}\) is a partition with three parts. \(Y\) shares 6 with \(X\) and shares 7 and 8 with \(Z\). A collection that contains \(Y\) together with \(X\) or \(Z\) is not mutually disjoint, however many of its other pairs are disjoint. The shared numbers are shaded, 6 in green and 7 and 8 in purple.

Equivalence classes

Let \(\rho\) be an equivalence relation on a set \(S\). For each \(a \in S\), the equivalence class of \(a\) is \[[a] = \{x \in S : x \mathrel{\rho} a\},\] the set of elements related to \(a\).

The equivalence classes of an equivalence relation on a set \(S\) form a partition of \(S\).

Congruence mod 3. For \(m \mathrel{T} n \leftrightarrow m \equiv n \pmod 3\) on \(\mathbb{Z}\) there are three classes:

\[[0] = \{\dots, -6, -3, 0, 3, 6, \dots\}, \qquad [1] = \{\dots, -5, -2, 1, 4, 7, \dots\}, \qquad [2] = \{\dots, -4, -1, 2, 5, 8, \dots\}.\]

Also \([0] = [3] = [-6]\). A class is a set, and the bracket only says which element was used to name it. Every element of a class names that same class, so a class with infinitely many elements has infinitely many names.

Figure 4: The integers from \(-6\) to 8, coloured by remainder on division by 3. Each colour is one equivalence class of \(m \equiv n \pmod 3\). The classes are spread along the number line, every third integer, and each integer has exactly one colour, so the three classes partition \(\mathbb{Z}\). The line at the right gives one class three of its names: \([0]\), \([3]\) and \([-6]\) are the same set, named after three different elements of it.

Same parity. The relation \(\rho\) on \(\mathbb{Z}\) defined by “\(m \mathrel{\rho} n\) if and only if \(m\) and \(n\) have the same parity” is an equivalence relation. Its equivalence classes are

\[\mathbb{Z}^{even} = \{\dots, -4, -2, 0, 2, 4, \dots\} \qquad\text{and}\qquad \mathbb{Z}^{odd} = \{\dots, -3, -1, 1, 3, 5, \dots\},\]

and these two classes partition \(\mathbb{Z}\).

As an arrow diagram, the inside of a class has a loop at every element and arrows both ways between every pair. All of its elements are related to each other and to themselves, and none is related to anything outside.

Figure 5: Inside one equivalence class every element is related to every other, in both directions, and to itself. Between two different classes there are no arrows at all. Shown for the relation same parity on \(\mathbb{Z}\), with four of the even integers and three of the odd ones. Each double-headed line stands for one arrow each way.

Worked: the classes of \(\tau\)

\(\tau\) is the equivalence relation from before: for all \(x, y \in \mathbb{R}\), \(x \mathrel{\tau} y\) if and only if \(x - y \in \mathbb{Q}\).

(a) Describe the equivalence class \([1]\).

\[1 \mathrel{\tau} y \ \leftrightarrow\ 1 - y \in \mathbb{Q} \ \leftrightarrow\ y \in \mathbb{Q}, \qquad\text{so}\qquad [1] = \mathbb{Q}.\]

The method is to ask which \(y\) are related to 1 and unfold the definition until it is a plain condition on \(y\). The class is defined as the \(x\) with \(x \mathrel{\tau} 1\), and this works with \(1 \mathrel{\tau} y\) instead. For an equivalence relation the order makes no difference, because it is symmetric.

(b) State three elements that are in the equivalence class \([\sqrt2]\).

  • \(\sqrt2 \in [\sqrt2]\), because \(\sqrt2 - \sqrt2 = 0 \in \mathbb{Q}\), so \(\sqrt2 \mathrel{\tau} \sqrt2\).
  • \(1 + \sqrt2 \in [\sqrt2]\), because \(\sqrt2 - (1 + \sqrt2) = -1 \in \mathbb{Q}\).
  • \(-3 + \sqrt2 \in [\sqrt2]\), because \(\sqrt2 - (-3 + \sqrt2) = 3 \in \mathbb{Q}\).

The whole class is

\[[\sqrt2] = \{y + \sqrt2 : y \in \mathbb{Q}\}.\]

The first element is the standard one. \(a\) is always in \([a]\), because the relation is reflexive.

(c) Is \([\sqrt2] = [-\sqrt2]\)?

\(\sqrt2 - (-\sqrt2) = 2\sqrt2 \notin \mathbb{Q}\), so \(\sqrt2 \mathrel{\not\tau} {-\sqrt2}\). Therefore \([\sqrt2] \neq [-\sqrt2]\).

To compare two classes, test their two names against each other. Related names give the same class, and unrelated names give different classes. Why that is enough is the next section.

So \(\mathbb{R}\) is cut into classes, of which \([1] = \mathbb{Q}\), \([\sqrt2]\) and \([-\sqrt2]\) are three.

Figure 6: Three of the equivalence classes of \(\tau\), each on its own copy of the real line. A class cannot be drawn in full, so only the numbers a multiple of \(\tfrac12\) away from the class’s name are shown. \([1]\) is \(\mathbb{Q}\). \([\sqrt2] = {y + \sqrt2 : y \in \mathbb{Q}}\) is \(\mathbb{Q}\) slid \(\sqrt2\) to the right, and \([-\sqrt2]\) is \(\mathbb{Q}\) slid \(\sqrt2\) to the left. The ringed points are 1, the three elements found for \([\sqrt2]\), and \(-\sqrt2\). No point of one line is directly above a point of another, since a real number is in only one class.

Each class of \(\tau\) is a copy of \(\mathbb{Q}\), so it is countable, and \(\mathbb{R}\) is not (countable-and-uncountable-sets). So there are infinitely many classes besides these three.

Two classes are equal or disjoint

True or false: if the equivalence class \([a]\) is equal to the equivalence class \([b]\), then \(b \in [a]\).

True. \(b \in [b]\) because the relation is reflexive. So if \([a] = [b]\) then

\[b \in [b] = [a].\]

The result behind it:

Important result. If \(\rho\) is an equivalence relation on a set \(S\), and \(a, b \in S\), then either \[[a] = [b] \qquad \text{or} \qquad [a] \cap [b] = \emptyset.\] If \(a \mathrel{\rho} b\) the classes are equal, and if \(a \mathrel{\not\rho} b\) they are disjoint.

Two classes are either the same set or have nothing in common. They never partly overlap.

This is why the equivalence classes form a partition:

  • the classes are non-empty, since \(a \in [a]\);
  • every element is in a class, its own, so their union is \(S\);
  • two different classes are disjoint, by the result.

The proof of the result, with a picture, is in equivalence-classes-and-partitions.

Worked: a relation defined with “or”

The relation \(\sigma\) on \(\mathbb{Z}\) is defined by \(m \mathrel{\sigma} n \leftrightarrow (8 \text{ divides } m - n) \text{ or } (8 \text{ divides } m + n)\). It is an equivalence relation. Describe its equivalence classes.

The proof that it is an equivalence relation is below. The classes are worked out in 2026-09-22-partial-order-relations: there are five of them.

From a partition to an equivalence relation

The link also runs the other way.

Given any partition of a set \(S\), we can define an equivalence relation on \(S\) by taking two elements to be related if and only if they are in the same part of the partition. The parts of the partition are then the equivalence classes of that relation.

Any partition defines an equivalence relation, and any equivalence relation defines a partition.

Example. Let \(S = \{1,2,3,4,5,6\}\) with the partition \(\big\{\{1,2,3\}, \{4,5\}, \{6\}\big\}\). The equivalence relation \(R\) on \(S\) built from this partition is

\[R = \{(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3), (4,4), (4,5), (5,5), (5,4), (6,6)\}.\]

\(R\) has three equivalence classes:

\[[1] = \{1,2,3\} = [2] = [3], \qquad [4] = \{4,5\} = [5], \qquad [6] = \{6\}.\]

A part with \(k\) elements contributes all \(k \times k\) pairs of its elements, loops included, so \(R\) has \(3^2 + 2^2 + 1^2 = 14\) pairs. Reading the classes back off \(R\) returns the partition it was built from.

Figure 7: From a partition to the relation it defines. Left: the three parts of \(S = {1, \dots, 6}\), and inside each part every arrow, since two elements are related exactly when they are in the same part. Right: the same relation as a set of points in the grid \(S \times S\), the first coordinate across and the second up. Each part gives a solid square block on the diagonal, \(3 \times 3\), \(2 \times 2\) and \(1 \times 1\), so \(R\) has \(9 + 4 + 1 = 14\) pairs. Yellow marks \({1,2,3}\) and its nine pairs, cyan \({4,5}\) and its four, purple \({6}\) and \((6,6)\).

Question. Consider the partition of the integers given by \(\{\mathbb{Z}^{-}, \{0\}, \mathbb{Z}^{+}\}\). Describe an equivalence relation that corresponds to this partition.

Answered in 2026-09-22-partial-order-relations.

See also