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

Question

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.

Answer 1

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$.

Answer 2

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.

Answer 3

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$.