Return to Theorems, Glossary, Homework Problems.

**Statement:**

Let $A$ be a nonempty set, and let $S_A$ be the collection of all permutations of $A$. Then $S_A$ is a group under permutation multiplication.

**Proof:**

Through previous examples (Example 8.4), we have shown that the composition of two permutations of $A$ yields a permutation of $A$, so $S_A$ is closed under permutation multiplication.

Now permutation multiplication is defined as function composition, and in Section 2, we showed that *function composition is associative*. Hence $\mathscr{G}_1$ is satisfied.

The permutation $\iota$ such that $\iota(a) = a \;\;\forall a \in A$ acts as identity. Therefore $\mathscr{G}_2$ is satisfied.

For a permutation $\sigma$, the inverse function, $\sigma^{-1}$, is the permutation that reverses the direction of the mapping $\sigma$, that is, $\sigma (a)$ is the element $a'$ of $A$ such that $a = \sigma (a')$. The existence of exactly one such element $a'$ is a consequence of the fact that, as a function, $\sigma$ is both one-to-one and onto. For each $a \in A$ we have

(1)and also

(2)so that $\sigma^{-1} \sigma$ and $\sigma \sigma^{-1}$ are both the permutation $\iota$. Thus $\mathscr{G}_3$ is satisfied. $\blacksquare$