One might wonder how “common” permutation groups are in math. They are, it turns out, ubiquitous in abstract algebra: in fact, *every group* can be thought of as a group of permutations! We will prove this, but we first need the following lemma. (We will not use the maps \(\rho_a\) or \(c_a\text{,}\) defined below, in our theorem, but define them here for potential future use.)

#####
Lemma6.4.1

Let \(G\) be a group and \(a\in G\text{.}\) Then the following functions are permutations on \(G\text{,}\) and hence are elements of \(S_G\text{:}\)

\(\lambda_a\,:\,G\to G\) defined by \(\lambda_a(x)=ax\text{;}\)

\(\rho_a\,:\,G\to G\) defined by \(\rho_a(x)=xa\text{;}\)

\(c_a\,:\,G\to G\) defined by \(c_a(x)=axa^{-1}\text{.}\)

To show that \(\lambda_a\) is a bijection, first assume \(x_1,x_2 \in G\) with \(\lambda_a(x_1)=\lambda_a(x_2)\text{.}\) Then \(ax_1=ax_2\text{;}\) so, by left cancellation, \(x_1=x_2\text{.}\) Thus, \(\lambda_a\) is one-to-one. Further, each \(y\in G\) equals \(\lambda_a(a^{-1}y)\) for \(a^{-1}y\in G\text{,}\) so \(\lambda_a\) is onto. Thus, \(\lambda_a\) is a bijection from \(G\) to \(G\text{:}\) that is, it's a permutation on \(G\text{.}\) The proofs that \(\rho_a\) and \(c_a\) are bijections are similar.

#####
Definition6.4.2

We say that \(\lambda_a\text{,}\) \(\rho_a\text{,}\) and \(c_a\) perform on \(G\text{,}\) respectively, *left multiplication by \(a\)*, *right multiplication by \(a\)*, and *conjugation by \(a\)*. (Note: Sometimes when people talk about conjugation by \(a\) they instead are referring to the permutation of \(G\) that sends each \(x\) to \(a^{-1}xa\text{.}\))

Now we are ready for our theorem:

#####
Theorem6.4.3Cayley's Theorem

Let \(G\) be a group. Then \(G\) is isomorphic to a subgroup of \(S_G\text{.}\) Thus, every group can be thought of as a group of permutations.

##### Proof

For each \(a\in G\text{,}\) let \(\lambda_a\) be defined, as above, by \(\lambda_a(x)=ax\) for each \(x\in G\text{;}\) recall that each \(\lambda_a\) is in \(S_G\text{.}\) Now define \(\phi\,:\, G\to S_G\) by \(\phi(a)=\lambda_a\text{,}\) for each \(a\in G\text{.}\)

We claim that \(\phi\) is both a homomorphism and one-to-one. Indeed, let \(a,b\in G\text{.}\) Now, \(\phi(a)\phi(b)\) and \(\phi(ab)\) are both functions with domain \(G\text{,}\) so we need to show \((\phi(a)\phi(b))(x)=(\phi(ab))(x)\) for each \(x\in G\text{.}\) Well, let \(x\in G\text{.}\) Then

\begin{align*}
(\phi(a)\phi(b))(x)\amp =(\lambda_a\lambda_b)(x)\amp \amp\\
\amp =\lambda_a(\lambda_b(x)) \amp \amp \text{ (since the operation on \(S_G\) is
composition) }\\
\amp =\lambda_a(bx)\amp \amp\\
\amp =a(bx)\amp \amp\\
\amp =(ab)x\amp \amp\\
\amp =\lambda_{ab}(x)\amp \amp\\
\amp =(\phi(ab))(x).\amp \amp
\end{align*}
So \(\phi\) is a homomorphism. Further, if \(a, b\in G\) with \(\phi(a)=\phi(b)\text{,}\) then \(\lambda_a=\lambda_b\text{.}\) In particular, \(\lambda_a(e)=\lambda_b(e)\text{.}\) But \(\lambda_a(e)=ae=a\) and \(\lambda_b(e)=be=b\text{,}\) so \(a=b\text{.}\) Thus, \(\phi\) is one-to-one.

Since by definition \(\phi(G)\) we have that \(\phi\) maps \(G\) *onto* \(\phi(G)\text{,}\) we conclude that \(\phi\) provides an isomorphism from \(G\) to the subgroup \(\phi(G)\) of \(S_G\text{.}\)