Eli Bendersky’s website » Blog Archive » Equivalence classes and group partitions

Equivalence classes and group partitions

July 17th, 2009 at 3:47 pm

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 a=b is a relation, and so is $a\geq b$ .

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 $A\times A$ . More generally, a binary relation between two sets A and B is a subset of $A\times B$ .

Note it says ordered pairs. What this means is that the order of elements in a relation is important. Intuitively, given the relation $\geq$ and the set of integers, it’s clear that $a\geq b$ does not generally imply $b\geq a$ .

An important sub-class of relations we’ll be most interested with is the equivalence relations:

(II) Equivalence relation: A relation $\sim$ on a set is called an equivalence relation if it’s reflexive, symmetric and transitive:

Reflexive: for all a in S it holds that $a\sim a$ .
Symmetric: for all a and b in S it holds that if $a\sim b$ then $b\sim a$ .
Transitive: for all a, b and c in S it holds that if $a\sim b$ and $b\sim c$ then $a\sim c$ .

Examples: equality is an equivalence relation, but greater-or-equal is not, as $a\geq b$ doesn’t imply $b\geq a$ – the symmetric condition doesn’t hold.

Another important equivalence relation is the congruence modulo an integer, $a\equiv b\: (mod n)$ .

(III) Example: Let G be a group and H a subgroup of G. For $a,b\in G$ , define $a\sim b$ if $ab^{-1}\in H$ . Then $\sim$ 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: $aa^{-1}$ is the identity element e. However, since H is a subgroup of G, it means that $e\in H$ . Therefore $aa^{-1}\in H$ , so $a\sim a$ .

Symmetric: Assume that $ab^{-1}\in H$ . Since H is a subgroup, then this element has an inverse in H: $(ab^{-1})^{-1}\in H$ . Using the associative law of groups several times it’s possible to show that $(ab^{-1})^{-1}=(b^{-1})^{-1}a^{-1}=ba^{-1}$
So, $ba^{-1}\in H$ , hence $b\sim a$ .

Transitive: Given $ab^{-1}\in H$ and $bc^{-1}\in H$ .
$(ab^{-1})(bc^{-1})=ac^{-1}$ So, $ac^{-1}\in H$ , hence $a\sim c$ .

Thus, we’ve proved that this $\sim$ is an equivalence relation. Let’s see a concrete application of the result we’ve just proved:

Consider that if $G=\mathbb{Z}$ with the operation +, and H is the subgroup consisting of all multiples of some n>1 , then $ab^{-1}\in H$ actually means that a+(-b)=kn for some $k\in \mathbb{Z}$ . In other words $a\equiv b\: (mod n)$ . This proves that congruence modulo n is an equivalence relation, since it’s a special case of (III).

(IV) Equivalence class: If $\sim$ is an equivalence relation on S, then [a], the equivalence class of a is defined by $[a] = \{b\in S|b\sim a\}$

For example, let’s take the integers $\mathbb{Z}$ and define an equivalence relation "congruent modulo 5". For instance, $1\sim 6$ . The congruence class of 1 modulo 5 (denoted [1]_5 ) is $\{\mathellipsis, -9, -4, 1, 6, 11, \mathellipsis\}$ .

(V) Group partition: If $\sim$ is an equivalence relation on S, then $S=\bigcup [a]$ for all $a\in S$ , and $[a]\ne [b]$ implies that $[a]\cap [b]=\varnothing$ . In other words, $\sim$ partitions S into disjoint equivalence classes.

Proof: the first part is easy. Since always $a\in [a]$ , then $\bigcup_{a\in S}[a]=S$ . To prove the second part, we’ll show that if $[a]\cap [b]\ne \varnothing$ then [a]=[b] .

Suppose that $[a]\cap [b]\ne \varnothing$ , and let $c\in [a]\cap [b]$ . Therefore $c\sim a$ and $c\sim b$ . But $\sim$ is an equivalence relation and thus is transitive and symmetric. So $a\sim b$ . But this means that a and b are in the same equivalence class: [a]=[b] . Q.E.D.

This entry was posted on Friday, July 17th, 2009 at 15:47 and is filed under Math. You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.

One Response to “Equivalence classes and group partitions”

tadaham Says:
August 1st, 2009 at 01:22
Equivalence classes are very useful stuff.
For example, Given a set of line-segments, partition them into connected sets.

Equivalence classes and group partitions

One Response to “Equivalence classes and group partitions”

Leave a Reply