Equivalence relations

A relation that is reflexive, symmetric and transitive at once is an equivalence relation.

Congruence of triangles in a plane is one: every triangle is congruent to itself, T₁ ≅ T₂ gives T₂ ≅ T₁, and T₁ ≅ T₂, T₂ ≅ T₃ give T₁ ≅ T₃.

On the integers Z, a R b ⇔ 2 divides a − b is an equivalence relation. Reflexive: a − a = 0 is divisible by 2. Symmetric: if 2 divides a − b it divides b − a = −(a − b). Transitive: a − c = (a − b) + (b − c) is a sum of two even numbers, hence even.

The same argument works with any fixed divisor: a R b ⇔ 3 divides a − b is also an equivalence relation on Z.

Relations of the form 'has the same … as' are equivalence relations: the same parity, the same number of pages, the same distance from the origin. More generally, for any function f on X, a R b ⇔ f(a) = f(b) is an equivalence relation on X.

If R₁ and R₂ are equivalence relations on A, then R₁ ∩ R₂ is one too, because each of the three properties survives the intersection.

The smallest equivalence relation containing a given pair: on {1, 2, 3}, the one containing (1, 2) must hold the three diagonal pairs and the mirror pair (2, 1), five pairs in all. Adding any further pair forces, by symmetry and transitivity, all the rest, so only two equivalence relations on {1, 2, 3} contain (1, 2): this one and the universal relation.