Equivalence relation

An equivalence relation over a set X is a binary relation over X that is reflexive, symmetric and transitive, i.e., if the relation is written as ~ it holds for all a, b and c in X that

1. (Reflexivity) a ~ a
2. (Symmetry) if a ~ b then b ~ a
3. (Transitivity) if a ~ b and b ~ c then a ~ c

Examples of equivalence relations

• The relation "=" between real numbers
• The relation "is congruent to (mod 5)" between integers
• The relation "is similar to" on the set of all triangles.
• The relation "has the same birthday as" on the set of all human beings.

All three conditions are necessary

• The relation ">=" between real numbers is not an equivalence relation, because although it is reflexive and transitive, it is not symmetric. E.g. 7 >= 5 does not imply that 5 >= 7!
• The relation "has a common factor with" between natural numbers is not an equivalence relation, because although it is reflexive and symmetric, it is not transitive (2 and 6 have a common factor, and 6 and 3 have a common factor, but 2 and 3 do not have a common factor).
• The empty relation R on a set 'X' (i.e. 'a' R 'b' is never true) is not an equivalence relation, because although it is vacuously symmetric and transitive, it is not reflexive.

Partitioning into equivalence classes

Equivalence relations are often used to define equivalence classes. Conversely, if a set can be partitioned into classes, then we can define an equivalence relation R by the rule "a R b if and only if a and b lie in the same class".

/Talk