Equivalence Classes and Partitions
An equivalence relation sorts its set into groups of mutually related elements, the equivalence classes. The classes cut the set into non-overlapping pieces, a partition, and every partition comes from an equivalence relation in this way. Equivalence relations themselves are in equivalence-relations. First met in 2026-09-21-equivalence-relations, and finished at the start of 2026-09-22-partial-order-relations.
The definition
Let \(\rho\) be an equivalence relation on a set \(S\). For each \(a \in S\), define the equivalence class of \(a\) by \[[a] = \{x \in S : x \mathrel{\rho} a\}\] (the set of elements related to \(a\)).
Three things to read off the definition:
- \([a]\) is a set, a subset of \(S\). It is not an element of \(S\), and it is not a number.
- \(a \in [a]\) always, because \(\rho\) is reflexive. So no class is empty.
- The bracket depends on the relation. \([1]\) means one thing for congruence mod 3 and another for \(x - y \in \mathbb{Q}\). Say which relation is meant.
| Relation | Class | As a set |
|---|---|---|
| \(m \equiv n \pmod 3\) on \(\mathbb{Z}\) | \([1]\) | \(\{\dots, -5, -2, 1, 4, 7, \dots\}\) |
| same parity on \(\mathbb{Z}\) | \([0]\) | \(\mathbb{Z}^{even}\) |
| \(x - y \in \mathbb{Q}\) on \(\mathbb{R}\) | \([1]\) | \(\mathbb{Q}\) |
| \(x - y \in \mathbb{Q}\) on \(\mathbb{R}\) | \([\sqrt2]\) | \(\{y + \sqrt2 : y \in \mathbb{Q}\}\) |
| same part of \(\{\{1,2,3\},\{4,5\},\{6\}\}\) | \([4]\) | \(\{4, 5\}\) |
Describing a class
To find \([a]\), ask which \(x\) are related to \(a\): write down \(x \mathrel{\rho} a\), unfold the definition of \(\rho\), and simplify until it is a plain condition on \(x\).
\([1]\) for \(x \mathrel{\tau} y \leftrightarrow x - y \in \mathbb{Q}\). A real \(y\) is related to 1 exactly when \(1 - y \in \mathbb{Q}\), which happens exactly when \(y \in \mathbb{Q}\). So \([1] = \mathbb{Q}\).
\([\sqrt2]\) for the same relation. \(x \mathrel{\tau} \sqrt2\) means \(x - \sqrt2 = y\) for some \(y \in \mathbb{Q}\), that is, \(x = y + \sqrt2\). So \([\sqrt2] = \{y + \sqrt2 : y \in \mathbb{Q}\}\). It contains \(\sqrt2\), \(1 + \sqrt2\), \(-3 + \sqrt2\), and so on.
\([1]\) for \(m \mathrel{\sigma} n \leftrightarrow 8 \mid (m - n) \text{ or } 8 \mid (m + n)\). \[[1] = \{n \in \mathbb{Z} : 8 \mid (1 - n) \text{ or } 8 \mid (1 + n)\} = \{n \in \mathbb{Z} : n \equiv 1 \text{ or } 7 \pmod 8\}.\] The second alternative says \(n \equiv -1 \pmod 8\), and \(-1 \equiv 7\). All five classes of \(\sigma\) are in 2026-09-22-partial-order-relations.
These three are worked in 2026-09-21-equivalence-relations and 2026-09-22-partial-order-relations. The definition has \(x \mathrel{\rho} a\) and the workings sometimes use \(a \mathrel{\rho} x\). For an equivalence relation the two say the same thing, by symmetry.
When the class is infinite, describe it by a condition, as above. Listing “\(\{\dots, -7, -1, 1, 7, 9, \dots\}\)” is a useful check, but the pattern has to be stated.
One class, many names
For congruence mod 3, \[[0] = [3] = [-6].\] These are three names for one set, \(\{\dots, -6, -3, 0, 3, 6, \dots\}\). The element inside the bracket is a representative of the class, and every element of a class is a representative of it. The rule for when two names give the same class is:
\([a] = [b]\) if and only if \(a \mathrel{\rho} b\).
So to decide whether two classes are equal, test the two representatives against each other. For example, is \([\sqrt2] = [-\sqrt2]\) for \(\tau\)? \(\sqrt2 - (-\sqrt2) = 2\sqrt2 \notin \mathbb{Q}\), so \(\sqrt2 \mathrel{\not\tau} {-\sqrt2}\), and \([\sqrt2] \neq [-\sqrt2]\).
The rule follows from the result in the next section: if \(a \mathrel{\rho} b\) the classes are equal, and if \(a \mathrel{\not\rho} b\) they are disjoint and non-empty, so not equal. By convention the simplest representative is used. For congruence mod \(n\) the usual choice is \([0], [1], \dots, [n-1]\) (integers-modulo-n).
Equal or disjoint
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. If \(a \mathrel{\not\rho} b\) they are disjoint.
Two classes never partly overlap. The proof uses each of the three properties.
Proof. Let \(\rho\) be an equivalence relation on \(S\) and let \(a, b \in S\).
Case 1: \(a \mathrel{\rho} b\). We show \([a] \subseteq [b]\) and \([b] \subseteq [a]\). Let \(x \in [a]\). Then \(x \mathrel{\rho} a\). Since also \(a \mathrel{\rho} b\), transitivity gives \(x \mathrel{\rho} b\), so \(x \in [b]\). Hence \([a] \subseteq [b]\). By symmetry, \(b \mathrel{\rho} a\), and the same argument with \(a\) and \(b\) exchanged gives \([b] \subseteq [a]\). Hence \([a] = [b]\).
Case 2: \(a \mathrel{\not\rho} b\). Suppose, for a contradiction, that \([a] \cap [b] \neq \emptyset\), and take \(x \in [a] \cap [b]\). Then \(x \mathrel{\rho} a\) and \(x \mathrel{\rho} b\). By symmetry, \(a \mathrel{\rho} x\). By transitivity, \(a \mathrel{\rho} x\) and \(x \mathrel{\rho} b\) give \(a \mathrel{\rho} b\). \((\Rightarrow\Leftarrow)\) Hence \([a] \cap [b] = \emptyset\). \(\square\)
Reflexivity is what puts \(a\) into \([a]\). It gives if \([a] = [b]\) then \(b \in [a]\) in one line: \(b \in [b] = [a]\).
Figure 1: The two things that can happen to two equivalence classes, and the one that cannot. Left: if \(a \mathrel{\rho} b\) then \([a]\) and \([b]\) are the same set. Middle: if \(a\) and \(b\) are not related then the two classes share no element. Right: a partial overlap is impossible. A shared element \(x\) is related to both \(a\) and \(b\); symmetry turns \(x \mathrel{\rho} a\) round into \(a \mathrel{\rho} x\), and transitivity along \(a \to x \to b\) then forces \(a \mathrel{\rho} b\), the dashed arrow, which puts the pair back in the left-hand picture.
Putting the pieces together, for an equivalence relation \(\rho\) these four statements stand or fall together:
\[a \mathrel{\rho} b \qquad\qquad [a] = [b] \qquad\qquad b \in [a] \qquad\qquad [a] \cap [b] \neq \emptyset\]
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.
So a collection of subsets of \(S\) is a partition when it passes three checks:
- every part is non-empty;
- the parts are mutually disjoint: no element is in two of them;
- their union is \(S\): no element is left out.
Checks 2 and 3 together say that every element of \(S\) is in exactly one part. The same definition, in Lecture 17’s words and with more worked examples, is in sets-and-set-notation.
Mutually disjoint is about pairs. \(W = \{1,2,3\}\), \(X = \{4,5,6\}\), \(Y = \{6,7,8\}\) are not mutually disjoint, because \(X \cap Y = \{6\}\), even though \(W\) is disjoint from both of the others. More examples are in 2026-09-21-equivalence-relations.
The classes form a partition
The equivalence classes of an equivalence relation on a set \(S\) form a partition of the set \(S\).
The three checks, for the collection of all classes \(\{[a] : a \in S\}\):
- Non-empty. \(a \in [a]\), by reflexivity.
- Mutually disjoint. Two distinct classes are not equal, so by the result above they are disjoint.
- Union is \(S\). Each \(a \in S\) lies in the class \([a]\), and every class is a subset of \(S\).
In the collection each class is counted once, however many names it has. For congruence mod 3 the collection is \(\{[0], [1], [2]\}\), with three members, although \([0] = [3] = [-6] = \cdots\).
| Relation | Number of classes |
|---|---|
| \(m \equiv n \pmod 3\) on \(\mathbb{Z}\) | 3 |
| same parity on \(\mathbb{Z}\) | 2 |
| \(8 \mid (m-n)\) or \(8 \mid (m+n)\) on \(\mathbb{Z}\) | 5 |
| \(x - y \in \mathbb{Q}\) on \(\mathbb{R}\) | infinitely many |
| \(x = y\) on a set \(S\) | one for each element of \(S\) |
From a partition to a relation
Given any partition of a set \(S\), we can define an equivalence relation on \(S\), by defining two elements to be related if and only if they are in the same part of the partition. The parts in a partition form the equivalence classes of the corresponding equivalence relation.
“In the same part” is an equivalence relation. The check is short, and it shows what each condition on a partition is for.
- Reflexive. Let \(x \in S\). The union of the parts is \(S\), so \(x\) is in some part, and it is in the same part as itself.
- Symmetric. If \(x\) and \(y\) are in the same part, then \(y\) and \(x\) are.
- Transitive. Suppose \(x\) and \(y\) are both in a part \(P\), and \(y\) and \(z\) are both in a part \(Q\). Then \(y \in P \cap Q\). The parts are mutually disjoint, so \(P\) and \(Q\) cannot be distinct: \(P = Q\). So \(x\) and \(z\) are in the same part.
Reflexivity uses “the union is \(S\)”, and transitivity uses “mutually disjoint”.
Writing the relation down. For a small set, list the pairs: a part with \(k\) elements gives all \(k^2\) ordered pairs of its elements. The partition \(\{\{1,2,3\},\{4,5\},\{6\}\}\) of \(\{1,\dots,6\}\) gives \(9 + 4 + 1 = 14\) pairs, drawn in 2026-09-21-equivalence-relations. For an infinite set, turn “in the same part” into a condition. For the partition \(\{\mathbb{Z}^{-}, \{0\}, \mathbb{Z}^{+}\}\) of \(\mathbb{Z}\) the condition is
\(a \mathrel{\tau} b \longleftrightarrow a, b\) both positive \(\ \) or \(\ a = b = 0\ \) or \(\ a, b\) both negative
with one alternative for each part (2026-09-22-partial-order-relations).
Two descriptions of one thing
Any partition defines an equivalence relation and any equivalence relation defines a partition.
In short, equivalence relations \(\iff\) partitions. The two constructions undo each other:
- Start with an equivalence relation, take its classes, and relate elements in the same class. That gives back the relation you started with, since \(x \mathrel{\rho} y\) exactly when \([x] = [y]\).
- Start with a partition, relate elements in the same part, and take the classes. That gives back the parts.
So an equivalence relation on \(S\) and a partition of \(S\) carry the same information. A question about one can be answered with the other. To count or describe the equivalence relations on a small set, describe its partitions. To show a collection of sets is a partition, it is enough to recognise it as the classes of an equivalence relation.
Finding the classes of a finite relation
For an equivalence relation given by a list of pairs or an arrow diagram:
- Pick any element \(a\). Its class is \(a\) together with everything joined to \(a\) by an arrow.
- Pick any element not yet in a class, and do the same.
- Stop when every element is in a class.
Step 1 is the definition of \([a]\), so it collects the whole class at once. There is no need to follow arrows further, because the relation is transitive. Step 2 starts a new class because, by the equal-or-disjoint result, an element outside the classes found so far has a class disjoint from all of them.
Worked (practice-problems, Q2). On \(A = \{a,b,c,d,e\}\), \[\rho = \{(a,a), (a,b), (a,d), (b,b), (c,c), (d,d), (b,a), (d,a), (b,d), (d,b), (c,e), (e,c), (e,e)\}.\] Start at \(a\): it is related to \(a\), \(b\), \(d\), so \([a] = \{a,b,d\}\). The first unused element is \(c\): it is related to \(c\) and \(e\), so \([c] = \{c,e\}\). Every element is used, and \[[a] = [b] = [d] = \{a,b,d\}, \qquad [c] = [e] = \{c,e\}.\] The same problem asks for the smallest equivalence relation contained in \(\rho\). A relation on \(A\) must contain all five loops to be reflexive, and the five loops alone are already an equivalence relation: \(\tau = \{(a,a),(b,b),(c,c),(d,d),(e,e)\}\), which is equality on \(A\). Its classes are the five singletons.
Figure 2: Two equivalence relations on \({a,b,c,d,e}\), with each class shaded. Left: \(\rho\) has 13 pairs, 9 inside \({a,b,d}\) and 4 inside \({c,e}\). A double-headed line stands for an arrow each way. Its classes are the two clusters of the diagram. Right: \(\tau\) keeps only the five loops. It is still reflexive, symmetric and transitive, and each element is in a class by itself. Here \(\tau\) is contained in \(\rho\), and the smaller relation has more, smaller classes.
Common mistakes
- Treating \([a]\) as an element. \([a] \subseteq S\), and \(a \in [a]\). Writing \([a] \in S\) or \([1] = 1\) confuses a set with one of its members (sets-and-set-notation).
- Thinking different names mean different classes. \([0]\) and \([3]\) are the same class mod 3. \(a \neq b\) does not give \([a] \neq [b]\). Only \(a \mathrel{\not\rho} b\) does.
- Giving one example in place of the class. “\([\sqrt2]\) contains \(1 + \sqrt2\)” does not describe \([\sqrt2]\). \(\{y + \sqrt2 : y \in \mathbb{Q}\}\) does.
- Classes that overlap or leave something out. If your list of classes is not a partition of \(S\), something is wrong. Check that each element is in exactly one.
- Taking classes of a relation that is not an equivalence relation. The definition starts “let \(\rho\) be an equivalence relation”. For \(x + y \in \mathbb{Q}\) on \(\mathbb{R}\), the set of things related to \(\sqrt2\) does not even contain \(\sqrt2\).
- An empty part. \(\{\emptyset, \mathbb{Z}\}\) is not a partition of \(\mathbb{Z}\). Parts are non-empty.
See also
- equivalence-relations — the definition, the proof template, and the relations used here
- sets-and-set-notation — partitions as first defined, with more examples
- integers-modulo-n — the classes of congruence mod \(n\) as a number system
- counting-principles — the size of a finite set as the sum of the sizes of the parts of a partition
- reflexive-symmetric-and-transitive-relations — the three properties the proofs here use
- proof-techniques — double containment and proof by contradiction, both used in the equal-or-disjoint proof
- 2026-09-21-equivalence-relations — Lecture 24 · 2026-09-22-partial-order-relations — Lecture 25, which finishes it
- practice-problems — §31, with full worked solutions