Group Theory 6: Lagrange's Theorem

 In this lecture, we study Lagrange's Theorem which is named after the Italian/French
mathematician, physicist and astronomer Joseph-Louis Lagrange. It states that the order of a subgroup $H$ of a finite group $G$ divides the order of $G$. Lagrange's Theorem has many important applications in group theory. Before we discuss the theorem we first need to study an important class of binary relations called equivalence relations.

Definition. A binary relation $R$ on a nonempty set $S$ is a subset $R\subset S\times S$. If $(a,b)\in R$, we say $a$ is $R$-related to $b$ and write $aRb$. A binary relation $R$ on a set $S$ is called an equivalence relation on $S$ if it satisfies:

1. $\forall a\in S$, $aRa$. ($R$ is reflexive.)
2. $\forall a,b\in S$, $aRb\Longrightarrow bRa$. ($R$ is symmetric.)
3. $\forall a,b,c\in S$, $aRb$ and $bRc$ $\Longrightarrow$ $aRc$. ($R$ is transitive.)
   

Examples.

1. Define a binary relation $\equiv\mod n$ on $\mathbb{Z}$, the set of integers by$$\forall a,b\in\mathbb{Z},\ a\equiv b\mod n\ \mbox{if}\ n|(a-b).$$Then $\equiv\mod n$ is an equivalence relation on $\mathbb{Z}$, called the congruence relation modulo $n$. If $a\equiv b\mod n$, we say $a$ is congruent to $b$ modulo $n$. Note that $n|(a-b)$ if and only if $a-b=nk$ for some $k\in\mathbb{Z}$ if and only if $a$ and $b$ have the same remainder when they are divided by $n$ if and only if $a-b\in n\mathbb{Z}$ where$$n\mathbb{Z}=\{nk: k\in\mathbb{Z}\},$$the set of all integer multiples of $n$. $\forall n\in\mathbb{Z}$, $n\mathbb{Z}$ is a subgroup of the additive group $(\mathbb{Z},+)$. 

Proof. (a) $\forall a\in\mathbb{Z}$, $n|(a-a)=0\Rightarrow a\equiv a\mod n$. That is, $\equiv\mod n$ is reflexive.

(b) $\forall a,b\in\mathbb{Z}$,
\begin{align*}
a\equiv b\mod n\Rightarrow n|(a-b)&\Rightarrow a-b=nk\ \mbox{for some}\ k\in\mathbb{Z}\\
&\Rightarrow b-a=n(-k)\ \mbox{and}\ -k\in\mathbb{Z}\\
&\Rightarrow n|(b-a)\\
&\Rightarrow b\equiv a\mod n
\end{align*}
That is, $\equiv\mod n$ is symmetric.

(c) $\forall a,b,c\in\mathbb{Z}$,
\begin{align*}
a\equiv b\mod n\ \mbox{and}\ b\equiv c\mod n&\Rightarrow n|(b-a)\ \mbox{and}\ n|(c-b)\\
&\Rightarrow n|[(b-a)+(c-b)]=(c-a)\\
&\Rightarrow a\equiv c\mod n
\end{align*}
That is, $\equiv\mod n$ is transitive. Hence, $\equiv\mod n$ is an equivalence relation on $\mathbb{Z}$.

 

2. Let $G$ be a group and $H\leq G$. Define a binary relation $R$ on $G$ by$$\forall a,b\in G,\ aRb\ \mbox{if}\ ab^{-1}\in H \tag{1}$$Then $R$ is an equivalence relation on $G$.

Proof. a) $\forall a\in G$, $aa^{-1}=e\in H\Rightarrow aRa$. That is, $R$ is reflexive.

(b) $\forall a,b\in G$,
\begin{align*}
aRb&\Rightarrow ab^{-1}\in H\\
&\Rightarrow (ab^{-1})^{-1}=ba^{-1}\in H\\
&\Rightarrow bRa
\end{align*}
That is, $R$ is symmetric.

