\chapter{Homomorphisms and quotient groups}
\label{ch:homomorphisms_quotient}
\section{Generators and group presentations}
\prototype{$D_{2n} = \left< r,s \mid r^n=s^2=1, rs = sr\inv\right>$}

Let $G$ be a group.
Recall that for some element $x \in G$,
we could consider the subgroup
\[ \left\{ \dots, x^{-2}, x^{-1}, 1, x, x^2, \dots \right\} \]
of $G$.
Here's a more pictorial version of what we did:
\textbf{put $x$ in a box, seal it tightly, and shake vigorously}.
Using just the element $x$,
we get a pretty explosion that produces the subgroup above.

What happens if we put two elements $x$, $y$ in the box?
Among the elements that get produced are things like
\[ xyxyx, \quad x^2y^9x^{-5}y^3, \quad y^{-2015}, \quad \dots\]
Essentially, I can create any finite product of $x$, $y$, $x\inv$, $y\inv$.
This leads us to define:
\begin{definition}
	Let $S$ be a subset of $G$.
	The subgroup \vocab{generated} by $S$,
	denoted $\left<S\right>$,
	is the set of elements which can be written as a
	finite product of elements in $S$ (and their inverses).
	If $\left<S\right> = G$ then we say $S$ is a set of
	\vocab{generators} for $G$,
	as the elements of $S$ together create all of $G$.
