\documentclass[12pt,titlepage]{article}

\usepackage{amsmath}
\usepackage{mathrsfs}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{mathtools}
\usepackage{graphicx}
\usepackage{color}
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
\usepackage{xparse}
\usepackage{hyperref}

%----Macros----------
%
% Unresolved issues:
%
%  \righttoleftarrow
%  \lefttorightarrow
%
%  \color{} with HTML colorspec
%  \bgcolor
%  \array with options (without options, it's equivalent to the matrix environment)

% Of the standard HTML named colors, white, black, red, green, blue and yellow
% are predefined in the color package. Here are the rest.
\definecolor{aqua}{rgb}{0, 1.0, 1.0}
\definecolor{fuschia}{rgb}{1.0, 0, 1.0}
\definecolor{gray}{rgb}{0.502, 0.502, 0.502}
\definecolor{lime}{rgb}{0, 1.0, 0}
\definecolor{maroon}{rgb}{0.502, 0, 0}
\definecolor{navy}{rgb}{0, 0, 0.502}
\definecolor{olive}{rgb}{0.502, 0.502, 0}
\definecolor{purple}{rgb}{0.502, 0, 0.502}
\definecolor{silver}{rgb}{0.753, 0.753, 0.753}
\definecolor{teal}{rgb}{0, 0.502, 0.502}

% Because of conflicts, \space and \mathop are converted to
% \itexspace and \operatorname during preprocessing.

% itex: \space{ht}{dp}{wd}
%
% Height and baseline depth measurements are in units of tenths of an ex while
% the width is measured in tenths of an em.
\makeatletter
\newdimen\itex@wd%
\newdimen\itex@dp%
\newdimen\itex@thd%
\def\itexspace#1#2#3{\itex@wd=#3em%
\itex@wd=0.1\itex@wd%
\itex@dp=#2ex%
\itex@dp=0.1\itex@dp%
\itex@thd=#1ex%
\itex@thd=0.1\itex@thd%
\advance\itex@thd\the\itex@dp%
\makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}}
\makeatother

% \tensor and \multiscript
\makeatletter
\newif\if@sup
\newtoks\@sups
\def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}%
\def\reset@sup{\@supfalse\@sups={}}%
\def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else%
  \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}%
  \else \append@sup#2 \@suptrue \fi%
  \expandafter\mk@scripts\fi}
\def\tensor#1#2{\reset@sup#1\mk@scripts#2_/}
\def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2%
  \reset@sup\mk@scripts#3_/}
\makeatother

% \slash
\makeatletter
\newbox\slashbox \setbox\slashbox=\hbox{$/$}
\def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$}
  \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa
  \copy\slashbox \kern-\@tempdima \box\@tempboxa}
\def\slash{\protect\itex@pslash}
\makeatother

% math-mode versions of \rlap, etc
% from Alexander Perlis, "A complement to \smash, \llap, and lap"
%   http://math.arizona.edu/~aprl/publications/mathclap/
\def\clap#1{\hbox to 0pt{\hss#1\hss}}
\def\mathllap{\mathpalette\mathllapinternal}
\def\mathrlap{\mathpalette\mathrlapinternal}
\def\mathclap{\mathpalette\mathclapinternal}
\def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}}
\def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}}
\def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}}

% Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2}
\let\oldroot\root
\def\root#1#2{\oldroot #1 \of{#2}}
\renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}}

% Manually declare the txfonts symbolsC font
\DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n}
\SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n}
\DeclareFontSubstitution{U}{txsyc}{m}{n}

% Manually declare the stmaryrd font
\DeclareSymbolFont{stmry}{U}{stmry}{m}{n}
\SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n}

% Manually declare the MnSymbolE font
\DeclareFontFamily{OMX}{MnSymbolE}{}
\DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n}
\SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n}
\DeclareFontShape{OMX}{MnSymbolE}{m}{n}{
    <-6>  MnSymbolE5
   <6-7>  MnSymbolE6
   <7-8>  MnSymbolE7
   <8-9>  MnSymbolE8
   <9-10> MnSymbolE9
  <10-12> MnSymbolE10
  <12->   MnSymbolE12}{}

