\chapter{Review of Point-Set Topology} 
\setcounter{example}{0} 
\begin{dfn}[topology]
\index{topology on a set}
A {\em topology} on a set $X$ is a non-empty collection $\mathcal{T}$ of subsets of $X$
such that:
\begin{eqnarray*}
\mathrm{1.\ }& &\hspace*{-1.5em}\emptyset\in\mathcal{T}\\ 
\mathrm{2.\ }& &\hspace*{-1.5em}X\in\mathcal{T}\\
\mathrm{3.\ }& &\hspace*{-1.5em}\bigcup_{\alpha\in J}U_\alpha\in\mathcal{T}\mathrm{\ for\ any\ }\{U_\alpha\}_{\alpha\in J}\subset\mathcal{T}\\
\mathrm{4.\ }& &\hspace*{-1.5em}\bigcap_{1}^n U_i\in\mathcal{T}\mathrm{\ for\  any\ finite\ collection }\{U_1,\ldots,U_n\}\subset\mathcal{T}.
\end{eqnarray*}

The set $X$ with a given topology $\mathcal{T}$ is called
a {\em topological space},\index{topological space}
and is denoted by $(X,\mathcal{T})$ or simply $X$ if 
the topology is implicitly understood.
Elements of $X$ are called {\em points} of $X$.
\end{dfn}

\begin{dfn}[open set, neighborhood]
\index{open set}\index{neighborhood}
Given a topological space $X$ with a topology $\mathcal{T}$, the sets in $\mathcal{T}$ are called {\em open
sets}. If $x$ contains $X$ and $U$ is an open set containing $x$, we say $U$ is a {\em neighborhood} of $x$.
\end{dfn}

Note that the definition of neighborhood includes the fact that it is open. Not all authors use that definition,
some say a set $N\ni x$ is a neighborhood of $x$ if there is an open set $U$ such that $x\in U\subset N$. In 
this case $N$ need not be open. 

\begin{example}{\rule{0cm}{0.1cm}}\newline\vspace*{-0.5cm}
\be
\item For any set $X$, $\mathcal{T}=\{\emptyset, X\}$ is called the {\em trivial topology} on $X$.
\item $\R$ with 
\[
\mathcal{T}=\left\{\ U=\cup_{i\in J}(a_i,b_i)| a_i < b_i, a_i,b_i\in\R \right\}
\cup\left\{ \emptyset \right\},
\]
called the {\em standard topology} on $\R$. All non-empty open subsets of $\R$ 
consist of unions of open intervals.
\ee
\end{example}

The second example above suggests that we can define a topology by giving a subcollection
of open sets that generate the toplogy:

\begin{dfn}[basis for a topology]
\index{basis}\index{topology!basis of}
A {\em basis} of a topology is a sub-collection $\mathcal{B}\subset\mathcal{T}$
such that for every $U\in\mathcal{T}$, $U$ can be written as the union of an arbitrary
collection of sets in $\mathcal{B}$.
\end{dfn}

Equivalently, $\mathcal{B}\subset\mathcal{T}$ is a basis for $\mathcal{T}$ 
if for every $U\in\mathcal{T}$, and every $x\in U$, there is 
some $B\in\mathcal{B}$ such that $x\in B\in\mathcal{B}$.

\begin{dfn}[limit point]
\index{limit point}
Given a toplogical space $(X, \mathcal{T})$, and $A\subset X$, 
$x\in X$ is a {\em limit
point} of $A$ if any neighborhood of $x$ contains a point in $A$
different from $x$.
The set of all limit points of $A$ is denoted by $A'$.
\end{dfn}

Note that if $x\in A'$, then $x$ may or may not be in $A$ itself.
Also, if $x\in A$, it may or may not be in $A'$.

\begin{dfn}[closed set]
\index{closed set}
Given a toplogical space $(X, \mathcal{T})$, then if $C\subset X$ contains all
of its limit points, $C$ is called a {\em closed set}.
\end{dfn}

\begin{thm}
Given a toplogical space $(X, \mathcal{T})$, then if $C\subset X$ closed, then
$C=X-U$ for some
$U\in\mathcal{T}$.
\end{thm}

Note that there can be (and often are) sets that are neither open nor closed, and sets that are
both open and closed. 

\begin{exercise}
Define a topology in terms of the closed sets. What conditions must a collection
of closed sets possess so that their complements form a topology?
\end{exercise}

