Last time we have introduced a notion of a group $(G, *) .$ In a certain sense which we make precise later in the course, the following example is an ultimate source of all groups.
Let $X$ be an arbitrary set. Consider
$$
\mathcal{B}(X, X) \subset \mathcal{F}(X, X)
$$
the set of all bijections from $X$ to itself $X$.
Since the composition of bijections is a bijection, we have a set with a composition law:
$$
(\mathcal{B}(X, X), \circ)
$$
- This composition law is trivially associative, since the composition of functions is always associative
- $\mathcal{B}(X, X)$ also admits a neutral element with respect to $\circ$ – the identity $\operatorname{map} \operatorname{id}_{X} \in \mathcal{B}(X, X)$.
Now, the point of considering only bijections among all maps $X \rightarrow X$, is that a bijection $f: X \rightarrow X$ always admits an inverse $f^{-1}: X \rightarrow X$ which makes $(\mathcal{B}(X, X), \circ)$ a group. Some of you might have seen this group under the disguise of permutation group of $X$.
The group of bijections is not commutative, unless the set $X$ consists of $\leqslant 2$ elements.
If $G$ is finite set consisting of $|G|$ elements, and we want to specify a composition law on $G$, the most straightforward way is to use a Cayley table. This is a table of size $|G| \times|G|$, with rows and columns labeled by elements of $G$.
To fill out Cayley table, in the cell at the intersection of a row of element $x \in G$ and of a column of element $y \in G$ we record their composition $x * y$.
Given a Cayley table of $(G, *)$ we can read off all the possible compositions of all the pairs of elements of $G .$
Problem $1:$ If $(G, *)$ is a group, then every column (resp. row) of its Cayley table contains every element exactly once.
Let $X={A, B, C}$ and consider the set of bijections $\mathcal{B}(X, X)$. Any bijection would permute elements $A, B, C .$ To define a bijection we have to specify the image of $A$ ( 3 choices), the image of $B$ (only 2 choice left), and the image of $C$ will be determined uniquely. Therefore we will have exactly $3 \times 2=6$ bijections. If $f:{A, B, C} \rightarrow{A, B, C}$ is a bijection, we will represent it as a $2 \times 3$ matrix:
$$
f=\left(\begin{array}{ccc}
A & B & C \
f(A) & f(B) & f(C)
\end{array}\right)
$$
We have the following 6 bijections:
$$
\begin{aligned}
& \mathrm{id}{X}=\left(\begin{array}{lll} A & B & C \ A & B & C \end{array}\right) \ \tau{1}:=\left(\begin{array}{lll}
A & B & C \
A & C & B
\end{array}\right) \tau_{2}:=\left(\begin{array}{lll}
A & B & C \
C & B & A
\end{array}\right) \tau_{3}:=\left(\begin{array}{lll}
A & B & C \
B & A & C
\end{array}\right) \
\mu_{1} &:=\left(\begin{array}{lll}
A & B & C \
B & C & A
\end{array}\right) \mu_{2}:=\left(\begin{array}{lll}
A & B & C \
C & A & B
\end{array}\right)
\end{aligned}
$$
So $G=\mathcal{B}(X, X)$ is
$$
G=\left{\mathrm{id}{X}, \tau{1}, \tau_{2}, \tau_{3}, \mu_{1}, \mu_{2}\right}
$$
To finish description of the group $(G, \circ)$ it remain to construct the (multiplication) Cayley table.
Since each of $\tau_{1}, \tau_{2}, \tau_{3}$ just swaps two elements, we find that $\tau_{i} \circ \tau_{i}=\mathrm{id}_{X} .$
Also, it is easy to see that $\mu_{1}^{2}=\mu_{2}$ and $\mu_{1}^{3}=\mathrm{id}_{X}$. The latter implies that
$$
\mu_{2}^{-1}=\mu_{1}
$$
Therefore $\mu_{2}=\mu_{1}^{-1}$, and since $\left(\mu_{1}^{-1}\right)^{3}=\mathrm{id}_{X}$, we see that
$$
\mu_{2}^{3}=\mathrm{id}_{X}
$$
To see that group $(G, \circ)$ is not commutative, we consider
$$
\tau_{1} \circ \tau_{2} \text { and } \tau_{2} \circ \tau_{1}
$$
Let us find out how map $\tau_{1} \circ \tau_{2}: X \rightarrow X$ acts on $A, B, C:$
$$
\begin{aligned}
&\left(\tau_{1} \circ \tau_{2}\right)(A)=\tau_{1}\left(\tau_{2}(A)\right)=\tau_{1}(C)=B \
&\left(\tau_{1} \circ \tau_{2}\right)(B)=\tau_{1}\left(\tau_{2}(B)\right)=\tau_{1}(B)=C \
&\left(\tau_{1} \circ \tau_{2}\right)(C)=\tau_{1}\left(\tau_{2}(C)\right)=\tau_{1}(A)=A
\end{aligned}
$$
So we see that $\tau_{1} \circ \tau_{2}=\mu_{1}$.
Problem 2: Check hat $\tau_{2} \circ \tau_{1}=\mu_{2}\left(\neq \mu_{1}\right)$. This is a manifestation of the fact that $(G, \circ)$ is not commutative.
So far we have essentially computed the following entries of the Cayley table (see below)
(The first row and column just reflect the fact that $\mathrm{i} d_{X}$ is a neutral element)
\begin{tabular}{c||cccccc}
$\circ$ & $\mathrm{id}{X}$ & $\tau{1}$ & $\tau_{2}$ & $\tau_{3}$ & $\mu_{1}$ & $\mu_{2}$ \
\hline \hline $\mathrm{id}{X}$ & $\mathrm{id}{X}$ & $\tau_{1}$ & $\tau_{2}$ & $\tau_{3}$ & $\mu_{1}$ & $\mu_{2}$ \
$\tau_{1}$ & $\tau_{1}$ & $\mathrm{id}{X}$ & $\mu{1}$ & & & \
$\tau_{2}$ & $\tau_{2}$ & $\mu_{2}$ & $\mathrm{id}{X}$ & & & \ $\tau{3}$ & $\tau_{3}$ & & & $\mathrm{id}{X}$ & & \ $\mu{1}$ & $\mu_{1}$ & & & & $\mu_{2}$ & $\mathrm{id}{X}$ \ $\mu{2}$ & $\mu_{2}$ & & & & $\mathrm{id}{X}$ & $\mu{1}$
\end{tabular}
Part of the Cayley table of $\mathcal{B}(X, X), X={A, B, C}$
From the known compositions, we can formally find, for example, $\mu_{2} \circ \tau_{1}$ :
$$
\tau_{2} \circ \tau_{1}=\mu_{2} \Rightarrow \tau_{2} \circ \tau_{1} \circ \tau_{1}=\mu_{2} \circ \tau_{1} \Rightarrow \tau_{2}=\mu_{2} \circ \tau_{1}
$$
Problem 3: Fill in the remaining entries of the table. Check that the product of two $\tau$ ‘s is either identity of $\mu$, and the product of a $\tau$ and a $\mu$ is always a $\mu .$
Let $(G, )$ be a group. Often we would like to understand $G$ by considering subsets which themselves are groups with respect to $$. To this end we need the following definition.
bset $H \subset G$ is called a subgroup if it satisfies the following properties:
- $e \in H$
- if $x, y \in H$, then $x * y \in H$;
- if $x \in H$, then $x^{-1} \in H$.
9. Clearly $(H, *)$ is itself a group.
Problem 4: Prove that a subset $H \subset G$ satisfying
- if $x, y \in H$, then $\left(x^{-1}\right) * y \in H$,
is a subgroup.
10. Example 3: Obvious subgroups
Any group $(G, *)$ has two obvious subgroups:
- $H={e}$ (trivial subgroup)
- $H=G$.
If subgroup $H$ is neither of the above, we will say that $H \subset G$ is a proper subgroup.
Group $\left(\mathbb{Z}{3},+\right)$ does not have any subgroups besides ${0}$ and $\mathbb{Z}{3}$.
Indeed, we have $\mathbb{Z}{3}={[0],[1],[2]} .$ If $H \in \mathbb{Z}{3}$ is a nontrivial subgroup, then either $[1] \in H$ or $[2] \in H .$ If $[1] \in H$, then by the second property $-[1]=[2] \in H$ and $H=\mathbb{Z}_{3}$.
If $H \subset G$ is a subgroup, and $h \in H$ is an element in $H$, then for any integer $m \in H$ we also have $h^{m} \in H .$
Let $\left(\mathbb{Z}{7}^{\times}, \times\right)$be the set of units (i.e., elements admitting multiplicative inverse) in $\mathbb{Z}{7}$ under multiplication operation. In this group we have a subgroup
$$
H={[1],[6]}
$$
Indeed, since $[6] \times[6]=[36]=[1]$, this subset satisfies all the properties of a subgroup.
There is another proper subgroup in $\left(\mathbb{Z}_{7}^{\times}, \times\right):$
$$
K={[1],[2],[4]} .
$$
Problem 5: Prove that subset $K \subset \mathbb{Z}_{7}^{\times}$satisfies all the properties of a subgroup.
Consider group $(\mathbb{Z},+) .$ Then for any fixed nonzero $m \in \mathbb{Z}$ there is a subgroup of elements divisible by $m$
$$
m \mathbb{Z}:={k \cdot m \mid k \in \mathbb{Z}} \subset \mathbb{Z} .
$$
It turns out that the above example provides an exhaustive list of subgroups of $(\mathbb{Z},+) .$ Specifically, we have the following theorem:
Let $H \subset \mathbb{Z}$ be a subgroup with respect to addition. Then either $H$ is trivial:
$$
H={0}
$$
or $H$ is of the form
$$
H=m \mathbb{Z}
$$
for some fixed nonzero $m \in \mathbb{Z}$.
Proof. Assume that $H$ is nontrivial. Then we have some nonzero integer $a \in H .$ By subgroup property, we also have $-a \in H$, hence there is at least one positive integer in $H$.
Let $m$ be the smallest positive integer in $H$. We claim that $H=m \mathbb{Z}$.
- $m Z \subset H:$ Since $m \in H$, by subgroup properties, we have $-m \in H, 2 m=m+m \in H$, and, more generally, for any $k \in \mathbb{Z}$ we have $k \cdot m \in H .$ This proves $m \mathbb{Z} \subset H .$
- $H \subset m \mathbb{Z}$. Let us take any element $a \in H$. We claim that $a$ is divisible by $m$ without remainder. Indeed, let us divide $a$ by $m$ with remainder:
$$
a=m \cdot q+r, \quad r \in{0,1, \ldots, m-1}
$$
Since $a \in H$ and $m \in H$, by subgroup properties we have
$$
a-k \cdot m \in H
$$
for any $k \in \mathbb{Z}$. In particular taking $k=q$ we conclude that
$$
r \in H .
$$
But $m$ is the smallest positive element of $H$, therefore $r$ must be 0 .