Equivalence Relations

definitions
discrete-math
set-theory
relations
proof

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