\begin{dfn}[closure of a set]
\index{closure of a set}
\index{$\overline{A}$}
\index{$\cl{A}$}
Let $(X,\mathcal{T})$ be a topological space. Then the {\em closure} of $A\in X$,
denoted by $\overline{A}$ or $\cl{A}$,
is $A\cup A'$.
\end{dfn}


\begin{thm}
Let $(X,\mathcal{T})$ be a topological space. Then the { closure} of $A\in X$,
$\overline{A}$
is the smallest closed set containing $A$, in other words, 
it is the intersection of all closed sets of $(X,\mathcal{T})$ that
contain $A$.
\end{thm}

\begin{dfn}[interior of a set]
\index{interior of a set}
\index{$\stackrel{\circ}{A}$}
\index{$\interior{A}$}
Let $(X,\mathcal{T})$ be a set $X$ endowed with the topology $\mathcal{T}$. Then the {\em interior} of $A\in X$
denoted by $\stackrel{\circ}{\!A}$ or $\interior{A}$,
is the largest open set contained in $A$, in other words, the union of all open sets of $\mathcal{T}$ that
are contained in $A$.
\end{dfn}


\begin{dfn}[boundary of a set]
\index{boundary}
\index{$\partial{A}$}
\index{$\bd{A}$}
Let $(X,\mathcal{T})$ be a set $X$ endowed with the topology $\mathcal{T}$. Then the {\em boundary} of $A\in X$
denoted by $\bd{A}$ or $\partial{A}$,
is $\cl{A}-\interior{A}$.
\end{dfn}


\begin{dfn}[subspace topology]
\index{subspace topology}\index{topology!subspace}
Let $A\subset X$, a topological space with topology $\mathcal{T}$. Then $A$ inherits
a topology from $X$ in a natural way: 
$\mathcal{T}_A=\{U\cap A|U\in\mathcal{T}\}$. $A$ with this topology is called a 
(topological) {\em subspace} of $X$.
\end{dfn}



\begin{dfn}[continuity]
\index{continuity}
Let $X$ and $Y$ be two sets with their respective topologies, and 
$f:X\to Y$ a function such that 
for each open set $V$ in $Y$, $f^{-1}(V)$ is open in $X$. 
Then $f$ is called a {\em continuous function} from
$X$ to $Y$.  
\end{dfn}

In other words $f:X\to Y$ is continuous if and only if the {\em preimage} of every
open set in $Y$ is open in $X$. Note that the image of an open set under a continuous function
need not be open.



\begin{dfn} [quotient topology]
\index{quotient topology}%
\index{topology!quotient} Let $X$ be a topological space and $Y$ be a 
set and let $f:X\rightarrow Y$ be a
surjective (onto) function. Then the {\em quotient topology} on $Y$ is 
defined by saying that a subset $U$ is
open in $Y$ if and only if $f^{-1}(U)$ is open in $X$.
\end{dfn}

\begin{thm} Let $X$ be a topological space, $f:X\rightarrow Y$ a
surjective function onto the space $Y$ that has the quotient 
topology. Then $f$ is continuous and,
furthermore, if the topology on $Y$ included any more sets in 
addition to those in the quotient
topology, then $f$ would fail to be continuous.
\end{thm}

\begin{dfn}[identification or quotient space]
\index{identification space}
\index{identification topology}
\index{quotient space}
\index{space!quotient}
\index{space!identification} Let $X$ be a topological space and $X^*$ 
be a partition of
$X$. Let $f:X\rightarrow X^*$ be the map taking each point $x\in X$ 
to $[x]$, the element of
$X^*$ containing $x$ ($[x]$ is called the {\em equivalence class} of 
$x$). Then $X^*$ with the
quotient topology is called the {\em identification space} of $X$ 
under the partition
$X^*$. The quotient topology applied in this manner to a partition of 
$X$ is sometimes called the {\em
identification topology}.
\end{dfn}

\begin{dfn}[homeomorphism]
\index{homeomorphism}
Let $X$ and $Y$ be two sets with their respective topologies, and 
$f:X\to Y$ a one-to-one and onto (or surjective) 
function which is continuous, and such that its inverse function $f^{-1}$ is continuous. 
Then $f$ is called a {\em homeomorphism}, and we say that 
$X$ and $Y$ are {\em homeomorphic}.  
\end{dfn}

