# Can someone explain Cayley's Theorem step by step?

This is from Fraleigh's First Course in Abstract Algebra (page 82, Theorem 8.16) and I keep having hard time understanding its proof. I understand only until they mention the map $$\lambda_x (g) = xg$$. Can someone explain this proof step by step? Thank you so much! Here is the proof:

Let $$G$$ be a group. We show that $$G$$ is isomorphic to a subgroup of $$S_G$$.

Define a one-to-one function $$\phi: G \to S_G$$ such that $$\phi(xy)=\phi(x) \phi(y)$$ for all $$x,y \in G$$. For $$x \in G$$, let $$\lambda_x: G \to G$$ be defined by $$\lambda_x (g) = xg$$ for all $$g \in G$$. The equation $$\lambda_x (x^{-1} c) = x(x^{-1} c) = c$$ for all $$c \in G$$ shows that $$\lambda_x$$ maps $$G$$ onto $$G$$. If $$\lambda_x (a) = \lambda_x (b)$$, then $$xa=xb$$ so $$a=b$$ by cancellation. Thus $$\lambda_x$$ is also one to one, and is a permutation of $$G$$. We now define $$\phi: G \to S_G$$ by defining $$\phi(x) = \lambda_x$$ for all $$x \in G$$.

To show that $$\phi$$ is one to one, suppose that $$\phi(x) = \phi(y)$$. Then $$\lambda_x = \lambda_y$$ as functions mapping $$G$$ into $$G$$. In particular $$\lambda_x (e) = \lambda_y (e)$$, so $$xe=ye$$ and $$x=y$$. Thus $$\phi$$ is one to one. It only remains to show that $$\phi(xy) = \phi(x) \phi(y)$$, that is, that $$\phi_{xy} = \lambda_x \lambda_y$$. Now for any $$g \in G$$, we have $$\lambda_{xy} (g) = (xy)g$$. Permutation multiplication is function composition, so $$(\lambda_x \lambda_y)(g) = \lambda_x (\lambda_y (g)) = \lambda_x (yg) = x(yg)$$. Thus by associativity, $$\lambda_{xy} = \lambda_x \lambda_y$$.

• What is it you don't understand?
– Pedro
Apr 22, 2013 at 20:09
• I think this post has a clear example. Cayley's theorem says that any group with $n$ elements can be understood as a subgroup of $S_n$. The example in the post shows in detail how to understand the 4-element "$V$-group" as a subgroup of $S_4$. It can be easy to get lost in notation in the proof, but the basic idea is quite simple.
– MJD
Apr 22, 2013 at 20:15
• The construction of $\lambda_x$ is an example of currying (en.wikipedia.org/wiki/Currying). This is a fundamental construction in mathematics and it is well worth your time to thoroughly understand it; it will reappear over and over again. Apr 23, 2013 at 6:29

First let's think about what Cayley's theorem is trying to do. The desired conclusion is that every finite group is isomorphic to a subgroup of the symmetric group. In order to do this, we prove that the group operation defines permutations of the elements of the group. How do we do this?

Step 1. Suppose we line all of the elements of the $G$ up in some arbitrary order and number them from left to right, like so: $$\begin{array}{ccccc}1 & 2 & 3 & \cdots & n \\ a_1 & a_2 & a_3 & \cdots & a_n \end{array}$$ Step 2. Now pick an element $x\in G$. Let's left multiply all of the elements of $G$ by $x$. $$\begin{array}{ccccc}1 & 2 & 3 & \cdots & n \\ xa_1 & xa_2 & xa_3 & \cdots & xa_n \end{array}$$

Step 3. Multiplying on the left by $x$ rearranges the elements of $G$. Recall that in step 1, we assigned all the elements of $G$ a number. That means we can look up which element $xa_i$ was in step $1$ and write $xa_i=a_j$. This is not very far from saying "$x$ sends the element at position $i$ to position $j$." So let's define a function from $\lambda_x:\{1,\ldots,n \}\rightarrow \{1,\ldots,n \}$ by $\lambda_x(i)=j$ when $x$ sends $a_i$ to $a_j$. This is just another way of writing what we did in step $2$: $$\begin{array}{ccccc}1 & 2 & 3 & \cdots & n \\ a_{\lambda_x(1)} & a_{\lambda_x(2)} & a_{\lambda_x(3)} & \cdots & a_{\lambda_x(n)} \end{array}$$

