\documentclass[oneside,pdftex,a4paper,bibtotoc]{scrartcl} \title{A topological proof of the Nielsen-Schreier theorem} \author{Benjamin Debeerst} \date{May 23, 2010} %%%%%%%%%%%%%%%%%%%%% % begin header %%%%%%%%%%%%%%%%%%%%% % Sprache \usepackage{english} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} % Inhaltliche Extras \usepackage{graphicx} % Grafiken \usepackage{caption} % und ihre Captions \usepackage{listings} % Fuer die Rechngungen \usepackage{array} % Für schöne Matrizen \usepackage{enumerate} % Listenkonfiguration (römische Nummerierung usw.) % Desgin \usepackage{fancyhdr} % fuer schoene Kopf- und Fusszeilen \usepackage{color} % Farben \usepackage{amsthm} % Theoremstyles % Symbole etc. \usepackage{amsmath} % Mathe \usepackage{amssymb} % Symbole % Kopfzeilen \pagestyle{fancy} \fancyhead{} \fancyfoot[R]{\thepage} \fancyfoot[C]{} \fancyhead[R]{\leftmark} % Literaturverzeichnis \bibliographystyle{alpha} % Saetze, Lemmas etc. \newtheorem{theorem}{Theorem}[section] \newtheorem{prop}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{cor}[theorem]{Corollary} \newtheorem{rem}[theorem]{Remark} \theoremstyle{definition} \newtheorem{defi}[theorem]{Definition} \newtheorem{ex}[theorem]{Example} \newtheorem{exs}[theorem]{Examples} \renewenvironment{proof}[1][Proof]{\noindent\textbf{#1. }}{\hfill$\square$\bigskip} % Symbolkurzschreibweisen \newcommand{\C}{\mathbb{C}} \newcommand{\R}{\mathbb{R}} \renewcommand{\P}{\mathcal{P}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \renewcommand{\L}{\mathbb{L}} \newcommand{\ini}{\mathrm{initial}} \newcommand{\fin}{\mathrm{final}} \renewcommand{\t}{\tilde} \renewcommand{\a}{\alpha} \renewcommand{\b}{\beta} \renewcommand{\c}{\gamma} \renewcommand{\d}{\partial} \newcommand{\e}{\varepsilon} \renewcommand{\phi}{\varphi} \newcommand{\E}{\mathcal{E}} %%%%%%%%%%%%%%%%%%%%% % end header %%%%%%%%%%%%%%%%%%%%% \begin{document} \maketitle \thispagestyle{empty} \abstract{This article is a project work for the course ``Topology and Algebraic Topology'' in the school year 2009/2010 at the University of Ghent. It treats the topological proof for the Nielsen-Schreier theorem, which states that every subgroup of a free group is free. For this, some theory about free groups and infinite graph theory is given first in sections 1 and 2. The reader familiar with finite graphs will see known structures in a broader context. The following sections \ref{sec-cayley-graph}, \ref{sec-fundamental-group} and \ref{sec-graph-coverings} work out the basics for the topological proof in section \ref{sec-subgroups-of-free-groups}. For this, the \emph{Cayley graph} of a group and the \emph{fundamental group} of a graph are declared. The reader familiar with topology will recognise the topological arguments, although none of the classic topologic theory is directly used. Topologic notions as \emph{path}, \emph{path equivalence} and \emph{fundamental groups} are newly defined. The results on subgroups and the corresponding graphs lead directly to the proof of Nielsen-Schreier. This short and elegant proof is followed by a sketch of the algebraic proof in section \ref{sec-algebraic-proof}, which is quite technical and therefore not given completely. The interested reader can find the details in \cite{basicalgebra}. Some consequences of the Nielsen-Schreier theorem are given in section \ref{sec-consequences}. The article ends with a justification of the use of topologic terms in section \ref{sec-justification}. Since all notions are newly defined within this article, the connection to classical topology is not directly clear. A sketch on how the connection can be made is given here. For this section, a basic knowledge of topology is needed, for example the definition of topological spaces and the terms of quotient space, paths, homotopy and covering spaces. The general scope and way of treating the subject is taken from \cite{classicaltopology}. \newpage \tableofcontents \newpage %\section{Introduction} \section{Free Groups} \begin{defi}[Generators, words, relations] A \emph{generator} is a symbol $x_i$ with a formal inverse symbol $x_i^{-1}$. A collection of generators is called \emph{alphabet}. A \emph{word} is a finite sequence of some generators or their inverses $$x_{i_1}^{\e_1}x_{i_2}^{\e_2}\cdots x_{i_n}^{\e_n}, \quad n \in \N_0,\ \e_j \in \{-1,1\}.$$ The product of two words $w_1$ and $w_2$ is the concatenation of the corresponding sequences $w_1\cdot w_2 := w_1w_2$. This product is trivially associative. There is a neutral element for this product, namely the empty word, denoted by $1$ (in literature sometimes also $\e$). We obviously have $1\cdot w = w \cdot 1 = w$ for any word $w$. A \emph{relation} is an equation $r = 1$, where the word $r$ is called \emph{relator}. Two words $w_1$ and $w_2$ are said to be equivalent with respect to some set of relators $R$ if $w_1$ can be converted to $w_2$ by a sequence of the following operations: \begin{enumerate}[(i)] \item insertion or deletion of a relator $r \in R$, \item insertion or deletion of a subword $xx^{-1}$ or $x^{-1}x$. \end{enumerate} \end{defi} \begin{lemma} \label{wordequivalency} The equivalence of words is a equivalence relation. \end{lemma} \begin{proof} Reflexivity is trivial. Symmetry follows from the fact that insertion and deletion of subwords are each others inverse operations. Thus, provided a sequence of operations $s_1,\ldots,s_n$ that converts $w_1$ to $w_2$, the sequence $s_n^{-1},\ldots, s_1^{-1}$ converts $w_2$ to $w_1$. Transitivity is also easy since these operations can be concatenated. \end{proof} The product of words extends in a natural way to a product on the equivalence classes of words via $$[w_1]\cdot[w_2]:=[w_1\cdot w_2].$$ This is well-defined since $w_1w_2$ and $w_1'w_2$ are equivalent if $w_1$ and $w_1'$ are. Associativity is inherited from the product of words. Thus, the set of equivalence classes of words on a certain alphabet $A$ without any more than the trivial relations together with the given multiplication form a group. This group is called the \emph{free group} on $A$, denoted by $\langle A \rangle$. \section{Basic Notions of Graph Theory} The graph notion in the context of free groups is somewhat different from the notion the usually seen in (finite) combinatorics, therefore these are completely defined and explained below. \begin{defi}[Graph] \label{def-graph} A \emph{graph} is a couple $G = (V,E)$, where $V$ is a set of \emph{vertices} and $E$ a set of \emph{edges}. Each edge $e_j \in E$ is a set $\{ e_j^{+1}, e_j^{-1}\}$, containing two \emph{directed edges}, one in positive and one in negative direction. The set of directed edges, the union of all element in $E$ is denoted as $\E$. There are two incidence functions $\ini(), \fin(): \E \rightarrow V$, which mark an \emph{initial point} and an \emph{end point} of every directed edge, with the property that $\ini(e_j^{-1})=\fin(e_j^{+1})$ and $\ini(e_j^{+1})=\fin(e_j^{-1})$. Initial and final point are referred to collectively as \emph{endpoints}. Every edge is said to be \emph{incident} with its endpoints and any edge $e_j$ without a superscript is understood to be directed positively. Also $e_j^{-1}$ and $e_j^{+1}$ are called each others inverses, with $({e_j^{-1}})^{-1} := e_j^{+1}$. A \emph{subgraph} of a graph $G = (V,E)$ is a graph $G = (V',G')$, with $V' \subset V$, $G' \subset G$ and where the incidence functions the ones inherited from $G$. \end{defi} One could criticise this definition of a graph with the sets of directed edges as undirected edges as more complex then necessary, but this definition makes it easy to switch between the directed and undirected version of the same graph without losing formal accuracy. Notice that the sets of vertices and edges are often written as $\{ e_1,e_2,\ldots \}$ or $\{ v_1,v_2,\ldots \}$ although they are not assumed to be countable sets (but they can be). This style is chosen for easy reading and referring and to avoid the need of some index set every time. \begin{defi}[Path, path reducing, path equivalence] A path $p$ of length $r$ in a graph $G$ a finite sequence $d_1,\ldots, d_r$ of directed edges with the property $$\ini(d_i) = \fin(d_{i-1}),\quad \forall i \in \{2,\ldots,r-1\}.$$ One says that $p$ is a path from $\ini(d_1)$ to $\fin(d_r)$. It is called \emph{closed} if $\ini(d_1) = \fin(d_r)$. One writes $p = d_1,\ldots, d_r$ and also $p_3 = pp'$ if $p_3= d_1,\ldots, d_r,d_1',\ldots, d_l'$ and $p' = d_1', \ldots, d_l'$. A path $p$ is called \emph{reduced} if no two successive directed edges are each others inverses. Such a subpath $e_j^{-1}e_j^{+1}$ or $e_j^{+1}e_j^{-1}$ is called \emph{spur}. A single vertex is also admitted as a path (which is trivially reduced). The \emph{inverse} of the path $p = d_1,\ldots, d_r$ is the path $p^{-1} = d_r^{-1},\ldots, d_1^{-1}$. Two paths $p_1$ and $p_2$ are called \emph{equivalent} if one can de derived from the other by a finite number of insertions or removals of spurs between successive directed edges, at the beginning or at the end. \end{defi} \begin{lemma} \label{pathequivalency} Path equivalency is an equivalence relation. \end{lemma} \begin{proof} There is nothing to show for reflexivity. Since insertion and deletion of a spur at a certain point are each others inverse operations, symmetry follows directly. Transitivity is also easy since we deal with finite sequences of operations which can be performed successively. \end{proof} The lemma and its proof are not surprising in any sense, but its consequences are interesting: reducing a path $p$ iteratively by removing stepwise an arbitrary spur, one will get to an end, i.e.~a reduced path which contains no spurs. Transitivity and symmetry guarantee that this reduced path is unique. Therefore, it makes sense to talk about \emph{the} reduced form of $p$, which is a canonical representative for the equivalence class of $p$. \begin{defi}[Connected graph, tree] A graph $G = (V,E)$ is called \emph{connected} if for any two vertices $x, y \in V$ there is a path from $x$ to $y$. A \emph{tree} is a connected graph with no other reduced closed paths than single vertices. \end{defi} One can define trees in a number of different ways from which two are stated in the following lemma: \begin{lemma} The following are equivalent for a graph $G$: \begin{enumerate}[(i)] \item $G$ is a tree. \item Any two vertices of $G$ are connected by a unique reduced path. \item $G$ is a tree and any two paths between two fixed vertices in $G$ are equivalent. \end{enumerate} \end{lemma} \begin{proof} (i)$\Rightarrow$(ii): Assume there are vertices $x, y$ with at least two different reduced paths from $x$ to $y$, $p_1 = a_1,\ldots,a_r$ and $p_2 = b_1,\ldots,b_l$. One can assume one of these paths to be of minimal length, for example $p_1$, and that there is no other pair of vertices with a non-unique reduced path of smaller length. The path $p_1p_2^{-1}$ is closed, and therefore cannot be reduced since the only closed reduced paths in a tree are single vertices. But $p_1$ and $p_2^{-1}$ are themselves reduced, thus the subpath $a_rb_l$ is a spur. Removing this spur leads to a pair of vertices with a non-unique path of shorter length then before, a contradiction. (ii)$\Rightarrow$(iii): Any path $p$ is equivalent to its reduced form. Thus, if two paths have the same reduced form, they are equivalent. (iii)$\Rightarrow$(i): A reduced closed path $p = d_1,\ldots,d_r$ different from a single vertex cannot be equivalent to the single vertex $x := \ini(d_1)$ as a path since both are reduced. Thus, such a path does not exist. \end{proof} In arbitrary graphs reduced paths between two fixed vertices need not to be unique. Therefore, it sometimes makes sense to reduce the view to a subgraph where this uniqueness holds. This leads to the concept of a spanning tree: \begin{defi} A \emph{spanning tree} of a graph $G$ is a subgraph that is a tree with the same vertex set as $G$. \end{defi} \begin{lemma} Every connected graph contains a spanning tree. \end{lemma} \begin{proof} The proof is easy for finite graphs since one can construct a subtree starting with a single edge iteratively. One can expand this to the countable case. More interesting is the uncountable part. The proof given here is taken from \cite{trees}. The set of subgraphs of $G$ that are trees is a directed set and therefore Zorns lemma can be used: there is a maximal subtree $T$ in $G$. Assume $T$ would not contain all vertices, then there is an edge $e$ in $G$ with initial point in $T$ and final point outside $T$ because $G$ is connected. Adding this edge and its final point to $T$ gives another tree $T'$ where $T$ is an unequal larger subtree. This is a contradiction to the assumption that $T$ is maximal. \end{proof} % \newpage % \section{The Nielsen-Schreier Theorem} \section{The Cayley Graph} \label{sec-cayley-graph} \begin{defi} Given a free group $F$ on the generator set $A$, the \emph{Cayley graph} $G$ is defined as $CG(F) := (V,E)$ where the vertex set is $V := G$ and the edge set is $$E := \left\{[g,h]_x = \{[g,h]_x, [h,g]_{x^{-1}}\} \mid g,h \in F,x\in A, g\cdot x = h\right\}.$$ The incidence relation here is $\ini([g,h]_x) = g$, $\fin([g,h]_x) = h$ and $([g,h]_x)^{-1} = ([h,g]_{x^{-1}})$. \end{defi} Since $F$ is a group, every element $x$ has an inverse $x^{-1}$. Thus, the defined structure indeed fits the definition \ref{def-graph}. \begin{lemma} \label{lem-cayley-free-groups} Suppose $F = \langle a_1,\ldots,a_n \rangle$ a free group. Then $CG(F)$ is a tree. \end{lemma} \begin{proof} Assume there is a nontrivial reduced closed path starting and ending in $x$. Thus, there is a series of multiplications indicated by this path such that $x = x\cdot x_1\cdots x_r$. This implies $\e = x_1\cdots x_r$. The path was nontrivial, hence $r \neq 0$. Since there are no relations between the generators besides the trivial ones, this product contains two successive factors $x_j, x_{j+1}$ with $x_j^{-1} = x_{j+1}$. But these factors are represented in the path by two successive edges $[u,v]_{x_j}, [v,w]_{x_{j+1}}$, and from $x_j^{-1} = x_{j+1}$ we have $w = u$. Thus, these edges are the two directions of the same edge. This is a contradiction since the path was assumed to be reduced. \end{proof} From this proof one can see that paths in the Cayley graph of a free group $F$ emanating from the vertex $\e$ correspond to elements in $F$ in a natural, bijective way: there is a unique reduced path to every vertex, thus a unique reduced word corresponding to this vertex and thus representing this vertex as element in $F$. Conversely, given a reduced word in $F$, the series of generators or their inverses indicates a unique reduced path to a certain vertex, which again corresponds to the given word. In particular, spurs correspond to the relations $aa^{-1}$ or $a^{-1}a$, thus the notion of reduced words in a free group and reduced paths in a graph coincide. \section{The Fundamental Group of a Graph} \label{sec-fundamental-group} \begin{defi} Let $G$ be a graph and $v$ a fixed vertex in $G$. The \emph{fundamental group} of $G$ in $v$ is defined as $$\pi_1(G,v) := \{[p] \mid p\mathrm{~is~a~closed~path~starting~in~}v\},$$ where $[p]$ is the equivalence class of the path $p$. The multiplication on $\pi_1(G,v)$ is defined as $$[p_1]\cdot[p_2] := [p_1\cdot p_2].$$ \end{defi} \begin{lemma} The fundamental group of a graph $G$ is a group. When $G$ is connected it is independent from the choice of $v$. \end{lemma} \begin{proof} As for the product of equivalence classes of words, the concatenation of paths is independent from insertion or deletion of spurs, thus the product of equivalence classes of paths is well-defined. The multiplication is obviously associative and we have (just as for words) $[p]^{-1} = [p^{-1}]$. Also obvious is the identity element, namely the equivalence class of the trivial path $v$. Now assume $G$ is connected. Fix another vertex $w$ in $G$, then there is a path $p$ from $v$ to $w$. Now define the map $\phi: \pi_1(G,v) \longrightarrow \pi_1(G,w)$, $[q] \longmapsto [p^{-1}][q][p]$. We will show that $\phi$ is an isomorphism. We have a path $p$ from $v$ to $w$, $p^{-1}$ is the same path in the opposite direction, thus the concatenation $p^{-1}qp$ is well-defined and a closed path on $w$, hence $\phi$ is well-defined. It also is an homomorphism since \begin{align*} \phi([q_1][q_2]) &= [p^{-1}][q_1][q_2][p]\\ &= [p^{-1}][q_1][p][p^{-1}][q_2][p]\\ &= \phi([q_1])\cdot\phi([q_2]). \end{align*} The map $\phi$ is surjective, because for every closed path $q$ on $w$, $\phi([p][q][p^{-1}]) = [q]$, and injective since from $[p^{-1}][q_1][p] = [p^{-1}][q_2][p]$, $[q_1] = [q_2]$ immediately follows. \end{proof} For the fundamental group of connected graphs the notation $v$ is often omitted since it makes no difference for the group structure. The following theorem gives the fundamental connection between graphs and free groups. Since the Nielsen-Schreier theorem \ref{the-nielsenschreier} is proved by the construction of certain graphs, it is in fact the reason why the topological proof is possible at all. \begin{theorem} \label{the-fundamental-group-of-graph} The fundamental group of a connected graph $G$ is free. \end{theorem} \begin{proof} Fix a vertex $v$. We will construct a canonical representative for the equivalence class of any path. Consider a spanning tree $T$ of $G$. Then every vertex $w_i$ has a unique reduced \emph{approach path} $p_i$ in $T$. For each edge $e_i$ with $\ini(e_i)=w_j$ and $\fin(e_i)=w_k$, define the path $a_i := p_j e_i p_k^{-1}$ in $G$ which is a closed path on $v$. Now any closed path on $v$ has a canonical equivalent by the row of $a_i$s corresponding to the row of edges. This is, because the approach paths of succeeding edges cancel and the approach path $w_i$ for $p_i = v$ is the path containing just the single vertex $v$, thus $1$ in the fundamental group. Furthermore, any path $a_i$ corresponding to an edge $e_i$ in $T$ is a closed path in the tree $T$, thus equivalent to $1$. All these paths $a_i$ are therefore unnecessary: every closed path in $G$ on $v$ can equivalently be written as product of $a_i$s, where $e_i$ is not in $T$. In other words, the set $A = \{ [a_i] \mid e_j\mathrm{~is~not~in~} T\}$ generates the fundamental group of $G$. If it can be shown that these generators are free, i.e.~that no relations between the generators but the trivial ones hold, the theorem is proved. Assume there is some nontrivial reduced relation, that is $[a_1]\cdots[a_n] = 1$, where no subsequent factors are each others inverse. We have: \begin{align*} 1 &\sim a_1\cdots a_n\\ &= p_{i_1}e_1 p_{i_2}^{-1}p_{i_2}\cdots p_{i_{n}}e_n p_{i_{n+1}}^{-1}\\ &\sim p_{i_1}e_1 \cdots e_n p_{i_{n+1}}^{-1} \end{align*} By construction, $p_{i_1}$ and $p_{i_{n+1}}^{-1}$ are paths in $T$ while the edges $e_i$ are not in $T$. Thus, there cannot be any possible cancellation between these paths and the edges $e_i$. The subpath $e_1,\ldots, e_n$ must therefore contain spurs, i.e.~two successive $e_j$s are each others inverses. But then, the corresponding $a_j$s would be each others inverses, a contradiction to the assumption that the product is reduced. This shows that there are no relations among the $[a_j]$s but the trivial ones, which proves the theorem. \end{proof} It is important to notice that the maps $\pi_1(\cdot)$ and $CG(\cdot)$ are \emph{not} each others inverses. This is easy to see: the fundamental group $G$ of a connected graph $T$ is free, thus the Cayley graph of $G$ is a tree by lemma \ref{lem-cayley-free-groups}. But if $T$ is no tree, this Cayley graph and $T$ cannot be the same graph.\footnote{To be more exactly: they cannot be isomorphic. But since graph isomorphism is not declared, I avoid this notion here.} The good news is, given a free group $F$, a graph with fundamental group isomorphic to $F$ is easy to construct. \begin{lemma} Assume $F$ is a free group on the generators $a_i$. Define the \emph{bouqet of circles} as the graph $B = (V,E)$, where $V = \{v\}$ and $E = \{a_1, a_2,\ldots\}$. All edges in $E$ have initial and final point $v$. Then $\pi_1(B,v)$ is isomorphic to $F$. \end{lemma} \begin{proof} Every word in $F$ can be read as path in $B$ and conversely. A word is reduced in $F$ if and only if the corresponding path is reduced. But since there is only one vertex in $B$, every path in $B$ is a closed path on $v$. \end{proof} \section{Graph Coverings} \label{sec-graph-coverings} \begin{defi}[Covering Graph] \label{def-covering-graph} Consider two graphs $\t G=(\t V,\t E)$, $G=(V,E)$ with $\t V \neq \emptyset$ and a map $\phi: \t V \cup \t \E \rightarrow V\cup \E$, where the sets of edges and vertices are assumed to be disjoint. Suppose the following properties hold: \begin{enumerate}[(i)] \item $\phi$ preserves endpoints, i.e.~for every directed edge $\t e \in \t \E$ we have $\phi(\ini(\t e)) = \ini(\phi(\t e))$ and $\phi(\fin(\t e)) = \fin(\phi(\t e))$, \item $\phi({\t e}^{-1}) = \phi(\t e)^{-1}$, \item If $\t v$ is a vertex in $\t G$ and $\{ e_1,e_2,\ldots\}$ is the set of directed edges in $G$ with initial point $\phi(\t v)$, than $\phi$ maps the set $\{ \t e_1,\t e_2,\ldots\}$ of edges in $\t G$ with initial point $\t v$ bijective on $\{ e_1,e_2,\ldots\}$. \end{enumerate} Then $\t G$ is said to \emph{cover} $G$ where $\phi$ is called the \emph{covering map} or \emph{projection}. \end{defi} The third condition can be understood as a `local homeomorphism' condition, because it says that `neighbourhoods' of corresponding edges look alike. Altogether, these conditions give a strict bound on the structure of $\t G$ which is stated in lemma \ref{lem-covering-properties}. The notation of the covering graph $\t G$ and the covered graph $G$ will be used throughout the following sections. An element in $\t G$ mapped to the element $a$ in $G$ will always be denoted as $\t a$. Different elements in the inverse image of $a$ will be distinguished by upper indexes $\t a^{(1)},\t a^{(2)}, \ldots$ if necessary. \begin{ex} \label{ex-covering} Consider the graph $G$ with one single vertex and two edges $e_1$, $e_2$ and the covering graph $\t G$ as in figure \ref{fig-graphs}. One can see that the map $\phi:\t G\rightarrow G$ can be fully described by a certain labelling of the graph $\t G$ given some labelling of $G$. In the case of figure \ref{fig-graphs} this is indeed a covering map: since all vertexes are mapped to one single vertex, condition (i) holds trivially. Condition (ii) is complied since the edges are only given in one direction implying the inverse edge with convenient properties. Condition (iii) holds since every vertex in $\t G$ is incident with four directed edges, $e_1$ and $e_2$ each outgoing and incoming. The same is true for the single vertex in $G$. Thus the local homeomorphism condition holds which can also be seen quite literally in figure \ref{fig-neighbourhoods}.\footnote{Notice that, different from what the second figure might suggest, the labelling of the edges is of course important in this condition.} \end{ex} \begin{figure} \centering \includegraphics{graphs2.pdf} \caption{An example for a graph covering.} \label{fig-graphs} \end{figure} \begin{figure} \centering \includegraphics{neighbourhoods2.pdf} \caption{Neighbourhoods of corresponding vertices look alike.} \label{fig-neighbourhoods} \end{figure} \begin{lemma} \label{lem-covering-properties} Given a graph $\t G$ covering the connected graph $G$ the following properties hold: \begin{enumerate}[(i)] \item Given a path $p = d_1,\ldots,d_n$ in $G$, there is a unique path in $\t G$ which is mapped on $p$ by $\phi$ for every vertex $\t v$ in $\phi^{-1}(\ini(d_1))$. \item Every path in $\t G$ corresponding to a spur in $G$ is a spur in $\t G$ itself. \item The cardinality of $\phi^{-1}(\{v\})$, called the \emph{sheet number}, is a constant, i.e.~independent from the choice of $v$. \end{enumerate} \end{lemma} \begin{proof} To proof the lemma, one first has to see that $\phi$ is surjective. Assume it is not, then there is a vertex $v$ or an edge $e$ not in the image of $\phi$. The case of an edge can be easily reduced to the vertex case. Consider $v = \ini(e)$. If $v$ is in the image of $\phi$ while $e$ isn't, this contradicts condition (iii) of definition \ref{def-covering-graph}. Thus $v$ is not in the image of $\phi$. The case of a vertex works as follows. Consider $v$ not in the image of $\phi$. Since $\t V$ is not empty, there is a vertex $\t w$ in $\t G$ with $\phi(\t w) = w$. $G$ is connected, so there is a path $e_1,\ldots,e_n$ from $w$ to $v$. Condition (iii) of the definition gives an edge $\t e_1$ that is mapped on $e_1$ and condition (i) guarantees that the initial and final points are mapped on each other respectively. Doing the same with the $\fin(e_1)$ and iterating this process leads to the corresponding edges $\t e_1,\ldots,\t e_n$ with $\phi(\t e_i)=e_i$ for every $i$. Endpoints are preserved, therefore we have $\phi(\fin(\t e_n)) = v$, a contradiction. Thus $\phi$ is surjective. \begin{enumerate}[(i)] \item The above construction can be repeated for every element in the inverse image of $\ini(d_1)$. Any of these paths is unique, because of condition (iii) in the definition: for an edge in $G$ and a vertex in $\t v$ there can only be exactly one corresponding edge in $\t G$ with initial point $\t v$ since $\phi$ gives a bijective relation. \item Assume a path $p = e_1,e_2$ is a spur. That means $e_2 = e_1^{-1}$. For every edge $\t e_1$, the completion of the corresponding path is unique and conditions (i) and (ii) in the definition make this path a spur as well. \item Given two vertices $v$ and $w$ in $G$, there is a path $p$ from $v$ to $w$ since $G$ is connected. Every vertex $\t v^{(i)}$ in the inverse image of $v$ corresponds to a unique path $\t p^{(i)}$ with endpoint $\t w^{(i)}$. This is induces a bijective map between the inverse images of $v$ and $w$. \end{enumerate} This proofs the lemma. \end{proof} This properties immediately lead to the following: \begin{theorem} \label{the-covering-subgroup} For a covering $\t G$ of a connected graph $G$, $\pi_1(\t G)$ is isomorphic to a subgroup of $\pi_1(G)$. \end{theorem} \begin{proof} Item (ii) of the above lemma implies that equivalent paths in $G$ are covered by equivalent paths in $\t G$ and vice versa. Elements in $\pi_1(G)$ are equivalence classes of loops $p$ on a certain vertex $v$. But item (i) then tells us, once having fixed an element $\t v$ that is mapped to $v$, that the corresponding path in $\t G$ is unique. Thus, there is a bijective map $\phi_*$ between the elements of $\pi_1(G)$ and the equivalence classes $[\t p]$ of paths $\t p$ that emanate from some fixed vertex $\t v$. These paths aren't necessarily closed. But one can restrict the map to closed paths in $\t G$ on $\t v$, which gives an injective map $$\phi_*:\pi_1(\t G,\t v) \longrightarrow \pi(G,v).$$ Properties (i) and (ii) of the definition of coverings imply that products are sent to products and inverses to inverses, thus $\phi_*$ in fact is a monomorphism, which proofs the theorem. \end{proof} Since $\phi_*$ is injective, it is convenient not to distinguish between $\pi_1(\t G,\t v)$ and the image $\phi_*(\pi_1(\t G,\t v))$. \begin{figure}[th] \centering \includegraphics{graphs.pdf} \caption{The \emph{universal abelian cover} for $G$} \label{fig-abelian-cover} \end{figure} \begin{ex} Reconsidering example \ref{ex-covering}, we want to find out which groups are represented by $G$ and $\t G$. The fundamental group of $G$ is generated by exactly two free generators $e_1$ and $e_2$ since the unique vertex is a spanning tree. Thus we have $\pi_1(G) = \langle e_1,e_2 \rangle$. For the fundamental group of $\t G$, fix the unique vertex where the outgoing edge mapped to $e_1$ is a loop (see figure \ref{fig-graphs}). Since the rest of the graph is a tree, the only possible reduced closed paths in $\t G$ are paths of the form $e_1^{n}$, $n\in \Z$. Thus the fundamental group of $\t G$ is the cyclic group generated by $e_1$, which indeed is a subgroup of $\langle e_1 , e_2 \rangle$. As a more complex example consider the covering graph $\t A$ given in figure \ref{fig-abelian-cover}. Fixing a vertex in $\t A$, a path emanating from this vertex is closed if and only if the sums of the exponents of $e_1$ and $e_2$ each equal zero. As a word in the fundamental group of $\t A$, each such path would equal the neutral element if the generators $e_1$ and $e_2$ would commute, which is expressed by the relator $e_1e_2e_1^{-1}e_2^{-1}$. Thus the quotient group of $\pi_1(\t A)$ modulo the \emph{commutator subgroup} $\langle e_1e_2e_1^{-1}e_2^{-1} \rangle$ is trivial which is equivalent to $\pi_1(\t A) \cong \langle e_1e_2e_1^{-1}e_2^{-1} \rangle$. This cover with the commutator subgroup as fundamental group is called the \emph{universal abelian cover} for $G$. \end{ex} The subgroup induced by the covering $\t G$ is the fundamental group of $\t G$ and hence free. If it is possible to construct a covering graph such that its fundamental group isomorphic a given subgroup, the Nielsen-Schreier theorem would be proved. \section{Subgroups of Free Groups} \label{sec-subgroups-of-free-groups} In the construction of $\phi_*$ above, an element from the inverse image of $v$ is chosen. It is important to understand, how the other possible choices correspond to the right cosets of $ \pi_1(G,v)$ modulo $\pi_1(\t G, \t v^{(0)})$. Closed paths in $G$ which lift to non-closed paths in $\t G$ end in some vertex $\t v^(i) \neq \t v$, and thus can be classified by their endpoints in $\t G$. But this is in fact a right coset decomposition of $\pi_1(G)$ modulo $\pi_1(\t G)$. \begin{lemma} Consider the following equivalence class on $\pi_1(G,v)$: $$[p] \sim [p'] :\Leftrightarrow \t p\mathrm{~and~}\t p'\mathrm{~end~in~the~same~point~}\t v^{(j)}$$ The paths $\t p$ and $\t p'$ are understood to emanate from a fixed point $\t v^{(0)}$. There is a bijective map between the right coset decomposition of $\pi_1(G,v)$ modulo $\pi_1(\t G, \t v^{(0)})$ and $\pi_1(G, v)/\sim$. As a concequence, the sheet number $\t G$ covering $G$ is equal to the index of $\pi_1(\t G, \t v^{(0)})$ in $\pi_1(G,v)$. \end{lemma} \begin{proof} Two elements $[p], [p'] \in \pi_1(G,v)$ are in the same right coset if and only if $[g][p] = [p']$ for some $[g] \in \pi_1(\t G,\t v^{(0)})$. This implies $[\t g][\t p] = [\t p']$, where $\t g$ is a path from $\t v^{(0)}$ to $\t v^{(0)}$, thus the paths $[\t p] = [\t p']$ must have the same initial point $\t v^{(0)}$ and end point $\t v^{(i)}$. By definition, this means $[p] \sim [p']$. Now consider two equivalent elements $[p], [p'] \in \pi_1(G,v)$. These lift to paths $\t p,\t p'$ in $\t G$ from $\t v^{(0)}$ to $\t v^{(i)}$. Since $\phi(\t v^{(0)}) = \phi(\t v^{(i)})=v$, the projected paths $p$ and $p'$ are loops on $v$, thus elements of $\pi_1(G,v)$. The path $\t p'\t p^{-1}$ is closed in $\t G$, thus element of $\pi_1(\t G, \t v^{(0)})$. But this implies $[p'][p]^{-1} \in \phi(\t G, \t v^{(0)})$, thus $[p]$ and $[p']$ are in the same right coset of $\pi_1(G,v)$ modulo $\pi_1(\t G, \t v^{(0)})$. \end{proof} We're now ready to proof the basic result from which the Nielsen-Schreier theorem directly will follow. \begin{lemma} \label{lem-subgroups-of-free-groups} Given a free group $F$, $F$ can be realized as the fundamental group of the bouquet of circles $G$. For every subgroup $H$ of $F$, there is a graph $\t G$ that covers $G$ with fundamental group isomorphic to $H$. \end{lemma} \begin{proof} We will construct such a graph $\t G = (\t V , \t E)$ covering $G$ as follows. According to the previous lemma, there has to be a vertex in $\t V$ that is mapped to the single vertex $v$ in $G$ for every right coset of $H$ in $F$. If $\{ p_0, p_1, \ldots \} $ is a set of representatives for these cosets, then define $\t V := \{\t v_0, \t v_1,\ldots \}$ as the vertex set of $\t G$, where every vertex $v_i$ corresponds to the coset $H[p_i]$. As $\t G$ is intended to be a covering, it is subject to the `local homeomorphism' condition \ref{def-covering-graph}(iii). Since $G$ has just one vertex, every edge of $G$ starts in $v$. Consider the set of directed edges $$\t \E := \{\t e_i^{(j)} \mid e_i \in \E, \t v_j \in \t V \},$$ where each of the edges $\t e_i^{(j)}$ has initial point $\t v_j$. But from this, these edges are fully determined: the final point of such an edge $\t e_i^{(j)}$ must be the vertex corresponding to the coset $H[p_je_i]$, because of the previous lemma. The fundamental group of the constructed graph is isomorphic to $H$. A path $\t p$ in $\t G$ emanating from $\t v^{(0)}$ and covering the path $p$ ends at some vertex $\t v^{(j)}$ corresponding to the the right coset $H[p]$. This is, $\t p$ is closed if and only if $H[p] = H$ which is equivalent to $[p] \in H$. That means $\pi_1(\t G)$ and $H$ correspond bijectively, while the bijection is in fact a isomorphism according to the proof of theorem \ref{the-covering-subgroup}. \end{proof} Our goal is an immediate consequence. \begin{theorem}[Nielsen-Schreier] \label{the-nielsenschreier} Any subgroup of a free group is free. \end{theorem} \begin{proof} Given a free group $F$ and a subgroup $H$, one can realize $F$ as the fundamental group of a bouquet of circles. A subgroup can be realized by the fundamental group of some covering graph since lemma \ref{lem-subgroups-of-free-groups}, and therefore is free. \end{proof} \section{Sketch of the Algebraic Proof} \label{sec-algebraic-proof} To proof the Nielsen-Schreier theorem algebraically, we will need the following results from combinatorial group theory. The proofs can be found in \cite{basicalgebra}. For the whole section let $F$ be a free group on the generator set $A$, define $A' := A \cup A^{-1}$, let $H$ be a subgroup of $F$ and $C$ a set of representatives for the cosets of $H$ in $F$. Furthermore, define the map $\rho:F\rightarrow C$, where $g \in F$ is mapped to the coset representative of $Hg$. This function has the property that $\rho(hg) = \rho(g)$ for every $h \in H$ since $Hhg = Hg$. \begin{lemma} There is a set $C$ of representatives for the cosets $Hg \subset F$ where every $g\in C$ is a reduced word $g = b_1b_2\cdots b_n$ in $F$ with the property that also $b_1b_2\cdots b_{n-1} \in C$. Such a set of representatives is called a \emph{Schreier set}. \end{lemma} Notice that from the conditions it follows that the empty word which is the identity in $F$ is an element of $C$ and therefore the representative for $H$ as a coset. \begin{lemma} \label{lem-generators} The elements of the form $ga\rho(ga)^{-1}$ with $g\in C$ and $a \in A$ form a set of generators for H. Furthermore the element $g' = \rho(ga)$ has the properties that $g = \rho(g'a^{-1})$ and $ga^{-1}\rho(ga^{-1})^{-1} \sim (g'a\rho(g'a)^{-1})^{-1}$. \end{lemma} \begin{proof}[Algebraic proof of the Nielsen-Schreier theorem] We will show that the nontrivial generators from lemma \ref{lem-generators} are free. Consider an element $u = ga\rho(ga)^{-1}$. This element is already reduced or equivalent to $1$, which can be seen as follows. Define $g' := \rho(ga)$. Since $g$ and $g'$ are elements of $C$ they are reduced, thus the only possible place for a reduction in $u$ is at $a$. That is, the last factor of $g$ is $a^{-1}$ or the last factor of $g'$ is $a$. If the last factor of $g$ is $a^{-1}$, then $ga$ is equivalent to a prefix of $g$ which must be contained in the Schreier set, thus $\rho(ga) \sim ga$ an therefore $u = ga\rho(ga)^{-1} \sim 1$. The same works for the other case: if the last factor of $g'$ is $a$, then $g'a^{-1}$ is equivalent to a prefix of $g'$ and therefore $\rho(g'a^{-1}) \sim g'a^{-1}$. Lemma \ref{lem-generators} gives $u^{-1} = (ga\rho(ga)^{-1})^{-1} \sim g'a^{-1}\rho(g'a^{-1})^-1 \sim 1$. As a consequence, elements of the form $u = ga\rho(ga)^{-1}$ and $v = fb\rho(fb)^{-1}$ where $f,g \in C$ and $a,b \in A$, are different if and only if they are not equal to one and $(g,a) \neq (f,b)$. Assuming $u$ and $v$ were equal, the words $g$ and $f$ must have the same length. If not, one of them is shorter, for example $g$. But this means $ga$ is a prefix of $f$ and therefore in $C$ since $C$ is a Schreier set. But this means $\rho(ga) = ga$, from which $u = 1$ would follow. Thus they do have the same length, that means $u$ and $v$ are the same reduced word, thus symbolically the identical, from which follows $(g,a) = (f,b)$. It remains to show that a product $u_1 \cdots u_n$ is not equivalent to $1$, when the elements $u_i$ are of the form as $u$ and $v$ above and $u_i \neq u_{i+1}^{-1}$ for $i \in \{1,\ldots,n-1\}$. We will show this first for products of length two. Assume $u$ and $v$ have the form as above, $u^{-1} \neq v$ and both are not equivalent to $1$. The element $u$ is reduced and therefore determines its (reduced) subwords $g$ and $a$, the same is true for $v$. Thus it makes sense to refer to $a$ and $b$ as the \emph{significant factors} of $u$ and $v$ respectively. Define $g' := \rho(ga)$ and $f' := \rho(fb)$. To show the non-equivalency of the product $u\cdot v = gag'^{-1}\cdot fbf'^{-1}$ to $1$ we will show that the significant factors cannot vanish due to cancellation. Assume they do, then we have one of the following cases: \begin{enumerate}[(i)] \item $a$ cancels because the last factor of $g'$ is $a$. Then $g'a^{-1}$ is equivalent to a prefix of $g'$, thus $g'b^{-1} = \rho(g'b^{-1})$, from which $u \sim 1$ follows, \item $b$ cancels because the last factor of $f$ is $b^{-1}$. As in (i), then $fb$ is equivalent to a prefix of $f$ and it follows $v \sim 1$, \item $a$ and $b$ cancel because $g'^{-1}f \sim 1$ and $ab \sim 1$. Then $f = g'$ and $b = a^{-1}$, which with lemma \ref{lem-generators} implies $u = v^{-1}$. \end{enumerate} All these cases are contradicted by the assumptions, thus the significant factors do not cancel, which means that the product cannot be equivalent to $1$. This automatically expands to finite products $u_1 \cdots u_n$, because this is true for every pair of successive factors. This shows that the nontrivial generators for $H$ are free, and therefore form a free generating set for $H$. \end{proof} %\newpage \section{Consequences} \label{sec-consequences} From the previous sections there are some easy consequences. Consider the free group $F$ to be generated by a finite set of generators $A = \{a_1,\ldots,a_r\}$. The number $r$ is called the \emph{rank} of the free group $F$. The following result is referred to as the \emph{Schreier index formula}. \begin{lemma} Suppose $F$ has rank $r$ and the subgroup $H \leq G$ has index $i$ in $G$. Then the rank $s$ of $H$ is given by $$s = i\cdot r - i + 1.$$ \end{lemma} \begin{proof} As $F$ has rank $r$ it is realized as the fundamental group of a bouquet of circles $G$ with $r$ edges, one for each generator of $F$. The subgroup $H$ is realized by the fundamental group of the graph $\t G$ which is a covering for $G$. There are exactly $i$ vertexes in $\t G$ since $i$ this is the sheet number of $\t G$ and $G$ has just one unique vertex. Accordingly, $\t G$ has exactly $i \cdot r$ edges due to construction in the proof of lemma \ref{lem-subgroups-of-free-groups}. A tree with $i$ vertexes has exactly $i-1$ edges, thus for every spanning tree $T$ of $\t G$ there are $i \cdot r - (i-1) = i\cdot r - i + 1$ edges in $\t G$ that are not in $T$. But this is the number of generators for $H$, according to the proof of theorem \ref{the-fundamental-group-of-graph}. \end{proof} Another form in which the formula is often written is $$i = \frac{(s-1)}{r-1}$$ since it reveals the boundary of this formula on the possible ranks of subgroups of free groups with finite index: $r-1$ must be devisor of $s-1$. This says of course nothing about subgroups with infinite index, and counterexamples for this boundary with subgroups of infinite index are easily found. For example contains the group generated by three elements $F = \langle a, b, c\rangle$ the subgroup of infinite index generated by two elements $H = \langle a, b \rangle$, while $2$ is no divisor of $1$. Thus, the contraposition of the lemma can also useful: a subgroup of rank $s$ where $r-1$ is no devisor of $s-1$ must be of infinite index. Also interesting is the special case of normal subgroups. \begin{lemma} Let $F$ be a free group realized as the fundamental group of a bouquet of circles $G$, and let $N$ be a normal subgroup. The covering graph $\t G$ which realizes the subgroup $N$ is the Cayley graph of $F/N$. \end{lemma} \begin{proof} Define $C := CG(F/N)$. There is a vertex in $\t G$ for every (right) coset of $N$ in $F$. But these are exactly the elements of $F/N$ and thus the vertices of $C$. Fix a vertex $v$ in $C$ respectively $\t G$, representing the coset $Nv$. For every generator $a$ of $F$, there is an edge starting in $v$ end ending in the vertex $v\cdot a$, which represents the coset $Nva$. These are all edges of $\t G$. But the same is true for $C$: there is exactly one edge in $C$ for every possible multiplication of the element $Nv$ by some element $Na \in F/N$, which ends in the vertex corresponding to the product, $Na\cdot Na' = N\cdot aa'$. These are all edges of $C$. Therefore the graphs $C$ and $\t G$ are the same. \end{proof} The presented lemmas are just a small cutout of what can be done starting with the Nielsen-Schreier theorem. The interested reader will find more in \cite{classicaltopology}. \nocite{computationalgroups} \section{Connection to Topology} \label{sec-justification} All theory given in this article makes use of topological terms, although no topological space is declared and all treated terms are newly defined. It is possible to build up the same theory from a strict topological point of view. I chose not to do so, because pure algebraically most calculations are literally the same, while the combinatorial terms are sometimes easier to understand. An outline of how the strict topological viewpoint can be treated is give in this section. Such a viewpoint is for example given in \cite{trees}. \bigskip For some graph $G = (V,E)$, consider the discrete topology on $V$ and $\E$ (this is, every subset is an open set) and the following equivalence relation on the disjoint union $T := V \cup ( \E \times [0,1] )$: \begin{alignat*}{2} v_1 \sim v_2 &\Leftrightarrow v_1 = v_2\\ (e_1,s) \sim (e_2,t) &\Leftrightarrow (e_1,s) = (e_2,t)\mathrm{~or~}\\ &\qquad\! e_1 = e_2^{-1}\mathrm{~and~}s=1-t\\ v_1 \sim (e_1,s) &\Leftrightarrow s = 0\mathrm{~and~}v_1 = \ini(e_1)\mathrm{~or~}\\ &\qquad\! s=1\mathrm{~and~}v_1 = \fin(e_1) \end{alignat*} The topological quotient space $R = T/\sim$ is called the \emph{realization} of the graph $G$. What happens here, is that every directed edge is replaced by a standard interval $[0,1]$ while the endpoints of these intervals are identified according to the incidence relations in $G$. Also, the intervals belonging to two directions of one edge are identified appropriately. Paths in $G$ directly translate to paths in $R$ in the topological sense since every edge $e \in \E$ can be identified with the path $p(t) := (e,t)$. Thus if $G$ is connected, so is $R$ (it is even path-connected). The opposite is also true: every path in $R$ with endpoints $(e_1,s)$, $(e_2,t)$ can be `stretched' to a path from $(e_1,0)$ to $(e_2,1)$, and thus is homotopic to a sequence of paths in the form of $p$ above. This is a consequence of the simple connectedness of $[0,1]$. It is now clear that equivalent paths in $G$ translate to homotopic paths in $R$, thus the fundamental group defined on graphs is isomorphic to the fundamental group of its realization. The terms of a coverings also coincide. Suppose $\t G$ is a covering for $G$ then the realization $\t R$ of $\t G$ is a covering space for the realization $R$ of $G$. Notice that the map $\phi:\t G \rightarrow G$ induces a map $\psi: \t R \rightarrow R$, by carrying over the map of vertices and define \begin{align} \psi(e,s) := (\phi(e),s). \label{def-psi} \end{align} One can proof that this is well-defined considering the equivalence relation. Now the following needs to be shown: for every point $x$ in $R$ there is a open neighbourhood $U$ for $x$ where the inverse image of $U$ under $\psi$ is a disjoint union of some open subsets $U_\alpha \subset R$ where each $U_\alpha$ is homeomorphic to $U$. This can be sketched as follows: Suppose first that $x \in R$ is no vertex in $G$. Then $x = (e,t)$ is a point `somewhere on an edge', that is $e$ an edge in $G$ and $t \in\,]0,1[\,$. The open edge $\ddot e := \{(e,s) \in R \mid s \in\,]0,1[\, \}$ then is a open neighbourhood of $x$, whereas the inverse image of $\ddot e$ is a union of open edges in $\t R$, which are distinct or equal by definition (\ref{def-psi}). It clear that $\psi$ is a homeomorphism on each of these edges in $\t R$. Let $x$ be a vertex in $G$. A half-open edge in $R$ with initial point $x$ is the set $\dot e := \{(e,s) \in R \mid s \in\,[0,\frac{1}{2}[\,,\ini(e) = x \} \subset R$. The union $U_x$ of all the half-open edges with initial point $x$ is open (because $[0,\frac{1}{2}[$ is open in $[0,1]$ and $V$, $\E$ have discrete topology) and therefore a neighbourhood for $x$. As in the last paragraph the inverse image of this neighbourhood under $\psi$ is the union of neighbourhoods $U_{\t x^{(i)}}$ for every element $\t x^{(i)}$ in the inverse image of $\{x\}$. These neighbourhoods are indeed homeomorphic to $U_x$ from condition (iii) of definition \ref{def-covering-graph}. (This is in fact where the name `local homeomorphism' condition comes from.) They are also disjoint by construction since $[0,\frac{1}{2}[ \cap ]\frac{1}{2},1] = \emptyset$. This shows that $\t R$ is a covering space for $R$. It is now clear, that lemma \ref{lem-covering-properties} is corresponding to the result from topology known as the path-lifting-lemma. Theorem \ref{the-covering-subgroup} states functoriality, and the fact that different choices of $\t v^{(0)}$ in the inverse image of $v$ correspond to right cosets of the subgroup corresponds to homotopy-lifting. \bigskip As a result, the whole article could have been written in a strict topological way, which was avoided for reasons mentioned above. Thus the proof for the Nielsen-Schreier theorem given in section \ref{sec-subgroups-of-free-groups} does not only use `topological methods', but is factual a proof by topology, although not explicitly visible. \newpage \bibliography{literature} \end{document}