\begin{dfn}[Hausdorff]
\index{Hausdorff}
\index{topology!Hausdorff}
A topological space $X$ is {\em Hausdorff}
if for all $x\neq y$ points in $X$, there are disjoint open sets $U$ and $V$
such that $x\in U$ and $y\in V$.
\end{dfn}

\begin{dfn}[cover]
\index{cover}\index{subcover}\index{open cover}
Let $A$ be a subset of $X$, a topological space. A {\em cover} of 
$A$ is a collection $\mathcal U$ of subsets of $X$ such that $A$ is contained (as a subset) 
in their union. An {\em open cover}
is a cover in which all the sets of the cover are open.
A {\em subcover} is a subcollection of $\mathcal U$ that is a 
cover of $A$.
\end{dfn}

\begin{dfn}[compactness]
\index{compact space}
\index{topological space!compact}
Let $A$ be a subset of $X$, a topological space.
$A$ is {\em compact} if every open cover 
of $A$ have a finite subcover.
\end{dfn}


\begin{dfn}[connectedness]
\index{connectedness}
\index{topological space!compact}
Let $X$ be a topological space. Then $X$ is {\em connected} if whenever $X$ 
is decomposed into the union of two disjoint open sets $U$ and $V$ (so $X=U\cup V$
and $U\cap V=\emptyset$), either $U$ or $V$ must be the empty set.
\end{dfn}

\begin{dfn}[path]
\index{path}
Let $p:I\to X$ be a continuous function, where $I=[0,1]$ with the subspace topology
inherited from the standard topology on $\R$ and $X$ a topological space. 
Suppose $p(0)=x$ and $p(1)=y$.
Then $p$ is called a {\em path} in $X$ from $x$ to $y$.
\end{dfn}

\begin{dfn}[path connectedness]
\index{path connectedness}\index{connectedness!path}
\index{topological space!path connected}
A space $X$ is {\em path connected} if for any two points $x$ and $y$
in $X$ there is a path from $x$ to $y$
\end{dfn}

\begin{dfn}[local path connectedness]
\index{path connectedness!local}\index{connectedness!path!local}
\index{topological space!path connected!local}
A space $X$ is {\em locally path connected} if for every $x\in X$
and neighborhood $U$ of $x$, there is a path connected open set $V$
containing $x$ such that $V\subset U$. 
\end{dfn}

The following example
is a space
with infinitely many
circles all tangent at a point. 
This ``Hawaiian earring" sometimes
is useful in seeing the limits of generality of some of 
our theorems
\begin{example}[Hawaiian earring]
\index{Hawaiian earrings}
\[
\bigcup_{n=1}^{\infty} \left\{ S_n \in \R^2 \left|
S_n=\left\{(x,y)\left|\left(x-\frac{1}{2n}\right)^2+y^2=\frac{1}{4n^2}\right.\right\}\right.\right\}
\]
\end{example}

\begin{dfn}[metric]
\index{metric}
Let $X$ be a set and $d:X\times X\to\R_{0, +}$, a function to the 
non-negative real numbers, satisfying, 
for all $x$, $y$, and $z$ in $X$:
\be
\item $d(x,y)=0$ if and only if $x=y$ 
\item $d(x,y)=d(y,x)$
\item $d(x,z)\leq d(x,y)+d(y,z)$ (triangle inequality)
\ee
is called a {\em $d$-metric} on $X$.
\end{dfn}

\begin{dfn}[metric space]
\index{metric space}\index{topological space!metric}
Let $X$ be a space with a metric $d$. Then
$\mathcal{B}=\left\{B_d(x,r)=\{y\in X| d(x,y)<r\}\right\}$
is a basis for a topology on $X$, called the {\em metric topology}.
$B_d(x,r)$ is called the 
{\em open ball of radius $r$ centered at $x$}.
\end{dfn}

\chapter{Review of Group Theory}
\setcounter{example}{0}

\begin{dfn}[group]
\index{group}
A {\em group} is a set $G$ along with a binary operation
$G\times G\to G$, denoted by $\cdot$ (multiplicative notation)
or $+$ (additive notation) satisfying the following three 
conditions:
\be
\item[1.] There exists an element $1\in G$, called the {\em identity element}
such that $g\cdot 1= 1\cdot g$ for all $g\in G$. When we are dealing with multiplicative groups we will write
$1_G$ to denote the identity of $G$. 
\item[2.] For every $g\in G$ there exists an element $g^{-1}\in G$, called the {\em inverse} of $G$, such
that $g\cdot g^{-1}=g^{-1}\cdot g=1$.
\item[3.] For all $g_1,g_2,g_3\in G$ we have $(g_1\cdot g_2)\cdot g_3=g_1\cdot(g_2\cdot g_3)$ ({\em associativity})
\ee
\end{dfn}