% Declare specific arrows from txfonts without loading the full package
\makeatletter
\def\re@DeclareMathSymbol#1#2#3#4{%
    \let#1=\undefined
    \DeclareMathSymbol{#1}{#2}{#3}{#4}}
\re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46}
\re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12}
\re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64}
\re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6}
\re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77}
\re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77}
\makeatother

% \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE
\makeatletter
\def\Decl@Mn@Delim#1#2#3#4{%
  \if\relax\noexpand#1%
    \let#1\undefined
  \fi
  \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}}
\def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}}
\def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}}
\Decl@Mn@Open{\llangle}{mnomx}{'164}
\Decl@Mn@Close{\rrangle}{mnomx}{'171}
\Decl@Mn@Open{\lmoustache}{mnomx}{'245}
\Decl@Mn@Close{\rmoustache}{mnomx}{'244}
\makeatother

% Widecheck
\makeatletter
\DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}}
\def\@widecheck#1#2{%
    \setbox\z@\hbox{\m@th$#1#2$}%
    \setbox\tw@\hbox{\m@th$#1%
       \widehat{%
          \vrule\@width\z@\@height\ht\z@
          \vrule\@height\z@\@width\wd\z@}$}%
    \dp\tw@-\ht\z@
    \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@
    \setbox\tw@\hbox{%
       \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box
\tw@}}}%
    {\ooalign{\box\tw@ \cr \box\z@}}}
\makeatother

% \mathraisebox{voffset}[height][depth]{something}
\makeatletter
\NewDocumentCommand\mathraisebox{moom}{%
\IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{%
\IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}%
}{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}%
\mathpalette\@temp{#4}}
\makeatletter

% udots (taken from yhmath)
\makeatletter
\def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.}
\mkern2mu\raise4\p@\hbox{.}\mkern1mu
\raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}}
\makeatother

