Definition of Equivalence Relations
You'll learn: What makes a relation an "equivalence relation" and why these three properties matter.
The Core Idea
An equivalence relation is a special kind of relation that behaves like "sameness" or "similarity." Just as equality (=) groups numbers that are exactly the same, equivalence relations partition sets into groups of related objects.
A relation R on a set A is an equivalence relation if and only if it satisfies three properties simultaneously:
1. Reflexivity
Every element is related to itself: for all a ∈ A, we have a R a.
Think: Every person has the same birthday as themselves.
2. Symmetry
If a is related to b, then b is related to a: if a R b, then b R a.
Think: If Alice is a sibling of Bob, then Bob is a sibling of Alice.
3. Transitivity
If a is related to b and b is related to c, then a is related to c: if a R b and b R c, then a R c.
Think: If you live in the same city as Bob, and Bob lives in the same city as Carol, then you live in the same city as Carol.
Example: "Same Remainder When Divided by 3"
Define a R b if a and b have the same remainder when divided by 3.
- Reflexive? Yes: any number has the same remainder as itself.
- Symmetric? Yes: if
aandbshare a remainder, so dobanda. - Transitive? Yes: if
aandbshare a remainder, andbandcshare a remainder, thenaandcdo too.
This partitions integers into three groups: {..., -3, 0, 3, 6, ...}, {..., -2, 1, 4, 7, ...}, {..., -1, 2, 5, 8, ...}
Key Takeaway: An equivalence relation must be reflexive, symmetric, and transitive—all three properties together create a relation that partitions a set into distinct, non-overlapping equivalence classes.