
\part{Fundamentals}

\chapter{Groups and Subgroups}


Readers will be familiar with elementary algebra; solving for $x$ by leveraging the laws of operations. Algebra is a useful tool, and it proves powerful when generalized to other objects in mathematics. To generalize the idea of one operation working on a set, we introduce the notion of a \emph{group}.

Our success with these methods has lead us to generalize arithmetic and elementary algebra to \emph{abstract algebra}; the study of algebraic structures. To do this, we consider algebraic structures to be sets with \emph{operations} working on them; functions working on the set that spit out another element of the set (multiplication and addition are operations on $\mathbb{Z}$). These operations may also be bound by certain algebraic equations that define its behaviour.


$xy=yx$ (Commutativity)
$x(yz)=(xy)z$ (Associativity)
$1x = x$ (Identity element)
$xx^{-1} = 1$ (Inverse elements)


See 'Universal Algebra' for more details on operations; this theory is vital for developing group theory.

\section{Groups}

The simplest algebraic structure one can consider is a set with a single operation. There are many classes of such algebraic structures bound by different algebraic equations (loop, magma, monoid, category, etc.), however one structure stands out due to its frequent occurence and body of rich theorems; the \emph{group}.




\begin{definition}[Group]
A \emph{group} is an ordered pair $(G, \circ )$ of a set $G$ and a binary operation $\circ : G \times G \to G$ with the following properties:
\begin{itemize}
	\item $x \circ (y \circ z) = (x \circ y) \circ z$ ($\circ$ is associative)
	\item $\exists 1_G \in G [ \forall g \in G [g\circ 1_G = 1_G \circ g = g ] ]$ ($G$ contains an identity element with respect to $\circ$)
	\item $\forall g \in G [ \exists g^{-1} \in G [g \circ g^{-1} = g^{-1} \circ g = 1_G ]]$ (Every element of $G$ is invertible with respect to $\circ$)
\end{itemize}

We often write $g \circ h$ as $gh$, and call $\circ$ by the name $G$-composition.
When the operation is apparent, a group $(G,\circ)$ may be denoted as $G$.

%\[ (G, \circ) \textrm{ is a group } \iff \circ\text{ is associative on } G \land \exists 1_{G} \in G [ \forall g \in G ( g 1_{G} = 1_{G} g = g ) ] \land \forall g \in G  [ \exists g^{-1} (  g g^{-1} = g^{-1} g = 1_{G} ) ] \]
\end{definition}


Many algebraic strucutres of one operation encountered in mathematics and the sciences can be represented as groups, and the study of groups as an abstraction can lead to some deep propositions with profound consequences. Indeed, more complex algebraic structures often extend upon the notion of a group.

Though all groups find common ground in the three properties above, they may exhibit various behaviours due to extra properties regarding the group's set and operation. One fundamental property that may differ among groups is their \emph{order}.

\begin{definition}[Order of a group]
The \emph{order} of a group is the cardinality of its set.
The order of $G$ is denoted as $|G|$ or $\mathrm{ord}(G)$.
\end{definition}


\begin{definition}[rank of a group]
The \emph{rank} of a group is the cardinality of its smallest subset that can generate the group.
The order of $G$ is denoted $\mathrm{rank}(G)$.
	\[\mathrm{rank}(G)= \mathrm{min}\{|X| : X \subseteq G \land \langle X \rangle = G \}\]
\end{definition}


\begin{definition}[Finite group]
A \emph{finite group} is a group with a finite order.
\end{definition}


Note that when the group operation is clear, we will use the notation $g^n$ for the operation working on $g$, $n$ times. Note that we can prove the following.

\begin{definition}[Exponential notation for group operation]
\[g^0 = 1_G\]
\[g^n = g^{n-1}g\]
\end{definition}

This notation follows all the familiar relations from arithmetic.

\begin{proposition}
\[ g^n g^m = g^{n+m}\]
\[ (g^{n})^{m} = g^{nm}\]
\[ g^{-n}  = (g^{-1})^{n}\]
\end{proposition}




\subsection{Properties of Groups}


Groups require the notion of identity elements and inverse elements. With some more work, we can see some elementary properties of these elements, namely their uniqueness.

\begin{proposition}Let $G$ be a group:
\begin{itemize}
	\item $G$ contains a unique identity element
	\item Every element of $G$ is invertible by a unique inverse element
\end{itemize}
	\[\exists! 1_{G} \in G [ \forall g \in G (  g 1_{G} = 1_{G}  g = g)] \]
	\[ \forall g \in G  [ \exists! g^{-1} (  g  g^{-1} = g^{-1} g = 1_G )] \]