Step 4. Finally we define $\phi:G\rightarrow S_n$ by $\phi(x)=\lambda_x$. In other words, we're associating the element $x$ with the permutation of $\{1,\ldots, n\}$ that $x$ induces - that is, the permutation $\lambda_x$. It's easy to verify that $\phi$ is an injective homomorphism. So, we're done.

Note that there are a couple details missing from the above proof which you'll find in Fraleigh's (e.g. that $\lambda_x$ is a bijection for any $x$). I recommend you comb through the proof again and prove these subtle points to make sure you understand everything. Good luck!

• I love you, this makes it so clear what is going on. The proofs I had seen looked a bit magic. Feb 1, 2016 at 22:07

For each $$x\in G$$, define function $$\lambda_x: G \to G$$ such that $$\lambda_x(g)=x\cdot g$$ ($$\cdot$$ here means the group operation), for all $$g\in G$$. Since $$G$$ is a group, it is closed under the group operation. So, $$\lambda_x$$ maps $$G$$ to $$G$$, which means that $$\lambda_x$$ is well-defined.

We also know that $$x^{-1}\in G$$. Thus, $$\forall c\in G$$, $$x^{-1}\cdot c\in G.$$ By our definition, $$\lambda_x(x^{-1}\cdot c)=x\cdot (x^{-1}\cdot c)=(x\cdot x^{-1})\cdot c=c$$. This means that for each $$c\in G$$, there exists $$u\in G$$ (with $$u=x^{-1}\cdot c$$) such that $$\lambda_x(u)=c$$, i.e. $$\lambda_x$$ is surjective.

Then we show that $$\lambda_x$$ is injective. For $$a,b\in G$$, suppose $$\lambda_x(a)=\lambda_x(b)$$, i.e. $$x\cdot a = x\cdot b$$. Then we have $$x^{-1}\cdot x\cdot a=x^{-1}\cdot x\cdot b \implies a=b$$. Thus, $$\lambda_x$$ is injective.

Now that we've shown that $$\lambda_x$$ is bijective, it is a permutation of $$G$$. Thus, $$\lambda_x\in S_G$$. We now define $$\phi: G\to S_G$$ by defining $$\phi(x)=\lambda_x$$ for all $$x\in G$$.

What we want to show next is that $$\phi$$ is injective. Once this is proven, we know that $$\phi: G\to \phi(G)$$ is bijective. To show that $$\phi$$ is injective, suppose $$x,y\in G$$ and $$\phi(x)=\phi(y)$$. Then, $$\lambda_x=\lambda_y$$, meaning that for all $$c\in G$$, $$\lambda_x(c)=\lambda_y(c)$$, i.e. $$x\cdot c = y\cdot c.$$ Let $$c=e$$. Then, $$x\cdot e=y\cdot e$$, so $$x=y$$. Thus, $$\phi$$ is injective.

For $$\lambda_x,\lambda_y\in \phi(G)$$, $$\lambda_x\cdot\lambda_y\in \phi(G)$$ because $$\lambda_x\cdot\lambda_y(c)=x\cdot y\cdot c=(x\cdot y)\cdot c=\lambda_{x\cdot y} c$$. Also, observe that $$\lambda_{-x}\in \phi(G)$$. Thus, $$\phi(G)$$ is a subgroup of $$S_G$$,

Lastly, we only need to show that $$G$$ is isomorphic to $$\phi(G)$$. This requires $$\phi(x\cdot y)=\phi(x)\cdot \phi(y)$$.

Note that $$\phi(x\cdot y)=\lambda_{xy}$$ and $$\phi(x)\cdot\phi(y)=\lambda_x\cdot\lambda_y.$$ By our definition, for any $$c\in G$$, we have $$\lambda_{x\cdot y}(c)=(x\cdot y)\cdot c=x\cdot (y\cdot c)=\lambda_x(\lambda_y(c))=\lambda_x\cdot \lambda_y(c)$$. Thus, $$\phi(x\cdot y)=\phi(x)\cdot \phi(y)$$.