1.10. Groups

We introduce the notion of groups in this section.

Note

All functions in this section are total functions.

1.10.1. Definition

A group is a set with a single binary operation. It is one of the simplest algebraic structures.

Definition 1.115 (Group)

Let $G$ be a set. Let $\cdot :G\times G\to G$ be a binary operation defined on $G$ mapping $(g_1,g_2)\to \cdot (g_1,g_2)$ and denoted as

$$\cdot (g_1,g_2)\triangleq g_1\cdot g_2.$$

If the binary operation $\cdot$ satisfies the following properties:

1. [Closure] The set $G$ is closed under the binary operation $\cdot$. i.e.

   $$\mathrm{\forall }{g}_1,g_2\in G,g_1\cdot g_2\in G.$$

2. [Associativity] For every $g_1,g_2,g_3\in G$

   $$g_1\cdot (g_2\cdot g_3)=(g_1\cdot g_2)\cdot g_3$$

3. [Identity element] There exists an element $e\in G$ such that

   $$g\cdot e=e\cdot g=g\mathrm{\forall }g\in G$$

4. [Inverse element] For every $g\in G$ there exists an element $g^{-1}\in G$ such that

   $$g\cdot g^{-1}=g^{-1}\cdot g=e$$

then the set $G$ together with the operator $\cdot$ denoted as $(G,\cdot )$ is known as a group.

Above properties are known as group axioms. Note that commutativity is not a requirement of a group.

Remark 1.22

Frequently, the group operation is the regular mathematical addition. In those cases, we write $g_1\cdot g_2$ as $g_1+g_2$. Otherwise, we will write $g_1\cdot g_2$ as $g_1{g}_2$.

Often, we may simply write a group $(G,\cdot )$ as $G$ when the underlying operation $\cdot$ is clear from the context.

1.10.1.1. Commutative groups

A commutative group is a richer structure than a group. Its elements also satisfy the commutativity property.

Definition 1.116 (Commutative group)

Let $(G,\cdot )$ be a group such that its binary operation $\cdot$ satisfies an additional property:

1. [Commutativity] For every $g_1,g_2\in G$

   $$g_1{g}_2=g_2{g}_1$$

Then $(G,\cdot )$ is known as a commutative group or an Abelian group.

1.10.2. Permutation Groups

Definition 1.117 (Permutation)

Let $X$ be a nonempty set. A bijective function $\pi :X\to X$ is called a permutation of $X$.

The set of all permutations of a set $X$ is denoted by $\mathrm{Sym}(X)$.

Theorem 1.37 (Permutation group)

Let $X$ be a nonempty set. The set of all permutations of $X$, namely $\mathrm{Sym}(X)$, is a group under the operation of function composition.

It is known as the permutation group of $X$ and denoted as $(\mathrm{Sym}(X),\circ )$.

Proof. Since every permutation $\pi :X\to X$ is a bijection, hence it has a unique inverse function ${\pi }^{-1}:X\to X$ which is also a permutation (as it is also a bijection).

Closure

1. Let $\pi$ and $\sigma$ be permutations.

2. Then they are both bijections.

3. Hence Their composition $\pi \circ \sigma$ is also a bijection.

4. Hence $\pi \circ \sigma$ is also a permutation.

5. Hence $\mathrm{Sym}(X)$ is closed under function composition.

Associativity

1. Function composition is by definition associative.

Identity element

1. Consider the identity function ${\mathrm{id}}_X:X\to X$ defined as

   $${\mathrm{id}}_X(x)=x\mathrm{\forall }x\in X.$$

2. ${\mathrm{id}}_X$ is a bijection. Hence ${\mathrm{id}}_X\in \mathrm{Sym}(X)$.

3. For any $\pi \in \mathrm{Sym}(X)$, we can see that $\pi \circ {\mathrm{id}}_X=\pi$.

4. Similarly, ${\mathrm{id}}_X\circ \pi =\pi$.

