# symmetric group is generated by adjacent transpositions

## Primary tabs

\documentclass{article}
% this is the default PlanetMath preamble.  as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.

% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}

% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
\usepackage{amsthm}
% making logically defined graphics
%%%\usepackage{xypic}

% there are many more packages, add them here as you need them

% define commands here
\newtheorem{thm}{Theorem}
\begin{document}
\begin{thm}
The symmetric group on $\{1, 2, \ldots, n\}$ is generated by the permutations
$(1, 2), (2, 3), \ldots, (n-1, n).$
\end{thm}

\begin{proof}
We proceed by induction on $n$.  If $n = 2$, the theorem is trivially true
because the the group only consists of the identity and a single transposition.

Suppose, then, that we know permutations of $n$ numbers are generated
by transpositions of successive numbers.  Let $\phi$ be a permutation of
$\{1, 2, \ldots, n+1\}$.  If $\phi(n+1) = n+1$, then the restriction of
$\phi$ to $\{1, 2, \ldots, n\}$ is a permutation of $n$ numbers, hence,
by hypothesis, it can be expressed as a product of transpositions.

Suppose that, in addition, $\phi (n+1) = m$ with $m \neq n+1$.  Consider
the following product of transpositions:
$(n n+1) (n-1 n) \cdots (m+1 m+1) (m m+1)$
It is easy to see that acting upon $m$ with this product of transpositions
produces $+1$.  Therefore, acting upon $n+1$ with the permutation
$(n n+1) (n-1 n) \cdots (m+1 m+1) (m m+1) \phi$
produces $n+1$.  Hence, the restriction of this permutation to
$\{1, 2, \ldots, n\}$ is a permutation of $n$ numbers, so,
by hypothesis, it can be expressed as a product of transpositions.
Since a transposition is its own inverse, it follows that
$\phi$ may also be expressed as a product of transpositions.
\end{proof}
%%%%%
%%%%%
nd{document}