(c) $\forall a,b,c\in G$,
\begin{align*}
aRb\ \mbox{and}\ bRc&\Rightarrow ab^{-1}\in H\ \mbox{and}\ bc^{-1}\in H\\
&\Rightarrow (ab^{-1})(bc^{-1})=ac^{-1}\in H\\
&\Rightarrow aRc
\end{align*}
That is, $R$ is transitive. Hence, $R$ is an equivalence relation on $G$.

Definition. If $R$ is an equivalence relation on a set $S$, then $[a]$, the equivalence class of $a\in S$, is defined by
$$[a]=\{b\in S: bRa\}.$$

Theorem 1. Let $R$ be an equivalence relation on a set $S$. Then

1. $S=\bigcup_{a\in S}[a]$.
2. $\forall a,b\in S$, either $[a]=[b]$ or $[a]\cap [b]=\emptyset$.
   

Proof.

1. Clearly $\bigcup_{a\in S}[a]\subset S$. Conversely, let $a\in S$. Since $R$ is reflexive, $aRa\Rightarrow a\in [a]\ne\emptyset\Rightarrow S\subset\bigcup_{a\in S}[a]$. Hence, $S=\bigcup_{a\in S}[a]$.
2. Let $a\ne b\in S$. If $[a]\cap[b]=\emptyset$, then we are done. Suppose otherwise. Then
   

\begin{align*}
\exists c\in[a]\cap[b]&\Rightarrow cRa\ \mbox{and}\ cRb\\
&\Rightarrow aRc\ \mbox{and}\ cRb\ (R\ \mbox{is symmetric})\\
&\Rightarrow aRb
\end{align*}
$aRb$ if and only if $[a]=[b]$. The "if" part is clear by the definition of an equivalence class. To prove "only if" part, if $d\in[a]$ then $dRa$. Since $aRb$ and $R$ is transitive, $dRb$ i.e. $d\in[b]$. Thus, $[a]\subset [b]$. Similarly, we also show that $[b]\subset [a]$. Hence, $[a]=[b]$.

This means that an equivalence relation $R$ on a set $S$ partitions $S$ into equivalence classes. The set of all equivalence classes $\{[a]: a\in S\}$ is denoted by $S/R$ and is called the quotient set of $S$ modulo $R$.

The converse of the above theorem is also true, namely

Theorem 2. Let $\wp=\{A_i:i\in I\}$ be a partition of a set $S$ i.e. $S=\bigcup_{i\in I}A_i$ and $\forall i\ne j\in I$, $A_i\cap A_j=\emptyset$. Define a binary relation $R$ on $S$ by
$$\forall a,b\in S,\ aRb\ \mbox{if}\ a,b\in A_i\ \mbox{for some}\ i\in I.$$
Then $R$ is an equivalence relation on $S$, called the equivalence relation induced by the partition $\wp$.

Proof. The proof is left as an exercise for readers. See Problem Set 4 #2.

Example. Let $f: X\longrightarrow Y$ be a surjective map. Then $\{f^{-1}(y): y\in Y\}$ forms a partition of $X$. The equivalence relation induced by this partition is
$$\ker f=\{(a,b)\in X\times X: f(a)=f(b)\}.$$
This equivalence relation is called the kernel of the function $f$.

Proof. We show that $\{f^{-1}(y): y\in Y\}$ forms a partition of $X$. Then by theorem 1, $\ker f$ is an equivalence relation on $X$.

1. Let $x\in X$. Then

$$y=f(x)\in Y\Rightarrow x\in f^{-1}(y)\Rightarrow x\in\bigcup_{y\in Y}f^{-1}(y)$$
Hence, $X=\bigcup_{y\in Y}f^{-1}(y)$.