In additive notation the identity element is
denoted by $0$: $g+0=0+g=g$ $\forall g\in G$, the inverse by $-g$ so that
we write $g+(-g)=(-g)+g=0$. Additive notation is usually reserved
for {\em commutative} or {\em abelian} groups:

\begin{dfn}[abelian or commutative group] 
A group $G$ is {\em commutative} or {\em abelian} if $g_1\cdot g_2=g_2\cdot g_1$ for all
$g_1,g_2\in G$.
\end{dfn}

Often instead of using $\cdot$ to denote the group operation, we use juxtaposition. In other words, $xy=x\cdot y$.
We often use the verb ``to multiply" to indicate the group operation.
 
\begin{dfn}[trivial group]
The {\em trivial group} is the group that contains only one element, namely the identity. In other words $G=\{1\}$
or  $=\{0\}$ (depending on which notation is being used).
\end{dfn}

\begin{dfn}[permutation]
\index{permutation}\index{cycle!permutation}
Let $A$ be a set of $n$ elements. Then a {\em permutaion} is a bijective function from $A$ to
itself. Usually we use positive integers to describe $A$, that is
$A=\{1,\ldots, n\}$. Let $\{a_1,\ldots, a_m\}\subseteq A$, then we use
$(a_1 a_2 \ldots a_m)$ to represent the function that takes $a_i$ to $a_{i+1}$ for 
$1\leq i\leq m-1$ and $a_m$ to $a_1$. Such a permutation is called an {\em $m$-cycle}.
A $2$-cycle is called a {\em transposition}.
\end{dfn}

\begin{exercise}{\rule{0cm}{0.1cm}}\newline\vspace*{-0.5cm}
\be
\item Show that the set of all permutations on $n$ elements forms a group with
the group operation of function composition.
\item Show that any permutation can be written as a composition of disjoint cycles.
\item Show that any $m$-cycle can be written as a composition of transpositions.
\ee
\end{exercise}

\begin{dfn}[order of a group]
\index{group!order of}\index{order of a group}%
Let $G$ be a 
finite group. 
Then the 
group's cardinality $\left| G \right|$ is called 
the {\em order} of $G$.
\end{dfn}

\begin{dfn}[symmetric group]
\index{symmetric group}\index{group!symmetric}\index{$S_n$}
The group of all permutations on the first $n$ positive integers
is called the {\em symmetric group}, denoted by $S_n$. 
\end{dfn}

\begin{question}
What is the order of $S_n$?
\end{question}

Note that $S_n$ is not an abelian group for $n\geq 3$.
\begin{dfn}[even and odd permutations]
\index{permutation!odd}\index{permutation!even}
A permutation is {\em even} if it can be written as the composition
of an even number of transpositions and {\em odd} otherwise.
\end{dfn}

\begin{exercise} {\rule{0cm}{0.1cm}}\newline\vspace*{-0.5cm}
\be
\item Show that an $n$-cycle can be written as the composition of $n-1$ transpositions.
Thus a $3$-cycle is an even permutation and a $4$-cycle is an odd permutation!
\item Show that the group of even permutations is a subgroup of $S_n$.
\ee
\end{exercise}

\begin{dfn}[alternating group]
\index{group!alternating}
\index{alternating group}
\index{$A_n$}
The group of even permutations is called the {\em alternating group}, denoted by 
$A_n$.
\end{dfn}

\begin{question}
What is the order of $A_n$?
\end{question}

\begin{dfn}[dihedral group]
\index{group!dihedral}\index{dihedral group}\index{$D_n$}
The symmetry group of a regular $n$-sided polygon (under composition) is
called the dihedral group. 
\end{dfn}

\begin{exercise}
Show that if we let $a$ represent a reflection along a line
passing through the polygon's center and a vertex, and $b$ a rotation of $2\pi/n$
around its center, then the elements of 
$D_n$ are the set $\{1, b,\ldots, b^{n-1}, ab,\ldots, ab^{n-1}\}$ 
\end{exercise}

