Discrete Math · Undergraduate
Relations, Equivalence Relations and Partial Orders
Quick answer
A relation on a set A is any set of ordered pairs from A × A, written a ~ b when the pair (a, b) is in it. Four properties sort relations: reflexive, symmetric, antisymmetric and transitive. A relation with the first, second and fourth is an equivalence relation, and its equivalence classes split the set into non-overlapping parts, as congruence mod 3 splits the integers into three classes. A relation that is reflexive, antisymmetric and transitive is a partial order, like ≤ or "divides".
What you'll learn
- Test a relation for reflexivity, symmetry, antisymmetry and transitivity
- Recognize equivalence relations and partial orders
- Find the equivalence classes of an equivalence relation
- Pass between partitions and equivalence relations
Relations as sets of pairs
A relation on a set is any collection of ordered pairs from . When we write . “Is less than”, “divides”, “has the same remainder mod ” and “was born in the same month” are all relations.
Four properties sort them. For all , , in :
| Property | Meaning |
|---|---|
| reflexive | |
| symmetric | gives |
| antisymmetric | and force |
| transitive | and give |
An equivalence relation is reflexive, symmetric and transitive: it says two things are “the same” in some respect. A partial order is reflexive, antisymmetric and transitive: it ranks things, though some pairs may not be comparable.
Why equivalence classes never overlap
The equivalence class of is . Suppose two classes and share an element . Then and . By symmetry , and by transitivity . Now anything related to is related to , and the reverse, so . Two classes are either the same class or have nothing in common. By reflexivity every element lies in its own class, so the classes split into non-overlapping parts, a partition. The reverse holds too: any partition defines an equivalence relation, “in the same part”.
Worked examples
Common mistakes
Practice problems
-
Is ” is even” an equivalence relation on the integers? If so, name its classes.
Answer
Yes; the classes are the even and the odd integers.
Full solution
It is congruence mod : reflexive, symmetric and transitive, with two remainder classes.
-
On , which properties does have?
Answer
Reflexive, antisymmetric and transitive, so a partial order; not symmetric
Full solution
is in but is not, so it is not symmetric. Every chain closes up: gives , which is present.
-
Is on the integers a partial order?
Answer
Yes
Full solution
; and force ; gives .
-
How many equivalence classes does congruence mod have on the integers?
Answer
Full solution
One for each remainder , , , .
-
How many relations are there on a set with elements?
Answer
Full solution
has pairs, and each is in or out: .
-
List the pairs of the equivalence relation on whose classes are and .
Answer
Full solution
Two elements are related exactly when they lie in the same part.
-
How many equivalence relations are there on ?
Answer
Full solution
Count partitions: ; three ways to put one element alone and pair the other two; and three singletons. .
-
A student says “is a sibling of” (not counting yourself) is transitive. Test the claim.
Answer
It fails: Ann is a sibling of Ben and Ben of Ann, but Ann is not her own sibling.
Full solution
Transitivity with and would demand , which this relation excludes.
Frequently asked questions
What is a relation on a set?
Any set R of ordered pairs (a, b) with a and b in the set. We write a ~ b, or a R b, when (a, b) is in R.
What makes a relation an equivalence relation?
It is reflexive (a ~ a), symmetric (a ~ b gives b ~ a) and transitive (a ~ b and b ~ c give a ~ c).
What is an equivalence class?
The set [a] of everything related to a. Two classes are either identical or share no elements, so the classes split the set into parts.
What is a partial order?
A relation that is reflexive, antisymmetric (a ~ b and b ~ a force a = b) and transitive, such as ≤ on numbers or ⊆ on sets.
How many equivalence relations does a 3-element set have?
Five, one for each way to split the set into parts: all together, all apart, or one of three ways to pair two elements.