Tags Math

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.