\documentclass[]{article}

\usepackage{epsfig}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{graphicx}
\pagestyle{empty}
%\setlength{\topmargin}{-1in}
%\setlength{\oddsidemargin}{-.3in}
%\setlength{\textheight}{9.5in}
%\setlength{\textwidth}{7.2in}
\newcommand{\bZ}{\mathbb{Z}}
\newcommand{\bR}{\mathbb{R}}
\newcommand{\mcg}{\vspace{0.3cm}}
\newcommand{\blank}{\underline{\hspace{2cm}}}
\newcommand{\solution}[1]{\parbox{1cm}{} \hfill {#1}\parbox{3cm}{: \hrulefill} \\}
\newtheorem*{thm}{Cayley's Theorem}
\newtheorem{p}{Problem}
\begin{document}

\begin{center}
\Large Cayley's Theorem
\end{center}

{\Large M366} \hfill {\Large Fall 2013} \\


\vspace{0.5cm}

{
This homework will guide you to understanding and proving one of the highlights of our course: Cayley's theorem. I am going to look at this homework very carefully, so please take great care in doing it!}

\begin{thm}
	Every finite group $G$ is isomorphic to a subgroup of some symmetric group.
\end{thm}

Philosophically, this is quite amazing. This is saying that symmetric groups contain all finite groups inside themselves. Before we embark in proving the theorem, let us make sure we understand what it means, by doing some examples.

\begin{p}
Construct an injective group homomorphism from $\mathbb{Z}/n\bZ$ to $S_n$.
\end{p}
\begin{p}
Construct an injective group homomorphism from $\mathbb{Z}/2\bZ\oplus\mathbb{Z}/2\bZ\oplus\mathbb{Z}/2\bZ $ to $S_6$.
\end{p}

Now we break down the proof into a couple simple steps.
\begin{p}
Given a finite group $G$ of order $n$, for any fixed $g\in G$ we construct a function:
$$
r_g: G\to G
$$
defined as follows: for any $x\in G$,  $r_g(x)= xg$.
\begin{enumerate}
\item Is $r_g$ a group homomorphism?
\item Prove that $r_g$ is a bijection.
\end{enumerate}
\end{p}

Now, having established that $r_g $ is a bijection between $G$ and itself - and remembering that $G$ is  in particular a set with $n$ elements, then $r_g$ is an element of the symmetric group $S_n$ (we just arbitrarily choose a labeling $1,...n$ of the elements of $G$). This leads us to the next step.

\begin{p}
Now consider the function:
$$
\phi: G \to S_n
$$
defined as follows: for any $g \in G$, $\phi(g)= r_g$.
\begin{enumerate}
\item Prove that $\phi$ is a group homomorphism.
\item Prove that $\phi$ is injective by showing $Ker(\phi)=e$.
\end{enumerate}
\end{p}

All together, $G$ is isomorphic to $Im(\phi)$ which is a subgroup of $S_n$. This proves Cayley's theorem.

We finally note that this proof shows that for every finite  group $G$ of order $n$,  $G$ is isomorphic to a subgroup of $S_n$. Sometimes $n$ is not the smallest integer for which it is possible to find a subgroup isomorphic to $G$ in the symmetric group. For example, in problem $2$ you constructed  an isomorphism between a group of order $8$ and a subgroup of $S_6$. Familiarize yourself with Cayley's algorithm by doing another inefficient thing.

\begin{p}
Realize $S_3$ as a subgroup of $S_6$ using the algorithm in the proof of Cayley's theorem.
\end{p}

\end{document}