Symmetric Group
The symmetric group $ S_n $, which was mentioned in lecture, is a group of permutation mappings on an arbitrary $ n $ element set. Each element of $ S_n $ is actually a bijection $ \pi:B\to B $ where $ B $ is an arbitrary $ n $ element set. Often, but without loss of generality, $ B $ is taken to be the set $ \{1, 2, \ldots, n\} $. There are $ n! $ elements of $ S_n $. So, for example, the group $ S_3 $ consists of the following 6 elements (each a function from $ \{1, 2, 3\} $ (or any arbitrary 3 element set) to itself):
| $ \pi_e $ | $ e $ | $ 1 \mapsto 1, 2 \mapsto 2, 3 \mapsto 3 $ |
| $ \pi_{12} $ | $ (1 2) $ | $ 1 \mapsto 2, 2 \mapsto 1, 3 \mapsto 3 $ |
| $ \pi_{13} $ | $ (1 3) $ | $ 1 \mapsto 3, 2 \mapsto 2, 3 \mapsto 1 $ |
| $ \pi_{23} $ | $ (2 3) $ | $ 1 \mapsto 1, 2 \mapsto 3, 3 \mapsto 2 $ |
| $ \pi_{123} $ | $ (1 2 3) $ | $ 1 \mapsto 2, 2 \mapsto 3, 3 \mapsto 1 $ |
| $ \pi_{132} $ | $ (1 3 2) $ | $ 1 \mapsto 3, 2 \mapsto 1, 3 \mapsto 2 $ |
The binary operation of the symmetric group is function composition. For example,
$ (\pi_{12} \circ \pi_{23})(x) = \pi_{12}(\pi_{23}(x)) $
But notice (by computing its value on all 3 elements of the domain) that $ \pi_{123} = \pi_{12} \circ \pi_{23} $. This set of functions is actually closed under function composition. It can be shown that this binary operation is associative. Also $ \pi_e $ is obviously the group identity element, and each element has an inverse, specifically:
| $ \pi_e = \pi_e^{-1} $ |
| $ \pi_{12} = \pi_{12}^{-1} $ |
| $ \pi_{13} = \pi_{13}^{-1} $ |
| $ \pi_{23} = \pi_{23}^{-1} $ |
| $ \pi_{123} = \pi_{132}^{-1} $ |
| $ \pi_{132} = \pi_{123}^{-1} $ |
so the group axioms hold.
--Jvaught 20:14, 30 March 2010 (UTC)