\end{proposition}

\begin{proposition}
	\[ G \text{ is a group} \land g,g_1,g_2 \in G \implies (g_1 g_2 )^{-1} = g_{2}^{-1}  g_{1}^{-1} \]
\end{proposition}





The cancellation law is also permitted by groups due to the ability of composing both sides of an equation by inverse elements.




\begin{proposition}[Cancellation law for Groups]
Let $G$ be a group and $g,h_1 , h_2 \in G$, then $g  h_1 = g h_2$ iff $h_1 = h_2$
\[ G \text{ is a group} \land g,h_1,h_2 \in G \implies g  h_1 = g h_2 \iff h_1 = h_2  \]
\end{proposition}

Here is a curious fact about groups that will frequently be required of us.
The cancellation law implies the following proposition, that will be immensely important throughout our study of group theory.

\begin{proposition}
The function $ f : G \to G$ defined as $f(h) = gh$ is a bijection.
\end{proposition}

This essentially means that (left) composition by $g$ permutes group elements around.







\subsection{Abelian groups}
Another fundamental property that some particularly 'nice' groups have is commutativity of it's operation, that is to say, the order of elements under an operation does not affect the result (like how $ 9+10=10+9$).

\begin{definition}[Abelian group]
An \emph{Abelian group} is a group $(G,\circ)$ such that $\forall g,h \in G [ gh=hg] $ ($\circ$ is commutative).
%For Abelian groups, we often write $\circ(g,h)$ as $g+h$ and call $\circ$ by the name $G$-addition. We also denote the identity element as $0_G$ instead.
\[ (G, \circ ) \text{ is Abelian } \iff (G, \circ) \text{ is a group} \land \circ \text{ is commutative on } G \]
\end{definition}

Even though some groups may not be Abelian, they could have a collection of elements that act commutatively with every other element; this is called the \emph{center}.

\begin{definition}[Center of a group]
The \emph{center} of a group $G$ is a set $Z(G)$ containing the elements that commute with every other element.
\[ Z(G) = \{ z \in G : \forall g \in G (zg=gz) \} \]
\end{definition}



\subsection{Cayley table and group presentations}

Recall how on the back of primary school books, one can find addition and multiplication tables to help students memorize them (or more likely, to cheat on tests).

We can use a generalization of this table to describe the behaviour of a finite group's operation. A \emph{Cayley table} is a table showing the result of applying every combination of two elements with the group operation. It is formally represented as a square matrix $\mathbb{C}$, since finite groups have $|G|^2$ possible combination of elements into the group operation
\[ \mathbf{C}_{ij} =  g_{j} g_{i} \]



Though Cayley tables describe finite groups by explicitly describing the results of the operator, perhaps one wants to define a group by some predicate (condition that the group elements should follow). This is permitted by \emph{group presentations}; they specify a set of elements and rules for generating the group.
\[ G = \langle S : R \rangle \]
\begin{itemize}
	\item $S$ is the set of elements generating the group
	\item $R$ is the relation that the group must follow
\end{itemize}



\subsection{Examples of Groups}

In kindergarten we learn that 1+1=2 and that we can add any integers together to get a new integer. I guess kindergarten students aren't aware of the negative numbers though; they are needed in order to ensure inverse elements exist with respect to addition. When little Johnny passes year 1 and learns this fact, he has the \emph{additive group of integers} at his command.

\begin{example}
The \emph{additive group of integers} $(\mathbb{Z}, +)$
Group of integers under addition.
\end{example}


\begin{example}
The \emph{dihedral group} $\mathrm{Dih}(n)$
Group of symmetries a $n$-gon has when rotating and flipping.
\end{example}

We're literally doing toddler level math right now, but don't feel disheartened if your kid doesn't know the term 'dihedral group' by year 2; this is quite an abstract generalization.


\begin{example}
The \emph{Klein fourgroup} $K_4$
Group of 4 elements such that each element is its own inverse.
$K_4 = \langle a,b \in a^2=b^2=(ab)^2=1_{K_4}\rangle$
\end{example}


\begin{example}
The \emph{general linear group} $\mathrm{GL}(n,\mathbb{R})$
Group of $n \times n$ matrixes under matrix multiplication.
\end{example}

If you have taken a course in linear algebra you would be taught that the order of multiplying matrixes matters; it could change the result, hence these groups are non-Abelian. We're also taught that not all square matrix have an inverse matrix, therefore such matrixes aren't in this group.


