Relations / Equivalence Relations
Least You Need to Know: Equivalence Relations
An equivalence relation groups objects into classes using three properties: reflexive, symmetric, and transitive.
The least you need to know
- Equivalence relations are reflexive, symmetric, and transitive.
- Equivalent objects belong to the same equivalence class.
- Equivalence classes partition the underlying set.
- Failing any one of the three properties means the relation is not an equivalence relation.
- Congruence modulo n is a standard equivalence relation.
Key notation
[a]
equivalence class of a
a ~ b
a is related to b
a ≡ b (mod n)
same remainder modulo n
Tiny worked example
- On the integers, define `a ~ b` when `a` and `b` have the same parity.
- Every integer has the same parity as itself, so the relation is reflexive.
- Same parity is symmetric and transitive too.
- The two classes are the even integers and the odd integers.
Common mistakes
- Students often confuse symmetric with transitive.
- Students sometimes list classes that overlap, which cannot happen in a partition.
- Students may verify examples instead of the defining properties.
How to recognize this kind of problem
- The prompt mentions classes or partitions.
- You are asked whether a relation is reflexive, symmetric, and transitive together.
- The relation is defined by equality of some computed feature such as parity or remainder.