# Partitions and equivalence relations

Recall from last time we introduced the notion of a cyclic group, and said that we’d introduce cosets. For this, we need the notion of partitions and equivalence relations (which are handy in more general scenarios). As I said previously, this is just a transcript of a talk given at the abstract algebra seminars. This talk was given by my good friend, Nadir Akhtar. Since I LiveTeXed it, any errors are mine. (I’ve added a proof that equivalence relations are basically the same as partitions at the end.)

Today we’re going to be talking about equivalence relations between different groups. There are three parts to the definition.

Definition. X is a set, equivalence relation $\sim$.

• reflexive: for every $x\in X$, $x\sim x$.
• symmetry: for all $x,y\in X$, $x\sim y$ if and only if $y\sim x$.
• transitive property: for every $x,y,z\in X$, if $x\sim y$ and $y\sim z$ then $x\sim z$.

All three of these conditions have to be met. Some examples: suppose we have a set $S$ (examples below), and $a,b\in S$. Define $a\sim b$ as $a=b$. Then this is an example of an equivalence relation. For e.g. $S=\mathbf{R,Z,C,Q}$, etc. Here’s a non-example. Suppose $S$ is one of the above sets; then define $a\sim b$ if $a\geq b$. This isn’t an equivalence relation. Now suppose $S=\mathbf{Z}$, and let $a,b\in \mathbf{Z}$. Say that $a\sim b$ if and only if $a\equiv b\bmod n$. This is an equivalence relation. Here’s a nice question: is there an example of a relation on $\mathbf{Z}$, say, which is not transitive?

(A quick review of subgroups.) Consider a group $G$ and a subgroup $H$.

Definition. Define the following equivalence relation on $G$: say that $a\sim b$ if and only if $b^{-1}a\in H$.

Let’s prove that this is an equvialence relation.

Proof. Let $a\in G$. Then $a^{-1}a=e\in H$. So $a\sim a$. Proves reflexivity. Now symmetry. Suppose $a\sim b$. Then $b^{-1}a\in H$. If this is true, then it has an inverse which is also in $H$, because $H$ is a subgroup. Now, $(b^{-1}a)^{-1}=(b^{-1})^{-1}\bullet a^{-1}=b\bullet a^{-1}$. So $ba^{-1}\in H$, and so $b\sim a$. Move on to transitivity. Let $a,b,c\in H$. Suppose $a\sim b$ and $b\sim c$. Then $b^{-1}a,c^{-1}b\in H$. Then multiply them to get $(c^{-1}b)(b^{-1}a)=c^{-1}a\in H$. Thus $a\sim c$. QED.

So another definition is that of the equivalence class. Let’s say that $\sim$ is an equivalence relation on a set $X$, and let $a\in X$. Then the equivalence class of $a$, denoted $[a]$, is defined as $\{b\in X|b\sim a\}$. For example, $X=\mathbf{Z}$, and let $\sim$ be $=$. Then $[a]=\{a\}$. Suppose $\sim$ is $\equiv \bmod 2$. Then if $a$ is odd (resp. even) then $[a]$ is the set of odd numbers (resp. even numbers). (some clarification on modular arithmetic.)

Now onto partitions. Let $X$ be a set. A partition $\mathscr{P}$ of $X$ is a collection of subsets $A_i\subset X$, with $i\in I$, such that:

1. $\bigcup_{i\in I}A_i=X$ (pizza used as an example here; now I’m hungry).
2. For any $i,j\in I$, then $A_i\cap A_j=\emptyset$.

Significance of partitions are: an equivalence relation gives rise to a unique partition, and vice-versa. Suppose we’ve got $\mathbf{Z}$, with $\sim$ given by $\equiv \bmod 2$. Then $[1]$ and $[0]$ are disjoint, and cover $\mathbf{Z}$.

We’ll prove that an equivalence relation gives rise to a unique partition, and vice-versa. Let’s do the first part now. Let $X$ be a set, with equivalence relation $\sim$. Then $x\in [x]$ by reflexivity. Since every element is in some equivalence class, the union of all the equivalence classes contains $X$ itself. So we need to show that none of the equivalence classes intersect each other. Now if $x\sim y$, then $[x]\subset [y]$. So let $a\in [x]$. Then $a\sim x$. And since $x\sim y$, $a\sim y$. But also $[y]\subset[x]$ by symmetry, so if $x\sim y$ then $[x]=[y]$.

Now let $x\in X$ and $y\in X$, and let $a\in[x]\cap[y]$. Since $a\in[x]$, $a\sim x$. Since $a\in [y]$, $a\sim y$. Because of the above, therefore, $[x]=[a]=[y]$! Thus every equivalence class gives rise to a unique partition.

Let $\mathscr{P}=\{A_i|i\in I\}$ be a partition of $X$, and define $\sim$ on $X$ by $x\sim y$ if and only if $x,y\in A_i$. It’s easy to check that this is an equivalence relation. Reversing the above argument shows that an equivalence relation gives rise to a unique partition, and vice-versa!

This is really quite cool. Let $X=\mathbf{Z}$, considered as a group under addition. Let $\sim$ be the equivalence relation on a group with a chosen subgroup earlier, where the subgroup here is $n\mathbf{Z}$. Then this gives rise to an equivalence relation, namely that $a\sim b$ if and only if $a-b$ is a multiple of $n$, i.e., if and only if $a=b+nm$; but then $a\equiv b\bmod n$!

Similarly, we can generalize this to all groups, which leads to the notion of a coset. Let $G$ be a group and let $H\leq G$. Let $\sim$ be the equivalence relation defined on a group with a chosen subgroup defined earlier, and let $g\in G$. Let $[g]$ denote the equivalence class of $g$ under this equivalence relation. Then $[g]=gH=\{gh|h\in H\}$. This is called the left coset of $H$.

To see that $[g]=gH$, suppose $i\in [g]$. Then $g^{-1}i\in H$. Write $k=g^{-1}i\in H$; then $i=gk$. Since $g,k\in gH$, we see that $[g]\subset gH$. Now let $i\in gH$. Then $i=gk$ for some $k$; but then $k=g^{-1}i$, so $i\sim g$. Then $i\in [g]$, so $gH\subset [g]$. QED.

Next time we’ll prove Lagrange’s theorem, which, unfortunately, has had to be postponed yet again!

Have fun,
SKD