# Groups

## Contents

# 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.

(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

If the binary operation \(\cdot\) satisfies the following properties:

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

\[ \forall g_1, g_2 \in G, g_1 \cdot g_2 \in G. \][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 \][Identity element] There exists an element \(e \in G\) such that

\[ g \cdot e = e \cdot g = g \quad \forall g \in G \][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.

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.

(Commutative group)

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

[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#

(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 \(\Sym(X)\).

(Permutation group)

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

It is known as the permutation group of \(X\) and denoted as \((\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

Let \(\pi\) and \(\sigma\) be permutations.

Then they are both bijections.

Hence Their composition \(\pi \circ \sigma\) is also a bijection.

Hence \(\pi \circ \sigma\) is also a permutation.

Hence \(\Sym(X)\) is closed under function composition.

Associativity

Function composition is by definition associative.

Identity element

Consider the identity function \(\id_X : X \to X\) defined as

\[ \id_X(x) = x \Forall x \in X. \]\(\id_X\) is a bijection. Hence \(\id_X \in\Sym(X)\).

For any \(\pi \in \Sym(X)\), we can see that \(\pi \circ \id_X = \pi\).

Similarly, \(\id_X \circ \pi = \pi\).

Hence \(\id_X\) serves as an identity permutation.

Inverse

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

Hence \((\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

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

One can think of a permutation as a rearrangement of the elements of the set \(X\).

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\).

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#

\(n\))

(Symmetric group of degreeConsider 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\).

\(S_4\))

(Symmetric groupLet \(X = \{ 1, 2, 3, 4 \}\).

Let \(\pi\) and \(\sigma\) be two permutations given by

\[\begin{split} \pi = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 1 & 3 & 2 \end{pmatrix} \text{ and } \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 2 & 4 & 1 \end{pmatrix}. \end{split}\]\(\pi^{-1}\) is given by

\[\begin{split} \pi^{-1} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 3 & 1 \end{pmatrix}. \end{split}\]\(\sigma^{-1}\) is given by

\[\begin{split} \sigma^{-1} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 2 & 1 & 3 \end{pmatrix}. \end{split}\]Then \(\pi \sigma\) is given by

\[\begin{split} \pi \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 2 & 4 \end{pmatrix}. \end{split}\]We have \((\pi \sigma) (i) = \pi (\sigma (i))\). E.g. \((\pi \sigma) (3) = \pi (4) = 2\).

Then \(\sigma \pi\) is given by

\[\begin{split} \pi \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 3 & 4 & 2 \end{pmatrix}. \end{split}\]We can see that \(\pi \sigma \neq \sigma \pi\). Hence the permutation group is not commutative.

(Cardinality of symmetric group)

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

Proof. We can write a permutation as

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

There are \(n\) ways of choosing \(y_1\).

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.

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.

We continue in this manner.

Finally, there is just one way of choosing \(y_n\).

Each choice of \(y_i\) can occur with each choice of \(y_j\).

Hence total number of permutations is given by

\[ n (n - 1) (n -2) \dots 1 = n!. \]