Equivalence Relations
A relation that is reflexive, symmetric and transitive at once. Such a relation behaves like “is the same as, in some respect”, and it sorts its set into groups, the equivalence classes of equivalence-classes-and-partitions. The three properties are in reflexive-symmetric-and-transitive-relations. First met in 2026-09-21-equivalence-relations.
The definition
A relation is an equivalence relation if and only if it is: reflexive, symmetric and transitive.
For a relation \(\rho\) on a set \(A\) that is three “for all” statements:
(1) reflexive: \(\forall x \in A,\ x \mathrel{\rho} x\).
(2) symmetric: \(\forall x, y \in A,\ x \mathrel{\rho} y \to y \mathrel{\rho} x\).
(3) transitive: \(\forall x, y, z \in A,\ (x \mathrel{\rho} y \text{ and } y \mathrel{\rho} z) \to x \mathrel{\rho} z\).
All three are needed, and none follows from the other two (reflexive-symmetric-and-transitive-relations).
Relations here are named \(\rho\), \(\tau\), \(\sigma\), \(R\) and \(T\). The symbol \(\sim\) is also used as the name of a relation, as in \((a,b) \sim (c,d)\). It is the same symbol used for not in logic (logical-connectives). Position tells them apart: between two objects it is a relation, and in front of a statement it is a negation.
What the arrow diagram looks like
In the arrow diagram of an equivalence relation every dot has a loop, every arrow has its return, and every two-step path has its short cut. Put together, the diagram falls into separate clusters, with every possible arrow inside a cluster and none between clusters. The clusters are the equivalence classes. The even integers under same parity are a single such cluster (2026-09-21-equivalence-relations). The same shape shows for five real numbers in 2026-09-21-equivalence-relations, and for congruence mod 6 in relations-on-sets.
Figure 1 shows the shape, and one way to break each property.
Figure 1: An equivalence relation on \({1,2,3,4,5}\) and three near misses, each differing from it in one place. A double-headed line stands for an arrow each way, and what is missing is dashed. First: two clusters, complete inside, nothing between them. Second: the loop at 5 is removed, so the relation is not reflexive. Third: \(5 \to 4\) is removed, so \(4 \to 5\) has no return and the relation is not symmetric. Fourth: a link between 3 and 4 is added, so the path \(3 \to 4 \to 5\) has no short cut \(3 \to 5\) and the relation is not transitive. A link between two clusters has to be completed until they are one cluster, or removed.
Proving a relation is an equivalence relation
Prove the three properties one at a time, and label each part. Each part is a direct proof of a “for all” statement (proof-techniques):
| Part | Start with | Show |
|---|---|---|
| reflexive | Let \(x \in A\). | \(x \mathrel{\rho} x\) |
| symmetric | Let \(x, y \in A\) and suppose \(x \mathrel{\rho} y\). | \(y \mathrel{\rho} x\) |
| transitive | Let \(x, y, z \in A\) and suppose \(x \mathrel{\rho} y\) and \(y \mathrel{\rho} z\). | \(x \mathrel{\rho} z\) |
In each part, unfold what \(\rho\) means for the elements in hand, work with that, and fold it back into a statement about \(\rho\). Finish with a sentence naming all three: Since \(\rho\) is reflexive, symmetric and transitive, it is an equivalence relation.
Worked: \(x \mathrel{\tau} y \leftrightarrow x - y \in \mathbb{Q}\) on \(\mathbb{R}\)
The proof is written out in full in 2026-09-21-equivalence-relations. Its shape:
- Reflexive. \(x - x = 0 \in \mathbb{Q}\).
- Symmetric. Unfold \(x - y \in \mathbb{Q}\) to \(x - y = \frac{a}{b}\) with \(a, b \in \mathbb{Z}\), \(b \neq 0\). Then \(y - x = \frac{-a}{b} \in \mathbb{Q}\).
- Transitive. Unfold to \(x - y = \frac{a}{b}\) and \(y - z = \frac{c}{d}\). Then \(x - z = (x - y) + (y - z) = \frac{ad + bc}{bd} \in \mathbb{Q}\), with \(bd \neq 0\).
The second fraction gets new letters \(c\), \(d\). The transitive step rests on one identity, \(x - z = (x - y) + (y - z)\), which gets rid of the middle element. Most transitivity proofs need a step like it.
Congruence is the same proof with integers in place of rationals. \(m \mathrel{\rho} n \leftrightarrow d \mid (m - n)\) on \(\mathbb{Z}\) is worked for \(d = 6\) in reflexive-symmetric-and-transitive-relations, and nothing in it depends on the 6.
Worked: a definition with an “or”
\(m \mathrel{\sigma} n \leftrightarrow (8 \mid (m - n)) \text{ or } (8 \mid (m + n))\) on \(\mathbb{Z}\).
The proof is written out in full in 2026-09-21-equivalence-relations. When the definition is an or, every hypothesis of the form \(m \mathrel{\sigma} n\) splits into cases, and each case has to reach the conclusion. A conclusion of the form \(k \mathrel{\sigma} n\) needs only one of its two alternatives.
- Reflexive. No cases: \(8 \mid (m - m)\), the first alternative.
- Symmetric. One hypothesis, two cases. From \(8 \mid (m - n)\) get \(8 \mid (n - m)\). From \(8 \mid (m + n)\) get \(8 \mid (n + m)\).
- Transitive. Two hypotheses, \(2 \times 2 = 4\) cases:
| Case | \(k \mathrel{\sigma} m\) because | \(m \mathrel{\sigma} n\) because | Combine | So 8 divides |
|---|---|---|---|---|
| 1 | \(8 \mid (k - m)\) | \(8 \mid (m - n)\) | add | \(k - n\) |
| 2 | \(8 \mid (k - m)\) | \(8 \mid (m + n)\) | add | \(k + n\) |
| 3 | \(8 \mid (k + m)\) | \(8 \mid (m - n)\) | subtract | \(k + n\) |
| 4 | \(8 \mid (k + m)\) | \(8 \mid (m + n)\) | subtract | \(k - n\) |
In every row the two quantities are added or subtracted, whichever cancels the \(m\).
Disproving
A relation fails to be an equivalence relation as soon as it fails one of the three properties, and a property fails as soon as there is one witness. So a disproof is short: name the property, give specific elements, check them.
\(x \mathrel{\rho} y \leftrightarrow x + y \in \mathbb{Q}\) on \(\mathbb{R}\) is not an equivalence relation: it is not reflexive, because \(\sqrt2 + \sqrt2 = 2\sqrt2 \notin \mathbb{Q}\), so \(\sqrt2 \mathrel{\not\rho} \sqrt2\).
That is the whole answer (2026-09-21-equivalence-relations). Try reflexivity first, since it involves only one element. A relation can fail on any of the three:
| Fails | Relation | Witness | Worked in |
|---|---|---|---|
| reflexive | \(x + y \in \mathbb{Q}\) on \(\mathbb{R}\) | \(\sqrt2 \mathrel{\not\rho} \sqrt2\) | 2026-09-21-equivalence-relations |
| symmetric | \(x\) is a multiple of \(y\), on \(\mathbb{Z}\) | 4 is a multiple of 2, but 2 is not a multiple of 4 | practice-problems, Q1 (\(\beta\)) |
| transitive | \(\lvert x - y \rvert \le 1\) on \(\mathbb{Z}\) | \(0\) and \(1\) are related, \(1\) and \(2\) are related, \(0\) and \(2\) are not | — |
The last one is reflexive and symmetric, and still not an equivalence relation. “Close to” is not transitive, and that is why it never works as a kind of sameness.
“The same …”
Most of the course’s equivalence relations say that two elements have the same something:
| Relation | \(x\) and \(y\) are related when they have the same … |
|---|---|
| \(m \equiv n \pmod 3\) on \(\mathbb{Z}\) | remainder on division by 3 |
| same parity on \(\mathbb{Z}\) | parity |
| in the same part of a partition | part |
| \((a,b) \sim (c,d) \leftrightarrow ad = bc\) | value as a fraction |
| \(R_n\) on strings | first \(n\) characters (practice-problems, Q3) |
| \(x = y\) on any set | identity |
A relation of the form “\(x\) and \(y\) have the same value of \(f\)”, that is \(f(x) = f(y)\) for some function \(f\) on the set, is always an equivalence relation, because the three properties are inherited from \(=\): \(f(x) = f(x)\); if \(f(x) = f(y)\) then \(f(y) = f(x)\); and if \(f(x) = f(y)\) and \(f(y) = f(z)\) then \(f(x) = f(z)\). Recognising this shape tells you the answer is yes before you start. The proof still has to be written out for the relation as given.
Not every example is given in that form. \(x - y \in \mathbb{Q}\) and the relation \(\sigma\) above have to be proved from their definitions.
The same fraction
An equivalence relation that is neither congruence nor equality:
\((a,b) \sim (c,d)\ \) if and only if \(\ ad = bc\)
The set is \(\mathbb{Z}^{+} \times \mathbb{Z}^{+}\), pairs of positive integers, with \((a,b)\) standing for the fraction \(\frac{a}{b}\). Two pairs are related when cross-multiplying gives equal products. The condition \(ad = bc\) says \(\frac{a}{b} = \frac{c}{d}\) without dividing, so it stays inside the integers. For example \(\frac12 = \frac24 = \frac36\), so \((1,2)\), \((2,4)\) and \((3,6)\) are all related.
- Reflexive. Let \((a,b) \in \mathbb{Z}^{+} \times \mathbb{Z}^{+}\). Then \(ab = ba\), so \((a,b) \sim (a,b)\).
- Symmetric. Suppose \((a,b) \sim (c,d)\), so \(ad = bc\). Then \(cb = da\), so \((c,d) \sim (a,b)\).
- Transitive. Suppose \((a,b) \sim (c,d)\) and \((c,d) \sim (e,f)\), so \(ad = bc\) and \(cf = de\). Then \[(af)d = (ad)f = (bc)f = b(cf) = b(de) = (be)d,\] and since \(d \neq 0\) we may cancel it: \(af = be\). So \((a,b) \sim (e,f)\).
Each equivalence class is one positive rational number, with all the ways of writing it: \([(1,2)] = \{(1,2), (2,4), (3,6), \dots\}\). So the positive rationals \(\mathbb{Q}^{+}\) can be built as the classes of this relation. The figure below draws the classes as rays.
Figure 2: The pairs \((a,b)\) with \(a\) and \(b\) from 1 to 6, plotted as points. Two pairs satisfy \(ad = bc\) exactly when they lie on the same line through the origin, so the equivalence classes are the rays out of the origin, and each ray is one positive rational. The red ray holds \((1,2)\), \((2,4)\) and \((3,6)\), the three fractions of \(\tfrac12 = \tfrac24 = \tfrac36\). Six more rays are coloured and labelled with their fraction. Every grey point is on a ray of its own within this window.
The examples side by side
| Relation | on | Equivalence relation? | Classes |
|---|---|---|---|
| \(m \equiv n \pmod 3\) | \(\mathbb{Z}\) | yes | \([0]\), \([1]\), \([2]\) |
| same parity | \(\mathbb{Z}\) | yes | \(\mathbb{Z}^{even}\), \(\mathbb{Z}^{odd}\) |
| \(x - y \in \mathbb{Q}\) | \(\mathbb{R}\) | yes | \([a] = \{y + a : y \in \mathbb{Q}\}\), infinitely many |
| \(8 \mid (m - n)\) or \(8 \mid (m + n)\) | \(\mathbb{Z}\) | yes | five: \([0]\), \([1]\), \([2]\), \([3]\), \([4]\) |
| in the same part of \(\{\{1,2,3\},\{4,5\},\{6\}\}\) | \(\{1,\dots,6\}\) | yes | the three parts |
| \(ad = bc\) | \(\mathbb{Z}^{+} \times \mathbb{Z}^{+}\) | yes | one for each positive rational |
| \(x = y\) | any set | yes | one for each element, \([a] = \{a\}\) |
| \(3 \mid (x^2 - y^2)\) | \(\mathbb{Z}\) | yes | multiples of 3, non-multiples of 3 |
| \(x + y \in \mathbb{Q}\) | \(\mathbb{R}\) | no, not reflexive | — |
| \(x\) is a multiple of \(y\) | \(\mathbb{Z}\) | no, not symmetric | — |
The classes for the first five rows and the ninth are worked in equivalence-classes-and-partitions. The eighth and tenth are \(\gamma\) and \(\beta\) of practice-problems, Q1.
Common mistakes
- Proving two properties and stopping, or checking a property on a few examples. Each property is a “for all”, and needs a general argument about arbitrary elements.
- Assuming the conclusion in the symmetric part. The hypothesis is only \(x \mathrel{\rho} y\). \(y \mathrel{\rho} x\) is what has to come out.
- Reusing a letter when unfolding twice. \(x - y = \frac{a}{b}\) and \(y - z = \frac{a}{b}\) would say the two differences are equal. Use \(\frac{c}{d}\).
- Skipping reflexivity because “symmetric and transitive give it”. They do not (reflexive-symmetric-and-transitive-relations).
- Disproving without a witness. “It isn’t always true that \(x + x\) is rational” is not a disproof. \(x = \sqrt2\) is.
- Forgetting the set. The same rule on a different set is a different relation. \(x + y \in \mathbb{Q}\) fails on \(\mathbb{R}\), but on \(\mathbb{Q}\) every pair is related and it is an equivalence relation with a single class.
See also
- equivalence-classes-and-partitions — the classes of an equivalence relation, and why they partition the set
- reflexive-symmetric-and-transitive-relations — the three properties, one at a time
- relations-on-sets — relations as sets of pairs, and arrow diagrams
- partial-order-relations — the other important kind of relation, with antisymmetric in place of symmetric
- modular-arithmetic · integers-modulo-n — congruence, and its classes as the elements of \(\mathbb{Z}_n\)
- rational-and-irrational-numbers — the definition of rational that the \(x - y \in \mathbb{Q}\) proof unfolds
- 2026-09-21-equivalence-relations — Lecture 24
- practice-problems — §31, with full worked solutions