2.3Closures and counting relations
The idea
The closure of a relation is the smallest extension that gains a property. Reflexive closure adds the missing (a, a), symmetric closure adds reverses, transitive closure adds all the missing shortcuts (Warshall). Counting how many relations have a property uses the formulas for pairs that are forced or free.
Think of it like this: Filling in a family tree: start with parent-of pairs and keep adding ancestor-of until nothing new appears.
Why it exists
GATE loves "how many reflexive / symmetric / antisymmetric relations exist on an n-set" and "what is the size of the transitive closure".
How it works
- Reflexive closure R ∪ I; symmetric closure R ∪ Rᵀ.
- Transitive closure: keep adding (a, c) whenever (a, b) and (b, c) exist (Warshall, O(n³)).
- Count relations on an n-set: all 2^(n²), reflexive 2^(n²−n), symmetric 2^(n(n+1)/2).
- Antisymmetric 2ⁿ·3^(n(n−1)/2), asymmetric 3^(n(n−1)/2), equivalence Bell(n).
Worked example: Reflexive and symmetric relations on a 4-set
The 4 diagonal pairs are forced; the 6 off-diagonal pairs are chosen in mirrored couples, so 2⁶ = 64.
Now play with it
- →Load the cycle 1 → 2 → 3 → 1 and read its transitive closure.
- →Raise n in the count table to see how fast the numbers grow.
Click a matrix cell to add or remove a pair. Row = first element, column = second.
| 1 | 2 | 3 | |
|---|---|---|---|
| 1 | 0 | 1 | 0 |
| 2 | 0 | 0 | 1 |
| 3 | 0 | 0 | 0 |
| Kind of relation on an n-set | Formula | For n = 3 |
|---|---|---|
| All relations | 2^(n²) | 512 |
| Reflexive | 2^(n²−n) | 64 |
| Irreflexive | 2^(n²−n) | 64 |
| Symmetric | 2^(n(n+1)/2) | 64 |
| Antisymmetric | 2^n · 3^(n(n−1)/2) | 216 |
| Asymmetric | 3^(n(n−1)/2) | 27 |
| Reflexive and symmetric | 2^(n(n−1)/2) | 8 |
| Equivalence relations | Bell number B(n) | 5 |
| Functions A → A | nⁿ | 27 |
| Bijections A → A | n! | 6 |
Check yourself
How many symmetric relations exist on a 3-element set?
Exam notes (the dense version)
Reflexive closure R ∪ I; symmetric closure R ∪ Rᵀ; transitive closure R ∪ R² ∪ … ∪ Rⁿ (Warshall in O(n³)). Counting on an n-set: all 2^(n²); reflexive 2^(n²−n); symmetric 2^(n(n+1)/2); antisymmetric 2ⁿ·3^(n(n−1)/2); asymmetric 3^(n(n−1)/2); equivalence relations Bell(n).
Previous year questions: Sets, Relations & Functions (20)
PYQs are grouped by topic, so this is the full set for Sets, Relations & Functions; try the ones that match this subtopic. Open all 20 on the topic page.