We want to discuss rearranging the order of some set.

Let $X$ be a nonempty set. A permutation is a bijection from $X$ to $X$.

It happens that the set of permutations with
the operation of composition is a *group*
(see Groups).^{1}
To see this, suppose $\pi : X \to X$ and
$\sigma : X \to X$ are two permutations.
Then $\pi \circ \sigma $ is a permutation (the
composition of two invertible functions is
invertible).
Also, the identity function $\id_{X}: X \to X$
is a permutation (it has an inverse,
*itself*).
The identity *function* is the identity element, since $\pi \id = \id\pi $ for all
permutations $\pi $.
Since each permutation is invertible, inverse
elements exist.
And the associative law is valid for
permutations since function composition is
associative.
We the group consisting of the set of
permutations on $X$ and the operation of
composition the symmetric group
on $X$.

If $X$ is finite and $\num{X} = n$, then we can associate each element of $X$ with a number $\upto{n}$ and in so doing consider permutations of the set $\set{1, \dots , n}$. This special symmetric group is called the symmetric group of degree $n$.

There are $n!$ permutations (see Factorials).

We denote the symmetric group on $X$ by $\Sym(X)$. It is common to denote the symmetric group of degree $n$ by $S_n$.

- Future editions will likely flip this prerequisite, and develop groups via consideration of polynomials a la Lagrange and Galois. ↩︎