Computer Science I / Relations
Practice question · Put in order

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.

Hints
  1. Reflexivity is the cheapest check and disqualifies immediately. Start there.
  2. The last step is not a check but the conclusion the three checks license.
Show the answer
  1. Does every element relate to itself? If not, some element belongs to no class.
  2. Is relatedness mutual? If a relates to b but not the reverse, the grouping has a direction and is not a partition.
  3. Does relatedness chain? If a to b and b to c leaves a and c unrelated, the classes would overlap without merging.
  4. All three hold, so the relation is an equivalence and its classes partition the set.
Why

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.

Read the lesson: Relations →

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