%% Fix array
\newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}}
%% \itexnum is a noop
\newcommand{\itexnum}[1]{#1}

%% Renaming existing commands
\newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}}
\newcommand{\widevec}{\overrightarrow}
\newcommand{\darr}{\downarrow}
\newcommand{\nearr}{\nearrow}
\newcommand{\nwarr}{\nwarrow}
\newcommand{\searr}{\searrow}
\newcommand{\swarr}{\swarrow}
\newcommand{\curvearrowbotright}{\curvearrowright}
\newcommand{\uparr}{\uparrow}
\newcommand{\downuparrow}{\updownarrow}
\newcommand{\duparr}{\updownarrow}
\newcommand{\updarr}{\updownarrow}
\newcommand{\gt}{>}
\newcommand{\lt}{<}
\newcommand{\map}{\mapsto}
\newcommand{\embedsin}{\hookrightarrow}
\newcommand{\Alpha}{A}
\newcommand{\Beta}{B}
\newcommand{\Zeta}{Z}
\newcommand{\Eta}{H}
\newcommand{\Iota}{I}
\newcommand{\Kappa}{K}
\newcommand{\Mu}{M}
\newcommand{\Nu}{N}
\newcommand{\Rho}{P}
\newcommand{\Tau}{T}
\newcommand{\Upsi}{\Upsilon}
\newcommand{\omicron}{o}
\newcommand{\lang}{\langle}
\newcommand{\rang}{\rangle}
\newcommand{\Union}{\bigcup}
\newcommand{\Intersection}{\bigcap}
\newcommand{\Oplus}{\bigoplus}
\newcommand{\Otimes}{\bigotimes}
\newcommand{\Wedge}{\bigwedge}
\newcommand{\Vee}{\bigvee}
\newcommand{\coproduct}{\coprod}
\newcommand{\product}{\prod}
\newcommand{\closure}{\overline}
\newcommand{\integral}{\int}
\newcommand{\doubleintegral}{\iint}
\newcommand{\tripleintegral}{\iiint}
\newcommand{\quadrupleintegral}{\iiiint}
\newcommand{\conint}{\oint}
\newcommand{\contourintegral}{\oint}
\newcommand{\infinity}{\infty}
\newcommand{\bottom}{\bot}
\newcommand{\minusb}{\boxminus}
\newcommand{\plusb}{\boxplus}
\newcommand{\timesb}{\boxtimes}
\newcommand{\intersection}{\cap}
\newcommand{\union}{\cup}
\newcommand{\Del}{\nabla}
\newcommand{\odash}{\circleddash}
\newcommand{\negspace}{\!}
\newcommand{\widebar}{\overline}
\newcommand{\textsize}{\normalsize}
\renewcommand{\scriptsize}{\scriptstyle}
\newcommand{\scriptscriptsize}{\scriptscriptstyle}
\newcommand{\mathfr}{\mathfrak}
\newcommand{\statusline}[2]{#2}
\newcommand{\tooltip}[2]{#2}
\newcommand{\toggle}[2]{#2}

% Theorem Environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{cor}{Corollary}
\newtheorem*{utheorem}{Theorem}
\newtheorem*{ulemma}{Lemma}
\newtheorem*{uprop}{Proposition}
\newtheorem*{ucor}{Corollary}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{example}{Example}
\newtheorem*{udefn}{Definition}
\newtheorem*{uexample}{Example}
\theoremstyle{remark}
\newtheorem{remark}{Remark}
\newtheorem{note}{Note}
\newtheorem*{uremark}{Remark}
\newtheorem*{unote}{Note}

%-------------------------------------------------------------------

\begin{document}

%-------------------------------------------------------------------


\section*{Nielsen-Schreier theorem}

\hypertarget{context}{}\subsubsection*{{Context}}\label{context}

\hypertarget{group_theory}{}\paragraph*{{Group Theory}}\label{group_theory}

[[!include group theory - contents]]

\hypertarget{contents}{}\section*{{Contents}}\label{contents}

\noindent\hyperlink{statement}{Statement}\dotfill \pageref*{statement} \linebreak
\noindent\hyperlink{related_entries}{Related entries}\dotfill \pageref*{related_entries} \linebreak
\noindent\hyperlink{related_concepts}{Related concepts}\dotfill \pageref*{related_concepts} \linebreak
\noindent\hyperlink{references}{References}\dotfill \pageref*{references} \linebreak


\hypertarget{statement}{}\subsection*{{Statement}}\label{statement}

\begin{theorem}
\label{NielsenSchreierTheorem}\hypertarget{NielsenSchreierTheorem}{}
\textbf{(Nielsen--Schreier theorem)}

Every [[subgroup]] $H$ of a [[discrete group|discrete]] [[free group]] $G$ is itself a [[free group]]. Moreover, if $G$ is free on $k$ generators and $H$ has index $n$ in $G$, then $H$ is free on $n k - n + 1$ generators.

\end{theorem}
The second part of this yields what is called the \emph{Schreier index formula}.

This has a number of different proofs. The first proof, perhaps nowadays the most familiar proof, is based on covering space theory (in particular, covering spaces of topological graphs). The second proof is quite similar in spirit but is based on groupoids (another way of viewing homotopy 1-types), and has the advantage that it circumvents the point-set topology considerations inherent to covering space theory.

\begin{proof}
\textbf{of theorem \ref{NielsenSchreierTheorem}}

A free group $G = F(S)$ is, by the [[van Kampen theorem]], a [[fundamental group]] of a bouquet\footnote{A bouquet of circles is the [[coproduct]] of a collection of circles, each with a basepoint, in the category of [[pointed spaces]]. In other words, a [[pushout|wide pushout]] in [[Top]] of inclusions of a 1-point space into circles, with the evident pointing.}  of $S$ many circles, which is in particular a [[connected space|connected]] 1-dimensional [[CW-complex]] $X$ (in simpler language, a connected graph). By general [[covering space]] theory, given a (pointed) connected space $X$ with $\pi_1(X, x) = G$, subgroups $H \subseteq G$ are in bijective correspondence with isomorphism classes of connected covering spaces $p: (E, e) \to (X, x)$, with $\pi_1(E, e) \cong H$. Now, a covering space $E$ of a connected graph $X$ is also a connected graph. But any connected graph is [[homotopy equivalence|homotopy equivalent]] to a bouquet of circles, whose fundamental group is a free group. Thus $\pi_1(E, e)$ is a free group.

The second statement is proved by observing that the Euler characteristic of $X$ is $\chi(X) = 1 - \rho(G)$, where $\rho(G)$ is the number of generators of the free group $G$, and $\chi(E) = n\chi(X)$ if $p \colon E \to X$ is a covering space with $n$ points in each fiber.

Full details may be found in \hyperlink{Maybook}{May}. Key technical ingredients include: (1) each connected graph $E$ contains a maximal [[tree]] $T$ (using [[Zorn's lemma]]), (2) the quotient map $E \to E/T$ is a homotopy equivalence, and $E/T$ is a bouquet of circles.

\end{proof}
This topological proof can be reformulated in more algebraic language, using a little groupoid theory (groupoids being [[homotopy n-type|homotopy 1-types]]). A key construction here is the [[action groupoid]] $X \sslash G$ formed from a $G$-set $X$, also called a homotopy quotient or homotopy orbit space.

\begin{proof}
\textbf{of theorem \ref{NielsenSchreierTheorem}}

By the discussion at \emph{\href{http://ncatlab.org/nlab/show/free+groupoid#FundamentalGroup}{free groupoid -- fundamental group}}, we may think of the [[free group]] $F(S)$ as the [[fundamental group]] of a homotopy 1-type which is freely built from a single vertex and one loop from that vertex to itself for each element in $S$. This is the \emph{[[free groupoid]]} $*\sslash F(S)$ on this [[directed graph]] (a bouquet of circles). It is a classical fact (see at \emph{[[universal principal bundle]]}) that the [[universal cover]] of this is the [[contractible]] groupoid $\mathbf{E}(F(S))$, the [[action groupoid]] $F(S)\sslash F(S)$ of $F(S)$ acting on itself from the right and that its [[quotient]] by the $F(S)$-action from the left recovers the original groupoid with fundamental group $F(S)$. If we instead quotient only by the given subgroup $H \hookrightarrow F(S)$, we obtain a connected groupoid with fundamental group $H$ (meaning simply that at any point or object $x$ of the groupoid, the group $\hom(x, x)$ is isomorphic to $H$).

Thus, consider the [[quotient]] $H \backslash \mathbf{E}F(S) \simeq H \backslash \backslash *$, [[generalized the|the]] connected groupoid whose [[fundamental group]] is $\pi_1 = H$. By the properties of [[free groupoids]] discussed at \emph{\href{http://ncatlab.org/nlab/show/free+groupoid#FundamentalGroup}{free groupoid -- fundamental group}} it is sufficient to show that $H \backslash \mathbf{E}F(S)$ is isomorphic to the [[free groupoid]] on a connected [[directed graph]]. But $\mathbf{E}F(S)$ itself is the free groupoid on a directed graph, namely on the \emph{action graph} $F(S)\sslash S$ (which is the same as the [[Cayley graph]] given by a set $S$ of generators and no relations), and we may consider the quotient graph $H \backslash (F(S) \sslash S)$. The free groupoid functor $F$ preserves this quotient. Thus we have

\begin{displaymath}
H \backslash \mathbf{E}F\left(S\right) = H  \backslash F\left( F\left(S\right)\sslash S \right) =  F \left(\left(H \backslash F\left(S\right)\right)\sslash S\right)
  \,.
\end{displaymath}
as desired.

\end{proof}
\begin{remark}
\label{}\hypertarget{}{}
The original algebraic proof of theorem \ref{NielsenSchreierTheorem} was rather long and complicated, based on Nielsen's method of short cancellations in [[combinatorial group theory]] based on words (Nielsen's transformations of words, word length functions, \ldots{}). The class of \emph{`projective groups'} ( that is, in this context, [[projective object]]s in [[Grp|the category of groups]]) coincides with the class of free groups.

The above simple [[homotopy theory|homotopy-theoretic]] proof was indicated in (\hyperlink{Higgins}{Higgins}), also (\hyperlink{GilbrtPorter}{Gilbert-Porter}).

\end{remark}
\hypertarget{related_entries}{}\subsection*{{Related entries}}\label{related_entries}

\begin{itemize}%
\item [[Cayley graph]]

\end{itemize}
\hypertarget{related_concepts}{}\subsection*{{Related concepts}}\label{related_concepts}

\begin{itemize}%
\item \href{free+module#SubmodulesOfFreeModules}{submodules of a free module}

\end{itemize}
\begin{theorem}
\label{DedekindTheorem}\hypertarget{DedekindTheorem}{}
\textbf{(Dedekind's theorem)}

Every subgroup of a [[free abelian group]] is itself a free abelian group.

\end{theorem}
See at \emph{\href{http://ncatlab.org/nlab/show/principal+ideal+domain#StructureTheoryOfModules}{pid - Structure theory of modules}} for details.

\hypertarget{references}{}\subsection*{{References}}\label{references}

The restricted statement that every subgroup of a free \emph{[[abelian group]]} is itself free was originally given by [[Richard Dedekind]].

[[Jakob Nielsen]] proved the statement for finitely-generated subgroups in 1921. The full theorem was proven in

\begin{itemize}%
\item [[Otto Schreier]], \emph{Die Untergruppen der freien Gruppen}, Abh. Mat Sem. Univ. Hamburg \textbf{3}, 167--169, 1927.

\end{itemize}
The topological proof is due to

\begin{itemize}%
\item [[Reinhold Baer]], [[Friedrich Levi]], \emph{Freie Produkte und ihre Untergruppen}, Compositio Math. 3: 391--398.

\end{itemize}
and another one due to [[Jean-Pierre Serre]].

Versions of the topological proof are given in many places. One is

\begin{itemize}%
\item [[Peter May]], \emph{A Concise Course in Algebraic Topology}, Chicago Lectures in Mathematics, U. Chicago Press (1999), pp. 34-35. Revised version available online (\href{http://www.math.uchicago.edu/~may/CONCISE/ConciseRevised.pdf}{pdf}), chapter 4.

\end{itemize}
Another can be found reviewed towards the end of

\begin{itemize}%
\item [[N. D. Gilbert]], [[T. Porter]], \emph{Knots and Surfaces}, Oxford U.P., 1994.

\end{itemize}
Other related texts include

\begin{itemize}%
\item H. Zieschang, \emph{\"U{}ber die Nielsensche K\"u{}rzungsmethode in freien Produkten mit Amalgam}, Invent. Math. \textbf{10}, 4--37, 1970.


\item W. Magnus, A. Karras, D. Solitar, \emph{Combinatorial group theory}


\item R. Lyndon, P. Schupp, \emph{Combinatorial group theory}, Springer 1977 (Russian transl. Mir, Moskva 1980)



\end{itemize}
A groupoid-based proof of the Nielsen-Schreier theorem appears as theorem 9 in chapter 14 in

\begin{itemize}%
\item [[Philip Higgins|P. J. Higgins]], \emph{Categories and groupoids}, \href{http://www.emis.de/journals/TAC/reprints/articles/7/tr7abs.html}{Repr. Theory Appl. Categ., 1 -- 178} , ISSN 1201-561X, reprint of the 1971 original \emph{Notes on categories and groupoids}, (Van Nostrand Reinhold, London; MR0327946) with a new preface by the author.

\end{itemize}
Similar material can also be found in

\begin{itemize}%
\item [[R. Brown]], \emph{Topology and groupoids}, Booksurge, 2006.

\end{itemize}
[[!redirects Nielsen's theorem]] [[!redirects Nielsen theorem]] [[!redirects Nielsen–Schreier theorem]] [[!redirects Nielsen--Schreier theorem]]

[[!redirects Dedekind-Nielsen-Schreier theorem]]



\end{document}