Equivalence Relations

Reflexive + symmetric + transitive: classes that partition a set.

The idea

An equivalence relation makes precise the idea of being alike for present purposes: it relates elements that need not be equal but agree on everything that matters for the problem at hand — two integers leaving the same remainder on division by $3$, two fractions written differently but worth the same, two congruent triangles sitting in different places.

All such notions share three properties, and they are the definition. A relation $\sim$ on a set is an equivalence relation when it is

- reflexive: $a \sim a$ for every $a$; - symmetric: whenever $a \sim b$, also $b \sim a$; - transitive: whenever $a \sim b$ and $b \sim c$, also $a \sim c$.

Given one, collect everything related to a given $a$ into its equivalence class

$[a] = \{x : x \sim a\}.$

The three properties make these classes well behaved: every element lies in at least one class, by reflexivity, and two classes that share an element are the same class, by symmetry and transitivity. So the classes are disjoint and cover the whole set — the relation cuts the set into pieces, one piece for each way of being alike.

Ways to work on it

• Walkthrough. The defining properties and equivalence classes, seen on congruence of integers.
• Practice. Find an equivalence class under congruence mod n.
• Hardest. Equivalence relations correspond to partitions — count them on a small set.

Not sure where to start? Take the ten-question placement test.