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$