\end{definition}
\begin{exercise}
	Why is the condition ``and their inverses''
	not necessary if $G$ is a finite group?
	(As usual, assume Lagrange's theorem.)
\end{exercise}

\begin{example}[$\ZZ$ is the infinite cyclic group]
	Consider $1$ as an element of $\ZZ = (\ZZ, +)$.
	We see $\left<1\right> = \ZZ$, meaning $\{1\}$ generates $\ZZ$.
	It's important that $-1$, the inverse of $1$, is also allowed:
	we need it to write all integers as the sum of $1$ and $-1$.
\end{example}

This gives us an idea for a way to try and express groups compactly.
Why not just write down a list of generators for the groups?
For example, we could write
\[ \ZZ \cong \left< a \right> \]
meaning that $\ZZ$ is just the group generated by one element.

There's one issue: the generators usually satisfy certain properties.
For example, consider $\Zc{100}$.
It's also generated by a single element $x$,
but this $x$ has the additional property that $x^{100} = 1$.
This motivates us to write
\[ \Zc{100} = \left< x \mid x^{100} = 1 \right>. \]
I'm sure you can see where this is going.
All we have to do is specify a set of generators and
\vocab{relations} between the generators,
and say that two elements are equal if and only if
you can get from one to the other using relations.
Such an expression is appropriately called a \vocab{group presentation}.

\begin{example}[Dihedral group]
	The dihedral group of order $2n$ has a presentation
	\[ D_{2n} = \left< r, s
		\mid r^n = s^2 = 1, rs = sr\inv \right>. \]
	Thus each element of $D_{2n}$ can be written uniquely in the form $r^\alpha$
	or $sr^\alpha$, where $\alpha = 0, 1, \dots, n-1$.
\end{example}

\begin{example}[Klein four group]
	The \vocab{Klein four group},
	isomorphic to $\Zc2 \times \Zc2$, is given by the presentation
	\[ \left< a,b \mid a^2=b^2=1, ab=ba \right>. \]
\end{example}

\begin{example}
	[Free group]
	The \vocab{free group on $n$ elements} is the group
	whose presentation has $n$ generators and no relations at all.
	It is denoted $F_n$, so
	\[
		F_n = \left< x_1, x_2, \dots, x_n \right>.
	\]
	In other words, $F_2 = \left<a,b\right>$ is the set of strings
	formed by appending finitely many copies of $a$, $b$, $a\inv$, $b\inv$ together.
\end{example}
\begin{ques}
	Notice that $F_1 \cong \ZZ$.
\end{ques}
\begin{abuse}
	One might unfortunately notice that ``subgroup generated by $a$ and $b$''
	has exactly the same notation as the free group $\left<a,b\right>$.
	We'll try to be clear based on context which one we mean.
\end{abuse}

Presentations are nice because they provide a compact way to write down groups.
They do have some shortcomings, though.\footnote{%
Actually, determining whether two elements of a presentation are equal is undecidable.
In fact, it is undecidable to even determine if a group is finite from its presentation.}

\begin{example}
	[Presentations can look very different]
	The same group can have very different presentations.
	For instance, consider:
	\[ D_{2n} = \left< x,y \mid x^2=y^2=1, (xy)^n=1 \right>. \]
	(To see why this is equivalent, set $x=s$, $y=rs$.)
\end{example}

\section{Homomorphisms}
\prototype{The ``mod out by $100$'' map, $\ZZ \to \Zc{100}$.}

How can groups talk to each other?

Two groups are ``the same'' if we can write an isomorphism between them.
And as we saw, two metric spaces are ``the same''
if we can write a homeomorphism between them.
But what's the group analogy of a continuous map?
We simply drop the ``bijection'' condition.

\begin{definition}
	Let $G = (G, \star)$ and $H = (H, \ast)$ be groups.
	A \vocab{group homomorphism} is a map $\phi \colon G \to H$
	such that for any $g_1, g_2 \in G$ we have
	\[ \phi(g_1 \star g_2) = \phi(g_1) \ast \phi(g_2). \]
\end{definition}
(Not to be confused with ``homeomorphism'' from
last chapter: note the spelling.)

\begin{example}
	[Examples of homomorphisms]
	Let $G$ and $H$ be groups.
	\begin{enumerate}[(a)]
		\ii Any isomorphism $G \to H$ is a homomorphism.
		In particular, the identity map $G \to G$ is a homomorphism.
		\ii The \vocab{trivial homomorphism} $G \to H$ sends
		everything to $1_H$.
		\ii There is a homomorphism from $\ZZ$ to $\Zc{100}$ by
		sending each integer to its residue modulo $100$.
		\ii There is a homomorphism from $\ZZ$ to itself by $x \mapsto 10x$
		which is injective but not surjective.
		\ii There is a homomorphism from $S_n$ to $S_{n+1}$ by ``embedding'':
		every permutation on $\{1,\dots,n\}$ can be thought of as a permutation
		on $\{1,\dots,n+1\}$ if we simply let $n+1$ be a fixed point.
		\ii A homomorphism $\phi: D_{12} \to D_6$
		is given by $s_{12} \mapsto s_6$
		and $r_{12} \mapsto r_6$.
		\ii Specifying a homomorphism $\ZZ \to G$ is the same as
		specifying just the image of the element $1 \in \ZZ$. Why?
	\end{enumerate}
\end{example}
The last two examples illustrate something: suppose we have a presentation of $G$.
To specify a homomorphism $G \to H$, we only have to specify where each generator of $G$ goes, in such a way that the relations are all satisfied.

Important remark:
the right way to think about an isomorphism is as a ``bijective homomorphism''.
To be explicit,
\begin{exercise}
	Show that $G \cong H$ if and only if there exist
	homomorphisms $\phi \colon G \to H$ and $\psi \colon H \to G$
	such that $\phi \circ \psi = \id_H$ and $\psi \circ \phi = \id_G$.
\end{exercise}
So the definitions of homeomorphism of metric spaces
and isomorphism of groups are not too different.

Some obvious properties of homomorphisms follow.
\begin{fact}
	Let $\phi \colon G \to H$ be a homomorphism.
	Then $\phi(1_G) = 1_H$ and $\phi(g\inv) = \phi(g)\inv$.
\end{fact}
\begin{proof}
	Boring, and I'm sure you could do it yourself if you wanted to.
\end{proof}

Now let me define a very important property of a homomorphism.
\begin{definition}
	The \vocab{kernel} of a homomorphism $\phi \colon G \to H$ is defined by
	\[ \ker \phi \defeq
		\left\{ g \in G : \phi(g) = 1_H \right\}.
		\]
	It is a \emph{subgroup} of $G$
	(in particular, $1_G \in \ker \phi$ for obvious reasons).
\end{definition}
\begin{ques}
	Verify that $\ker\phi$ is in fact a subgroup of $G$.
\end{ques}
We also have the following important fact, which we also encourage the reader to verify.
\begin{proposition}
	[Kernel determines injectivity]
	The map $\phi$ is injective if and only if $\ker\phi = \{1_G\}$.
\end{proposition}

To make this concrete, let's compute the kernel of each of our examples.
\begin{example}
	[Examples of kernels]
	\listhack
	\begin{enumerate}[(a)]
		\ii The kernel of any isomorphism $G \to H$ is trivial,
		since an isomorphism is injective.
		In particular, the kernel of the identity map $G \to G$ is $\{1_G\}$.
		\ii The kernel of the trivial homomorphism $G \to H$
		(by $g \mapsto 1_H$) is all of $G$.
		\ii The kernel of the homomorphism $\ZZ \to \Zc{100}$ by $n \mapsto \ol n$
		is precisely \[ 100\ZZ = \{\dots, -200, -100, 0, 100, 200, \dots \}. \]
		\ii The kernel of the map $\ZZ \to \ZZ$ by $x \mapsto 10x$ is trivial: $\{0\}$.
		\ii There is a homomorphism from $S_n$ to $S_{n+1}$ by ``embedding'',
		but it also has trivial kernel because it is injective.
		\ii A homomorphism $\phi\colon D_{12} \to D_6$
		is given by $s_{12} \mapsto s_6$ and $r_{12} \mapsto r_6$.
		You can check that
		\[ \ker \phi = \left\{ 1, r_{12}^{3} \right\} \cong \Zc2. \]
		\ii Exercise below.
	\end{enumerate}
\end{example}
\begin{exercise}
	Fix any $g \in G$.
	Suppose we have a homomorphism $\ZZ \to G$ by $n \mapsto g^n$.
	What is the kernel?
\end{exercise}

\begin{ques}
	Show that for any homomorphism $\phi: G \to H$,
	the image $\phi\im(G)$ is a subgroup of $H$.
	Hence, we'll be especially interested in the case where $\phi$ is surjective.
\end{ques}

\section{Cosets and modding out}
\prototype{Modding out by $n$: $\ZZ / (n \cdot \ZZ) \cong \Zc n$.}
\emph{The next few sections are a bit dense.
If this exposition doesn't work for you, try \cite{ref:gowers}.}

Let $G$ and $Q$ be groups, and suppose there exists
a \emph{surjective} homomorphism \[ \phi \colon G \surjto Q. \]
In other words, if $\phi$ is injective then $\phi \colon G \to Q$ is a bijection,
and hence an isomorphism.
But suppose we're not so lucky and $\ker\phi$ is bigger than just $\{1_G\}$.
What is the correct interpretation of a more general homomorphism?

Let's look at the special case where $\phi \colon \ZZ \to \Zc{100}$ is ``modding out by $100$''.
We already saw that the kernel of this map is
\[
	\ker \phi = 100\ZZ = \left\{ \dots, -200, -100, 0, 100, 200, \dots  \right\}.
\]
Recall now that $\ker \phi$ is a subgroup of $G$.
What this means is that \textbf{$\phi$ is indifferent to the subgroup $100\ZZ$ of $\ZZ$}:
\[ \phi(15) = \phi(2000 + 15) = \phi(-300 + 15) = \phi(700 + 15) = \dots. \]
So $\Zc{100}$ is what we get when we ``mod out by $100$''. Cool.

In other words, let $G$ be a group and $\phi \colon G \surjto Q$
be a surjective homomorphism with kernel $N \subseteq G$.
\begin{moral}
	We claim that $Q$ should be thought of as the quotient of $G$ by $N$.
\end{moral}
To formalize this, we will define a so-called
\vocab{quotient group} $G/N$
in terms of $G$ and $N$ only (without referencing $Q$)
which will be naturally isomorphic to $Q$.

For motivation, let's give a concrete description of $Q$ using just $\phi$ and $G$.
Continuing our previous example, let $N = 100\ZZ$ be our subgroup of $G$.
Consider the sets
\begin{align*}
	N &= \left\{ \dots, -200, -100, 0, 100, 200, \dots \right\} \\
	1+N &= \left\{ \dots, -199, -99, 1, 101, 201, \dots \right\} \\
	2+N &= \left\{ \dots, -198, -98, 2, 102, 202, \dots \right\} \\
	&\vdots \\
	99+N &= \left\{ \dots, -101, -1, 99, 199, 299, \dots \right\}.
\end{align*}
The elements of each set all have the same image when we apply $\phi$,
and moreover any two elements in different sets have different images.
Then the main idea is to notice that
\begin{moral}
	We can think of $Q$ as the group
	whose \emph{elements} are the \emph{sets} above.
\end{moral}

Thus, given $\phi$ we define an equivalence relation $\sim_N$
on $G$ by saying $x \sim_N y$ for $\phi(x) = \phi(y)$.
This $\sim_N$ divides $G$ into several equivalence classes in $G$
which are in obvious bijection with $Q$, as above.
Now we claim that we can write these equivalence classes very explicitly.

% Also, for each $g \in G$ define $\ol g$ to be the equivalence class of $g$ under $\sim_\phi$.
\begin{exercise}
	Show that $x \sim_N y$ if and only if $x = yn$ for some $n \in N$
	(in the mod $100$ example, this means they ``differ by some multiple of $100$'').
	Thus for any $g \in G$, the equivalence class of $\sim_N$ which contains $g$
	is given explicitly by \[ gN \defeq \left\{ gn \mid n \in N \right\}. \]
\end{exercise}
%Note that
%\[ \phi(x) = \phi(y)
%	\implies 1_Q = \phi(x)\phi(y)\inv = \phi(xy\inv)
%	\implies xy\inv \in \ker\phi. \]
%Hence another way to describe $\ol x$ is
%\[ \ol g = gN = \left\{ gn \mid n \in N \right\}. \]

Here's the word that describes the types of sets we're running into now.
\begin{definition}
	Let $H$ be any subgroup of $G$ (not necessarily the kernel of some homomorphism).
	A set of the form $gH$ is called a \vocab{left coset} of $H$.
\end{definition}
\begin{remark}
	Although the notation might not suggest it,
	keep in mind that $g_1N$ is often equal to $g_2N$ even if $g_1 \neq g_2$.
	In the ``mod $100$'' example, $3+N = 103+N$.
	In other words, these cosets are \emph{sets}.

	This means that if I write ``let $gH$ be a coset'' without telling you what $g$ is,
	you can't figure out which $g$ I chose from just the coset itself.
	If you don't believe me, here's an example of what I mean:
	\[ x+100\ZZ = \left\{ \dots, -97, 3, 103, 203, \dots \right\} \implies x = {?}. \]
	There's no reason to think I picked $x=3$. (I actually picked $x=-13597$.)
	\label{remark:coset_warning}
\end{remark}
\begin{remark}
	Given cosets $g_1H$ and $g_2H$,
	you can check that the map $x \mapsto g_2g_1\inv x$ is a bijection between them.
	So actually, all cosets have the same cardinality.
\end{remark}

So, long story short,
\begin{moral}
	Elements of the group $Q$ are naturally identified with left cosets of $N$.
\end{moral}
In practice, people often still prefer to picture elements of $Q$ as single points
(for example it's easier to think of $\Zc2$ as $\{0,1\}$
rather than $\big\{ \{\dots,-2,0,2,\dots\}, \{\dots,-1,1,3,\dots\} \big\}$).
If you like this picture,
then you might then draw $G$ as a bunch of equally tall fibers (the cosets),
which are then ``collapsed'' onto $Q$.

\begin{center}
	\begin{asy}
		size(9cm);
		for (int i=1; i<=6; ++i) {
			draw( (i,0)--(i,3.4) );
			dot( (i,0.6) );
			dot( (i,1) );
			dot( (i,1.7) );
			dot( (i,2.4) );
			dot( (i,2.8) );
			dot( (i,3) );
			label(rotate(90)*scale(1.4)*"$\Longleftarrow$", (i+0.02,-0.9), dir(90));
			dot( (i,-1) );
		}
		label("$G$", (0.5, 3));
		label("$Q$", (0.5,-1));
	\end{asy}
\end{center}

Now that we've done this, we can give an \emph{intrinsic}
definition for the quotient group we alluded to earlier.
\begin{definition}
	A subgroup $N$ of $G$ is called \vocab{normal} if it is the
	kernel of some homomorphism.
	We write this as $N \normalin G$.
\end{definition}
\begin{definition}
	Let $N \normalin G$.
	Then the \vocab{quotient group}, denoted $G/N$
	(and read ``$G$ mod $N$''),
	is the group defined as follows.
	\begin{itemize}
		\ii The elements of $G/N$ will be the left cosets of $N$.
		\ii We want to define the product of two cosets $C_1$ and $C_2$ in $G/N$.
		Recall that the cosets are in bijection with elements of $Q$.
		So let $q_1$ be the value associated to the coset $C_1$,
		and $q_2$ the one for $C_2$.
		Then we can take the product to be the coset corresponding to $q_1q_2$.

		Quite importantly,
		\textbf{we can also do this in terms of representatives of the cosets}.
		Let $g_1 \in C_1$ and $g_2 \in C_2$,
		so $C_1 = g_1N$ and $C_2 = g_2N$.
		Then $C_1 \cdot C_2$ should be the coset which contains $g_1g_2$.
		This is the same as the above definition since
		$\phi(g_1g_2) = \phi(g_1)\phi(g_2) = q_1q_2$;
		all we've done is define the product in terms of elements of $G$,
		rather than values in $H$.

		Using the $gN$ notation,
		and with \Cref{remark:coset_warning} in mind,
		we can write this even more succinctly:
		\[ (g_1N) \cdot (g_2N) \defeq (g_1g_2)N. \]
	\end{itemize}
\end{definition}
And now you know why the integers modulo $n$ are often written $\ZZ/n\ZZ$!
\begin{ques}
	Take a moment to digest the above definition.
\end{ques}
By the way we've built it, the resulting group $G/N$ is isomorphic to $Q$.
In a sense we think of $G/N$ as ``$G$ modulo the condition that $n=1$
for all $n \in N$''.

\section{(Optional) Proof of Lagrange's theorem}
As an aside, with the language of cosets
we can now show Lagrange's theorem in the general case.
\begin{theorem}
	[Lagrange's theorem]
	\label{thm:lagrange_grp}
	Let $G$ be a finite group, and let $H$ be any subgroup.
	Then $\left\lvert H \right\rvert$ divides $\left\lvert G \right\rvert$.
\end{theorem}

The proof is very simple: note that the cosets of $H$
all have the same size and form a partition of $G$
(even when $H$ is not necessarily normal).
Hence if $n$ is the number of cosets,
then $n \cdot \left\lvert H \right\rvert = \left\lvert G \right\rvert$.

\begin{ques}
	Conclude that $x^{\left\lvert G \right\rvert}=1$
	by taking $H = \left<x\right> \subseteq G$.
\end{ques}

\begin{remark}
	It should be mentioned at this point that
	in general, if $G$ is a finite group and $N$ is normal,
	then $|G/N| = |G| / |N|$.
\end{remark}

\section{Eliminating the homomorphism}
\prototype{Again $\ZZ/n\ZZ \cong \Zc n$.}
Let's look at the last definition of $G/N$ we provided.
The short version is:
\begin{itemize}
	\ii The elements of $G/N$ are cosets $gN$, which you can think
	of as equivalence classes of a relation $\sim_N$
	(where $g_1 \sim_N g_2$ if $g_1 = g_2n$ for some $n \in N$).
	\ii Given cosets $g_1N$ and $g_2N$ the group operation is
	\[ g_1N \cdot g_2N \defeq (g_1g_2)N. \]
\end{itemize}
Question: where do we actually use the fact that $N$ is normal?
We don't talk about $\phi$ or $Q$ anywhere in this definition.

The answer is in \Cref{remark:coset_warning}.
The group operation takes in two cosets,
so it doesn't know what $g_1$ and $g_2$ are.
But behind the scenes,
\textbf{the normal condition guarantees that the group operation can pick
any $g_1$ and $g_2$ it wants and still end up with the same coset.}
If we didn't have this property, then it would be hard to define the
product of two cosets $C_1$ and $C_2$ because it might make a difference
which $g_1 \in C_1$ and $g_2 \in C_2$ we picked.
The fact that $N$ came from a homomorphism meant we could pick any representatives
$g_1$ and $g_2$ of the cosets we wanted, because they all had the same $\phi$-value.

We want some conditions which force this to be true without referencing $\phi$ at all.
Suppose $\phi \colon G \to K$ is a homomorphism of groups with $H = \ker\phi$.
Aside from the fact $H$ is a group, we can get an ``obvious'' property:
\begin{ques}
	Show that if $h \in H$, $g \in G$,
	then $ghg\inv \in H$.
	(Check $\phi(ghg\inv) = 1_K$.)
\end{ques}
\begin{example}[Example of a non-normal subgroup]
	\label{ex:dihedral_normal_subgroup}
	Let $D_{12} = \left<r,s \mid r^6=s^2=1, rs=sr\inv\right>$.
	Consider the subgroup of order two $H = \{1,s\}$
	and notice that \[ rsr\inv = r(sr\inv)= r(rs) = r^2s \notin H. \]
	Hence $H$ is not normal, and cannot be the kernel of any homomorphism.
\end{example}
Well, duh -- so what?
Amazingly it turns out that this is the \emph{sufficient} condition we want.
Specifically, it makes the nice ``coset multiplication'' we wanted work out.
\begin{remark}
	[For math contest enthusiasts]
	This coincidence is really a lot like functional equations at the IMO.
	We all know that normal subgroups $H$ satisfy $ghg\inv \in H$;
	the surprise is that from the latter seemingly weaker condition,
	we can deduce $H$ is normal.
\end{remark}

Thus we have a new criterion for ``normal'' subgroups which does not
make any external references to $\phi$.
\begin{theorem}[Algebraic condition for normal subgroups]
	Let $H$ be a subgroup of $G$.
	Then the following are equivalent:
	\begin{itemize}
		\ii $H \normalin G$.
		\ii For every $g \in G$ and $h \in H$, $ghg\inv \in H$.
	\end{itemize}
\end{theorem}
\begin{proof}
	We already showed one direction.

	For the other direction, we need to build a homomorphism with kernel $H$.
	So we simply \emph{define} the group $G/H$ as the cosets.
	To put a group operation, we need to verify:
	\begin{claim}
		If $g_1' \sim_H g_1$ and $g_2' \sim_H g_2$ then $g_1'g_2' \sim_H g_1g_2$.
	\end{claim}
	\begin{subproof}
		Boring algebraic manipulation (again functional equation style).
		Let $g_1' = g_1h_1$ and $g_2' = g_2h_2$, so we want to show that
		$g_1h_1g_2h_2 \sim_H g_1g_2$.
		Since $H$ has the property, $g_2\inv h_1g_2$ is some element of $H$, say $h_3$.
		Thus $h_1 g_2 = g_2 h_3$, and the left-hand side becomes $g_1g_2(h_3h_2)$,
		which is fine since $h_3h_2 \in H$.
	\end{subproof}
	With that settled we can just \emph{define} the
	product of two cosets (of normal subgroups) by \[ (g_1H) \cdot (g_2H) = (g_1g_2)H. \]

	Thus the claim above shows that this multiplication is well-defined
	(this verification is the ``content'' of the theorem).
	So $G/H$ is indeed a group!
	Moreover there is an obvious ``projection'' homomorphism
	$G \to G/H$ (with kernel $H$), by $g \mapsto gH$.
\end{proof}
%Another way to write the condition is
%\[ H = gHg\inv \defeq \left\{ ghg\inv \mid h \in H \right\}. \]
%You should take a moment to check that these definitions are equivalent.

\begin{example}[Modding out in the product group]
	Consider again the product group $G \times H$.
	Earlier we identified a subgroup
	\[ G' =  \left\{ (g, 1_H) \mid g \in G \right\} \cong G. \]
	You can easily see that $G' \normalin G \times H$.
	(Easy calculation.)

	Moreover, you can check that
	\[ (G \times H) / (G') \cong H. \]
	Indeed, we have $(g, h) \sim_{G'} (1_G, h)$ for all $g \in G$ and $h \in H$.
\end{example}
\begin{example}[Quotients and products don't necessarily cancel]
	It is not necessarily true that $(G/H) \times H \cong G$.
	For example, consider $G = \ZZ/4\ZZ$
	and the normal subgroup $H = \{0,2\} \cong \ZZ/2\ZZ$.
	Then $G/H \cong \ZZ/2\ZZ$,
	but $\ZZ/4\ZZ \not\cong \ZZ/2\ZZ \times \ZZ/2\ZZ$.
	(Footnote: the precise condition for this kind of ``canceling'' is called the Schur-Zassenhaus lemma.)
\end{example}
\begin{example}[Another explicit computation]
	Let $\phi: D_8 \to \Zc 4$ be defined by \[ r \mapsto \ol 2, \quad s \mapsto \ol 2. \]
	The kernel of this map is $N = \{1,r^2,sr,sr^3\}$.

	We can do a quick computation of all the elements of $D_8$ to get
	\[ \phi(1) = \phi(r^2) = \phi(sr) = \phi(sr^3) = \ol 0
	\text{ and }
	 \phi(r) = \phi(r^3) = \phi(s) = \phi(sr^2) = \ol 2. \]
	The two relevant fibers are \[ \phi\pre(\ol 0) = 1N = r^2N = srN = sr^3N = \{1,r^2,sr,sr^3\} \] and
	\[ \phi\pre(\ol 2) = rN = r^3N = sN = sr^2N = \{r,r^3,s,sr^2\}. \]
	So we see that $|D_8/N| = 2$ is a group of order two, or $\Zc 2$.
	Indeed, the image of $\phi$ is \[ \left\{ \ol 0, \ol 2 \right\} \cong \Zc 2. \]
\end{example}

\begin{ques}
	Suppose $G$ is abelian.
	Why does it follow that any subgroup of $G$ is normal?
\end{ques}


Finally here's some food for thought:
suppose one has a group presentation for a group $G$
that uses $n$ generators.
Can you write it as a quotient of the form $F_n / N$,
where $N$ is a normal subgroup of $F_n$?

\section{(Digression) The first isomorphism theorem}
\label{sec:first_isomorphism_thm}
One quick word about what other sources usually say.

Most textbooks actually \emph{define} normal using the $ghg\inv \in H$ property.
Then they define $G/H$ for normal $H$ in the way I did above,
using the coset definition
\[ (g_1H) \cdot (g_2H) = g_1g_2H. \]
Using purely algebraic manipulations (like I did) this is well-defined,
and so now you have this group $G/H$ or something.
The underlying homomorphism isn't mentioned at all,
or is just mentioned in passing.

I think this is incredibly dumb.
The normal condition looks like it gets pulled out of thin air
and no one has any clue what's going on,
because no one has any clue what a normal subgroup actually should look like.

Other sources like to also write the so-called first isomorphism theorem.\footnote{There
	is a second and third isomorphism theorem.
	But four years after learning about them, I \emph{still} don't remember what they are.
	So I'm guessing they weren't very important.}
It goes like this.
\begin{theorem}
	[First isomorphism theorem]
	Let $\phi \colon G \to H$ be a homomorphism.
	Then $G / \ker \phi$ is isomorphic to $\phi\im(G)$.
\end{theorem}
To me, this is just a clumsier way of stating the same idea.

About the only merit this claim has is that if $\phi$ is injective,
then the image $\phi\im(G)$ is an \emph{isomorphic copy}
of $G$ inside the group $H$.
(Try to see this directly!)
This is a pattern we'll often see in other branches of mathematics:
whenever we have an \emph{injective structure-preserving map},
often the image of this map will be some ``copy'' of $G$.
(Here ``structure'' refers to the group multiplication,
but we'll see some more other examples of ``types of objects'' later!)

In that sense an injective homomorphism $\phi \colon G \injto H$
is an \emph{embedding} of $G$ into $H$.

\section\problemhead
\begin{problem}
	[18.701 at MIT]
	Determine all groups $G$ for which the map $\phi \colon G \to G$ defined by
	\[ \phi(g) = g^2 \] is a homomorphism.
	\begin{hint}
		Write it out: $\phi(ab) = \phi(a)\phi(b)$.
	\end{hint}
	\begin{sol}
		Abelian groups: $abab =a^2b^2 \iff ab= ba$.
	\end{sol}
\end{problem}

\begin{problem}
	Consider the dihedral group $G = D_{10}$.
	\begin{enumerate}[(a)]
		\ii Is $H = \left< r \right>$ a normal subgroup of $G$?
		If so, compute $G/H$ up to isomorphism.
		\ii Is $H = \left< s \right>$ a normal subgroup of $G$?
		If so, compute $G/H$ up to isomorphism.
	\end{enumerate}
	\begin{hint}
		Yes, no.
	\end{hint}
	\begin{sol}
		Yes to (a): you can check this directly
		from the $ghg\inv$ definition.
		For example, for (a)
		it is enough to compute $(r^a s) r^n (r^a s)\inv = r^{-n} \in H$.
		The quotient group is $\Zc2$.

		The answer is no for (b) by following
		\Cref{ex:dihedral_normal_subgroup}.
	\end{sol}
\end{problem}

\begin{problem}
	Does $S_4$ have a normal subgroup of order $3$?
	\begin{hint}
		No.
	\end{hint}
	\begin{sol}
		A subgroup of order $3$ must be generated by
		an element of order $3$, since $3$ is prime.
		So we may assume WLOG that $H = \left< (1\; 2 \; 3) \right>$
		(by renaming elements appropriately).
		But then let $g = (3 \; 4)$; one can check $gHg\inv \neq H$.
	\end{sol}
\end{problem}

\begin{problem}
	Let $G$ and $H$ be finite groups, where $\left\lvert G \right\rvert = 1000$
	and $\left\lvert H \right\rvert = 999$.
	Show that a homomorphism $G \to H$ must be trivial.
	\begin{hint}
		$\gcd(1000,999)=1$.
	\end{hint}
	\begin{sol}
		Let $\phi \colon G \to H$ be a homomorphism.
		Then $G / \ker\phi$ is isomorphic to a subgroup of $H$.
		The order of the former divides $1000$;
		the order of the latter divides $999$.
		This can only occur if $G / \ker\phi = \{1\}$
		so $\ker\phi = G$.
	\end{sol}
\end{problem}

\begin{problem}
	Let $\CC^\times$ denote the nonzero complex numbers under multiplication.
	Show that there are five homomorphisms $\Zc5 \to \CC^\times$
	but only two homomorphisms $D_{10} \to \CC^\times$,
	even though $\Zc5$ is a subgroup of $D_{10}$.
\end{problem}

\begin{problem}
	\onechili
	Find a non-abelian group $G$
	such that every subgroup of $G$ is normal.
	(These groups are called \vocab{Hamiltonian}.)
	\begin{hint}
		Find an example of order $8$.
	\end{hint}
	\begin{sol}
		Quaternion group.
	\end{sol}
\end{problem}

\begin{problem}
	[PRIMES entrance exam, 2018]
	\onechili
	Let $G$ be a group with presentation given by
	\[ G = \left< a,b,c \mid
		ab = c^2a^4, \; bc = ca^6, \; ac = ca^8, \;
		c^{2018} = b^{2019}
		\right>. \]
	Determine the order of $G$.
	\begin{hint}
		Try to show $G$ is the dihedral group of order $18$.
		There is not much group theory content here --- just manipulation.
	\end{hint}
	\begin{sol}
		The answer is $|G| = 18$.

		First, observe that by induction we have
		\[ a^n c = ca^{8n} \]
		for all $n \ge 1$.
		We then note that
		\begin{align*}
			a(bc) &= (ab)c \\
			a \cdot ca^6 &= c^2 a^4 \cdot c \\
			c a^8 \cdot a^6 &= c^2 a^4 \cdot c \\
			a^{14} &= c(a^4c) = c^2 a^{32}.
		\end{align*}
		Hence we conclude $c^2 = a^{-18}$.
		Then $ab = c^2a^4 \implies b = a^{-15}$.

		In that case, since $c^{2018} = b^{2019}$,
		we conclude $1 = a^{- 1009 \cdot 18 + 2019 \cdot 15} = a^{12123}$.
		Finally,
		\begin{align*}
			bc &= ca^6 \\
			a^{-15} c &= ca^6 \\
			a^{-15} c^2 &= c(a^6c) = c^2 a^{48} \\
			a^{-33} &= a^{30} \\
			\implies a^{63} &= 1.
		\end{align*}
		Since $\gcd(12123, 63) = 9$, we find $a^9 = 1$, hence finally $c^2 = 1$.
		So the presentation above simplifies to
		\[ G = \left< a,c \mid a^9=c^2=1, \; ac = ca^{-1} \right> \]
		which is the presentation of the dihedral group of order $18$.
		% a = r, r^9 = 1
		% b = r^3
		% c = s, s^2 = 2
		This completes the proof.
	\end{sol}
\end{problem}

\begin{problem}
	[Homophony group]
	\onechili
    The homophony group (of English) is the group
	with $26$ generators $a$, $b$, \dots, $z$
	and one relation for every pair of English words
	which sound the same.
	For example $knight = night$ (and hence $k=1$).
	Prove that the group is trivial.
	\begin{hint}
		Get yourself a list of English homophones, I guess.
		Don't try too hard.
		Letter $v$ is the worst; maybe $felt = veldt$?
	\end{hint}
	\begin{sol}
		You can find many solutions by searching ``homophone group'';
		one is \url{https://math.stackexchange.com/q/843966/229197}.
	\end{sol}
\end{problem}

% Copying math.SE content:
% F:=FreeGroup("a","b","c","d","e","f","g","h","i","j","k","l","m",
%              "n","o","p","q","r","s","t","u","v","w","x","y","z");
%
% AssignGeneratorVariables(F);
%
% pairs:=[
% "bye=by",          # e=1
% "lead=led",        # a=1
% "maid=made",       # mid=md => i=1
% "sow=sew",         # o=e=1
% "buy=by",          # u=1
% "sow=so",          # w=1
% "lye=lie",         # y=1
% "hour=our",        # h=1
% "knight=night",    # k=1
% "damn=dam",        # n=1
% "psalter=salter",  # p=1
% "plumb=plum",      # b=1
% "bass=base",       # s=1
% "butt=but",        # t=1
% "tolled=told",     # l=1
% "barred=bard",     # r=1
% "dammed=damned",   # m=1
% "chased=chaste",   # d=1
% "sign=sine",       # g=1
% "daze=days",       # z=1
% "cite=sight",      # c=1
% "jeans=genes",     # j=1
% "queue=cue",       # q=1
% "tax=tacks",       # x=1
% # "ruff=rough",    # f=1, we need not this relation used in the paper
% "phase=faze",      # f=1
% "chivvy=chivy"];   # v=1
%
% rels:=List( pairs, r -> ParseRelators(GeneratorsOfGroup(F),r)[1]);
% G:=F/rels;
