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.*

## Comments

comments powered by Disqus