Cayley's Group Isomorphism Theorem

# Cayley's Group Isomorphism Theorem

Recall from the Group Isomorphisms page that we say the groups $(G_1, *_1)$ and $(G_2, *_2)$ are isomorphic, notationally written as $G_1 \cong G_2$ if there exists a bijection $f : G_1 \to G_2$ such that for all $x, y \in G_1$ we have that $f(x *_1 y) = f(x) *_2 f(y)$. If such a bijection $f$ exists, then we call $f$ an isomorphism between the groups $(G_1, *_1)$ and $(G_2, *_2)$.

Also recall from awhile back on The Symmetric Group of a General n-Element Set page that if $A$ is an $n$-element set, then $S_A$ denotes the set of $n!$ permutations of the elements in $A$ (if $A$ is an infinite set then $S_A$ is defined analogously). We also proved that $S_A$ with the binary operation $\circ$ of function composition forms a group, $(S_A, \circ)$.

We will now prove a rather remarkable theorem discovered by Arthur Cayley which says that every group $(G,*)$ is isomorphic to a group of permutations.

 Theorem (Cayley's Group Isomorphism Theorem): Every group $(G, *)$ is isomorphic to a group of permutations $(G^*, \circ)$ where $G^* = \{ \sigma_a : a \in G$ and for each $a \in G$, $\sigma_a = a * x$ for all $x \in G$.
• Proof: In this proof, we will first define the group $G^*$ with the operation $\circ$, $(G^*, \circ)$, and then prove that $(G, *)$ is isomorphic to $(G^*, \circ)$.
• Let $(G, *)$ be a group and let $e$ be the identity element with respect to $*$. For every element $a \in G$ let $\sigma_a : G \to G$ be the function defined for each $x \in G$ by:
(1)
\begin{align} \quad \sigma_a = a * x \end{align}
• We will show that $\sigma_a$ is a permutation by showing that $\sigma_a$ is bijective. Suppose that $\sigma_a(x) = \sigma_a(y)$. Then:
(2)
\begin{align} \quad \sigma_a (x) &= \sigma_a(y) \\ \quad a * x &= a * y \\ \quad a^{-1} * (a * x) &= a^{-1} * (a * y)\\ \quad (a^{-1} * a) * x &= (a^{-1} * a) * y \\ \quad e * x &= e * y \\ \quad x &= y \end{align}
• Therefore $\sigma_a$ is injective. Now let $y \in G$. Then for $x = a^{-1} * y$ we have that:
(3)
\begin{align} \quad \sigma_a (a^{-1} * y) = a * (a^{-1} * y) = (a * a^{-1}) * y = e * y = y \end{align}
• So for all $y \in G$ there exists an $x \in G$ such that $\sigma_a(x) = y$, so $\sigma_a$ is also surjective. Since $\sigma_a$ is both injective and surjective we have by definition that $\sigma_a : G \to G$ is a bijection. Now let $G^*$ be the set of all of these permutations $\sigma_a$ for each $a \in G$, that is :
(4)
\begin{align} \quad G^* = \{ \sigma_a : a \in G \} \end{align}
• We will now show that the set $G^*$ with respect to the operation $\circ$ of function composition forms a group $(G^*, \circ)$. Notice that $G^*$ is a specific set of permutations of elements in $G$, and $S_G$ is the set of all permutations of elements in $G$. We've already proven that $(S_G, \circ)$ forms a group, and $G^* \subseteq S_G$, so we only need to show that $G^*$ is closed under $\circ$ and that for all permutations $\sigma \in G^*$ there exists $\sigma^{-1} \in G^*$ such that $\sigma \circ \sigma^{-1} = \sigma_{e}$ and $\sigma^{-1} \circ \sigma = \sigma_{e}$ where $\sigma_{e}$ is the identity permutation.
• Let $\sigma_a, \sigma_b \in G^*$. Then for all $x \in G$ we have that:
(5)
\begin{align} \quad (\sigma_a \circ \sigma_b)(x) = \sigma_a(\sigma_b(x)) = \sigma_a(b * x) = a * (b * x) = (a * b) * x = \sigma_{a*b} (x) \end{align}
• Since $(G, *)$ is a group, we see that $a*b \in G$, so $\sigma_{a*b} \in G^*$ and $G^*$ is closed under $\circ$.
• Now let $\sigma_a \in G^*$. Since $a \in G$ and $(G, *)$ is a group, we must have that $a^{-1} \in G$ and so $\sigma_{a^{-1}} \in G^*$ where:
(6)
\begin{align} \quad (\sigma_a \circ \sigma_{a^{-1}})(x) = a * (a^{-1} * x) = (a * a^{-1}) * x = e * x = \sigma_e (x) \end{align}
(7)
\begin{align} \quad (\sigma_{a^{-1}} \circ \sigma_a)(x) = a^{-1} * (a * x) = (a^{-1} * a) * x = e * x = \sigma_e (x) \end{align}
• So for each $\sigma_a \in G^*$ there exists $\sigma_{a^{-1}} \in G^*$ such that $\sigma_a * \sigma_{a^{-1}} = \sigma_e$ and $\sigma_{a^{-1}} * \sigma_a = \sigma_e$. Hence $(G^*, \circ)$ forms a group. We will now proceed to show that the group $(G, *)$ is isomorphic to the group of permutation $(G^*, \circ)$.
• Let $f : G \to G^*$ be the function defined for all $a \in G$ by:
(8)
\begin{align} \quad f(a) = \sigma_a (x) \end{align}
• To show that $(G, *)$ and $(G^*, \circ)$ are isomorphic we need to prove that $f$ is a bijection and that for all $x, y \in G$ we have that $f(x * y) = f(x) \circ f(y)$. First suppose that $f(a) = f(b)$. Then:
(9)
\begin{align} \quad f(a) &= f(b) \\ \quad \sigma_a(x) &= \sigma_b(x) \\ \quad a * x &= b * x \\ \quad (a * x) * x^{-1} &= (b * x) * x^{-1} \\ \quad a * (x * x^{-1}) &= b * (x * x^{-1}) \\ \quad a * e &= b * e \\ \quad a &= b \end{align}
• Therefore $f$ is injective. Now for each element $\sigma_a \in G^*$ we have that:
(10)
\begin{align} \quad \sigma_a = f(a) \end{align}
• Therefore $f$ is surjective. Since $f$ is both injective and surjective we have by definition that $f$ is bijective. Lastly, let $a, b \in G$. Then:
(11)
\begin{align} \quad f(a * b) = \sigma_{a * b}(x) = (a * b) * x \quad , \quad f(a) \circ f(b) = \sigma_a \circ \sigma_b = \sigma_a(\sigma_b(x)) = \sigma_a(b * x) = a * (b * x) = (a * b) * x \end{align}
• Hence $f(a * b) = f(a) \circ f(b)$. Thus $(G, *)$ is isomorphic to the group of permutations $(G^*, \circ)$. $\blacksquare$