Let $f: G \rightarrow H$ be a group homomorphism. Then $f$ is injective if and only if kernel of $f$ is trivial, i.e.:
$$
\operatorname{Ker}(f)=\left{e_{G}\right}
$$
Proof. Recall that
$$
\operatorname{Ker}(f)=\left{x \in G \mid f(x)=e_{H}\right} .
$$
We need to prove the statement in two directions.
- If $f$ is injective, then $\operatorname{Ker}(f)=\left{e_{G}\right} .$ Indeed, for any homomorphism $e_{G} \in \operatorname{Ker}(f)$, since $f\left(e_{G}\right)=e_{H} .$ On the other hand, since $f$ is injective, there is at most one element in $G$ which is mapped to $e_{H}$, thus Ker $(f)$ must consist of a single element.
- If $\operatorname{Ker}(f)=\left{e_{G}\right}$, then $f$ is injective.
Take any two elements $x, y \in G$ such that $f(x)=f(y)$. We are about to prove that $x=y$. Consider $x y^{-1} \in G$. For this element we have
$$
f\left(x y^{-1}\right)=f(x) f\left(y^{-1}\right)=f(x) f(y)^{-1}=e_{H},
$$
where in the first equality we used the defining property of a homomorphism, in the second equality we used the statement that $f(y)^{-1}=f\left(y^{-1}\right)$ and the last equality follows from the assumptions $f(x)=f(y)$.
Thus $x y^{-1} \in \operatorname{Ker}(f)$. Since $\operatorname{Ker}(f)$ consists only of $e_{G}$ this implies $x=y$.
The above proposition gives a very efficient way to check whether a given homomorphism is injective or not.
If $f: G \rightarrow H$ is an injective homomorphism, then $G$ is isomorphic to a subgroup Im $(G) \subset H$, where
$$
\operatorname{Im}(g)={f(x) \mid x \in G} \subset H
$$
Indeed, $f$ establishes a bijection between $G$ and $\operatorname{Im}(G)$ and respects the group operations.
Let $G$ be a finite group of size $n .$ Then $G$ is isomorphic to a subgroup of $S_{n} .$
Proof. We will construct an injective homomorphism from $G$ to $S_{n}$ :
$$
f: G \rightarrow S_{n}
$$
Label all elements of $G$ by $\left{a_{1}, a_{2}, \ldots a_{n}\right} .$ We will assign a permutation $\sigma \in S_{n}$ to every element $x \in G$ as follows.
Consider a string of elements in $G$ :
$$
x a_{1}, \ldots, x a_{n} .
$$
By the left cancellation property (or ‘Sudoku’ rule) this string contains all every element in $\left{a_{1}, \ldots, a_{n}\right}$ exactly once. In other words, there is a permutation $\sigma$ such that each $x a_{i}$ equals $a_{\sigma(i)}$. Thus we define $f(x)=\sigma \in S_{n}$.
- $f$ is a homomorphism. Assume that $f(x)=\sigma$ and $f(y)=\mu$. Then, to compute $f(x y)$ we analyze the effect of multiplying $\left{a_{1}, \ldots, a_{n}\right}$ with $x y$ :
$$
x y a_{1}, \ldots, x y a_{n}
$$
by definition of $f(y)=\mu$ is the same as
$$
x a_{\mu(1)}, \ldots x a_{\mu(n)}
$$
which in its turn by definition of $f(x)=\sigma$ is the same as
$$
a_{\sigma(\mu(1))}, \ldots, a_{\sigma(\mu(n))}
$$
Thus $f(x y)=\sigma \circ \mu=f(x) \circ f(y)$, proving that $f$ is a homomorphism.
- To prove that $f$ is injective, we just observe that if $x \in G$ is not identity, then
$$
x a_{1} \neq a_{1}
$$
thus $f(x)$ can not be the identity permutation. Thus $\operatorname{Ker}(f)=\left{e_{G}\right}, \operatorname{implying}$ that $f$ is injective.
This theorem shows that permutation group is in some sense ‘universal’, and understanding well-enough permutation group $S_{n}$ we can derive statements about groups of size $n$.
Consider $G=\mathbb{Z}_{4}$ and label its elements as
$$
a_{1}=0, a_{2}=1, a_{3}=2, a_{4}=3 .
$$
We will follow the construction in the above proof and provide an injective homomorphism $f: \mathbb{Z}{4} \rightarrow S{4} .$ The Cayley table for this group looks like
$$
\begin{array}{c|cccc}
- & a_{1} & a_{2} & a_{3} & a_{4} \
\hline a_{1} & a_{1} & a_{2} & a_{3} & a_{4} \
a_{2} & a_{2} & a_{3} & a_{4} & a_{1} \
a_{3} & a_{3} & a_{4} & a_{1} & a_{2} \
a_{4} & a_{4} & a_{1} & a_{2} & a_{3}
\end{array}
$$
Thus we can read off the map $f$ by considering rows of this table:
$$
f\left(a_{1}\right)=\left(\begin{array}{llll}
1 & 2 & 3 & 4 \
1 & 2 & 3 & 4
\end{array}\right)=\mathrm{i} d
$$
which is not surprising as $a_{1}=0$ is the neutral element. Proceeding in the same way, we find
$$
f\left(a_{2}\right)=\left(\begin{array}{llll}
1 & 2 & 3 & 4 \
2 & 3 & 4 & 1
\end{array}\right) \quad f\left(a_{3}\right)=\left(\begin{array}{llll}
1 & 2 & 3 & 4 \
3 & 4 & 1 & 2
\end{array}\right) \quad f\left(a_{4}\right)=\left(\begin{array}{llll}
1 & 2 & 3 & 4 \
4 & 1 & 2 & 3
\end{array}\right)
$$
In other words, $f$ sends $a_{2}=1$ to the cycles $(1234)$, and sends all other elements to its corresponding powers.
7. Definition 1: Dihedral groups
The group of rigid motions of a regular polygon with $n$ vertices $P_{n}(n \geqslant 3)$ is called the $n$-th dihedral group $D_{n}$.
For $n=3$ we get the group of rigid motions of an equilateral triangle, which consists of 3 axial symmetries, 2 rotations by $\pm 120^{\circ}$ and the identity. We know that
$$
D_{3} \simeq S_{3} .
$$
Let us label vertices of the polygon as ${1,2, \ldots, n} .$ Then any rigid motion of the polygon induces a permutation of ${1,2, \ldots, n}$, since every rigid motion permutes the vertices. Thus we can think of $D_{n}$ as a subgroup of $S_{n}$.
10. Proposition 2: Counting rigid motions
$\left|D_{n}\right|=2 n$
Proof. To count the number of elements in $D_{n}$, we first observe that every rigid motion $f$ of the polygon is completely determined by the images of two adjacent vertices 1 and 2 .
For vertex 1 we have exactly $n$ options for where to map it – any of the $n$ vertices of the polygon. If we fix
$$
f(1)=k
$$
then for vertex 2 we have exactly two options to define $f(2)$ :
$$
f(2)=k-1 \quad \text { or } \quad f(2)=k+1 .
$$
Overall this gives $n \times 2$ options, and we have $\left|D_{n}\right|=2 n$.
Let $r \in D_{n}$ be a rotation by $2 \pi / n$ clockwise, and denote by $s \in D_{n}$ the reflection in the axis going through vertex 1 and the center of the polygon. Then
$$
D_{n}=\left{r^{0}, r^{1}, \ldots, r^{n-1}, s r^{0}, s r^{1}, \ldots, s r^{n-1}\right}
$$