\section{Subgroups}


Sometimes groups consist of smaller groups within themselves, that is, not all the elements of the group are required to form a group.


\begin{definition}[Subgroup of a group]
A \emph{subgroup of $(G, \circ)$} is a group $(H,\circ)$ such that $H$ is a subset of $G$ and $\circ$ is closed over $H$.
We use the notation $H \leq G$ to denote that $H$ is a subgroup of $G$.
\[ H \leq G \iff (H \subseteq G) \land (H, \circ ) \text{ is a group} \]
\end{definition}

The idea is that it is a subset of the group where $G$-composition is closed on $H$, meaning that $H$ preserves its status as a group with $\circ$.

\begin{theorem}Let $(G,\circ)$ be a group:
\begin{itemize}
	\item $(G,\circ)$ is a subgroup of itself $G \leq G$
	\item $(\{1_{G} \},\circ)$ is a subgroup of $(G,\circ)$  (i.e the trivial group is a subgroup of every group) $\{1_{G}\} \leq G$
\end{itemize}
\end{theorem}


These subgroups are rather trivial, let's explore some more ways of naturally finding subgroups on some general group.

\begin{proposition}
\[ Z(G) \leq G \]
\[ Z(G) \text{ is Abelian} \]
\end{proposition}


\begin{proposition}
Let $H,K$ be subgroups of $G$, then $H \cap K \leq G$
\end{proposition}



Here's another idea for constructing subgroups; imagine we want the element $x\in G$ to end up in our subgroup, we can generate a group from this element by consider the $\circ$-exponentials of $x$. Taking exponentials is our way of "closing the group up" so that this set meets the requirements of being a group, and we should check that this construction indeed satisfies the criteria to be a group. One may see that this will give us the smallest such subgroup in which $x$ is included.

\begin{definition}[Subgroup generated by $x$]
The \emph{subgroup generated by $x \in G$} is the following.
\[ \langle x \rangle = \{ x^{n} : n \in \mathbb{Z} \} \].
\end{definition}

As we will see in a later chapter, groups that can be 'generated' from a single element are called \emph{cyclic groups}, hence subgroups generated by a single element are sometimes called \emph{cyclic subgroups}. When we study cyclic groups in a later chapter, we will see they are of grand importance in understanding group theory in general.

\begin{proposition}
The \emph{subgroup generated by $x \in G$} is the following.
\[\Lambda = \{H \leq G : x \in H\}\]
\[ \langle x \rangle = \bigcap_{H \in \Lambda} H\]
\end{proposition}




\subsection{Examples of Subgroups}


\begin{example}
	\[ k\mathbb{Z} = \{ kn  : n \in \mathbb{Z} \}\]
\end{example}


\begin{example}
The \emph{additive group of $n$-multiples} $(n\mathbb{Z}, +)$
Subgroup of $(\mathbb{Z},+)$ of multiples of $n$.
\end{example}

\begin{example}
The \emph{special linear group} $\mathrm{SL}(n,\mathbb{R})$
Subgroup of $\mathrm{GL}(n)$ of matrixes with determinant $1$.
\end{example}

\begin{example}
The \emph{orthogonal group} $\mathrm{O}(n,\mathbb{R})$
Subgroup of $\mathrm{GL}(n)$ of orthogonal matrixes
\end{example}

\begin{example}
The \emph{special orthogonal group} $\mathrm{SO}(n,\mathbb{R})$
Subgroup of $\mathrm{O}(n)$ of matrixes with determinant $1$
\begin{itemize}
	\item It is Abelian for $n \leq 2$
\end{itemize}
\end{example}



\subsection{Properties of Subgroups}



\begin{proposition}
Let $H$ be a subgroup of $G$, then $1_{G}$ is in the subgroup $H$.
\[ H \leq G \implies 1_{G} \in H \]
\end{proposition}


\section{Cosets}


There is an interesting property relating to how the orders of groups relate to the orders of their subgroups. Bringing this fact to light requires experimenting how subgroup elements behave with foreign elements in its 'supergroup'; this will be done by the use of \emph{cosets}.



\begin{definition}[Left coset]
Given the subgroup $(H,\circ)$ of $(G,\circ)$, a \emph{left coset} of $(H,\circ)$ is a set $gH$ containing the elements of the form $gh$, where $h \in H$.
\[ gH = \{ gh : h \in H \} \]</p>
The set $G / H$ is the set of all unique left cosets of $H$ on $G$.
\end{definition}