\begin{exercise}
Show that  in $D_n$ as above, we have $ab=b^{n-1}a$, and thus $D_n$ is not abelian for
$n> 2$.
\end{exercise}

\begin{dfn}[subgroup]
\index{subgroup}
A subgroup $H$ of a group $G$ is a subset of $G$ such that $H$ is a group with the binary operation
of $G$.
\end{dfn}

\begin{exercise}
Show that $D_n$ is isomorphic to a proper subgroup of $S_n$.
\end{exercise}

\begin{question}
Under what conditions, if ever, is
$D_n$ is isomorphic to a subgroup of $A_n$?
\end{question}

Since the symmetries of a polygon induce permutations on its vertices, it is easy to see that
$D_n\cong H\subset S_n$, and $H\neq S_n$.

\begin{dfn}[left coset]
\index{left coset}\index{coset!left}
Let $g\in G$, a group, and $H$ be a subgroup of $G$. Then the {\em left coset} of $H$ by $g$ is
\[
gH:=\{gh | h\in H\}.
\]
\end{dfn}

We can define the {\em right coset} $Hg$ similarly.\index{coset!right}

\begin{exercise}
Let $g, g'\in G$. Then either $gH=g'H$ or $gH\cap g'H=\emptyset$.
\end{exercise}

\begin{dfn}[index of a subgroup]
\index{subgroup!index}\index{index of a subgroup}
Let $H$ be a subgroup of $G$, then the {\em index} of $H$ in $G$, denoted
$[G:H]$, is the number of left cosets of $H$ in $G$.
\end{dfn}

