# 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:

- 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:

- Therefore $\sigma_a$ is injective. Now let $y \in G$. Then for $x = a^{-1} * y$ we have that:

- 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 :

- 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:

- 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:

- 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:

- 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:

- Therefore $f$ is injective. Now for each element $\sigma_a \in G^*$ we have that:

- 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:

- Hence $f(a * b) = f(a) \circ f(b)$. Thus $(G, *)$ is isomorphic to the group of permutations $(G^*, \circ)$. $\blacksquare$