Study guide: Relations
Overview
A relation from A to B is a subset of A × B; a relation on A is a subset of A × A. Equality, ≤, “divides”, friendship and “is a prerequisite of” are all relations, and the properties a relation has decide what kind of structure it describes.
Four properties (reflexive, symmetric, antisymmetric, transitive) combine into two cornerstone structures: equivalence relations, which partition a set, and partial orders, which arrange it in a hierarchy.
Key ideas explained
The four properties
Reflexive: (a, a) is in R for every a. Symmetric: (a, b) in R implies (b, a) in R. Antisymmetric: if both (a, b) and (b, a) are in R then a = b. Transitive: (a, b) and (b, c) in R imply (a, c) in R. Symmetric and antisymmetric are not opposites: equality is both, and {(1,2),(2,1),(1,3)} is neither.
Equivalence relations
Reflexive, symmetric and transitive. They split the set into disjoint equivalence classes. Congruence modulo 3 on the integers produces exactly three classes.
Partial orders
Reflexive, antisymmetric and transitive, like “divides” on the positive integers or ⊆ on sets. If every two elements are comparable, the order is total. Hasse diagrams draw a partial order without loops or implied edges.
Closures and composition
A closure is the smallest relation containing R that has a property. The reflexive closure adds missing (a, a) pairs, the symmetric closure adds reverses, and the transitive closure adds every pair connected by a chain. The composition S ∘ R links R-steps followed by S-steps.
Worked examples
Recognising an equivalence relation
Problem. On A = {1,2,3}, let R = {(1,1),(2,2),(3,3),(1,2),(2,1)}.
- Reflexive: all three loops are present.
- Symmetric: (1,2) has its reverse (2,1).
- Transitive: every chain, such as (1,2),(2,1) giving (1,1), lands back inside R.
- The classes are the groups of related elements.
Answer. R is an equivalence relation with classes {1,2} and {3}.
Building a transitive closure
Problem. A = {1,2,3,4}, R = {(1,2),(2,3),(3,4)}.
- Chains of length two: 1→2→3 gives (1,3); 2→3→4 gives (2,4).
- Now 1→3→4 gives (1,4).
- No further new pairs appear.
Answer. The transitive closure is R ∪ {(1,3),(2,4),(1,4)}, six pairs in total.
Enter these same values in the calculator above and compare each step with the working shown here.
Common mistakes to avoid
- Checking transitivity only on pairs that look obviously connected. Every chain must be checked.
- Assuming “not symmetric” means “antisymmetric”.
- Overlooking one missing loop (a, a), which already breaks reflexivity.
- Forgetting that the empty relation on a non-empty set is symmetric and transitive but not reflexive.
Where this shows up in computer science
- The relational model of databases treats a table as a relation, and a join is a composition.
- Transitive closure answers “can A eventually reach B?”, which build systems and package managers rely on.
- Equivalence classes underlie grouping by key, union–find, and modular arithmetic.
Test yourself
Try each question before opening the answer.
Is “divides” on {1,2,3,4,6,12} a partial order? A total order?
A partial order (reflexive, antisymmetric, transitive) but not total, since 2 and 3 are incomparable.
How many equivalence classes does congruence modulo 5 have on the integers?
Five.
What is the fewest pairs a reflexive relation on {1,2,3} can have?
Three: the loops (1,1), (2,2), (3,3).