2. Let $y_1\ne y_2\in Y$. Suppose that $f^{-1}(y_1)\cap f^{-1}(y_2)\ne\emptyset$. Then
$$\exists x\in f^{-1}(y_1)\cap f^{-1}(y_2)\Rightarrow y_1=f(x)\ \mbox{and}\ y_2=f(x)$$
This is a contradiction to $f$ being a function. Hence, $f^{-1}(y_1)\cap f^{-1}(y_2)=\emptyset$.
This completes the proof.

Lemma 3. Let $G$ be a group and $H\leq G$. Recall the equivalence relation $R$ on $G$ in (1).
Then for each $a\in G$, $[a]=Ha$ where $Ha=\{ha:h\in H\}$. $Ha$ is called a right coset of $H$ in $G$.

Proof.

\begin{align*}
b\in[a]&\Leftrightarrow bRa\\
&\Leftrightarrow ba^{-1}\in H\\
&\Leftrightarrow ba^{-1}=h\ \mbox{for some}\ h\in H\\
&\Leftrightarrow b=ha\ \mbox{for some}\ h\in H\\
&\Leftrightarrow b\in Ha
\end{align*}
Hence $[a]=Ha$.

Example. Consider $\equiv\mod n$, the congruence relation modulo $n$ on $\mathbb{Z}$. For each $a\in \mathbb{Z}$, $[a]=n\mathbb{Z}+a$. The right coset $n\mathbb{Z}+a$ is called the congruence class of $a$ modulo $n$.

Now, we are ready to discuss Lagrange's Theorem.

Theorem 4. [Lagrange's Theorem] If $G$ is a finite group and $H\leq G$, then $|H|||G|$.

Proof. By lemma 3, we have $G=Ha_1\cup Ha_2\cup\cdots\cup Ha_k$ and $Ha_i\cap Ha_j=\emptyset$ if $i\ne j$, $i,j=1,2,\dots, k$. Due to the cancellation law, we see that $|H|=|Ha_i|$ for all $i=1,2,\cdots, k$. Therefore,
\begin{align*}
 |G|&=\sum_{i=1}^k|Ha_i|\\
 &=\sum_{i=1}^k|H|\\
 &=k|H|.
\end{align*}
This completes the proof.

If $G$ is finite, the number of right cosets of $H$ in $G$, namely $\frac{|G|}{|H|}$ is called the index of $H$ in $G$ and is denoted by $|G:H|$ or $i_G(H)$. Here, we use the notation $|G:H|$.

It should be noted that the converse of Lagrange's Theorem need not be true. For example, the alternating group of degree 4
$$A_4=\{1,(123),(132),(124),(142),(134),(143),(234),(243),(12)(34),(13)(24),(14)(23)\}$$
has no subgroup of order 6 although $|A_4|=12$ and $6|12$.

Theorem 5. A group $G$ of prime order is cyclic.

Proof. Let $|G|=p$, a prime. Let $H\leq G$. Then by Lagrange's Theorem, $|H|||G|$ and so either $|H|=1$ or $|H|=p$. If $H\ne\{e\}$, then $H=G$. If $a\ne e\in G$, $\langle a\rangle=G$.

Let $G$ be a finite group and $a\ne e\in G$. Then $H=\langle a\rangle\leq G$. So, $a^m=e$ for some $m\in\mathbb{N}$.

Definition. If $G$ is finite, then the order of $a\ne e\in G$, denoted by $|a|$ or $o(a)$, is the least positive integer $n$ such that $a^n=e$.

Corollary 6. If $G$ is finite and $a\ne e\in G$, then $|\langle a\rangle|||G|$.

Theorem 7. If $G$ is a finite group of order $n$, then $a^n=e$ for all $a\in G$.

Proof. Let $a\ne e\in G$ and $|\langle a\rangle|=k$. Then by Lagrange's Theorem $k|n$ i.e. $n=kl$ for some $l\in\mathbb{N}$. So,
$$a^n=a^{kl}=(a^k)^l=e^l=e.$$