Aside on equivalence relations

A **relation** on a set is a subset of . By a slight abuse of notation, let us write, for any , if and only if . An **equivalence relation** is a relation satisfying (for equivalence relations, we write instead of )

- for all , (reflexive),
- for all , implies (symmetric),
- for all , if and then (transitivity).

- The most common example of an equivalence relation is equality .
- Another example is from high school geometry: the similarity or congruence relation for triangles.
- If is a fixed modulus then modulo is an equivalence relation. The verification of this is left as an exercise.

The **equivalence class** of is

David Joyner 2007-09-03