Theorem 8.5

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)
\begin{align} \iota (a) = a = \sigma (a') = \sigma (\sigma^{-1}(a)) = (\sigma \sigma^{-1})(a) \end{align}

and also

(2)
\begin{align} \iota (a') = a' = \sigma^{-1} (a) = \sigma^{-1} (\sigma(a')) = (\sigma^{-1} \sigma)(a'), \end{align}

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

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License