The Symmetric Group of a General n-Element Set

Recall from The Symmetric Groups, Sn page that if we consider the set $\{1, 2, ..., n \}$ then the symmetric group on $n$ elements is the set $S_n$ of all $n!$ permutations of $\{ 1, 2, ..., n \}$ with the binary operation $\circ$ of function composition.

Now consider any arbitrary set $A$ containing $n$ elements, say $A = \{ x_1, x_2, ..., x_n \}$. We can define a more general type of group of all of the permutations of the elements in $A$ (starting with any induced ordering of the elements in $A$) with the binary composition of function $\circ$ yet again.

Definition: Let $A = \{ x_1, x_2, ..., x_n \}$ be an $n$-element set. Then the Symmetric Group on $A$ is the set $S_A$ of all permutations of elements from $A$ with the binary operation $\circ$ of function composition.

For example, consider the set $A = \{ x, y, z \}$. Then the bijections $\sigma_1, \sigma_2, \sigma_3, \sigma_4, \sigma_5, \sigma_6 : A \to A$ define all of the permutations of the elements in $A$:

(1)

\begin{align} \quad \sigma_1 = \begin{pmatrix} x & y & z\\ x & y & z \end{pmatrix} , \quad \sigma_2 = \begin{pmatrix} x & y & z\\ x & z & y \end{pmatrix} , \quad \sigma_3 = \begin{pmatrix} x & y & z\\ y & x & z \end{pmatrix} \\ \sigma_4 = \begin{pmatrix} x & y & z\\ y & z & x \end{pmatrix} , \quad \sigma_5 = \begin{pmatrix} x & y & z\\ z & x & y \end{pmatrix} , \quad \sigma_6 = \begin{pmatrix} x & y & z\\ z & y & x \end{pmatrix} \end{align}

Let $S_A = \{\sigma_1, \sigma_2, \sigma_3, \sigma_4, \sigma_5, \sigma_6 \}$. Then for all $\sigma_i, \sigma_j \in S_A$ for $i, j \in \{1, 2, ..., 6 \}$ we have that $\sigma_i \circ \sigma_j \in S_A$ since $S_A$ consists of ALL permutations of elements from $A$. Since all of the $\sigma$'s are functions, the operation $\circ$ of function composition is inherently associative. The identity element is $\sigma_1$ which is the (bijective) identity function on the set $A$. Furthermore, each element in $S_A$ has an inverse (as you should verify), and hence $(S_A, \circ)$ is a group. (In some sense, $(S_A, \circ)$ is like $(S_3, \circ)$).

Now, consider the subset $G_{x_1} \subseteq S_A$ defined by:

(2)

\begin{align} \quad G_{x_1} = \{ \sigma_i \in S_A : \sigma_i (x_1) = x_1 \} \end{align}

In the examples above, we have that $G_{x_1} = \{ \sigma_1, \sigma_2 \}$ since $\sigma_1(x_1) = x_1$ and $\sigma_2(x_1) = x_1$. To verify that whether $G_{x_1}$ paired with $\circ$ is a subgroup of $S_A$ we will only need to check whether $G_{x_1}$ is closed under $\circ$ and whether each element in $G_{x_1}$ has an inverse in $G_{x_1}$.

We noted that $\sigma_1$ was the identity element of $(S_A, \circ)$ and fortunately $\sigma_1 \in G_{x_1}$. Now notice that $\sigma_1 \circ \sigma_1 = \sigma_1$ and $\sigma_2 \circ \sigma_2 = \sigma_1$. Therefore each element in $G_{x_1}$ has an inverse in $G_{x_1}$. Therefore $(G_{x_1}, \circ)$ is a subgroup of $(S_A, \circ)$.

We can generalize the observation above in the following proposition.

Proposition 1: Let $A$ be any set and let $a \in A$. Let $G_a \subseteq S_A$ be defined to be the set of permutations $\sigma$ of $S_A$ such that $\sigma(a) = a$, i.e., $G_a = \{ \sigma \in S_A : \sigma(a) = a \}$. Then $(G_a, \circ)$ is a subgroup of $(S_A, \circ)$.

• Proof: Since $G_a \subseteq S_A$ we only need to show that $G_a$ is closed under $\circ$ and that every element in $G_a$ has an inverse in $G_a$.

• Let $\sigma_1$ be the identity permutation of $S_A$. Then $\sigma_1(x) = x$ for all $x \in A$, and in particular, $\sigma_1(a) = a$. Therefore $\sigma_1 \in G_a$.

• Now let $\sigma \in G_a$. Then $\sigma(a) = a$. We note that there indeed exists an inverse in $S_A$, call it $\sigma^{-1}$ such that $\sigma^{-1}(\sigma(a)) = a$. But $\sigma(a) = a$, so $\sigma^{-1}(a) = a$. Hence $\sigma^{-1} \in G_a$. So for all $\sigma \in G_a$ there exists a $\sigma^{-1} \in G_a$ such that $\sigma(\sigma^{-1}) = \sigma_1 = \sigma^{-1}(\sigma)$.

• Hence $(G_a, \circ)$ is a subgroup of $(S_A, \circ)$. $\blacksquare$