5. Hence ${\mathrm{id}}_X$ serves as an identity permutation.

Inverse

1. Since bijections are invertible, hence for every permutation, there exists an inverse permutation.

Hence $(\mathrm{Sym}(X),\circ )$ is a group.

1.10.2.1. Permutations on Finite Sets

Let $X$ be a finite set written as $X=\{x_1,\dots ,x_n\}$. A convenient way of writing a permutation of a finite set is

(1.3)$$\begin{array}{r}\pi =\left(\begin{array}{cccc}{x}_1& x_2& \dots & x_n\\ \pi (x_1)& \pi (x_2)& \dots & \pi (x_n)\end{array}\right)\end{array}$$

1. We can see that the two rows are two different (ordered) arrangements of the elements of $X$.

2. One can think of a permutation as a rearrangement of the elements of the set $X$.

3. Recall from Definition 1.84 that for a finite set, there exists a bijection from the set $\{1,\dots ,n\}$ to the set $X$ given by $i\mapsto x_i$.

4. Hence, for every permutation of a finite $X$, there exists a corresponding permutation of the set $\{1,\dots ,n\}$.

1.10.2.2. Symmetric Groups

Definition 1.118 (Symmetric group of degree $n$)

Consider the set $X=\{1,\dots ,n\}$. The set of all permutations of $X$ under the operation of function composition is known as the symmetric group of degree $n$ and is denoted by $S_n$.

Example 1.24 (Symmetric group $S_4$)

1. Let $X=\{1,2,3,4\}$.

2. Let $\pi$ and $\sigma$ be two permutations given by

   $$\begin{array}{r}\pi =\left(\begin{array}{cccc}1& 2& 3& 4\\ 4& 1& 3& 2\end{array}\right)\text{ and }\sigma =\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 2& 4& 1\end{array}\right).\end{array}$$

3. ${\pi }^{-1}$ is given by

   $$\begin{array}{r}{\pi }^{-1}=\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 4& 3& 1\end{array}\right).\end{array}$$

4. ${\sigma }^{-1}$ is given by

   $$\begin{array}{r}{\sigma }^{-1}=\left(\begin{array}{cccc}1& 2& 3& 4\\ 4& 2& 1& 3\end{array}\right).\end{array}$$

5. Then $\pi \sigma$ is given by

   $$\begin{array}{r}\pi \sigma =\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 1& 2& 4\end{array}\right).\end{array}$$

   We have $(\pi \sigma )(i)=\pi (\sigma (i))$. E.g. $(\pi \sigma )(3)=\pi (4)=2$.

6. Then $\sigma \pi$ is given by

   $$\begin{array}{r}\pi \sigma =\left(\begin{array}{cccc}1& 2& 3& 4\\ 1& 3& 4& 2\end{array}\right).\end{array}$$

7. We can see that $\pi \sigma \ne \sigma \pi$. Hence the permutation group is not commutative.

Theorem 1.38 (Cardinality of symmetric group)

Let $X$ be a finite set with $n$ elements. Then $|\mathrm{Sym}(X)|=n!$.

Proof. We can write a permutation as

$$\begin{array}{r}\pi =\left(\begin{array}{cccc}{x}_1& x_2& \dots & x_n\\ y_1& y_2& \dots & y_n\end{array}\right)\end{array}$$

1. We need to count the number of ways of constructing the second row.

2. There are $n$ ways of choosing $y_1$.

3. Once $y_1$ has been chosen, there are $n-1$ ways of choosing $y_2$ since $y_1$ cannot be chosen again as $\pi$ is injective.

4. Similarly, there are $n-2$ ways of choosing $y_3$ since $y_1$ and $y_2$ have already been chosen and cannot be chosen again.

5. We continue in this manner.

6. Finally, there is just one way of choosing $y_n$.

7. Each choice of $y_i$ can occur with each choice of $y_j$.

8. Hence total number of permutations is given by

   $$n(n-1)(n-2)\dots 1=n!.$$