After studying additive groups modulo $n$, we now move from number-based groups to transformation groups. A permutation is a bijective function from a finite set to itself, and permutations form groups under composition. These groups are central because they describe symmetry and rearrangement. They also provide the first natural examples of non-commutative groups. In this lesson, students will learn the symmetric group $\mathbb{S}_n$, verify the group axioms under composition, and compute basic products and inverses of permutations. :::definition[Permutation] Let $X$ be a non-empty finite set. A $permutation$ of $X$ is a bijective function $$\begin{equation*} \sigma:X\to X. \end{equation*}$$ When $X=\{1,2,\ldots,n\}$, the set of all permutations of $X$ is denoted by $\mathbb{S}_n$. ::: :::definition[Symmetric Group] Let $n\in\mathbb{N}$. The set $\mathbb{S}_n$ of all permutations of $\{1,2,\ldots,n\}$ is called the $symmetric group of degree n$ under composition of functions. ::: The operation in $\mathbb{S}_n$ is composition. If $\sigma,\tau\in\mathbb{S}_n$, then $\sigma\circ\tau$ means first apply $\tau$ and then apply $\sigma$. This order is important. In general, $\sigma\circ\tau$ need not equal $\tau\circ\sigma$. This is why permutation groups are the standard first examples of non-abelian groups. :::theorem Let $n\in\mathbb{N}$. Then $(\mathbb{S}_n,\circ)$ is a finite group under composition of functions. ::: :::proof Given that $\mathbb{S}_n$ is the set of all permutations of $\{1,2,\ldots,n\}$ and $\circ$ is composition of functions. To prove that $(\mathbb{S}_n,\circ)$ is a finite group. [1] To prove closure. Let $\sigma,\tau\in\mathbb{S}_n$. Then $\sigma$ and $\tau$ are bijections from $\{1,2,\ldots,n\}$ to itself. The composition of two bijections is again a bijection. Therefore $$\begin{equation*} \sigma\circ\tau\in\mathbb{S}_n. \end{equation*}$$ [2] To prove associativity. Let $\sigma,\tau,\rho\in\mathbb{S}_n$. Since composition of functions is associative, $$\begin{equation*} (\sigma\circ\tau)\circ\rho=\sigma\circ(\tau\circ\rho). \end{equation*}$$ [3] To prove the existence of identity element. Let $I$ be the identity function on $\{1,2,\ldots,n\}$. Then $I\in\mathbb{S}_n$ and $$\begin{equation*} \sigma\circ I=I\circ\sigma=\sigma \quad \forall\, \sigma\in\mathbb{S}_n. \end{equation*}$$ Therefore $I$ is the identity element. [4] To prove the existence of inverse elements. Let $\sigma\in\mathbb{S}_n$. Since $\sigma$ is a bijection, it has an inverse function $\sigma^{-1}$, which is also a bijection from $\{1,2,\ldots,n\}$ to itself. Thus $\sigma^{-1}\in\mathbb{S}_n$ and $$\begin{equation*} \sigma\circ\sigma^{-1}=\sigma^{-1}\circ\sigma=I. \end{equation*}$$ Therefore every element has an inverse in $\mathbb{S}_n$. Since there are $n!$ permutations of an $n$-element set, $\mathbb{S}_n$ is finite and $$\begin{equation*} |\mathbb{S}_n|=n!. \end{equation*}$$ Hence, $(\mathbb{S}_n,\circ)$ is a finite group. $\square$ ::: :::example The group $\mathbb{S}_3$ has $3!=6$ elements. They are $$\begin{equation*} I,\quad (12),\quad (13),\quad (23),\quad (123),\quad (132). \end{equation*}$$ Here $(12)$ swaps $1$ and $2$, while $(123)$ sends $1$ to $2$, $2$ to $3$, and $3$ to $1$. ::: :::example The group $\mathbb{S}_2$ has $2$ elements: $$\begin{equation*} \mathbb{S}_2=\{I,(12)\}. \end{equation*}$$ The element $(12)$ has order $2$, because $$\begin{equation*} (12)\circ(12)=I. \end{equation*}$$ Thus $\mathbb{S}_2$ is a finite group of order $2$. ::: :::solved-problem Compute $(123)\circ(12)$ in $\mathbb{S}_3$, using the convention that the right permutation is applied first. ::: :::solution Let $\sigma=(123)$ and $\tau=(12)$. To compute $\sigma\circ\tau$. Apply $\tau$ first and then $\sigma$. For $1$: $$\begin{align*} 1&\xrightarrow{\tau}2\\ 2&\xrightarrow{\sigma}3. \end{align*}$$ Thus $1$ maps to $3$. For $3$: $$\begin{align*} 3&\xrightarrow{\tau}3\\ 3&\xrightarrow{\sigma}1. \end{align*}$$ Thus $3$ maps to $1$. For $2$: $$\begin{align*} 2&\xrightarrow{\tau}1\\ 1&\xrightarrow{\sigma}2. \end{align*}$$ Thus $2$ maps to $2$. Therefore the product sends $1$ to $3$, $3$ to $1$, and fixes $2$. Hence, $$\begin{equation*} (123)\circ(12)=(13). \end{equation*}$$ $\square$ ::: :::solved-problem Show that $\mathbb{S}_3$ is not abelian. ::: :::solution Let $\sigma=(123)$ and $\tau=(12)$ in $\mathbb{S}_3$. To prove that $\mathbb{S}_3$ is not abelian. From the previous computation, $$\begin{equation*} \sigma\circ\tau=(13). \end{equation*}$$ Now compute $\tau\circ\sigma$. Apply $\sigma$ first and then $\tau$. For $1$: $$\begin{align*} 1&\xrightarrow{\sigma}2\\ 2&\xrightarrow{\tau}1. \end{align*}$$ Thus $1$ maps to $1$. For $2$: $$\begin{align*} 2&\xrightarrow{\sigma}3\\ 3&\xrightarrow{\tau}3. \end{align*}$$ Thus $2$ maps to $3$. For $3$: $$\begin{align*} 3&\xrightarrow{\sigma}1\\ 1&\xrightarrow{\tau}2. \end{align*}$$ Thus $3$ maps to $2$. Therefore $$\begin{equation*} \tau\circ\sigma=(23). \end{equation*}$$ Since $$\begin{equation*} (13)\neq(23), \end{equation*}$$ we get $$\begin{equation*} \sigma\circ\tau\neq\tau\circ\sigma. \end{equation*}$$ Hence, $\mathbb{S}_3$ is not abelian. $\square$ ::: :::remark The identity element in a permutation group is the identity function, not the number $1$. The inverse of a permutation is its inverse function. Students often confuse cycle notation with multiplication of numbers. In permutation groups, the operation is function composition, and the order of composition must be respected. ::: A permutation of $\{1,2,3\}$ can be viewed as a directed map from each input to its image. We compare $\sigma\circ\tau$ with $\tau\circ\sigma$ by following arrows in opposite orders. Enter two image lists and observe that the two products may differ. This makes non-commutativity visible as a change in the final image list. :::scientific-preview[Permutation Composition Comparison] @libraries: plotly ::: Use the calculator to compose two permutations of $\{1,2,3\}$. Enter each permutation as a list of images, so $2,3,1$ means $1\mapsto2$, $2\mapsto3$, and $3\mapsto1$. The calculator applies the second permutation first and then the first. This matches the convention used in the worked problem above. :::calculator[Permutation Product] ::: :::exercise [1] Define $\mathbb{S}_n$. [2] Prove that $\mathbb{S}_n$ is closed under composition. [3] How many elements does $\mathbb{S}_4$ have? [4] Find the inverse of $(123)$ in $\mathbb{S}_3$. [5] Give two elements of $\mathbb{S}_3$ that do not commute. ::: :::answer [1] $\mathbb{S}_n$ is the set of all permutations of $\{1,2,\ldots,n\}$. [2] The composition of two bijections from the set to itself is again a bijection from the set to itself. [3] $|\mathbb{S}_4|=4!=24$. [4] The inverse of $(123)$ is $(132)$. [5] For example, $(123)$ and $(12)$ do not commute. ::: :::faq Q: What is the operation in $\mathbb{S}_n$? A: The operation is composition of functions. Q: What is the identity element in $\mathbb{S}_n$? A: The identity permutation $I$. Q: How many elements does $\mathbb{S}_n$ have? A: It has $n!$ elements. Q: Is every symmetric group abelian? A: No. $\mathbb{S}_n$ is non-abelian for $n\geq3$. ::: :::call-to-action[Alternating Groups] subtitle: Continue to even permutations and alternating groups as important finite subgroups of symmetric groups. button: Next Lesson | /abstract-algebra/introduction-to-groups/standard-examples-of-groups/alternating-groups button-ghost: Previous Lesson | /abstract-algebra/introduction-to-groups/standard-examples-of-groups/additive-groups-modulo-n :::