Eli Bendersky's website In this post I want to show some interesting definitions and theorems about equivalence relations & classes, and groups.
Relations are an important topic in algebra. Conceptually, a relation is a statement aRb about two elements of a set. If the elements are integers, then 
is a relation, and so is 
.
Here's a formal set-theoretic definition:
(I) Binary relation: A binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is the subset of 
. More generally, a binary relation between two sets A and B is a subset of 
.
Note it says ordered pairs. What this means is that the order of elements in a relation is important. Intuitively, given the relation 
and the set of integers, it's clear that does not generally imply 
.
An important sub-class of relations we'll be most interested with is the equivalence relations:
(II) Equivalence relation: A relation 
on a set is called an equivalence relation if it's reflexive, symmetric and transitive:
- Reflexive: for all a in S it holds that
. - Symmetric: for all a and b in S it holds that if
then 
. - Transitive: for all a, b and c in S it holds that if and
then 
.
Examples: equality is an equivalence relation, but greater-or-equal is not, as doesn't imply - the symmetric condition doesn't hold.
Another important equivalence relation is the congruence modulo an integer, 
.
(III) Example: Let G be a group and H a subgroup of G. For 
, define if 
. Then is an equivalence relation on G.
Proof: To prove that some relation is an equivalence relation, we have to prove the three properties of equivalence relations.
Reflexive: 
is the identity element e. However, since H is a subgroup of G, it means that 
. Therefore 
, so .
Symmetric: Assume that . Since H is a subgroup, then this element has an inverse in H: 
. Using the associative law of groups several times it's possible to show that 
So, 
, hence .
Transitive: Given and 
.
So, 
, hence .
Thus, we've proved that this is an equivalence relation. Let's see a concrete application of the result we've just proved:
Consider that if 
with the operation +, and H is the subgroup consisting of all multiples of some 
, then actually means that 
for some 
. In other words . This proves that congruence modulo n is an equivalence relation, since it's a special case of (III).
(IV) Equivalence class: If is an equivalence relation on S, then [a], the equivalence class of a is defined by 
For example, let's take the integers 
and define an equivalence relation "congruent modulo 5". For instance, 
. The congruence class of 1 modulo 5 (denoted 
) is 
.
(V) Group partition: If is an equivalence relation on S, then 
for all 
, and 
implies that 
. In other words, partitions S into disjoint equivalence classes.
Proof: the first part is easy. Since always 
, then 
. To prove the second part, we'll show that if 
then 
.
Suppose that , and let 
. Therefore 
and 
. But is an equivalence relation and thus is transitive and symmetric. So . But this means that a and b are in the same equivalence class: . Q.E.D.