\begin{thm}[Lagrange's Theorem]
\index{Lagrange's Theorem}
Let $G$ be a finite group, and $H$ a subgroup. Then the cardinality $|H|$ of $H$
divides the cardinality $|G|$of $G$ and 
\[
[G:H]=\frac{|G|}{|H|}
\]
\end{thm}

\begin{dfn}[normal subgroup]
\index{normal subgroup}\index{subgroup!normal}
A subgroup $H$ of $G$ is called a {\em normal subgroup} of $G$ (denoted $H\lhd G$) 
if $gHg^{-1}=H$, where $aHb:=\{ahb|h\in H\}$.  
\end{dfn}

Multiplying a group or an element on the left by one element 
and on the right by its inverse is called {\em conjugation},\index{conjugation} 
so a normal subgroup is one which is unchanged (set-wise) by conjugation.

\begin{thm}
Let $H\lhd G$ be a  normal subgroup. Then its left and right cosets coincide for all
$g\in G$, in
other words $gH=Hg$ for all $g\in G$. 
\end{thm}


\begin{dfn}[direct product, direct sum]
\index{direct product}\index{direct sum}
The {\em direct product} $G\otimes H$ of two groups $G$ and $H$ is the set $G\times H$ with the 
group operation defined by $(g,h)\cdot(g',h')=(gg', hh')$. When the groups are additive we
call this {\em direct sum} and write $G\oplus H$.
\end{dfn}

\begin{dfn}[homomorphism]
\index{homomorphism!group}
\index{group homomorphism}
A function $f: G\to H$ is a (group) {\em homomorphism} if
$f(g \cdot g')=f(g)\cdot f(g')$ for all $g,g'\in G$.
\end{dfn}

In other words $f$ preserves the group structure in the image of $G$.

\begin{dfn}[isomorphism]
\index{isomorphism!group}
\index{group isomorphism}
A bijective homomorphism $f:G\to H$ is an {\em isomorphism}, in which case we say $G$ is isomorphic to $H$
and write $G\cong H$.
\end{dfn}

But what about when the homomorphism is not bijective?

\begin{dfn}[kernel]
\index{kernel}\index{homomorphism!kernel}
The {\em kernel\/} of a homomorphism $f:G\to H$
is
\[
\kernel f:=\{ g\in G | f(g)=1_H \}
\]
\end{dfn}

\begin{thm}
An onto homomorphism $f:G\to H$ is an isomorphism if and only if $\kernel f=\{1_G\}$.
\end{thm}

\begin{thm}
Let  $f:G\to H$ be a homomorphism from a group $G$ to a group $H$, then $\kernel f \lhd G$.
\end{thm}

\begin{dfn}[quotient group]
\index{quotient group}\index{group!quotient}
A normal subgroup $N\lhd G$ has its left cosets equal its right cosets:
$gN=Ng$. Therefore the set $G/N:=\{gN|g\in G \}$ of all left cosets of $N$
is a group with the group operation 
\[
(gN)\cdot(g'N):=gg'N
\]
This group is called the {\em quotient group} of G by N.
\end{dfn}

\begin{dfn}[normalizer of a subgroup]
\index{normalizer}\index{subgroup!normalizer of}
Let $H$ be a subgroup of $G$. Then the {\em normalizer} of $H$ in $G$
is $N(H)=\left\{g\in G | gHg^{-1}=H \right\}$.
\end{dfn}

Note that $N(H)$ is a subgroup of $G$, $H\lhd N(H)$, 
and that it is the largest subgroup of $G$ in which $H$ is normal, meaning
that any subgroup of $G$ containing $H$ in which $H$ is normal must be
contained in $N(H)$.

\begin{thm}[First isomorphism theorem]
\index{isomorphism theorem, first}
Let $f:G\to H$ be an onto (or surjective) homomorphism with $\kernel f=N$.
Then $H\cong G/N$.
\end{thm}


\begin{dfn}[cyclic subgroup]
\index{cyclic subgroup}\index{subgroup!cyclic}
Let $g\in G$. Then $\left< g\right >$ the {\em cyclic subgroup generated by $g$} is the subgroup formed by
all powers of $g$: 
\[
\left< g \right>:=\{g^n| n\in\Z \}
\]
where $g^n=\overbrace{g\cdot g\cdots g}^{n{\rm{\ times}}}$ if $n>0$, $g^0=1$,
and $g^{-n}=\overbrace{g^{-1}\cdot g^{-1}\cdots g^{-1}}^{n{\rm{\ times}}}$ for $n\in\N$.
\end{dfn}

Note that with additive notation $\left< g \right>=\{ng | g\in G, n\in\Z \}$, where
$ng=\overbrace{g+ g+ \cdots +g}^{n{\rm{\ times}}}$ for $n\in\N$, $g^0=0$,
and $-ng=\overbrace{g+ g+\cdots + g}^{n{\rm{\ times}}}$ for $n\in\N$.

\begin{dfn}[cyclic group]
\index{group!cyclic}\index{cyclic group}
If $G=\left< g \right>$ for some $g\in G$ we say $G$ is a {\em cyclic group} with {\em generator} $g$.
\end{dfn}

Note that cyclic groups are abelian.

\begin{dfn}[finite cyclic group of order $n$]
If $G=\left< g \right>$ and there exists $n\in\Z$ such that $g^n=1$, then there exists
a least $n\in\N$ such that $g^n=1$. $G$ is said to have {\em order} $n$,
$|G|=n$.
\end{dfn}

\begin{thm}
A cyclic group that is non-finite must be isomorphic to $\Z$.
\end{thm}

\begin{thm}
A finite cyclic group of order $n$ is isomorphic to $\Z_n$, the
integers with addition $\mod n$.
\end{thm}


\begin{dfn}[free abelian group of rank $n$]
\index{abelian group!free}\index{free abelian group}
\index{rank}\index{group!free abelian}
A group $G\cong \overbrace{\Z\oplus \Z\oplus\ldots\oplus\Z}^{n{\rm{\ times}}}$
is called the {\em free abelian group of rank $n$}. $G$ has a generating set
of $n$ elements of infinite order, one for each $\Z$ factor.
\end{dfn}

\begin{dfn}[generators]
\index{group!generators}\index{generators of a group}
Let $G$ be a group and $S\subseteq G$. Then the smallest subgroup $H$ of $G$
containing $S$ is called the {\em subgroup generated by $S$}. If $H=G$ then
we say $G$ is generated by $S$, or that $S$ generates $G$. 
\end{dfn}

Note that the set of generators of a group is by no means necessarily unique.
We can view the subgroup $H$ generated by $S$ as the set of all possible products
$g_1 g_2 \ldots  g_n$ where $g_i\in S$ or $g_i^{-1}\in S$.
We can also view $H$ as the intersection of all subgroups of $G$ that contain $S$.
 
\begin{exercise}
{\rule{0cm}{0.1cm}}\newline\vspace*{-0.5cm}
\be
\item Verify that the dihedral group 
$D_n=\{1, b,\ldots, b^{n-1}, ab,\ldots, ab^{n-1}\}$ is generated by $\{a,b\}$.
\item Show that the symmetric group $S_n$, for $n\geq 2$, is generated by the set
of $2$-cycles: $\{(12),(23),\ldots,(n-1,n)\}$.
\item Show that the symmetric group $S_n$, for $n\geq 2$, is generated by the 
pair of cycles $(12)$ and $(12\ldots n)$.
\ee
\end{exercise}

\begin{dfn}[finitely generated group]
\index{finitely generated group}\index{group!finitely generated}
A group is {\em finitely generated} if there exists a finite subset $S$ of $G$
that generates $G$.
\end{dfn}

\begin{thm}[Classification of Finitely Generated Abelian Groups]
\index{finitely generated abelian groups}\index{abelian groups!finitely generated}
Let $G$ be a finitely generated abelian group. Then $G$ is isomorphic to:
\[
H_0\oplus H_1\oplus\ldots\oplus H_m
\]
where $H_0$ is a free abelian group, and $H_i\cong \Z_{p_i}$ ($i=1,\ldots,n$)
where $p_i$ is a prime.
The rank of $H_0$ is unique, and the orders $p_1,\ldots,p_m$ are unique up to reordering.
\end{thm}

\begin{dfn}[commutator, commutator subgroup]
A {\em commutator} in a group $G$ is an element of the form $ghg^{-1}h^{-1}$. The {\em
commutator subgroup} $G'$ is the subgroup generated by the commutators of $G$.
\end{dfn}

\begin{thm}
$G'\lhd G$, and is the smallest subgroup for which $G/G'$ is abelian.
In other words, if there is a subgroup $N\lhd G$ such that $G/N$ is abelian, then
$G'\subset N$.
\end{thm}

There is a useful notation for groups that,
roughly speaking, 
 uses the fact that if we know a set of generators
and the ``rules" (called ``relations") to tell when two elements are the same, then
the group (up to isomorphism) is determined by a list of these generators
and relations. What follows is a very non-technical description
of the generator-relation notation for groups. 

For example, in $D_n$ (as described above)
it is enough to know that
there are two generators $a$ and $b$, of order $2$ and $n$ respectively,
and that 
they satisfy $ab=b^{n-1}a$. These facts determine 
a complete list of elements
$1, b,\ldots, b^{n-1}, ab,\ldots, ab^{n-1}$.
The expressioin $ab=b^{n-1}a$ 
can be written as $aba^{-1}b=1$, and the word $aba^{-1}b$ is
called a {\em relation}. By $a$ and $b$'s order, 
we also know that $a$ and $b$ satisfy
$a^2=1$ and $b^n=1$.
The two letters $a$ and $b$, together with
the above relations completely determine the group $D_n$, and
thus we write:

\[
D_n=\langle a,b | a^2, b^n, aba^{-1}b \rangle
\]
 
Similarly, we can write the cyclic group of order $n$ as:
\[
C_n=\langle a | a^n\rangle.
\]
We can write the infinite cyclic group as:
\[
C_\infty=\langle a | \hspace*{3ex} \rangle.
\]
We can denote the free abelian group of rank $n$ as:
\[
F^{\textrm{ab}}_n=\langle a_1,\ldots,a_n | a_i a_j a_i^{-1} a_j^{-1}, i\neq j\in\{1,\ldots,n\}\rangle
\]


\begin{exercise}
Confirm that the lists of generators and relations given above completely determine
the groups.
\end{exercise}

We should note that 
since the relations $g\cdot g^{-1}=1$, $g\cdot 1= g$ and $1\cdot g=g$ hold 
for any $g\in G$, as they are implicit in the
definition of a group, such relations are not included in the list of relations.
In general a group $G$ can be written as $G=\langle${\em generators}$|${\em relations}$\rangle$.
This is called a {\em group presentation}\index{group!presentation}\index{presentation of a group} $G$. 
This notation is very useful, 
especially when dealing with fundamental group and Van Kampen's theorem.
The problem with this notation, however, is that it is {\em very} difficult, in general, given two
groups with this notation, to tell if the groups are isomorphic or not, or even if
two words represent the same group element.

\begin{exercise}
What is a group presentation for an arbitrary finitely generated abelian group? 
for the symmetric group? 
\end{exercise}

%%%% {\rule{0cm}{0.1cm}}\newline\vspace*{-0.5cm}

%%%%%%%%%%%%%
%\vspace*{1in}
%
%\hfill untwisted pairs \hfill twisted strips \hspace*{\fill}
%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Review of Graph Theory}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Although a graph is an abstract object (a pair $(V,E)$, where $E=\{v, w\}$, and
unordered pair of elements of $V$, we will look at \emph{embedded} graphs
formed of $1$-simplices in $\R^n$.

\begin{dfn}[graph] A {\em graph\/}
\index{graph}
$G$ is the union  of $1$-simplices $\{ \sigma_i\}_{i=1}^k$ in $\R^n$ 
such that for $i\ne  j$,
$\sigma_i \cap \sigma_j$ is empty or an endpoint of each of
$\sigma_i$ and $\sigma_j$. The $\sigma_i$'s are the {\em edges\/} of
$G$.
\end{dfn}

\begin{dfn}[walk]
A {\em walk\/}
\index{graph!walk}%
\index{walk} 
 is a finite sequence of oriented edges, with
the  
vertices starting at a
vertex $v_0$ and ending at a
vertex $v_n$:
\[ 
[v_0 v_1],[v_1 v_2],\ldots,[v_i v_{i+1}],\ldots,[v_{n-1} v_n].
\] 
Note that any two successive edges share a vertex.
We say the walk is a \emph{walk from $v_0$ to $v_n$}.
\end{dfn}


\begin{dfn}[trail]
A {\em trail\/}
\index{graph!trail}
\index{trail} is a path from $v_0$ to $v_n$
where no edge is repeated,
in other words it is finite sequence of edges  
vertices starting at
vertex $v_0$ and ending at vertex $v_n$:
\[ 
[v_0 v_1],[v_1 v_2],\ldots,[v_i v_{i+1}],\ldots,[v_{n-1} v_n],
\] 
and 
$[v_i v_{i+1}]\neq [v_j v_{j+1}]$ for $i\neq j$ and $0\leq i,j\leq n-1$.
\end{dfn}

\begin{dfn}[circuit]
A {\em circuit\/}
\index{graph!circuit}
\index{circuit} is a trail from $v_0$ back to $v_0$ 
(also called a closed trail),
in other words it is finite sequence of edges  
vertices starting and ending at a
vertex $v_0$:
\[ 
[v_0 v_1],[v_1 v_2],\ldots,[v_i v_{i+1}],\ldots,[v_{n-1} v_0],
\] 
 and no 
edge is repeated, that is:
$[v_i v_{i+1}]\neq [v_j v_{j+1}]$ for $i\neq j$ and $1\leq i,j\leq n-1$ 
(where the addition in the indices is done modulo $n$).
\end{dfn}

\begin{dfn}[path]
A {\em path\/}
\index{graph!path}%
\index{path} 
 is a walk from $v_0$ to $v_n$:
\[ 
[v_0 v_1],[v_1 v_2],\ldots,[v_i v_{i+1}],\ldots,[v_{n-1} v_n].
\] 
where $v_i\neq v_j$ when $i\neq j$. 
We say the walk is a \emph{path from $v_0$ to $v_n$}.
\end{dfn}


\begin{dfn}[cycle]
A {\em cycle\/}
\index{graph!cycle}
\index{cycle!graph}
is a path from $v_0$ to $v_0$
where $v_i\neq v_j$ whenever $i\neq j$, for 
$0\leq i,j \leq n$, 
in other words, it is finite sequence of edges  
vertices starting and ending at a
vertex $v_0$:
\[ 
[v_0 v_1],[v_1 v_2],\ldots,[v_i v_{i+1}],\ldots,[v_{n-1} v_0],
\] 
where no vertex (other than the starting vertex) is repeated, 
except for the ending vertex and beginning
vertex respectively of two successive edges.
\end{dfn}

\begin{dfn}[tree]
A {\em tree\/}
\index{tree}
\index{graph!tree}
  is a connected graph with no circuits.
\end{dfn}

\begin{dfn}[maximal tree]
Given a connected graph $G$ with edges $\{
\sigma_i\}_{i=1}^k$, a subgraph $T$ of $G$ is a {\em maximal tree\/}
\index{tree!maximal} if and only if $T$ is a tree and for any edge 
$e$ of $G$ not in $T$,
$T\cup e$ has a circuit.
\end{dfn}

\begin{thm}   Let $G$ be a connected graph. Then $G$ contains a 
maximal tree and every maximal
tree for $G$ contains every vertex of $G$.
\end{thm}