Discrete Math › Section C · Graph theory › Topic C.8

Equivalence relations and partitions

Mathematics often treats different things as "the same" for some purpose: numbers with the same remainder, people born in the same month, triangles of the same shape. Equivalence relations make that idea exact, and they always sort a set into neat, non-overlapping groups.

Sameness in some respect

Sort a class of students by birth month and two students land in the same pile exactly when they share a month. That rule behaves like equality in three ways. Everyone shares a month with themselves. If Ana shares a month with Ben, then Ben shares one with Ana. If Ana shares with Ben and Ben with Cara, then Ana shares with Cara. These are the three properties from the previous topic: reflexive, symmetric and transitive. Any relation with all three behaves like a kind of equality that ignores some details, such as the day and year of birth.

The definition

An equivalence relation on a set \(A\) is a relation that is reflexive, symmetric and transitive. It is often written \(a \sim b\). Examples: "has the same blood type as" on people; "has the same length as" on words; "has the same absolute value as" on the integers. Each property must be checked. "Is less than or equal to" is reflexive and transitive but not symmetric. "Lives within 10 km of" is reflexive and symmetric but not transitive: \(a\) can be 8 km from \(b\) and \(b\) 8 km from \(c\), with \(a\) and \(c\) 16 km apart.

Congruence modulo n

Fix a positive integer \(n\). Integers \(a\) and \(b\) are congruent modulo \(n\) when \(n\) divides \(a - b\):

a \equiv b \pmod{n} \iff n \mid (a - b)

So \(23 \equiv 8 \pmod{5}\), because \(23 - 8 = 15\) is a multiple of 5. Equivalently, \(a\) and \(b\) leave the same remainder on division by \(n\), as long as remainders are taken between 0 and \(n - 1\), even for negative numbers: \(-2 \equiv 3 \pmod{5}\), since \(-2 - 3 = -5\). Clock times work modulo 12: 15 hours after 9 o'clock it is 12 o'clock again.

Worked example: congruence is an equivalence relation

Prove that congruence modulo \(n\) is an equivalence relation on the integers. 1. Reflexive: \(a - a = 0 = n \cdot 0\), so \(n \mid (a - a)\) and \(a \equiv a\). 2. Symmetric: if \(a - b = nk\) for an integer \(k\), then \(b - a = n(-k)\), so \(b \equiv a\). 3. Transitive: if \(a - b = nk\) and \(b - c = nm\), add the two equations to get \(a - c = n(k + m)\), so \(a \equiv c\). 4. All three hold, so congruence modulo \(n\) is an equivalence relation. Each step used only the definition of divisibility.

Equivalence classes

The equivalence class of \(a\) is the set of everything equivalent to it:

[a] = \{b \in A : a \sim b\}

Modulo 3, the integers fall into three classes: \([0] = \{\ldots, -3, 0, 3, 6, \ldots\}\), \([1] = \{\ldots, -2, 1, 4, 7, \ldots\}\) and \([2] = \{\ldots, -1, 2, 5, 8, \ldots\}\). Any member can name its class: \([1] = [4] = [-2]\). Under "has the same absolute value" on the integers, the classes are \(\{0\}\), \(\{1, -1\}\), \(\{2, -2\}\) and so on, infinitely many classes of size at most 2.

Two classes never partly overlap

Any two equivalence classes are either identical or disjoint. Suppose \([a]\) and \([b]\) share an element \(c\), so \(a \sim c\) and \(b \sim c\). By symmetry \(c \sim b\), and by transitivity \(a \sim b\). Now any \(x\) in \([b]\) has \(b \sim x\), so \(a \sim x\) by transitivity, putting \(x\) in \([a]\). The same argument the other way gives \([a] \subseteq [b]\), so \([a] = [b]\). Reflexivity adds one more fact: every \(a\) lies in its own class \([a]\), so no class is empty and every element belongs to some class.

Partitions

A partition of a set \(A\) is a collection of non-empty subsets, called blocks, such that every element of \(A\) lies in exactly one block. The previous card shows that the equivalence classes of any equivalence relation form a partition. The reverse is also true: given a partition, the rule "\(a \sim b\) when \(a\) and \(b\) lie in the same block" is an equivalence relation, and its classes are exactly the blocks. So equivalence relations and partitions are two descriptions of one idea. For example, \(\{1, 2, 3\}\) has exactly 5 partitions, so it has exactly 5 equivalence relations. Computing is full of partitions: a hash table splits items into buckets by hash value, and "is an anagram of" splits a word list into groups such as {listen, silent, enlist}.

Worked example: from a partition to its pairs

Partition \(A = \{1, 2, 3, 4, 5, 6\}\) into the blocks \(\{1, 6\}\), \(\{2, 3, 5\}\) and \(\{4\}\). 1. The matching equivalence relation contains \((a, b)\) exactly when \(a\) and \(b\) share a block. 2. A block of size \(k\) contributes \(k \times k\) ordered pairs, including the loops. 3. So the relation has \(2^2 + 3^2 + 1^2 = 4 + 9 + 1 = 14\) pairs. 4. Listing the first block: \((1,1), (1,6), (6,1), (6,6)\). 5. Check the classes: \([5] = \{2, 3, 5\}\) and \([4] = \{4\}\), recovering the blocks. In the directed graph, each block appears as a cluster with every arrow and loop inside it.

Quotient sets and arithmetic on classes

The set of all equivalence classes is the quotient set, written \(A/{\sim}\). For congruence modulo \(n\) it is \(\mathbb{Z}_n = \{[0], [1], \ldots, [n-1]\}\), with exactly \(n\) classes. We can add classes by adding any representatives: \([a] + [b] = [a + b]\). This is well defined, meaning the answer never depends on which representatives you pick. Modulo 5, \([2] + [4] = [6] = [1]\); using 7 for \([2]\) and 9 for \([4]\) instead gives \([16]\), which is \([1]\) again. The later topic on GCD, congruences and modular arithmetic builds on this.

Common mistakes to avoid

First, checking only one or two of the three properties; "lives within 10 km of" fails only transitivity. Second, picturing classes that overlap; two classes are identical or disjoint. Third, forgetting that a partition has no empty blocks and must cover every element. Fourth, mishandling negatives in congruences: \(-1 \equiv 4 \pmod{5}\), because their difference, \(-5\), is a multiple of 5. Fifth, counting pairs in a relation from a partition without the loops \((a, a)\).

Key takeaways

An equivalence relation is reflexive, symmetric and transitive: a precise kind of sameness. Congruence modulo \(n\), where \(n\) divides \(a - b\), is the central example. The class \([a]\) collects everything equivalent to \(a\), and two classes are either equal or disjoint. So the classes form a partition, and every partition defines an equivalence relation whose classes are its blocks. The quotient set collects the classes; \(\mathbb{Z}_n\) has \(n\) of them, and adding classes through representatives is well defined.

Flashcards

Flashcard

Equivalence relation

A relation that is reflexive, symmetric and transitive

A precise kind of sameness.

Test your understanding

Question 1 of 5

Which of these relations on people is NOT an equivalence relation?

Question 2 of 5

Which integer is in the same equivalence class as 3 modulo 4?

Question 3 of 5

How many different equivalence relations are there on the set {1, 2, 3}?

Question 4 of 5

A partition of {1, 2, 3, 4, 5} has blocks {1, 2} and {3, 4, 5}. How many ordered pairs are in the matching equivalence relation?

Question 5 of 5

For an equivalence relation, the classes [a] and [b] share at least one element. What follows?

← Previous topicNext topic →