Equivalence relations

An equivalence relation is reflexive, symmetric and transitive, all three at once. It is the mathematical idea of being 'the same in some way'.

Everyday examples: 'has the same birthday as' among students; 'is congruent to' among triangles; 'is parallel to or the same as' among lines.

Proving it means checking the three properties one by one. Take R = {(a, b) : 3 divides a – b} on the integers Z:

• Reflexive: a – a = 0, and 3 divides 0. ✓
• Symmetric: if 3 divides a – b, then 3 divides b – a = –(a – b). ✓
• Transitive: if 3 divides a – b and 3 divides b – c, it divides their sum (a – b) + (b – c) = a – c. ✓

An equivalence relation sorts the set into separate groups, called equivalence classes. Everything inside one class is related; nothing in one class is related to anything in another; and every element lands in exactly one class.

For '3 divides a – b', an integer's class depends only on its remainder when divided by 3, so there are three classes:

• [0] = {..., –3, 0, 3, 6, ...}
• [1] = {..., –2, 1, 4, 7, ...}
• [2] = {..., –1, 2, 5, 8, ...}

Between them they cover all of Z, and no two overlap.

The smallest equivalence relation on a set is the identity relation (each element related only to itself); the largest is the universal relation (one class holding everything).

Counting equivalence relations on a small set: start from the identity relation and add pairs in reverse-pairs at a time, checking that transitivity still holds. On {1, 2, 3}, those containing (1, 2) and (2, 1) are just two: one where 3 stays alone, and the universal one.