Equivalence relations and partitions
Equivalence relations are relations that are reflexive, symmetric and transitive; they exactly correspond to partitions of a set into disjoint equivalence classes — a fundamental idea used to group objects by 'sameness' in engineering problems like modular arithmetic, state minimisation and type/cla
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Equivalence relations let an engineer formalise the idea of 'things that are the same for our purpose'. You will see them in congruence modulo n (useful in hashing and cryptography), in partitioning states in finite automata (state minimisation), and when defining quotient structures (e.g., integers modulo n). Understanding them helps in proofs and algorithms that group or collapse elements without losing essential information.
Key ideas
Start from basic words.
- Set: a collection of distinct objects. We write A, B for sets and a, b for their elements.
- Relation: a relation R on a set A is a subset of A × A (the set of ordered pairs). We write a R b to mean (a,b) ∈ R.
Define the three properties used to identify equivalence relations. Each uses universal quantifiers over A.
Reflexive: A relation R on A is reflexive if
∀a ∈ A, (a,a) ∈ R. That means every element is related to itself.Symmetric: R on A is symmetric if
∀a,b ∈ A, (a,b) ∈ R ⇒ (b,a) ∈ R. If a is related to b then b must be related to a.Transitive: R on A is transitive if
∀a,b,c ∈ A, (a,b) ∈ R ∧ (b,c) ∈ R ⇒ (a,c) ∈ R.Equivalence relation: A relation R on A is an equivalence relation if it is reflexive, symmetric and transitive.
Equivalence class: For x ∈ A, the equivalence class of x under R is the set
[x] = { y ∈ A | y R x }. (Some books reverse the order; here we write y R x.)Partition: A partition of a set A is a collection P = {B1, B2, ..., Bk, ...} of non-empty subsets of A such that (1) the union of all Bi is A, and (2) the subsets are pairwise disjoint: Bi ∩ Bj = ∅ for i ≠ j.
Main theorem (exact statement usually required in exams):
Theorem. Let A be a set.
- If R is an equivalence relation on A, then the set of equivalence classes { [x] | x ∈ A } is a partition of A.
- If P is a partition of A, define a relation R_P by a R_P b iff a and b belong to the same block of P. Then R_P is an equivalence relation on A.
Proof sketch (universities expect stepwise reasoning):
Part 1: R ⇒ partition.
- Non-empty classes: For any x ∈ A, reflexivity gives x R x, so x ∈ [x]. Thus every equivalence class is non-empty.
- Cover A: For any a ∈ A, a ∈ [a]. So ⋃_{x∈A} [x] = A.
- Pairwise disjoint or identical: Suppose [x] ∩ [y] ≠ ∅. Let z be in the intersection. Then z R x and z R y. By symmetry and transitivity we get x R y: from z R x (symmetry) gives x R z, and x R z and z R y (transitivity) give x R y. Now for any w ∈ [x], w R x, and x R y gives w R y (transitivity), so w ∈ [y]. So [x] ⊆ [y]. By symmetry of roles, [y] ⊆ [x]. Therefore [x] = [y]. Hence classes are either equal or disjoint.
Part 2: partition ⇒ equivalence.
- Reflexive: For any a ∈ A, a lies in some block B ∈ P, so a R_P a.
- Symmetric: If a R_P b then a and b lie in the same block, so b R_P a.
- Transitive: If a and b lie in block B and b and c lie in block C then B = C, so a and c lie in same block; hence a R_P c.
Corollary (useful exam fact): There is a one-to-one correspondence between equivalence relations on A and partitions of A. The set of classes is the quotient set A/R, and the canonical projection π: A → A/R maps x ↦ [x].
Other important example definition (common in exams):
- Congruence modulo n on integers Z: fix an integer n ≥ 1. Define a ≡ b (mod n) iff n divides (a − b). This is an equivalence relation. Its equivalence classes are the residue classes [0], [1], ..., [n−1]; there are exactly n such classes.
How to represent relations visually for answers:
- Draw a directed graph (digraph) with a vertex for each element of A. Put an arrow from a to b if a R b. For an equivalence relation you will see loops at every vertex (reflexive) and pairs of opposite arrows (symmetric); transitive edges may make many arrows.
- To show a partition, draw non-overlapping labelled boxes or disjoint ovals, put elements inside each block.
Formulas
∀a ∈ A, (a,a) ∈ R — Reflexive. Symbol meanings: A is a set; a is an element of A; R ⊆ A×A is a relation. Unit: none. Applies: when checking reflexivity.
∀a,b ∈ A, (a,b) ∈ R ⇒ (b,a) ∈ R — Symmetric. Symbol meanings as above. Unit: none. Applies: when checking symmetry.
∀a,b,c ∈ A, (a,b) ∈ R ∧ (b,c) ∈ R ⇒ (a,c) ∈ R — Transitive. Unit: none. Applies: when checking transitivity.
[x] = { y ∈ A | y R x } — Equivalence class of x. Symbol meanings: [x] is the class; y ranges over A. Unit: none. Applies: when constructing classes.
⋃_{x∈A} [x] = A — Classes cover A. Unit: none. Applies: in partition proof.
[x] ∩ [y] = ∅ or [x] = [y] — Classes are disjoint or identical. Unit: none. Applies: in partition proof.
x R y ⇔ [x] = [y] — Characterisation: for an equivalence relation R, two elements are equivalent iff their classes are equal. Unit: none. Applies: testing equivalence or merging classes.
a R_P b ⇔ a and b are in same partition block — Relation defined from a partition. Unit: none. Applies: in converse proof.
Worked examples
Example 1 — Show a relation is equivalence. Question: Let A = {1,2,3}. Define R = { (1,1),(2,2),(3,3),(1,2),(2,1) }. Show whether R is an equivalence relation. Answer (model exam style): Step 1: Reflexive? Check (1,1),(2,2),(3,3) are in R, so yes. Step 2: Symmetric? For (1,2) ∈ R we have (2,1) ∈ R. No other off-diagonal pair. So symmetric. Step 3: Transitive? Check all combinations: the only nontrivial chains are 1 R 2 and 2 R 1 giving 1 R 1 (present). Also 1 R 2 and 2 R 2 give 1 R 2 (present). 2 R 1 and 1 R 2 give 2 R 2 (present). There is no pair that requires (1,3) or similar. So transitive holds. Therefore R is an equivalence relation. Equivalence classes: [1] = {1,2}, [2] = {1,2}, [3] = {3}. Partition: { {1,2}, {3} }.
Example 2 — Congruence classes modulo 3 (typical long answer). Question: Prove that congruence modulo 3 is an equivalence relation on integers Z and list all equivalence classes. Answer:
- Reflexive: for any a ∈ Z, 3 divides a−a = 0, so a ≡ a (mod 3).
- Symmetric: if a ≡ b (mod 3) then 3 | (a−b). Then 3 | (b−a) so b ≡ a (mod 3).
- Transitive: if 3 | (a−b) and 3 | (b−c), then 3 divides (a−c) = (a−b)+(b−c); so a ≡ c (mod 3). Classes: [0] = {...,−6,−3,0,3,6,...}, [1] = {...,−5,−2,1,4,7,...}, [2] = {...,−4,−1,2,5,8,...}. These three disjoint classes partition Z.
Example 3 — From partition to equivalence (construction question). Question: Let A = {a,b,c,d} and partition P = { {a,b},{c},{d} }. Define relation R_P and show R_P is equivalence and list classes. Answer: Define a R_P b iff a and b are in same block. Then check reflexive (each element in a block), symmetric (same block is symmetric), transitive (if a and b in same block and b and c in same block then all three are in that same block). Classes: [a]={a,b}, [b]={a,b}, [c]={c}, [d]={d}. This matches P.
Common mistakes
- Confusing 'equivalence class representative' with the whole class: writing [x] = x (not a set) is wrong.
- Thinking equivalence classes can overlap partially — they are either equal or disjoint. If you think they overlap, you likely made an algebraic mistake.
- Forgetting the empty set edge case: if A = ∅, the relation R = ∅ is vacuously reflexive, symmetric, and transitive (so it is an equivalence relation).
- When defining relation from partition, failing to show blocks are non-empty.
For your exam
Kinds of questions:
- Definitions: state definitions of relation, reflexive/symmetric/transitive and equivalence.
- Short proofs: prove congruence is an equivalence; show equivalence classes partition A (write full proof); show from partition you can make an equivalence relation.
- Long answer: given a relation (list of pairs or rule) check properties and compute classes and the partition; draw digraph and partition diagram.
- Diagram question: draw digraph for R on small set and show equivalence classes as ovals.
- Counting: for a finite set of size n, the number of equivalence relations (partitions) is the Bell number B_n (e.g., B_0=1, B_1=1, B_2=2, B_3=5, B_4=15, B_5=52).
What a full-marks answer includes:
- Precise definitions with quantifiers where required.
- For proofs, clear steps: show nonempty classes, cover, and disjointness for one direction; show reflexive/symmetric/transitive for the other.
- For examples, list equivalence classes explicitly and write partition as collection of sets.
- If asked, describe diagram: list vertices, draw loops at every vertex for reflexivity, and arrows in both directions for symmetric pairs.
Quick check
- Give the three properties that define an equivalence relation.
- If R is an equivalence relation on A and x ∈ A, is x ∈ [x]? Explain briefly.
- Write the equivalence classes of integers under congruence modulo 2. Answers: 1) Reflexive, symmetric, transitive. 2) Yes, because reflexivity gives (x,x) ∈ R so x ∈ [x]. 3) [0]={...,−4,−2,0,2,4,...}, [1]={...,−3,−1,1,3,5,...}.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?