You are handed an unfamiliar relation and want to know whether it partitions its set into classes. Order the checks, from the one that rules out the most to the one that settles it.
- Is relatedness mutual? If a relates to b but not the reverse, the grouping has a direction and is not a partition.
- Does relatedness chain? If a to b and b to c leaves a and c unrelated, the classes would overlap without merging.
- All three hold, so the relation is an equivalence and its classes partition the set.
- Does every element relate to itself? If not, some element belongs to no class.
Hints
- Reflexivity is the cheapest check and disqualifies immediately. Start there.
- The last step is not a check but the conclusion the three checks license.
Show the answer
- Does every element relate to itself? If not, some element belongs to no class.
- Is relatedness mutual? If a relates to b but not the reverse, the grouping has a direction and is not a partition.
- Does relatedness chain? If a to b and b to c leaves a and c unrelated, the classes would overlap without merging.
- All three hold, so the relation is an equivalence and its classes partition the set.
The three properties are checked in increasing order of effort, and each failure has its own consequence.
Reflexivity failing means an element belongs to no class at all, so no partition exists - and it is a single glance to check.
Symmetry failing means the relation has a direction, which produces a hierarchy rather than a grouping; that is a partial order, useful and not a partition.
Transitivity failing is the subtle one, and "is one mile from" is the standard counterexample: symmetric, reflexive if you allow zero distance, and A a mile from B and B a mile from C says nothing about A and C. The classes would have to overlap without merging, which a partition forbids.
Only when all three hold do the classes come out disjoint and exhaustive - which is exactly the argument the equivalence-relation theorem makes.
Practise Relations
The app has 5 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Relations
- Congruence mod 5 partitions the integers into exactly five classes, while "less than or equal to" partitions…
- Task dependencies form a partial order and topological sort produces a valid build order. Why does the…
- R is the relation 'has the same remainder when divided by 4' on the integers. Select every pair of numbers…
- Because 'divides' is transitive on the positive integers, knowing 3 divides 12 and 12 divides 60 is enough to…