Permutations
Why
We want to discuss rearranging the order of some set.
Definition
Let $X$ be a nonempty set. A permutation is a bijection from $X$ to $X$.
As a group
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$.
Finite case
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).
Notation
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. ↩︎