\begin{definition}[Right coset]
If $(H,\circ)$ is a subgroup of $(G,\circ)$, a \emph{right coset} of $(H,\circ)$ is a set $Hg$ containing the elements of the form $h g$, where $h \in H$.
\[ Hg = \{h g : h \in H \} \]
The set $G \ H$ is the set of all unique right cosets of $H$ on $G$.
\end{definition}


\subsection{Properties of Cosets}

Among the more basic properties that cosets have are consequences of the basic properties of groups. The following propositions will explicitly deal with left cosets for brevity, however right cosets have similar properties.

\begin{proposition}The cardinality of left cosets of $(H,\circ)$ is the order of $(H,\circ)$
\[ |gH|=|Hg|=|H|  \]
\end{proposition}
This follows immediately from the fact that  $f(h)=gh$ is a bijection.

Heres another result that isn't too surprising.
\begin{proposition}
\[ H \leq G \land H \text{ is an Abelian group} \implies Hg=gH \]
\end{proposition}



\begin{lemma}
Let $H \leq G$, then there are the same amount of left cosets on $H$ as right cosets. Therefore we can use the notation $[G:H]$ to represent the cardinality of either the right or left cosets.
\[ H \leq G \]
\[ |G / H| = |G \\ H| = [G:H] \]
\end{lemma}





\begin{lemma}
\[ H \leq G \land h \in H \implies hH = H\]
\end{lemma}

We can generalize this result even further.

\begin{lemma}
\[ H \leq G \]
\[ k \in gH \implies gH=kH\]
\end{lemma}

\begin{proposition}
\[ H \leq G \land H \text{ is an Abelian group} \implies Hg=gH \]
\end{proposition}


\subsection{Examples of cosets}
Consider the cosets of the group $4\mathbb{Z} \leq \mathbb{Z}$

\[0+4\mathbb{Z} = 4\mathbb{Z}\]
\[1+4\mathbb{Z}\]
\[2+4\mathbb{Z}\]
\[3+4\mathbb{Z}\]
\[4+4\mathbb{Z} = 4\mathbb{Z}\]
\[5+4\mathbb{Z} = 1+4\mathbb{Z}\]

\[2+4\mathbb{Z}\]
\[(2+3)+4\mathbb{Z}\]
\[(6+3)+4\mathbb{Z}\]
\[(10+3)+4\mathbb{Z}\]
\[(14+3)+4\mathbb{Z}\]

It's almost like the cosets have an algebra of their own (foreshadowing).

Here's an important note of caution; recall our notation $k\mathbb{Z}$. Unfortunately, $(\mathbb{Z}, \circ )$ where $\circ$ is multiplication of integers doesn't even form a group, but we accept this 'abuse of notation' to write the subgroups of $(\mathbb{Z},+)$ more easily. This is the only example where we take a left coset of something that isn't a group, and though we cannot treat it like a left coset, we can still use its notation for subgroups of $(\mathbb{Z},+)$.



\subsection{Lagrange's theorem}

We've now got some intuition for cosets, but we've left the best property for last; cosets form a partition on a group.
Cosets can be used to describe a very interesting property about finite subgroups. We will construct a repertoire of lemmas to propound a notorious theorem in group theory.



\begin{lemma}Left cosets are either equal or disjoint.
\end{lemma}


\begin{lemma}Left cosets are equivalence classes on $G$.
\end{lemma}


\begin{theorem}[Lagrange's theorem (group theory)]
Let $H$ be a subgroup of $G$, then the order of $H$ divides the order of $G$ by the amount of distinct left cosets.
\[ H \leq G \implies |G| = [ G:H ] |H| \]
\end{theorem}


\begin{proposition}[Euler's theorem for groups]
Let $G$ be a group, then the following holds.
\[g^{|G|} = 1_{G}\]
\end{proposition}





\section{Conjugacy}


Before finishing the chapter, it is worth going over the idea of \emph{conjugacy}; it will occur spontaneously in many problems, and a formal theory on it will be most beneficial.




\subsection{Commutator}
We now introduce a useful operation generally across group theory.

\begin{definition}[Group commutator]
	\[[x,y] =  x^{-1}y^{-1}xy \]
\end{definition}

Why have such an operation? It was probably conceived because it can be used as a statistic that flags when elements can commute.

\begin{proposition}
\[xy=yx \iff [x,y] =  1_{G} \]
\end{proposition}

Therefore in Abelian groups the commutator is always the identity, however it appears in many identities to do with conjugation.
