Subgroups of Sufficiently Large Symmetric Groups / Cayley's Theorem explanation

Here's the question: is every finite group a subgroup of a symmetric group of sufficiently large order? More specifically, if a group $G$ has order $n$, then is it true that $G \le S_{n}$?

For instance, both groups of order $4$ can be found in $S_4$. $\{(1), (1 2 3 4), (1 3)(2 4), (1 4 3 2)\} \cong C_4$ and $\{(1), (1 2), (3 4), (1 2)(3 4)\} \cong \mathbb{Z}_2 \times \mathbb{Z}_2$. Also, in general, $C_n, A_n, D_{2n}, S_n \le S_n$.

After a short investigation, I was unable to find a subgroup in $S_4$ that was congruent to $Q$, the unit quaternions, but I would be quite surprised if $Q \not\le S_8$.

Okay, the answer is "yes", and this is known as Cayley's Theorem. However, the link points to a proof-less page and the proofs given on Wikipedia aren't very clear, so I would really, really appreciate a clear, intuitive, and conceptual proof of Cayley's Theorem.

• What is the action of each element of $Q$ on the elements of $Q$. I.e., how does "multiplication on the left by the element $x$" permute the elements of $Q$ as you iterate $x$ through $Q$? This should suggest to you that the multiplication table of a group can be embedded in permutations of the elements of the group... – Eric Towers Jul 8 '14 at 1:36
• – David Jul 8 '14 at 1:37
• @David: Cayley's Theorem is exactly what I was suspecting. – El'endia Starman Jul 8 '14 at 1:41
• – lhf Jul 8 '14 at 2:03
• Please explain why the proofs at Wikipedia do not work for you. – lhf Jul 8 '14 at 2:36

The intuation is that $$gG=G$$ for any $g\in G$ which means that every $g$ of permutes the elements of $G$. Surprisingly the corresponding permutations elements constitute a subgroup of $S_G$ which is isomorphic to $G$.
If $G$ is simple, $G$ can be embeded into $A_n$ where $n$ is the smallest index of nontrivial subgroup of $G$.
In any group $G$, any element $g \in G$ defines a function from $G$ to itself denoted $L_g : G \to G$, called "left multiplication": $$L_g(h) = gh$$ The group axioms show that this function is injective $$L_g(h) = L_g(h') \iff gh = gh' \iff h=h'$$ and that it is onto $$L_g(g^{-1} h) = g g^{-1} h = h$$ Therefore the formula $g \mapsto L_g$ defines a function $G \mapsto Sym(G)$, where $Sym(G)$ denotes the "symmetric group" of the set $G$, namely the group of self-bijections of $G$. The group axioms also show that the function $g \mapsto L_g$ is a homomorphism $$L_{g_1} \circ L_{g_2} (h) = g_1(g_2(h)) = (g_1 g_2)(h) = L_{g_1 g_2}(h)$$ and that it is injective $$L_g(h)=h \iff gh=h \iff g=Id$$ Therefore, $G$ embeds in $Sym(G)$ which is isomorphic to $S_{|G|}$; that isomorphism is obtained by enumerating the elements of $G$.
Yup. $G$ is always a subgroup of $S_{|G|}$.
On a related note, the question of the smallest $n$ such that $G\leq S_n$ is, in general, not known.