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

Equivalence relations are often used to group together objects that are similiar in some sense.

Examples of equivalence relations

• The relation "=" between real numbers.
• The relation "is congruent to (modulo 5)" between integers (see modular arithmetic).
• 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

Every equivalence relation on X defines a partition of X into subsets called equivalence classes: all elements equivalent to each other are put into one class. Conversely, if a set can be partitioned into subsets, 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 subset".

For example, if G is a group and H is a subgroup of G, then we can define an equivalence relation ~ on G by writing a ~ b if and only if ab^-1 lies in H. The equivalence classes of this relation are the right coset?s of H in G.

Generating equivalence relations

If two equivalence relations over the set X are given, then their intersection (viewed as subsets of X×X) is also an equivalence relation. This allows for a convenient way of defining equivalence relations: given any binary relation R on X, the equivalence relation generated by R is the smallest equivalence relation containing R.

/Talk