\documentclass[%
version=last,%
%a4paper,%
a5paper,%
%12pt,%
10pt,%
headings=small,%
bibliography=totoc,%
index=totoc,%
twoside,%
leqno,%
cleardoublepage=empty,%
open=any,%
parskip=half,%
draft=false,%
%draft=true,%
%DIV=classic,%
DIV=12,%
headinclude=false,%
pagesize]%{scrreprt}
{scrbook}

%\usepackage[notref,notcite]{showkeys}

\usepackage{scrpage2}
\pagestyle{scrheadings}
%\ohead{\pagemark}
\ohead{}
%\ihead{\headmark}
\ifoot{\headmark}
%\ofoot{}

\renewcommand{\captionformat}{ }

\usepackage{calc}
\newcounter{hours}\newcounter{minutes}\newcounter{ampm}
\newcommand\printtime{\setcounter{hours}{\time/60}%
                      \setcounter{minutes}{\time-\value{hours}*60}%
                      \ifthenelse{\time<720}
                                 {\setcounter{ampm}{1}}%
                                 {\ifthenelse{\time<780}%
                                             {\setcounter{hours}{12}}%
                                             {\setcounter{hours}{\time/60-12}}}%
                      \ifthenelse{\time<60}%
                                 {\setcounter{hours}{12}}%
                                 {}%       
         \ifthenelse{\value{minutes}>9}%
                    {\thehours:\theminutes\ \ifthenelse{\value{ampm}=1}{a.m.}{p.m.}}%
                    {\thehours:0\theminutes\ \ifthenelse{\value{ampm}=1}{a.m.}{p.m.}}} 
                    % code adapted from the
                                % LaTeX Companion (2d ed), p. 871  

\usepackage{url}
\usepackage{graphicx,rotating} % for the German script picture

\usepackage[polutonikogreek,english]{babel}
\newcommand{\gr}[1]{\foreignlanguage{polutonikogreek}{#1}}


\usepackage{relsize} % Here \smaller scales by 1/1.2; \relscale{X} scales by X

\renewenvironment{quote}{\begin{list}{}
{\relscale{.90}\setlength{\leftmargin}{0.05\textwidth}
\setlength{\rightmargin}{\leftmargin}}
\item[]}
{\end{list}}

\usepackage{amsmath,amssymb,amsthm}
\usepackage[all]{xy}
\usepackage{pstricks,pst-tree}

\newcommand{\corep}[1]{\overline{#1}}
\newcommand{\gpgen}[1]{\langle#1\rangle}
\newcommand{\gppres}[2]{\gpgen{#1\mathpunct|#2}}

\newcommand{\eps}{\varepsilon}
\newcommand{\inv}{^{-1}}
\newcommand{\lng}[1]{\ell(#1)}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\newcommand{\sg}{\leq}    % subgroup
\newcommand{\includes}{\supseteq}
\newcommand{\pincludes}{\supset}
\newcommand{\included}{\subseteq}
\newcommand{\pincluded}{\subset}
\renewcommand{\phi}{\varphi}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Zmod}[1]{\Z/#1\Z}
\newcommand{\N}{\mathbb N}
\newcommand{\C}{\mathbb C}
\newcommand{\Sym}[1]{\operatorname{Sym}(#1)}
\usepackage{upgreek}
\newcommand{\vnn}{\upomega}
\renewcommand{\setminus}{\smallsetminus}
\newcommand{\Tfg}{T_{\mathrm{fg}}}
\usepackage{mathrsfs}
\newcommand{\sig}{\mathscr S}
\newcommand{\Forall}[1]{\forall#1\;}
\newcommand{\Exists}[1]{\exists#1\;}
\usepackage{bm}
\newcommand{\tuple}[1]{\bm{#1}}
\newcommand{\seq}[1]{\mathcal{#1}}
\newcommand{\str}[1]{\mathfrak{#1}}
\newcommand{\Univ}[1]{\operatorname{Univ}(#1)}
\newcommand{\Th}[1]{\operatorname{Th}(#1)}
\newcommand{\Hom}[2][]{\operatorname{Hom}_{#1}(#2)}
\newcommand{\epim}{\twoheadrightarrow}
\newcommand{\isoc}[1]{\mathscr G(#1)}
\newcommand{\proves}{\vdash}
\newcommand{\lto}{\rightarrow}
\newcommand{\liff}{\leftrightarrow}
\newcommand{\Lb}[1][E]{B_{#1}}
\newcommand{\Stone}[1][\Lb]{\operatorname S(#1)}
\newcommand{\pow}[1]{\mathscr P(#1)}
\renewcommand{\emptyset}{\varnothing}
\newcommand{\ball}[1]{\operatorname B(#1)}
\newcommand{\me}{\mathrm e}
\newcommand{\nsfg}{{}^*F}
\newcommand{\supp}[1]{\operatorname{supp}(#1)}

\newcommand{\alg}[1]{#1^{\mathrm{alg}}}
\newcommand{\acf}{\mathrm{ACF}}
\newcommand{\elsub}{\preccurlyeq}
\newcommand{\pelsub}{\prec}

\newcommand{\stone}[1][T_{S,R}]{\operatorname S(#1)}
\newcommand{\diag}[2][S]{\operatorname{diag}_{#1}(#2)}
\newcommand{\bg}{F_{\vnn}}
\newcommand{\bs}{\isoc{\bg}}
\newcommand{\namely}{\text{, which is }}
%\newcommand{\say}{\text{, say, }}
\newcommand{\is}{\text{ is }}
\newcommand{\cl}[1]{\operatorname{c\ell}(#1)}
\newcommand{\dist}{\operatorname d}
\newcommand{\symdiff}{\mathbin{\vartriangle}}
\newcommand{\upow}[1]{{}^*#1}

\newcommand{\SL}[2][2]{\operatorname{SL}_{#1}(#2)}
\newcommand{\PSL}[2][2]{\operatorname{PSL}_{#1}(#2)}
\newcommand{\centr}[1]{\operatorname C(#1)}
\newcommand{\abs}[1]{\lvert#1\rvert}


\newlength{\mydots}
\settowidth{\mydots}{${}=E_0{}^{k_0}\cdot E_1{}^{k_1}\cdot E_0{}^{k_2}\dotsm E_1{}^{k_{n-1}}\cdot
\begin{pmatrix}
  \pm1&m\\
0&\pm1
\end{pmatrix}$}


\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{question}[theorem]{Question}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{porism}[theorem]{Porism}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}



\theoremstyle{definition}

\newtheorem{example}{Example}
\newtheorem{step}{Step}


\renewcommand{\theequation}{\fnsymbol{equation}}

\usepackage{hfoldsty}
\usepackage[neverdecrease]{paralist}

\begin{document}

\title{Free groups}
\subtitle{Notes from the Istanbul model theory seminar}
\author{David Pierce}
\date{\today, \printtime}
\publishers{Matematics Department\\
Mimar Sinan Fine Arts University\\
Istanbul\\
\mbox{}\\
\url{dpierce@msgsu.edu.tr}\\
\url{http://mat.msgsu.edu.tr/~dpierce/}}

\uppertitleback{\centering
These notes are usually based on my handwritten notes
  taken during the seminar.  The schedule of the talks and speakers is in an appendix. 
I have made adjustments and supplements according to my understanding
and preferences.} 

\maketitle

\tableofcontents

\listoffigures


\chapter{Free groups}

Our source is Baumslag,
\emph{Combinatorial Group Theory.}    

Let $G$ be a group, and let $H$ be a subgroup of $G$:
\begin{equation*}
H\sg G.
\end{equation*}
We consider the set 
\begin{equation*}
H\backslash G
\end{equation*}
of right cosets of $H$ in $G$.  The quotient map $g\mapsto Hg$ from $G$ to $H\backslash G$ is surjective, so it has a right inverse, which we may denote by
\begin{equation*}
Hg\mapsto\corep g.
\end{equation*}
(Here we use the Axiom of Choice if the index of $H$ in $G$ is infinite.)
Then
\begin{equation*}
H\corep g=Hg.
\end{equation*}
We may assume $\corep 1=1$.  We denote the range of the function $Hg\mapsto\corep g$ by $R$.  Then $R$ is a complete set of right-coset representatives of $H$ in $G$, and $R$ contains $1$.  In a word, $R$ is a right \textbf{transversal}\footnote{This word was introduced the following week.} of $H$ in $G$ (and $R$ contains $1$).
The situation is depicted in Figure~\ref{fig:R}.
\setlength{\unitlength}{1mm}
\begin{figure}[t]
\centering
\begin{picture}(55,34)
\put(0,0){\line(1,0){55}}
\put(55,0){\line(0,1){34}}
\put(55,34){\line(-1,0){55}}
\put(0,34){\line(0,-1){34}}
\put(6,0){\line(0,1){34}}
\put(3,20){\line(1,0){46}}
\put(3,20){\circle*1}
\put(3,20){\makebox(0,5){$1$}}
\put(30,0){\line(0,1){34}}
\put(36,0){\line(0,1){34}}
\put(33,20){\circle*1}
\put(33,20){\makebox(0,5){$\corep g$}}
\put(33,5){\circle*1}
\put(33,5){\makebox(0,5){$g$}}
\put(49,20){\makebox(5,0){$R$}}
\put(3,34){\makebox(0,5){$H$}}
\put(33,34){\makebox(0,5){$Hg$}}
\put(55,34){\makebox(5,5){$G$}}
\end{picture}
\caption{Transversal of a subgroup}\label{fig:R}
\end{figure}

For every $g$ in $G$, the element $\corep g$ of $R$ is such that
\begin{equation*}
g\in H\corep g.
\end{equation*}
Then there is a unique element $h$ of $H$ such that 
\begin{equation*}
g=h\cdot\corep g.
\end{equation*}
We define a function $(r,g)\mapsto\delta(r,g)$ from $R\times G$ to $H$ by
\begin{equation}\label{eqn:delta}
rg=\delta(r,g)\cdot\corep{rg}.
\end{equation}
In particular then,
\begin{equation*}
g=\delta(1,g)\cdot\corep g.
\end{equation*}
Note also that $\delta(r,g)$ is just another name for $rg\cdot(\corep{rg})\inv$.

Now suppose that $G$ is generated by $X$:
\begin{equation*}
G=\gpgen X.
\end{equation*}
Then we have:

\begin{theorem}\label{thm:delta}
The subgroup $H$ of $G$ is generated by the image of $R\times X$ under $\delta$:
\begin{equation*}
H=\gpgen{\delta(r,x)\colon r\in R\land x\in X}.
\end{equation*}
\end{theorem}


\begin{proof}
By definition, each $\delta(r,x)$ is in $H$, so we have
\begin{equation*}
\gpgen{\delta(r,x)\colon r\in R\land x\in X}\sg H.
\end{equation*}
To show the reverse inclusion, we let $h\in H$.  Then we can write $h$ as $x_1{}^{\eps_1}\dotsm x_n{}^{\eps_n}$, where $x_i\in X$ and $\eps_i=\pm1$.  Then we have
\begin{align*}
h
&=x_1{}^{\eps_1}\dotsm x_n{}^{\eps_n}\\
&=1\cdot x_1{}^{\eps_1}\dotsm x_n{}^{\eps_n}\\
&=\delta(1,x_1{}^{\eps_1})\cdot\corep{x_1{}^{\eps_1}}\cdot x_2{}^{\eps_2}\dotsm x_n{}^{\eps_n}\\
&=\delta(1,x_1{}^{\eps_1})\cdot\delta(\corep{x_1{}^{\eps_1}},x_2{}^{\eps_2})\cdot\corep{\corep{x_1{}^{\eps_1}}\cdot x_2{}^{\eps_2}}\cdot x_3{}^{\eps_3}\dotsm x_n{}^{\eps_n}
\end{align*}
and so on; ultimately,
\begin{equation*}
h=\underbrace{\delta(1,x_1{}^{\eps_1})\cdot\delta(r_2,x_2{}^{\eps_2})\dotsm\delta(r_n,x_n{}^{\eps_n})}_{\in H}\cdot r
\end{equation*}
for some $r_i$ and $r$ in $R$.  Then $r=\corep h$, so $r=1$, and therefore
\begin{equation*}
h=\delta(1,x_1{}^{\eps_1})\cdot\delta(r_2,x_2{}^{\eps_2})\dotsm\delta(r_n,x_n{}^{\eps_n}).
\end{equation*}
If we can move the $\eps_i$ outside the parentheses (perhaps by adjusting the $r_i$ within $R$), we are done.

We do this.  For arbitrary $r$ in $R$ and $x$ in $X$, we have
\begin{gather}\notag
	rx\inv=\delta(r,x\inv)\cdot\corep{rx\inv},\\\label{eqn:r}
	r=\delta(r,x\inv)\cdot\corep{rx\inv}\cdot x
	=\underbrace{\delta(r,x\inv)\cdot\delta(\corep{rx\inv},x)}_{\in H}\cdot\underbrace{\corep{\corep{rx\inv}\cdot x}}_{\in R}
\end{gather}
so $\delta(r,x\inv)\cdot\delta(\corep{rx\inv},x)=1$ and hence
\begin{equation}\label{eqn:inv}
\delta(r,x\inv)=\delta(\corep{rx\inv},x)\inv.\qedhere
\end{equation}
\end{proof}

\begin{corollary}
A subgroup of finite index of a finitely generated group is finitely generated.  Indeed, if $G$ is $n$-generated, and $H$ has index $k$ in $G$, then $H$ is at most $kn$-generated.
\end{corollary}

We aim now to prove that every subgroup of a free group is free.
To this end, we consider the group $G$ above as the free group $F$ on the set $X$.  Still $H\sg F$.  A set $S$ of right-coset representatives of $H$ in $F$ is called a (right) \textbf{Schreier set} (with respect to $X$ and $H$) if, whenever $x_1{}^{\eps_1}\dotsm x_n{}^{\eps_n}$ is a reduced word on $X$ that belongs to $S$, then each initial segment $x_1{}^{\eps_1}\dotsm x_i{}^{\eps_i}$ belongs to $S$.  A Schreier set is \textbf{complete,} or is a \textbf{transversal,} if it is complete as a set of (right-) coset representatives.

We shall be able to find a Schreier transversal by recursion on the \emph{lengths} of cosets.  In case $X$ is not otherwise known to be well-orderable, we shall have to use the Axiom of Choice.

If $g\in F$, then its \textbf{length,} $\lng g$, is the length of the reduced word on $X$ that is equal to $g$.  Then a coset $Hg$ has a \textbf{length,} $\lng{Hg}$, where
\begin{equation*}
\lng{Hg}=\min\{\lng{hg}\colon h\in H\}.
\end{equation*}
That is, $\lng{Hg}$ is the minimum length of a representative of $Hg$.

\begin{lemma}\label{lem:Schreier}
There is a Schreier transversal (with respect to $X$ and $H$).
\end{lemma}

\begin{proof}
We assign to the unique coset of length $0$ the representive $1$.  This representative itself has length $0$.

Suppose now that, for each coset of length at most $n$, a representative of the same length has been chosen, and moreover, when this representative is written out as a reduced word on $X$, then every initial segment is also one of the chosen representatives.  Say $\lng{Hg}=n+1$.  Then $Hg$ has an element $y_1\dotsm y_n\cdot y_{n+1}$, where $y_i\in X\sqcup X\inv$.  We have
\begin{equation*}
\lng{Hy_1\dotsm y_n}=m\leq n
\end{equation*}
for some $m$, and so, by hypothesis, $Hy_1\dotsm y_n$ has a chosen representative $z$ of length $m$.  Then
\begin{equation*}
Hg=Hy_1\dotsm y_n\cdot y_{n+1}=Hz\cdot y_{n+1},
\end{equation*}
and we may choose $z\cdot y_{n+1}$ as a representative of $Hg$.  We have
\begin{equation*}
n+1\leq\lng{z\cdot y_{n+1}}\leq m+1\leq n+1,
\end{equation*}
so $m=n$.  Therefore the recursion can indeed be continued.  Strictly, we need to be able to choose \emph{one} such $y_{n+1}$.  But, assuming $X$ has been well-ordered, we can well-order $X\sqcup X\inv$, and then we can well-order the reduced words in $X$ by a lexigraphic ordering; finally, we can let $y_1\dotsm y_n\cdot y_{n+1}$ be minimal in this ordering.
\end{proof}

We henceforth assume that the transversal $R$ above is a Schreier trans\-versal $S$.
In a free group, if $\lng{ab}=\lng a+\lng b$, we may write $ab$ as\label{triangle}
\begin{equation*}
a_{\triangle}b;
\end{equation*}
but if $\lng{ab}<\lng a+\lng b$, we may write $ab$ as
\begin{equation*}
a_{\sqcup}b.
\end{equation*}

\begin{lemma}\label{lem:2}
If $x\in X\sqcup X\inv$ and $\delta(s,x)\neq1$, then
\begin{equation*}
\delta(s,x)=s_{\triangle}x_{\triangle}(\corep{sx})\inv.
\end{equation*}
\end{lemma}

\begin{proof}
Suppose $sx=s_{\sqcup}x$.  Then $s=tx\inv$ for some $t$, which is also in $S$ since this is a Schreier set.  Then
\begin{equation*}
\delta(s,x)=sx(\corep{sx})\inv=t(\corep t)\inv=tt\inv=1.
\end{equation*}
The other possibility to consider is $x(\corep{sx})\inv=x_{\sqcup}(\corep{sx})\inv$.  Then $\corep{sx}\cdot x\inv=\corep{sx}_{\sqcup}x\inv$, so $\corep{sx}=tx$ for some $t$, which again must be in $S$.  We now have
\begin{equation*}
\delta(s,x)=sx(\corep{sx})\inv=sx(tx)\inv=st\inv,
\end{equation*}
so this is in $H$.  But then $Hs=Ht$, so $s=t$ and therefore $\delta(s,x)=1$.
\end{proof}

\begin{lemma}\label{lem:3}
If $x,y\in X\sqcup X\inv$ and $\delta(s,x)=\delta(t,y)\neq1$, then 
\begin{equation*}
(s,x)=(t,y).
\end{equation*}
\end{lemma}

\begin{proof}
By Lemma~\ref{lem:2}, we have
\begin{equation*}
s_{\triangle}x_{\triangle}(\corep{sx})\inv=t_{\triangle}y_{\triangle}(\corep{ty})\inv.
\end{equation*}
If $\lng s=\lng t$, then we must have $s=t$ and then $x=y$.  In the other case, we may assume $\lng s<\lng t$, so that $t=sxu$ for some $u$, and in particular $sx\in S$.  But then $\corep{sx}=sx$, so $\delta(s,x)=1$.
\end{proof}

\begin{lemma}\label{lem:4}
Suppose $h=\delta(s_1,x_1)^{\eps_1}\dotsm\delta(s_n,x_n)^{\eps_n}$, where none of the factors $\delta(s_i,x_i)^{\eps_i}$ is $1$ or is the inverse of the following.  Then
\begin{equation*}
h=\cdots _{\triangle}x_1{}^{\eps_1}{}_{\triangle}\cdots_{\triangle}x_2{}^{\eps_2}{}_{\triangle}\cdots;
\end{equation*}
in particular, $h\neq1$ unless $n=0$.
\end{lemma}

\begin{proof}
By Lemma~\ref{lem:2}, we have
\begin{equation*}
\delta(s,x)\cdot\delta(t,y) =(s_{\triangle}x_{\triangle}(\corep{sx})\inv) \cdot (t_{\triangle}y_{\triangle}(\corep{ty})\inv).
\end{equation*}
By~\eqref{eqn:inv} in the proof of Theorem~\ref{thm:delta}, it is enough to show that this product is $s_{\triangle}x_{\triangle}\cdots{}_{\triangle}y_{\triangle}(\corep{ty})\inv$, unless one of the factors, or the whole product, is $1$.
There are three possibilities to consider.

Suppose that $t$, as a reduced word in $X$, has an initial segment equal to $\corep{sx}\cdot x\inv$.  Then this segment is in $S$, so
\begin{equation*}
\corep{sx}\cdot x\inv=\corep{\corep{sx}\cdot x\inv}.
\end{equation*}
By~\eqref{eqn:r} in the proof of Theorem~\ref{thm:delta}, we now have
$s=\corep{sx}\cdot x\inv$, so $\delta(s,x)=1$.

Now suppose that $\corep{sx}$, as a reduced word in $X$, has an initial segment equal to $ty$.  Then $ty\in S$, so $\corep{ty}=ty$, and hence $\delta(t,y)=1$.

Suppose finally
\begin{equation*}
x_{\triangle}(\corep{sx})\inv=(t_{\triangle}y)\inv.  
\end{equation*}
Then $x=y\inv$ and $\corep{sx}=t$, so again by~\eqref{eqn:inv} 
\begin{equation*}
\delta(t,y)\inv=\delta(\corep{sx},x\inv)\inv=\delta(s,x).\qedhere
\end{equation*}
\end{proof}

\begin{theorem}\label{thm:sub-free}
Every subgroup of a free group is free.  Indeed, if
\begin{equation*}
Y=\{(s,x)\colon (s,x)\in S\times X\land\delta(s,x)\neq1\},
\end{equation*}
then the free group on $Y$ is isomorphic to $H$ under the map
\begin{equation*}
(s,x)\mapsto\delta(s,x).
\end{equation*}
\end{theorem}

\begin{proof}
By Theorem~\ref{thm:delta}, $H$ is generated by the image of $Y$ under $\delta$.
By Lemma~\ref{lem:3}, $\delta$ is injective on $Y$.
By~\eqref{eqn:inv}
and Lemma~\ref{lem:3}, we never have $\delta(s,x)=\delta(t,y)\inv$ for any $(s,x)$ and $(t,y)$ in $Y$.  Then also by Lemma~\ref{lem:4}, the extension of $\delta$ to a homomorphism from the free group on $Y$ to $H$ is an embedding.
\end{proof}

\begin{example}
Let $F=\gpgen{x,y}$ and let $H$ be the kernel of the homomorphism
\begin{align*}
x&\mapsto1,&y&\mapsto0
\end{align*}
 from $F$ onto $\Zmod2$.
Then $[F:H]=2$, so we may let $R=\{1,x\}$.  
Recalling the definition~\eqref{eqn:delta} and filling out the table
\begin{equation*}
\begin{array}{cc|cc}
R&X&H&R\\\hline
r&u&\delta(r,u)&\corep{ru}\\\hline
1&x&1&x\\
1&y&y&1\\
x&x&x^2&1\\
x&y&xyx\inv&x
\end{array}
\end{equation*}
we have that $H$ is free on $\{y,x^2,xyx\inv\}$, that is,
\begin{equation*}
\{y,x^2,y^{x\inv}\},
\end{equation*}
where we use the notation
\begin{equation*}
a^b=b\inv ab.
\end{equation*}
\end{example}

\begin{example}
Now letting the homomorphism be
\begin{align*}
x&\mapsto(1,0),&y&\mapsto(0,1)
\end{align*}
to $\Zmod2\oplus\Zmod2$, we have $[F:H]=4$, and we may let 
\begin{equation*}
R=\{1,x,y,xy\}, 
\end{equation*}
so that, from the table
\begin{equation*}
\begin{array}{cc|cc}
R&X&H&R\\\hline
r&u&\delta(r,u)&\corep{ru}\\\hline
1&x&1&x\\
1&y&1&y\\
x&x&x^2&1\\
x&y&1&xy\\
y&x&yxy\inv x\inv&xy\\
y&y&y^2&1\\
xy&x&xyxy\inv&y\\
xy&y&xy^2x\inv&x
\end{array}
\end{equation*}
$H$ is freely generated by $\{x^2,yxy\inv x\inv,y^2,xyxy\inv,xy^2x\inv\}$, that is,
\begin{equation*}
\{x^2,[y\inv,x\inv],y^2,xx^{y\inv},(y^2)^{x\inv}\},
\end{equation*}
where we use the notation
\begin{equation*}
[a,b]=a\inv b\inv ab.
\end{equation*}
\end{example}

\begin{example}
Now let the `same' homomorphism be onto $\Z\oplus\Z$.
Then $F'\sg H$ (where $F'$ is the subgroup of $F$ generated by the commutators $[a,b]$).
We can let 
\begin{equation*}
R=\{x^iy^j\colon(i,j)\in\Z\oplus\Z\}.
\end{equation*}
Since
\begin{gather*}
x^iy^j\cdot x=x^iy^jxy^{-j}x^{-i-1}\cdot x^{i+1}y^j,\\
x^iy^j\cdot y=1\cdot x^iy^{j+1},
\end{gather*}
we have that $H$ is freely generated by the $x^iy^jxy^{-j}x^{-i-1}$, that is,
\begin{equation*}
[(x^iy^j)\inv,x\inv].
\end{equation*}
In particular, $H\sg F'$, so
\begin{equation*}
H=F'.
\end{equation*}
\end{example}

\begin{theorem}\label{thm:fp}
Suppose $H$ is finitely generated.
Then there is a subgroup $K$ of $F$ such that the subgroup $\gpgen{H\cup K}$ of $F$ is the free product $H*K$, and this is of finite index in $F$.
\end{theorem}

\begin{proof}
Let $Y$ be as in Theorem~\ref{thm:sub-free}.  We want to extend $\delta(Y)$ to a set $\delta(Y)\sqcup W$ that freely generates a subgroup of $F$ of finite index; then $K$ can be $\gpgen W$.

  Let $T$ be the set of all initial segments of those $s$ and $\corep{sx}$ such that $(s,x)\in Y$.  Since $H$ is assumed finitely generated, $T$ is finite.
  
  Since $S$ is a Schreier set, it includes $T$; also then, $T$ is itself a Schreier set.  If $x\in X$, define
\begin{equation*}
T(x)=\{s\colon s\in T\land \corep{sx}\in T\}.
\end{equation*}
Then
\begin{equation*}
s\mapsto\corep{sx}\colon T(x)\to T.
\end{equation*}
This function is injective, since if $\corep{sx}=\corep{tx}$, then $Hsx=Htx$, so $Hs=Ht$.  Hence the function $s\mapsto\corep{sx}$ extends to a permutation $\phi_x$ of $T$.  Since $F$ is free on $X$, we obtain a right action $g\mapsto\phi_g$ of $F$ on $T$.

Suppose $(s,x)\in T\times X$.  If $sx\in T$, then $sx=\corep{sx}=s\cdot\phi_x$.  If $sx\inv\in T$, then
\begin{equation*}
(sx\inv)\cdot\phi_x=\corep{sx\inv x}=\corep s=s,
\end{equation*}
and therefore $s\cdot\phi_{x\inv}=(sx\inv)\cdot\phi_x\cdot\phi_{x\inv}=sx\inv$.  In short, if $sx^{\eps}\in T$, where $\eps=\pm1$, then
\begin{equation*}
s\cdot\phi_{x^{\eps}}=sx^{\eps}.
\end{equation*}
Now say $t$ is an element $x_1{}^{\eps_1}\dotsm x_n{}^{\eps_n}$ of $T$.  Then since $T$ is a Schreier set, we have
\begin{equation*}
1\cdot\phi_t=1\cdot\phi_{x_1{}^{\eps_1}}\dotsm\phi_{x_n{}^{\eps_n}}=x_1{}^{\eps_1}\dotsm x_n{}^{\eps_n}=t.
\end{equation*}
%So $T$ acts transitively on itself under $\phi$.
Now define
\begin{equation*}
J=\{f\colon f\in F\land 1\cdot\phi_f=1\},
\end{equation*}
the stabilizer of $1$ in $F$.  Then
\begin{equation*}
F=JT,
\end{equation*}
since if $1\cdot\phi_f=t$, then $ft\inv\in J$ and $f=ft\inv t$.  Moreover, if $f,g\in J$ and $s,t\in T$, and $fs=gt$, then
\begin{equation*}
s=1\cdot\phi_{fs}=1\cdot\phi_{gt}=t,
\end{equation*}
so $s=t$ and then $f=g$.  
Therefore $T$ is a complete set of right-coset representatives of $J$ in $F$.  Hence it is a Schreier transversal with respect to $X$ and $J$.  Moreover, if $1\cdot\phi_f=s$, then $1\cdot\phi_{fs\inv}=1$, so $fs\inv\in J$ and therefore
\begin{equation*}
Jf=Js.
\end{equation*}
That is, the representative of $Jf$ in $T$ is $1\cdot\phi_f$.
Hence, by Theorem~\ref{thm:delta}, $J$ is generated by the $sx\cdot(1\cdot\phi_{sx})\inv$ such that $(s,x)\in T\times X$; it is freely generated by an appropriate subset, by Theorem~\ref{thm:sub-free}.  Finally,
\begin{equation*}
1\cdot\phi_{sx}=1\cdot\phi_s\cdot\phi_x=s\cdot\phi_x=\corep{sx}.
\end{equation*}
So $J$ is freely generated by certain $sx\cdot(\corep{sx})\inv$, that is, $\delta(s,x)$.  Those generators that are not in $Y$ generate the desired subgroup $K$; indeed, we have then $J=H*K$, and the index of $J$ in $F$ is the size of $T$.
\end{proof}

As a partial converse, we have that,
if $F$ is finitely generated, and $H*K$ is a subgroup of $F$ of finite index, then $H*K$ is finitely generated by the corollary to Theorem~\ref{thm:delta}, and therefore $H$ (and $K$) must be finitely generated.  We also have:

\begin{corollary}
If $H$ is finitely generated \emph{normal} subgroup of $F$, then either $H$ is trivial or $H$ has finite index in $F$.
\end{corollary}

A group is \textbf{residually finite} if the intersection of all of its subgroups of finite index is trivial: that is, every nontrivial element lies outside some subgroup of finite index.

\begin{theorem}[F.W. Levi]
Free groups are residually finite.
\end{theorem}

\begin{proof}
Let $f\in F\setminus\gpgen1$.  By Theorem~\ref{thm:fp}, there is a subset $X$ of $F$ such that $\gpgen f*\gpgen X$ is a subgroup $H$ of $F$ of finite index.  Then
\begin{equation*}
f\notin\gpgen{f^2,X,H'},
\end{equation*}
and this group has index $2$ in $H$, since $H/H'$ is (isomorphic to)
the free \emph{abelian} group generated by $\{f\}\cup X$. 
\end{proof}

A group $G$ is \textbf{Hopfian} its its quotient by a nontrivial
normal subgroup is never isomorphic to $G$.  For
Theorem~\ref{thm:hopf} below, we need: 

\begin{lemma}\label{lem:fin}
A finitely generated group has only finitely many subgroups of a given
finite index. 
\end{lemma}

\begin{proof}
Supposing $G$ is generated by a set of size $m$, we consider subgroups
of index $n$.  Let $H$ be such.  We can embed $G$ in $\Sym{G/H}$ by
sending $g$ to $xH\mapsto gxH$.  There is a bijection from $G/H$ to
$\{0,\dots,n-1\}$, that is, to $n$ in the von-Neumann definition, that
takes $H$ to $0$.  This bijection induces an isomorphism from
$\Sym{G/H}$ to $\Sym n$.  Composing, we have an embedding of $G$ in
$\Sym n$; that is, we have an action of $G$ on $n$.  Moreover, the
stabilizer of $0$ under this action is just $H$; so $H$ is recovered
from the embedding. 

The number of embeddings of $G$ in $\Sym n$ is at most
\begin{equation*}
(n!)^m.
\end{equation*}
Therefore this is an upper bound on the number of subgroups $H$ of $G$.
\end{proof}

The foregoing proof uses the Axiom of Choice.  Indeed, let $A$ be the set of subgroups of $G$ of index $n$, and let $B$ be the set of embeddings of $G$ in $\Sym n$.  Then the proof uses an embedding of $A$ in $B$ that requires, for each $H$ in $A$, the choice of a bijection from $G/H$ to $n$.  

It might appear that we could argue as follows.  Suppose it is known that $A$ has an \emph{ordinal} cardinality $\kappa$.  (Such would be the case if $A$ were already known to be finite.)  For each $H$ in $A$, the set of bijections from $G/H$ to $n$ has cardinality $n!$.  The set $\kappa\times(n!)$ has an ordinal cardinality, which is either a finite number or $\kappa$.  So the set can be well-ordered, and therefore it might appear that we can obtain an embedding of $A$ in $B$ as desired.  However, the set that we want to well-order is the set $C$ comprising all bijections from $G/H$ to $n$ for all $H$ in $A$.  Without the Axiom of Choice, we do not have a bijection from $C$ to $\kappa\times(n!)$.

The solution is, given $H$ in $A$, to let $B_H$ comprise those elements of $B$ under which the stabilizer of $0$ is $H$.  We have proved that each $B_H$ is nonempty; so the function $H\mapsto B_H$ establishes our claim with use of the Axiom of Choice.

It is of interest that the proof of Theorem~\ref{thm:sub-free} \emph{does} (apparently) require the Axiom of Choice (because Lemma~\ref{lem:Schreier} requires it).  Because of this, for a given subgroup of a free group, it may be impossible to \emph{exhibit} a set that freely generates the subgroup (just as it is impossible to exhibit, say, a well-ordering of the set of real numbers).

\begin{theorem}[Mal'cev]\label{thm:hopf}
A finitely generated residually finite group is Hopfian.  In particular, a finitely generated free group is Hopfian.
\end{theorem}

\begin{proof}
Suppose $G$ is finitely generated and residually finite.  Say $N$ is a normal subgroup of $G$, and
\begin{equation*}
G\cong G/N.
\end{equation*}
The isomorphism sends a subgroup $H$ of $G$ to a subgroup of $G/N$, and the latter subgroup must have the form $H^*/N$ for some subgroup $H^*$ of $G$ such that
\begin{equation*}
N\sg H^*\sg G.
\end{equation*}
We have
\begin{equation*}
[G:H]=[G:H^*].
\end{equation*}
If this index is required to be a certain finite number, then, by Lemma~\ref{lem:fin}, there are only finitely many possibilities for $H$, and then the map $H\mapsto H^*$ is just a permutation of those possibilities.  This shows $N$ is a subgroup of every subgroup of $G$ of finite index.  Therefore $N$ is trivial.
\end{proof}

\begin{theorem}[Nielsen]\label{thm:Nielsen}
If $F$ is free of rank $n$, and $X$ generates $F$ and has size $n$, then $X$ freely generates $F$.
\end{theorem}

\begin{proof}
Suppose $F$ is freely generated by $Y$.  Extend a bijection from $Y$ to $X$ to an endomorphism $\phi$ of $F$.  Then $\phi$ must be surjective (since $X$ generates $F$), so
\begin{equation*}
F/\ker{\phi}\cong F.
\end{equation*}
By Theorem~\ref{thm:hopf}, $\ker{\phi}$ must be trivial, so $\phi$ is an automorphism of $F$.  In particular, since $Y$ freely generates $F$, so does $X$.
\end{proof}

\chapter{Groups acting on trees}

Considering $3$ under the von-Neumann definition whereby it is the set $\{0,1,2\}$, let $X$ consist of the finite sequences of elements of $3$.  That is, $X$ contains, for each $n$ in $\vnn$, the $n$-tuples
\begin{equation*}
(x_0,\dots,x_{n-1}),
\end{equation*}
where $x_i\in 3$.  If $n=0$, the only such tuple is the empty set.  In general, strictly, the $n$-tuple above is the set
\begin{equation*}
\{(0,x_0),\dots,(n-1,x_{n-1})\}
\end{equation*}
(where now $(s,t)$ stands for $\{\{s\},\{s,t\}\}$; but we do not need this).  Then $X$ is (partially) ordered by inclusion, so that we have
\begin{equation*}
(y_0,\dots,y_{m-1})\leq(x_0,\dots,x_{n-1})
\end{equation*}
if and only if $m\leq n$ and $(y_0,\dots,y_{m-1})=(x_0,\dots,x_{m-1})$.  In particular, as a (partially) ordered set, $X$ is a \emph{tree,} the lower levels of which can be depicted as in Figure~\ref{fig:tree}.
\begin{figure}[t]
\centering                           
\pstree[treemode=R,treesep=0ex]
{\TR{$(\ )$}}
{\pstree{\TR{$(0)$}}
        {\pstree{\TR{$(0,0)$}}
                {\TR{$(0,0,0)$}
                 \TR{$(0,0,1)$}
                 \TR{$(0,0,2)$}}
         \pstree{\TR{$(0,1)$}}
                {\TR{$(0,1,0)$}
                 \TR{$(0,1,1)$}
                 \TR{$(0,1,2)$}}
         \pstree{\TR{$(0,2)$}}
                {\TR{$(0,2,0)$}
                 \TR{$(0,2,1)$}
                 \TR{$(0,2,2)$}}}
 \pstree{\TR{$(1)$}}
        {\pstree{\TR{$(1,0)$}}
                {\TR{$(1,0,0)$}
                 \TR{$(1,0,1)$}
                 \TR{$(1,0,2)$}}
         \pstree{\TR{$(1,1)$}}
                {\TR{$(1,1,0)$}
                 \TR{$(1,1,1)$}
                 \TR{$(1,1,2)$}}
         \pstree{\TR{$(1,2)$}}
                {\TR{$(1,2,0)$}
                 \TR{$(1,2,1)$}
                 \TR{$(1,2,2)$}}}
 \pstree{\TR{$(2)$}}
        {\pstree{\TR{$(2,0)$}}
                {\TR{$(2,0,0)$}
                 \TR{$(2,0,1)$}
                 \TR{$(2,0,2)$}}
         \pstree{\TR{$(2,1)$}}
                {\TR{$(2,1,0)$}
                 \TR{$(2,1,1)$}
                 \TR{$(2,1,2)$}}
         \pstree{\TR{$(2,2)$}}
                {\TR{$(2,2,0)$}
                 \TR{$(2,2,1)$}
                 \TR{$(2,2,2)$}}}
}
\caption{A ternary tree}\label{fig:tree}
\end{figure}

Now let $\mathfrak S$ be the group of automorphisms of $X$ as a
(partially) ordered set.\footnote{Here $\mathfrak S$ is a German
  letter \emph{S,} obtained in \AmS-\LaTeX\ with 
\url{\mathfrak{S}}.  From \url{\mathfrak{G}} one gets $\mathfrak G$.
See Appendix~\ref{app:german}, p.~\pageref{app:german}.}  
We shall define $\alpha$ and $\tau$ in $\mathfrak S$ so that $\gpgen{\alpha,\tau}$ is an infinite $3$-group.
The definition of $\tau$ is easy: it is given by
\begin{equation*}
\tau(x_0,\dots,x_n)=(x_0+1,\dots,x_n),
\end{equation*}
where the addition is \emph{modulo} $3$.  Then
\begin{equation*}
\tau^3=1,
\end{equation*}
and $\tau$ permutes the (set of) the subtrees $\{x\colon(i)\leq x\}$.

To define $\alpha$, we introduce the following notation.  If $x$ is an $n$-tuple $(x_0,\dots,x_{n-1})$ in $X$, and $i\in3$, then by $i\cdot x$ we mean the $(n+1)$-tuple $(i,x_0,\dots,x_{n-1})$ in $X$.  So $\tau$ permutes the (set of) subtrees $\{i\cdot x\colon x\in X\}$.  If also $\beta\in\mathfrak S$, we define an element $\beta_i$ of $\mathfrak S$ by requiring
\begin{equation*}
\beta_i(i\cdot x)=i\cdot\beta(x),
\end{equation*}
but $\beta_i(x)=x$ if $x_i\neq i$.  Now we define
\begin{equation*}
\alpha=\tau_0\circ\tau_1{}^2\circ\alpha_2.
\end{equation*}
This is a recursive definition in the lengths of the arguments: $\alpha(\emptyset)=\emptyset$ of course, and then
\begin{align*}
\alpha(0\cdot x)&=0\cdot\tau(x),\\
\alpha(1\cdot x)&=1\cdot\tau^2(x),\\
\alpha(2\cdot x)&=2\cdot\alpha(x).
\end{align*}
By induction on those lengths,
\begin{equation*}
\alpha^3=1.
\end{equation*}
Let
\begin{equation*}
G=\gpgen{\alpha,\tau}.
\end{equation*}

\begin{theorem}[Grigorchuk, Gupta--Sidki]
$G$ is an infinite $3$-group.
\end{theorem}

\begin{proof}
We first show $G$ is infinite.  To this end, let
\begin{equation*}
H=\gpgen{\alpha,\alpha^{\tau},\alpha^{\tau^2}}.
\end{equation*}
This is a normal subgroup of $G$.  We shall show that $H$ has a quotient (by a nontrivial subgroup) that is isomorphic to $G$.

For each $i$ in $3$, the group $\mathfrak S$ has a subgroup $\mathfrak S_i$, comprising those $\sigma$ such that
\begin{equation*}
\sigma(j\cdot x)=j\cdot x
\end{equation*}
if $j\in3\setminus\{i\}$.  Then the subgroup $\gpgen{\mathfrak S_0,\mathfrak S_1,\mathfrak S_2}$ is an internal direct product,
\begin{equation*}
\mathfrak S_0\times\mathfrak S_1\times\mathfrak S_2.
\end{equation*}
Also, $G$ is a subgroup of this.  A typical element of the direct product is $(\pi_0,\rho_1,\sigma_2)$ for some $\pi$, $\rho$, and $\sigma$ in $\mathfrak S$.  We consider $H$ under the projection
\begin{equation*}
(\pi_0,\rho_1,\sigma_2)\mapsto\pi_0.
\end{equation*}
Conjugation in the direct product by $\tau$ is a kind of permutation of coordinates:
we have
\begin{gather*}
	(\pi_0,\rho_1,\sigma_2)^{\tau}=(\rho_0,\sigma_1,\pi_2),\\
	(\pi_0,\rho_1,\sigma_2)^{\tau^2}=(\sigma_0,\pi_1,\rho_2).
\end{gather*}
Therefore
\begin{equation*}
H=\gpgen{(\tau_0,\tau_1{}^2,\alpha_2), (\tau_0{}^2,\alpha_1,\tau_2),(\alpha_0,\tau_1,\tau_2{}^2)},
\end{equation*}
so the image of $H$ in $\mathfrak S_0$ is just
\begin{equation*}
\gpgen{\alpha_0,\tau_0},
\end{equation*}
which is isomorphic to $G$.  Since the kernel of the projection of $H$ onto this is nontrivial, it follows that $G$ is infinite.

Now we show that $G$ is a $3$-group, that is, every element has order a (finite) power of $3$.  Since $\gpgen{H\cup\{\tau\}}=G$, it is enough to establish the claim for elements of $H$.  An arbitrary element $\beta$ of this can be written as
\begin{equation*}
\alpha^{\tau^{\eps_0}}\circ\dotsb\circ\alpha^{\tau^{\eps_{n-1}}}\circ\tau^{\eps_n}
\end{equation*}
for some $\eps_i$ in $3$ and some minimal $n$ in $\vnn$.  Then $n$ can be called the \textbf{length} of the element.  In $\beta^3$, the factors that are powers of $\tau$ can be eliminated.  In particular,
if the $\eps_i$ are the same for all $i$ in $n$, then $\beta^3=1$.  If
they are not all the same, consider the image of $\beta$ under the
projection onto $\mathfrak S_0$.  This image will be a composition of
$n+1$ powers of $\alpha_0$ and $\tau_0$; but at least two of these are
powers of $\tau_0$; these two can be combined, and so the length of
the image is less than $n$.  By induction then, the order of every
element of $H$ (and therefore of $G$) is a power of $3$. 
\end{proof}

\chapter{The Burnside problem}

\begin{question}[Burnside, 1902]
Is there an infinite, finitely generated:
\begin{enumerate}[1)]
\item
torsion group?
\item
group of bounded exponent?
\end{enumerate}
\end{question}

\begin{theorem}[Godod, 1964]
There is an infinite $3$-generated $p$-group for every prime $p$.
\end{theorem}

\begin{theorem}[Aleshin, 1972]
There is an infinite $2$-generated $p$-group for every prime $p$.
\end{theorem}

The proof uses finite automata.

\begin{theorem}[Grigorchuk, 1980]
There is an infinite $3$-generated $2$-group of automorphisms of the regular $2$-tree.
\end{theorem}

\begin{theorem}[Gupta--Sidki]
There is an infinite $2$-generated $p$-group of automorphisms of the regular $p$-tree
for every odd primes $p$.
\end{theorem}

\begin{theorem}[Adian--Novikov, 1968]
There is an infinite $2$-generated group of \emph{odd} exponent $n$, whenever $n\geq4381$.
\end{theorem}

The question of whether there is an infinite $2$-generated group of exponent $5$ is open.

\begin{theorem}[Ivanov]
There is an infinite $2$-generated group of exponent $2^{48}$.
\end{theorem}

\chapter{Limit groups}

The reference now is 
\begin{quote}
Champetier and Guirardel, `Limit groups as limits of free groups:
compactifying the set of free groups', February 1, 2008.   
\end{quote}

We aim to show that limit groups are models of the universal theory of
free groups. 

Our signature $\sig$ is $\{1,{}\inv,{}\cdot{}\}$, and $n$ and $m$
range over $\vnn$.  When $X$ is a set, then $F_X$ is a free group on
$X$.  Also 
\begin{equation*}
F_n=F_{\{x_0,\dots,x_{n-1}\}}
\end{equation*}
(a free group on $n$ generators).

\begin{question}[Tarski, 1945]
Have we
\begin{equation*}
F_n\equiv F_m
\end{equation*}
when $n$ and $m$ are greater than $1$?
\end{question}

\begin{theorem}[Sela, Kharlampovich--Myasnikov, 2006]
Yes.
\end{theorem}

%Let $\Tfg$ be the theory of nonabelian free groups.  Since

The theory of nonabelian free groups interprets $\Z$ (as a group: it is the centralizer of a nontrivial element of a model), so the theory does not have finite Morley rank.  It does not have infinite Morley rank either, nor $U$-rank.  However, Sela showed that it is stable.

To solve Tarski's problem, we take an $\sig$-sentence $\sigma$ and show $F_n\models\sigma$ if and only if $F_m\models\sigma$.  What can $\sigma$ look like?  The $\sig$-terms are \textbf{words.}  So $\sigma$ has the form
\begin{equation*}
\Forall{\tuple x}\Exists{\tuple y}\Forall{\tuple z}\cdots\bigvee_i\bigwedge_j\bigl(w_{ij}(\tuple x,\tuple y,\tuple z,\dots)=1\bigr)^{\eps_{ij}}
\end{equation*}
where $\phi^{\eps_{ij}}$ is either $\phi$ or $\lnot\phi$.
The first step is to look at very simple $\sigma$:
\begin{equation*}
\Forall{\tuple x}\bigwedge_jw_j(\tuple x)=1,
\end{equation*}
a \emph{[positive] universal sentence;} here $w_j(\tuple x)=1$ is a \textbf{word equation.}

For the moment, let $\sig$ be arbitrary, and let $\str M$ and $\str N$ be $\sig$-structures.  A \textbf{universal $\sig$-sentence} is one of the form
\begin{equation*}
\Forall{\tuple x}\psi(\tuple x),
\end{equation*}
where $\psi$ is quantifier-free.  For the set of universal $\sig$-sentences that are true in $\str M$, we may write\footnote{Our authors use $\Univ{\str M}$.}
\begin{equation*}
\Th{\str M}_{\forall}.
\end{equation*}
If $\str M$ embeds in $\str N$ (in particular, if $\str M\included\str N$), then
\begin{equation*}
\Th{\str N}_{\forall}\included\Th{\str M}_{\forall}.
\end{equation*}

\begin{fact}
$\Th{F_n}_{\forall}=\Th{F_m}_{\forall}$.
\end{fact}

\begin{proof}
$F_n$ embeds in $F_2$, considered as $F_{\{x,y\}}$, under $x_k\mapsto x^{y^k}$.
\end{proof}

Let $G$ be a group, and let $\phi(\tuple x)$ be the formula
\begin{equation*}
\bigwedge_{i<m}w_i(\tuple x)=1.
\end{equation*}
We may write $\phi^G$ for the set of solutions of $\phi$ in $G$:
\begin{equation*}
\phi^G=\{\tuple a\colon G\models\phi(\tuple a)\}.
\end{equation*}
Let $E$ be the finitely presented group
\begin{equation*}
\gppres{\tuple x}{w_0,\dots,w_{m-1}},
%\gpgen{\tuple x\mathpunct{\mid} w_0,\dots,w_{m-1}},
\end{equation*}
which is a quotient $F_n/N$.

\begin{fact}
There is a natural bijection between $\phi^G$ and $\Hom{E,G}$.
\end{fact}

\begin{proof}
If  $\alpha\colon E\to G$, let
\begin{equation*}
\tuple a=(\alpha(x_0N),\dots,\alpha(x_{n-1}N)).
\end{equation*}
Then
\begin{equation*}
w_i(\tuple a)=\alpha(w_i(x_0N,\dots,x_{n-1}N))=\alpha(w_i(\tuple x)N)=\alpha(N)=1,
\end{equation*}
so $\tuple a\in\phi^G$.  For the other way around, if $\tuple a\in\phi^G$, define $\beta$ from $F_n$ to $G$ by
\begin{equation*}
\beta(x_i)=a_i.
\end{equation*}
Since $w_i(\tuple a)=1$ for all $i$, the homomorphism $\beta$ factors through $N$, giving an element $\alpha$ of $\Hom{E,G}$ such that $\alpha(x_iN)=a_i$.
\end{proof}

The foregoing is an instance of a general fact of universal algebra:

\begin{example}
If $K$ is a commutative unital ring (such as a field), and $F_i\in K[X_0,\dots,X_{n-1}]$, and $R$ is a $K$-algebra, then there is a bijection between
\begin{equation*}
\{\tuple a\colon\tuple a\in R^n\land\bigwedge_{i<m}F_i(\tuple a)=0\}
\end{equation*}
and
\begin{equation*}
\Hom[K]{K[\tuple X]/(F_0,\dots,F_{m-1}),R}.
\end{equation*}
\end{example}

The group $E$ has a distinguished sequence of generators, namely 
\begin{equation*}
(x_0N,\dots,x_{n-1}N),  
\end{equation*}
which we may denote by $(s_0,\dots,s_{n-1})$.
Therefore $(E,\tuple s)$ is called a \emph{marked group.}  In general, a \textbf{marked group} is the expansion of a group to a signature $\sig(\tuple s)$, where $\tuple s$ is a finite sequence of new constants, and the interpretations of these constants in the expanded group \emph{generate} the group.

\begin{example}
In $\Sym 3$, if $\sigma=(0\;1)$ and $\tau=(0\;1\;2)$, then the two marked groups
\begin{align*}
&(\Sym3,\sigma,\tau),&&(\Sym3,\tau,\sigma)
\end{align*}
are non-isomorphic as such.
\end{example}

If $\alpha\in\Hom{E,F_m}$, then we have a diagram thus:
\begin{equation*}
\xymatrix{
E\ar@{->>}[r]&\alpha(E)\ar@{<->}[d]^{\cong}\ar[r]^{\leq}&F_m\\
             &F_k                                       &
             }
\end{equation*}
We therefore restrict our attention to epimorphisms. 
We consider all pairs $(\alpha,G)$, where $\alpha$ is a homomorphism on $E$, and $G$ is its image.  We may denote this pair by
\begin{equation*}
E\overset{\alpha}{\epim}G
\end{equation*}
(or just by $E\epim G$ if the name of the epimorphism is unimportant).
We define
\begin{equation*}
(E\overset{\alpha_0}{\epim} G_0)\cong(E\overset{\alpha_1}{\epim} G_1)
\end{equation*}
if there is a group-isomorphism $\beta$ from $G_0$ to $G_1$ such that the diagram
\begin{equation*}
\xymatrix{
E\ar@{->>}_{\alpha_1}[dr]\ar@{->>}^{\alpha_0}[r]&G_0\ar@{->>}^{\beta}[d]\\
&G_1
}
\end{equation*}
commutes.
If $\tuple s$ is a generating sequence of $E$, and $\alpha\colon E\epim G$, then $G$ is marked by $\alpha(\tuple s)$.  The following are equivalent conditions on
$E\overset{\alpha_0}{\epim}G_0$
and 
$E\overset{\alpha_1}{\epim}G_1$.
\begin{enumerate}
\item
$(E\overset{\alpha_0}{\epim}G_0)\cong(E\overset{\alpha_1}{\epim}G_1)$.
\item
$(G_0,\alpha_0(\tuple s))\cong(G_1,\alpha_1(\tuple s))$.
\item
$\ker(\alpha_0)=\ker(\alpha_1)$.
\end{enumerate}
The point is to study the set $\isoc E$\label{isoc} of all
isomorphism-classes of $E\epim G$.  This set corresponds to the set of
normal subgroups of $E$.  We want to understand the `closure' in
$\isoc E$ of the set of epimorphisms $E\epim F_m$, where $m\geq2$. 

A logical or model-theoretic way to do this is to understand $\isoc E$
as the set of all complete quantifier-free $n$-types of $\sig$ that
contain the equations $w_i=1$ along with all equations that hold
universally in groups.  Or we can replace the variables $x_i$ with
constants $s_i$; then $\isoc E$ consists of the quantifier-free
theories in $\sig(\tuple s)$ of quotients of $E$.  See
Appendix~\ref{app:Stone}, page~\pageref{app:Stone}.  Otherwise, we can
proceed as follows.  

\begin{step}
On $E$ there is a \textbf{word metric,} in which the distance between
two elements is the length of the shortest path between them in the
\emph{Cayley graph} of $(E,\tuple s)$.  For present purposes, the
\textbf{Cayley graph} is a graph whose nodes are the
group-elements, and where an edge is drawn between $g$ and $h$ if
$g\inv h$ or $h\inv g$ is one of the given generators $s_i$.  

There is also
a more elaborate version of the Cayley graph: a \emph{labelled, directed}
  graph, where again the nodes are the group-elements, and now an arrow is drawn
  from $g$ to $h$, and is labelled as $g\inv h$, if this last
  group-element is one of the given generators.
\end{step}

\begin{example}
The two Cayley graphs of $(\Zmod6,2,3)$ are as in Figure~\ref{fig:6}.
\begin{figure}[t]
\begin{align*}
&\xymatrix{
4\ar@{-}[dd]\ar@{-}[rrr]&                      &            &1\ar@{-}[dd]\\
                        &2\ar@{-}[ul]\ar@{-}[r]&5\ar@{-}[ur]&            \\
0\ar@{-}[ur]\ar@{-}[rrr]&                      &            &3\ar@{-}[ul]
        }&
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
&\xymatrix{
4\ar[dd]|2\ar@/^/[rrr]|3&&&1\ar[dd]|2\ar@/^/[lll]|3\\
&2\ar[ul]|2\ar@/^/[r]|3&5\ar[ur]|2\ar@/^/[l]|3&\\
0\ar[ur]|2\ar@/^/[rrr]|3&&&3\ar[ul]|2\ar@/^/[lll]|3
        }
\end{align*}
\caption{Cayley graph of $(\Zmod6,2,3)$}\label{fig:6}
\end{figure}
\end{example}

\begin{step}
If $(X,x,\mathrm d)$ is a pointed metric space, the \textbf{pointed
  Gromov--Hausdorff metric} on $\pow X$ is defined as follows.  
  If $r$ is a non-negative real number,
  two
subsets $C$ and $D$ of $X$ are called \textbf{$r$-close} if 
\begin{equation*}
C\cap\ball{x,r}=D\cap\ball{x,r},
\end{equation*}
where $\ball{x,r}$ is the open ball about $x$ of radius $r$;
in this case we may write
\begin{equation*}
C\sim_rD.
\end{equation*}
Then we can define $\dist(C,D)$ as $\me^{-R}$, where $R$ is the supremum of the set of
$r$ such that $C\sim_rD$.  Such a supremum will in fact be a maximum (unless it is $\infty$, that is, $C=D$).  This metric is \textbf{ultrametric,} that
is, 
\begin{equation*}
\dist(C,E)\leq\max\bigl(\dist(C,D),\dist(D,E)\bigr).
\end{equation*}
Regardless of the metric, there is already a topology on $\pow X$, the
\textbf{Tychonoff topology:}  This has a basis consisting of the sets
$U_{A,B}$, where $A$ and $B$ are finite disjoint subsets of $X$, and
for all subsets $Y$ of $X$,
\begin{equation*}
  Y\in U_{A,B}\liff A\included Y\land B\cap Y=\emptyset.
\end{equation*}
The sets $U_{A,B}$ are both closed and open.
The Tychonoff topology corresponds to the product topology on $2^X$ when $2$---that is, $\{0,1\}$---is given the discrete topology.

\begin{fact}
The Gromov--Hausdorff topology on $\pow X$ is finer than, or the same as, the
Tychonoff topology.
If all balls around $x$ are finite in the metric on $X$, then the two
topologies are the same.
\end{fact}

\begin{proof}
Suppose $A$ and $B$ are arbitrary finite disjoint subsets of
$X$.  Then the set $\{\dist(x,y)\colon y\in A\cup B\}$ has an upper
bound.  Let $r$ be a strict upper bound.  Then for every element $C$
of $\pow X$, every element of $\ball{C,\me^{-r}}$ contains just the
points of $A\cup B$ that $C$ does.  Therefore
\begin{equation*}
  U_{A,B}=\bigcup_{A\included C\included X\setminus B}\ball{C,\me^{-r}}.
\end{equation*}
Thus the Gromov--Hausdorff topology is at least as fine as the
Tychonoff topology. 

We have generally in the former topology
\begin{align*}
  \ball{C,\me^{-r}}
&=\bigcap_{r<s}\{D\colon C\sim_sD\}\\
&=\bigcap_{r<s}\{D\colon\ball{x,s}\cap C=\ball{x,s}\cap D\}.
\end{align*}
Now suppose each open ball $\ball{x,s}$ in $X$ is finite.  Then
\begin{equation*}
\inf\{\dist(x,y)\colon y\notin\ball{x,r}\}>r.
\end{equation*}
Let $s$ be the infimum (which is a minimum).  Then
\begin{equation*}
  \ball{C,\me^{-r}}=\{D\colon\ball{x,s}\cap C=\ball{x,s}\cap D\}.
\end{equation*}
But we may also let
  \begin{align*}
    A&=\ball{x,s}\cap C,&
    B&=\ball{x,s}\setminus C,
  \end{align*}
  both finite sets.  Then
  \begin{equation*}
\ball{C,\me^{-r}}=U_{A,B}.\qedhere
\end{equation*}
\end{proof}

In\label{GHE} particular, when $X$ is the Cayley graph of $(E,\tuple s)$
with the word metric, and $x$ is $1$, then the Tychonoff and the
Gromov--Hausdorff topologies coincide.  

[This shows that the
  Gromov--Hausdorff topology on $\isoc E$ is independent of the
  choice of $\tuple s$.
  
  [If not all balls around $x$ in $X$ are finite, then the
    Gromov--Hausdorff topology on $\pow X$ may be strictly finer than
    the Tychonoff topology.  For example, if we give $X$ the discrete
    metric, then the Gromov--Hausforff topology on $\pow X$ is also
    discrete, so it is different from the Tychonoff topology unless
    $X$ is itself finite.

[If $X$ is countable, then every bijection with the set of positive
  integers induces a metric on $X$, hence a topology on $\pow X$; and
  the topology is independent of the choice of bijection.]  
\end{step}

\begin{step}
$\isoc E$, considered as the set of normal subgroups of $E$, is closed
  in $\pow E$, hence compact. 
\end{step}

\begin{proof}
Let $A\in\pow E\setminus\isoc E$.
\begin{enumerate}[{Case} 1.]\setcounter{enumi}0
\item
If $A=\emptyset$, then
\begin{equation*}
  A\in U_{\emptyset,\{1\}},
\end{equation*}
and no elements of this set are groups.
\item
If $A$ is neither empty nor a subgroup of $E$, then it contains some
$a$ and $b$ such that it does not contain $ab\inv$.  Then
\begin{equation*}
  A\in U_{\{a,b\},\{ab\inv\}},
\end{equation*}
and no elements of this set are groups.
\item
If $A$ is a subgroup of $E$, but not a normal subgroup, then it
contains some $a$, but not $a^g$, for some $g$ in $E$.  Then
\begin{equation*}
  A\in U_{\{a\},\{a^g\}},
\end{equation*}
and no elements of this set are normal subgroups of $E$.\qedhere 
\end{enumerate}
\end{proof}

\begin{question}
How does $\isoc E$ change with $E$?  
\end{question}

Each element of $E$ is $w(\tuple s)$ for some $w$ in $F_n$.  For each element $g$ of $E$, and for each normal subgroup $N$ of $G$, we have
\begin{equation*}
g\in N\quad\text{ if and only if }\quad G/N\models g=1.
\end{equation*}
More generally, if $A$ and $B$ are disjoint finite subsets of $E$, let $\sigma$ be the sentence
\begin{equation*}
\bigwedge_{g\in A}g=1\land\bigwedge_{h\in B}h\neq1.
\end{equation*}
Then
\begin{equation*}
N\in U_{A,B}\quad\text{ if and only if }\quad G/N\models\sigma.
\end{equation*}
Using the notation of Appendix~\ref{app:Stone}, we may write $U_{A,B}$ as
\begin{equation*}
[\sigma].
\end{equation*}
A sequence $\bigl((G_m,\tuple s_m)\colon m\in\vnn\bigr)$ of marked
groups whose isomorphism-classes are in $\isoc E$ converges to
$(G,\tuple s)$ if and only if, for each word $w$ in $F_n$, there is
some $M$ in $\vnn$ such that, for all $m$ in $\vnn$, if $m\geq M$,
then 
\begin{equation*}
  G_m\models w(\tuple s_m)=1\quad\text{ if and only if }\quad G\models
  w(\tuple s)=1. 
\end{equation*}


\begin{example}\mbox{}
  \begin{asparaenum}
    \item
$\lim_{m\to\infty}\gppres{\tuple x}{r_0,\dots,r_{m-1}}=
\gppres{\tuple x}{r_0,r_1,\dots}$.
\item
$\lim_{m\to\infty}(\Zmod m,1)=(\Z,1)$.
\item
$\lim_{m\to\infty}(\Z,1,m)=\bigl(\Z^2,(1,0),(0,1)\bigr)$.
  \end{asparaenum}
\end{example}

If $\alpha\colon E'\epim E$, this induces an embedding $\alpha^*$ of
$\isoc E$ in $\isoc{E'}$, where 
\begin{equation*}
\alpha^*(N)=\alpha\inv[N].
\end{equation*}

[The following is Lemma 2.2 of the paper; the proof there is left as an exercise.  Examples like the foregoing are given \emph{after} the lemma, but it seems better to put them before, as the proof of Lemma 2.2 can use convergent sequences.]

\begin{fact}
Consider $\alpha$ as an epimorphism of marked groups.
\begin{enumerate}
\item
$\alpha^*$ is a hom\oe omorphism onto its image.
\item
$\alpha^*$ is open if and only if $\ker(\alpha)$ is finitely generated
  as a normal subgroup. 
\end{enumerate}
\end{fact}

\begin{proof}
Since $\alpha$ is surjective, $\alpha^*$ is injective.  The Cayley graph of $(E,\tuple s)$ results from identifying two nodes $g$ and $g_1$ of $(E',\tuple s')$ if $\alpha(g)=\alpha(g')$: therefore, for all $g$ and $h$ in $E'$, there are $g_1$ and $h_1$ in $E'$ such that
\begin{align*}
\alpha(g)&=\alpha(g_1),&\alpha(h)&=\alpha(h_1),&
\dist(\alpha(g),\alpha(h))=\dist(g_1,h_1).
\end{align*}
Thus $\alpha^*$ is in fact an isometry.

If $\ker(\alpha)$ is infinitely generated as a normal subgroup, it is the limit of a strictly increasing sequence of normal subgroups; then none of these normal subgroups are in $\alpha^*[\isoc E]$, although $\ker{\alpha}$ itself is; so $\alpha^*[\isoc E]$ is not open.

Suppose now $\ker(\alpha)$ \emph{is} finitely generated as a normal subgroup of $E'$.
Let $(N_k\colon k\in\vnn)$ be a sequence of elements of $\isoc{E'}$ that converges to an element of $\alpha^*[\isoc E]$.
Every normal subgroup $N$ of $E'$ is determined by $\alpha[N]$ and $\ker(\alpha)\cap N$, and if the latter is just $\ker(\alpha)$ itself, then $N\in\alpha^*[\isoc E]$.  The sequence $(\ker(\alpha)\cap N_k\colon k\in\vnn)$ converges to $\ker(\alpha)$.  Therefore, if $k$ is large enough, then $N_k$ contains the generators of $\ker(\alpha)$, so it includes $\ker(\alpha)$ and is therefore in $\alpha^*[\isoc E]$.  Thus every point of this set is an interior point, so the set is open.
\end{proof}

Apply this to $F_n\overset{\pi}{\epim}E$: here $\pi^*$ is open if (and
only if) $E$ is finitely presented.  So we might as well replace $\isoc
E$ with $\isoc{F_n}$. 

A marked group is a \textbf{limit group} if it is in the closure of
the set of all (marked) free groups in $\isoc{F_n}$, where $F_n$ has
the marking $(x_0,\dots,x_{n-1})$.  A group is a limit group if it has
a marking in which it is a limit group. 

The following is Proposition 5.2 of the article [but we can use it to
  understand the examples below, which are based on those given in
  \S2.6 of the paper]. 

\begin{proposition}
If $\sigma$ is a universal sentence of $\sig(\tuple s)$, then the set
of models of $\sigma$ in $\isoc{F_n}$ is a closed subset; if
existential, then open.
\end{proposition}

\begin{proof}
  Suppose $\sigma$ is $\Exists{\tuple v}\psi(\tuple v)$, where $\psi$ is quantifier-free, and $(G,\tuple
  s)\models\sigma$.  Then for some tuple $\tuple w$ of words,
  \begin{equation*}
    (G,\tuple s)\models\psi(\tuple w(\tuple s)),
  \end{equation*}
and every model of this sentence is a model of $\sigma$.  That is, in the notation of Appendix~\ref{app:Stone} as introduced above, we have
\begin{equation*}
  (G,\tuple s)\in[\psi(\tuple w(\tuple s))],
\end{equation*}
and the open set $[\psi(\tuple w(\tuple s))]$ is included in
the set of all models of $\sigma$ in $\isoc{F_n}$.
\end{proof}

\begin{example}
The sets of (marked) abelian, $k$-nilpotent, and $k$-soluble groups are
closed.  The set of abelian groups is also open, since it consists of
the groups satisfying
\begin{equation*}
  \bigwedge_{i,j}[s_i,s_j]=1.
\end{equation*}
Similarly, the set of $2$-nilpotent groups is open.  Indeed, a group is $2$-nilpotent if and only if its every element commutes with every element of the commutator subgroup.  It is enough to check this property at generators; therefore the (marked) $2$-nilpotent groups are those that satisfy
\begin{equation*}
  \bigwedge_{i,j,k}[[s_i,s_j],s_k]=1.
\end{equation*}
Similarly, the $k$-nilpotent groups are those satisfying
\begin{equation*}
\bigwedge_{i(0),\dots,i(k-1)}[[\dots[[s_{i(0)},s_{i(1)}],s_{i(2)}],\dots],s_{i(k-1)}].
\end{equation*}
But the $2$-soluble groups are those whose commutator subgroups are abelian, and it is not clear that the commutator subgroup is generated by the commutators \emph{of the generators,} that is, by the $[s_i,s_j]$; so we do not have that the set of marked $2$-soluble groups is open.
In fact it is \emph{not} open, provided one grants:
\begin{itemize}
\item
there are free objects in the category of finitely generated $2$-soluble groups;
\item
those free objects are infinitely presented groups.
\end{itemize}
Then there is a $2$-soluble group $G$, namely $\gppres{s_0,\dots,_{n-1}}{r_0,\dots}$, such that:
\begin{itemize}
\item
$G$ is not equal to $G_m$, namely $\gppres{s_0,\dots,_{n-1}}{r_0,\dots,r_{m-1}}$, for any $m$;
\item
every $2$-soluble group on $n$ generators is a quotient of $G$.
\end{itemize}
In particular, $G_m$ is not $2$-soluble; but $G$ is the limit of the $G_m$.
\end{example}

Having $k$-torsion is an existential property, so the set of groups with this property is open, and the set of torsion-free groups is closed.
In particular, limit groups are torsion-free.

The following is Proposition 5.3 of the paper.

\begin{theorem}
If $G$ is a finitely generated group, and $H$ is a group such that
\begin{equation*}
\Th H_{\forall}\included\Th G_{\forall},
\end{equation*}
then for any tuple $\tuple s$ that generates $G$, the marked group $(G,\tuple s)$ is a limit of marked subgroups of $H$.
\end{theorem}

\begin{proof}
Every open neighborhood of $(G,\tuple s)$ is $[\phi(\tuple s)]$ for some quantifier-free formula $\phi$ of $\sig$.  Then
\begin{align*}
(G,\tuple s)&\models\phi(\tuple s),&
G&\models\Exists{\tuple x}\phi(\tuple x),&
H&\models\Exists{\tuple x}\phi(\tuple x),
\end{align*}
so $H\models\phi(\tuple c)$ for some $\tuple c$.  Thus $[\phi(\tuple s)]$ contains $(\gpgen{\tuple c},\tuple c)$.
\end{proof}

This allows us to prove:

\begin{theorem}\label{thm:sub}
  For all finitely generated groups $G$, the following are equivalent.
  \begin{enumerate}
  \item 
$G$ is a limit group.
\item
$\Th{F_2}_{\forall}\included\Th G_{\forall}$.
\item
For any finite marking $\tuple s$ of $G$, the marked group $(G,\tuple
s)$ is a limit group.
  \end{enumerate}
\end{theorem}

\begin{proof}
  Trivially, $(\text3)\lto(\text1)$.

$(\text1)\lto(\text2)$.  Suppose $\sigma\in\Th{F_2}_{\forall}$ and $(G,\tuple
  s)$ is a limit group.  Let
  \begin{equation*}
    D=\{(H,\tuple s_H)\colon H\models\sigma\}.
  \end{equation*}
For any marking $\tuple s'$ of the same length as $\tuple s$, for any
$m$, $(F_m,\tuple s')\in D$ (since $F_m$ and $F_2$ have the same
universal theory).  Since $(G,\tuple s)$ is in the closure of such
marked free groups and $D$ is closed, we have $(G,\tuple s)\in D$.
Therefore $\sigma\in\Th G_{\forall}$.

$(\text2)\lto(\text3)$.  This is a special case of the last theorem.
\end{proof}

The following is Proposition 2.20---called `marked subgroups'---of the paper.

\begin{theorem}\label{thm:seq-sub}
Suppose the marked groups $(G_m,\tuple s_m)$ converge to $(G,\tuple s)$ in $\isoc{F_n}$, and $H$ is a subgroup of $G$ that is generated by $\tuple t$, which is $\tuple v(\tuple s)$ for some tuple $\tuple v$ of words from $F_n$.  Then the marked groups $(\gpgen{\tuple v(\tuple s_m)},\tuple v(\tuple s_m))$ converge to $(H,\tuple t)$.
\end{theorem}

\begin{proof}
Write $\tuple t_m$ for $\tuple v(\tuple s_m)$.
For all words $w$ in as many letters as the length of $\tuple t$, if $m$ is large enough, then the following are equivalent:
\begin{gather*}
(H,\tuple t)\models w(\tuple t)=1,\\
(G,\tuple t)\models w(\tuple t)=1,\\
(G,\tuple s)\models w(\tuple v(\tuple s))=1,\\
(G_m,\tuple s_m)\models w(\tuple v(\tuple s_m)=1,\\
(G_m,\tuple t_m)\models w(\tuple t_m)=1,\\
(\gpgen{\tuple t_m},\tuple t_m)\models w(\tuple t_m)=1.\qedhere
\end{gather*}
\end{proof}

As a special case, we obtain Proposition 3.1(4) of the paper:

\begin{theorem}\label{thm:sub-lim}
Every $2$-generated subgroup of a limit group is either a free group or a free abelian group, that is, it is isomorphic to one of
\begin{align*}
&\gpgen1,&
&\Z,&
&\Z\times\Z,&
&F_2.
\end{align*}
\end{theorem}

\begin{proof}
Let $H$ be a subgroup $\gpgen{a,b}$ of a limit group.  By the last theorem, $(H,a,b)$ is the limit of a sequence of marked free groups $(F_{n(m)},a_m,b_m)$ (where $n(m)\leq2)$.  Suppose $H$ is not free of rank $2$.  Then
\begin{equation*}
(H,a,b)\models w(a,b)=1
\end{equation*}
for some nontrivial word $w$.  Hence if $m$ is large enough, we have
\begin{equation*}
(F_{n(m)},a_m,b_m)\models w(a_m,b_m)=1.
\end{equation*}
By Theorem~\ref{thm:Nielsen} above, $F_{n(m)}$ must not be free of rank $2$; so $n(m)=1$, that is, $F_{n(m)}$ is isomorphic to $\Z$.  In particular, $[a_m,b_m]=1$, so $[a,b]=1$, that is, $H$ is abelian.  We have already observed that limit groups are torsion-free; in particular, $H$ is torsion-free.
\end{proof}

\begin{corollary}
If $G$ is a non-abelian limit group, then $F_2$ embeds in $G$.
\end{corollary}

Now we have what is Theorem 5.1 of the paper:

\begin{theorem}
Suppose $G$ is a finitely generated nonabelian group.  The following are equivalent.
\begin{enumerate}
\item
$G$ is a limit group.
\item
$\Th G_{\forall}=\Th{F_2}_{\forall}$.
\end{enumerate}
\end{theorem}

\begin{proof}
We have $(\text2)\lto(\text1)$ by Theorem~\ref{thm:sub} above.  If $G$ is a nonabelian limit group, then by the same theorem we have $\Th{F_2}_{\forall}\included\Th G_{\forall}$, and we have the reverse inclusion by the last corollary.
\end{proof}

For ultraproducts and \L o\'s's Theorem, see Appendix~\ref{app:Los}.  Given an infinite sequence of groups, we define the normal subgroup $N$ of the direct product as there.

\begin{theorem}
If a sequence of marked groups $(G_m,\tuple s_m)$ converges to $(G,\tuple s)$, then there is an embedding of $G$
in the ultraproduct $\prod_{m\in\vnn}G_m/N$, namely
\begin{equation*}
w(\tuple s)\mapsto (w(\tuple s_m)\colon m\in\vnn)\cdot N
\end{equation*}
\end{theorem}

\begin{proof}
If the putative embedding is well-defined, it is a homomorphism.  Therefore it \emph{is} well-defined, since if $w(\tuple s)=1$, then $\{m\colon w(\tuple s_m)=1\}$ is cofinite and therefore large.  Similarly it is an embedding, since if $w(\tuple s)\neq1$, then $\{m\colon w(\tuple s_m)\neq1\}$ is cofinite and therefore large.
\end{proof}

A \textbf{non-standard free group} is a nonprincipal ultraproduct
 of nonabelian free groups.  Let us denote such an ultraproduct by
 \begin{equation*}
\nsfg.
\end{equation*}
By \L o\'s's Theorem, 
\begin{equation*}
\Th{\nsfg}_{\forall}=\Th{F_2}_{\forall}.
\end{equation*}
If $G\sg\nsfg$, then $\Th{\nsfg}_{\forall}\included\Th G_{\forall}$; therefore $G$ is a limit group.  The previous theorem gives the converse:

\begin{corollary}
Every limit group embeds in $\nsfg$.
\end{corollary}

\chapter{Limit groups 2}


\section{Topologies}

Given a group $E$, we let
\begin{equation*}
\isoc E=\{\text{quotient groups of }E\}.
\end{equation*}
%be the set of quotients of $E$.  
We have topologized this set in two equal ways:

\begin{asparaenum}
\item
If $G\in\isoc E$, then
\begin{equation*}
G=E/1^G.
\end{equation*}
Hence we can give $\isoc E$ the \textbf{Tychonoff topology} by
embedding it in $\pow E$ under 
\begin{equation*}
G\mapsto 1^G.
\end{equation*}
If $A$ and $B$ are disjoint finite subsets of $E$, then $\isoc E$ has
the basic open set
\begin{equation*}
U_{A,B}\namely\{G\colon A\included1^G\land B\cap1^G=\emptyset\}.
\end{equation*}
\emph{No presentation of $E$ is required.}  (This is the advantage of
the Tychonoff topology.)

Say $D\in\isoc E$.  If
$G\in\isoc D$, then 
\begin{equation*}
G=D/1^G=(E/1^D)/(N/1^D)\cong E/N,
\end{equation*}
where
\begin{equation*}
N=\bigcup1^G.
\end{equation*}
Thus $\isoc D$ embeds in $\isoc E$ under
\begin{equation*}
G\mapsto E/\bigcup1^G.
\end{equation*}
But the induced topology on $\isoc D$ is the same as its own Tychonoff
topology. 
\item
Let
\begin{equation*}
\sig=\{1,{}\inv,{}\cdot{}\}.
\end{equation*}
Suppose $E$ is presented as $\gppres SR$.  We may suppose
\begin{itemize}
\item
$S$ is a set of new constants,
\item
$R$ is a set of closed terms of $\sig(S)$.
\end{itemize}
Let  
\begin{equation*}
T_{S,R}
\end{equation*}
be the quantifier-free theory of groups in $\sig(S)$, with an additional
axiom
\begin{equation*}
w=1
\end{equation*}
for each $w$ in $R$.
Then $E\models T_{S,R}$, but $T_{S,R}$ is generally not complete.
  Let 
\begin{equation*}
\stone
\end{equation*}
be the space of quantifier-free completions of $T_{S,R}$.  Then $\isoc
E$ is in bijection with this space under 
\begin{equation*}
G\mapsto\diag G,
\end{equation*}
where $\diag G$ is the quantifier-free theory of $G$ in $\sig(S)$.  (It is practically the \textbf{Robinson diagram} of $G$.)
Then $\isoc E$ inherits the \textbf{Stone topology:} if $\sigma$ is a
quantifier-free sentence of $\sig(S)$, then $\isoc E$ has a basic open set
\begin{equation*}
[\sigma]\namely\{G\colon G\models\sigma].
\end{equation*}
If $g\in E$, then $g=w_g{}^E$ for some closed term $w_g$ of $\sig(S)$.  Then
\begin{equation*}
U_{A,B}=[\sigma],
\end{equation*}
where
\begin{equation*}
\sigma\is\bigwedge_{a\in A}w_a=1\land\bigwedge_{b\in B}w_b\neq1.
\end{equation*}
So the Tychonoff and Stone topologies are the same.  Elements of
$\isoc E$ are \textbf{marked} by $S$: they are groups in $\sig(S)$
that are generated by their interpretations of $S$.  

\emph{We can now
  consider elements of $\isoc E$ as isomorphism-classes of groups
  marked by $S$.}  (This is the advantage of the Stone topology.)
\end{asparaenum}

The foregoing holds for any group $E$.  However, if $E$ has a metric $\dist$,
then $\isoc E$ has the \textbf{Gromov--Hausdorff topology.}  In this,
for each positive real number $r$, an element $G$ of $\isoc E$ has an
open neighborhood comprising those $H$ in $\isoc E$ such that, for all
$g$ in $E$,
\begin{equation*}
  g\in 1^G\symdiff 1^H\lto\dist(g,h)\geq r.
\end{equation*}
\emph{The Gromov--Hausdorff topology on $\isoc E$ agrees with the
  Tychonoff topology if and only if every ball around $1$ in
  $(E,\dist)$ is finite.}
Such is the case when $E$ is finitely generated, and $\dist$ is the
\textbf{word metric.}  But even if $E$ is not finitely generated, but
is still countable, an appropriate metric can be defined, as for
example by means of a bijection with $\Z$.

In any case, we shall just use the Tychonoff topology.

If $E$ is countable,
then the $\isoc E$ topology is \emph{first countable} (points have countable
neighborhood bases; in fact the topology is \emph{second countable}---itself has
a countable basis).  So the following are equivalent conditions on
a subset $A$ and a point $P$ of $\isoc E$: 
\begin{enumerate}
\item
$P\in\cl A$.
\item
A sequence $(P_k\colon k\in\vnn)$ of points of $A$
converges to $P$. 
\end{enumerate}

\begin{theorem}
Given a set $\Omega$ and a sequence $(A_k\colon
k\in\vnn)$ of elements of $\pow{\Omega}$, 
we have
\begin{equation*}
	\liminf_kA_k=\bigcup_{k\in\vnn}\bigcap_{k\leq m}A_m\included
	\bigcap_{k\in\vnn}\bigcup_{k\leq m}A_m=\limsup_kA_k.
\end{equation*}
[The \emph{equations} are by definition.]
The two limits are equal to the same set $A$ if and only if the
sequence converges to $A$ in the Tychonoff topology on $\pow{\Omega}$.
In particular, the sequence converges to $A$ in either of two cases:
\begin{enumerate}
\item 
$A_0\included A_1\included\dots$ and $\bigcup_{k\in\vnn}A_k=A$.
\item
$A_0\includes A_1\includes\dots$ and 
$\bigcap_{k\in\vnn}A_k=A$.
\end{enumerate}
\end{theorem}

\begin{proof}
  Say $\liminf_kA_k=A$.  For every open neighborhood $U_{X,\emptyset}$
  of $A$, we have $X\included A$, and therefore (since $X$ is finite)
  $A_m\in U_{X,\emptyset}$ if $m$ is large enough.  

Similarly, if
  $\limsup_kA_k=B$, then for every neighborhood $U_{\emptyset,Y}$ of
  $B$, we have $Y\cap B=\emptyset$, so $A_m\in U_{\emptyset,Y}$ if $m$
  is large enough.  

Finally, in any case,
  \begin{equation*}
    U_{X,Y}=U_{X,\emptyset}\cap U_{\emptyset,Y}.
  \end{equation*}
Therefore, if $A=B$,
then $(A_k\colon k\in\vnn)$ converges to this.

But suppose now $c\in B\setminus A$.
\begin{itemize}
\item 
If $c\in C$, then $C\in U_{\{c\},\emptyset}$, but for all $k$ in
$\vnn$, there is $m$ such that $k\leq m$, and $c\notin A_m$, so
$A_m\notin U_{\{c\},\emptyset}$.
\item 
If $c\notin C$, then $C\in U_{\emptyset,\{c\}}$, but for all $k$ in
$\vnn$, there is $m$ such that $k\leq m$, and $c\in A_m$, so
$A_m\notin U_{\emptyset,\{c\}}$.\qedhere
\end{itemize}
\end{proof}

We have examples of each of the special cases:
\begin{asparaenum}
\item
$\lim\limits_{m\to\infty}\gppres{\vnn}m=\gppres{\vnn}{\vnn}=\gpgen{\ }$, that
  is,  
  \begin{equation*}
\lim\limits_{m\to\infty}\gppres{s_0,s_1,\dots}{s_0,\dots,s_{m-1}}=\{0\}.
\end{equation*}
\item
$\lim\limits_{m\to\infty}\gppres{\vnn}{\vnn\setminus m}=\gppres{\vnn}{\ }=F_{\vnn}$, that
  is,  
  \begin{equation*}
\lim\limits_{m\to\infty}\gppres{s_0,s_1,\dots}{s_m,s_{m+1},\dots}=F_{\vnn}.
\end{equation*}
\end{asparaenum}
There is no convergence here in the Gromov--Hausdorff topology induced by
the word metric.
We are in a more general situation with:
\begin{asparaenum}\setcounter{enumi}2
\item
$\lim\limits_{m\to\infty}(\Zmod m,1+m\Z)=(\Z,1)$,
because we can write
\begin{align*}
  \Zmod m&=\gppres s{s^m},&
\Z&=\gppres s{\ }
\end{align*}
(this makes the claim meaningful),
and
\begin{multline*}
\gpgen{\ }=\{0\}
\included\bigcap_{k\in\vnn}\bigcup_{k\leq m}m\Z\\
\included\bigcap_{k\in\vnn}\Bigl(\Z\setminus\bigl(\{-k+1,-k+2,\dots,-1\}\cup\{1,2,\dots,k-1\}\bigr)\Bigr)
=\{0\}. 
\end{multline*}
\end{asparaenum}

The last is an example of:

\begin{theorem}\label{thm:int-triv}
Suppose $\mathscr A\included\isoc E$.  If
$E\in\cl{\mathscr A}$, then
\begin{equation*}
\bigcap_{G\in\mathscr A}1^G=\gpgen{\ }.
\end{equation*}
\end{theorem}

\emph{Finitely presented} groups that are limits can always be
considered as being of the
type of the last example.  The following corresponds to Lemma 2.3 of Champetier and
Guirardel \cite{MR2151593}; with the Stone topology, it becomes a
triviality. 

\begin{theorem}\label{thm:nbhd}
Suppose $E=\gppres SR$, where $R$ is finite.
Then $\isoc E$ is a
neighborhood of $E$ in $\isoc{F_S}$.  Thus if $\mathscr A\included\isoc{F_S}$ and $E\in\cl{\mathscr
  A}$, then
\begin{equation*}
  \bigcap_{G\in\mathscr A\cap\isoc E}1^G=\gpgen{\ }.
\end{equation*}
\end{theorem}

\begin{proof}
$E$ has the neighborhood $[\sigma]$ in $\isoc{F_S}$, and
  $[\sigma]\included\isoc E$, where
  \begin{equation*}
\sigma\is\bigwedge_{w\in R}w=1.\qedhere
  \end{equation*}
\end{proof}

The converse of Theorem~\ref{thm:int-triv} fails: if $G_m$ is
$\gppres{\vnn}{\vnn\setminus\{m\}}$ in $\bs$, then 
\begin{align*}
\bigcap_{m\in\vnn}1^{G_m}&=\gpgen{\ },&
\lim_{m\to\infty}G_m&=\gppres{\vnn}{\vnn}\neq\bg.
\end{align*}

By definition, a \textbf{limit group} is the limit of a sequence of
free groups in some $\isoc{F_n}$ (where
$n\in\vnn$).  If $E$ is a \emph{finitely presented} limit group, then, by Theorem~\ref{thm:nbhd},
it is the limit of a sequence of free groups in
$\isoc E$.  
Thus, being a finitely presented limit group is invariant under isomorphism.
Champetier and Guirardel \cite{MR2151593} show this for all limit groups in
\S2.7, Corollary 2.18.  We shall have it instead as a consequence of Theorems~\ref{thm:full-iff} and~\ref{thm:lim-frf}.


\section{Ultrapowers}

{}[Not presented; just a summary of Appendix~\ref{app:Los}.]

A \textbf{(nonprincipal) ultrapower} of a group $G$ is a quotient
$G^{\vnn}/N$, understood as follows. 

The group $G^{\vnn}$, or $\prod_{\vnn}G$,
is the group of sequences $(g_k\colon k\in\vnn)$, where $g_k\in G$ in
each case.  
We can write $(g_k\colon k\in\vnn)$ as $g$.
The \textbf{support} of $g$
 is the set
\begin{equation*}
\{k\colon g_k\neq1\};
\end{equation*}
we can write this as
$\supp g$.

\begin{lemma}
Among subgroups $H$ of $G$ such that
\begin{equation*}
g\in H\lto\supp g\pincluded\vnn,
\end{equation*}
there is a maximal instance, $N$, which is normal; and we may require
\begin{equation*}
\sum_{\vnn}G\sg N.
\end{equation*}
\end{lemma}

\begin{proof}
Let $\mathfrak m$ be a maximal ideal of $\pow{\vnn}$ as a Boolean ring:
\begin{equation*}
A\in\mathfrak m\land B\in\mathfrak m\liff\vnn\setminus(A\cup
B)\notin\mathfrak m. 
\end{equation*}
Elements of $\mathfrak m$ can be called \textbf{small;} of
$\pow{\vnn}\setminus\mathfrak m$, \textbf{large.} 
Then we can let $N$ be the set of elements of $G$ with small support:
\begin{equation*}
N=\{g\colon g\in G^{\vnn}\land \supp g\in\mathfrak m\}.
\end{equation*}
To meet the second condition, we require $\mathfrak m$ to be non-principal.
\end{proof}

When $N$ is as in the lemma, $G^{\vnn}/N$ is a non-principal
ultrapower of $G$, and we may denote it by 
\begin{equation*}
\upow G.
\end{equation*}
The proof of the lemma suggests how to replace $G$ with an arbitrary
structure, such as a ring. 

\begin{theorem}[\L o\'s]
The homomorphism $g\mapsto(g,g,\dots)\cdot N$ from $G$ to $\upow G$ is
an elementary embedding: 
\begin{equation*}
G\pelsub\upow G.
\end{equation*}
Likewise with arbitrary structures for $G$.
\end{theorem}

Piotr showed:

\begin{theorem}
The limit groups are just the finitely generated subgroups of
$\upow{F_2}$.
\end{theorem}


\section{Residual properties}

Say $\mathfrak X$ is an adjective of groups that is true of the
trivial group.  More precisely, $\mathfrak X$ is a class of groups
that is closed under isomorphism and contains $\gpgen{\ }$.  Some
quotients $E/N$ are $\mathfrak X$.  The quotient 
\begin{equation*}
E/\bigcap_{E/N\in\mathfrak X}N
\end{equation*}
may not be $\mathfrak X$; but it is called \textbf{residually}
$\mathfrak X$.  Thus, $E$ is residually $\mathfrak X$ if and only if 
\begin{equation}\label{eqn:res}
\bigcap_{E/N\in\mathfrak X}N=\gpgen{\ };
\end{equation}
equivalently, for all $g$ in $E\setminus\{1\}$, there is
an epimorphism $\phi$ from $E$ to an $\mathfrak X$ group $H$ such that 
\begin{equation*}
g\notin\ker(\phi).
\end{equation*}
Note that~\eqref{eqn:res} can be written as
\begin{equation*}
\bigcap_{G\in\mathfrak X\cap\isoc E}1^G=\gpgen{\ }.
\end{equation*}
Therefore, by Theorem~\ref{thm:int-triv}, we have:

\begin{theorem}\label{thm:itself}
A group is residually $\mathfrak X$
if it is a limit of $\mathfrak X$ quotients of itself.
\end{theorem}

We shall see that the converse fails.
Meanwhile,
by Theorem~\ref{thm:nbhd}, we have the following, which
Champetier and Guirardel \cite[\S2.4 (e)]{MR2151593} state in case
$\mathfrak X$ is free.

\begin{theorem}\label{thm:lf-rf}
  Finitely presented groups that are limits of $\mathfrak X$ groups are
  residually $\mathfrak X$.
\end{theorem}

In particular, finitely presented limit groups are residually free.  We shall show (Theorem~\ref{thm:lim-frf}) that \emph{all} limit groups are residually free.

Ali showed the following.  How easily is it obtained from Theorem~\ref{thm:itself}?

\begin{theorem}
Free groups are residually finite.
\end{theorem}

One has the following, for example, though it is obvious for free
groups.  (It is found in Derek J.S. Robinson \cite[2.2.5]{MR1357169}.)

\begin{theorem}
The word problem of a finitely presented residually finite group is
soluble.
\end{theorem}

\begin{proof}
Say $G=\gppres{s_0,\dots,s_{n-1}}{w_0,\dots,w_{p-1}}$.  Given $w$ in
$F_n$, writing $G$ as $F_n/N$, we want to know whether $w\in N$. 
\begin{asparaenum}
\item
We can effectively list the elements of $N$ as $(g_k\colon k\in\vnn)$.
(This requires only that $G$ be recursively presented.) 
\item
We can effectively list, as $(a_k\colon k\in\vnn)$, the images of $w$
under homomorphisms from $G$ into (finite) groups
$(\{0,\dots,m\},\cdot)$, where $n\in\vnn$. 
\end{asparaenum}
Either $w\in N$, so $g_k=w$ for some $k$; or $w\notin N$, so
$a_k\neq1$ for some $k$. 
\end{proof}

The group $E$ is \textbf{fully residually} $\mathfrak X$, or
\textbf{$\vnn$-residually} $\mathfrak X$, if for all finite subsets
$A$ of $E\setminus\{1\}$ there is an epimorphism $\phi$ from $E$ to an
$\mathfrak X$ group such that 
\begin{equation*}
A\cap\ker(\phi)=\emptyset;
\end{equation*}
equivalently, there is $G$ in $\isoc E$ such that
\begin{align*}
  G&\in\mathfrak X,& A\cap1^G&=\emptyset,
\end{align*}
that is, $\mathfrak X\cap U_{\emptyset,A}$ is nonempty in $\isoc E$.
In this space, $E$ has
a neighborhood base consisting of such sets $U_{\emptyset,A}$.
Now Theorem~\ref{thm:itself} leads to what is basically a restatement of the new definition: 

\begin{theorem}\label{thm:full-iff}
A group $G$ is fully residually $\mathfrak X$ if and only if it is a
limit point of $\mathfrak X\cap\isoc G$.
\end{theorem}

In particular, finitely generated fully residually free groups are limit groups.  The converse is true for \emph{finitely presented} limit groups, by Theorem~\ref{thm:nbhd}.
We shall show that the converse is true generally in Theorem~\ref{thm:lim-frf}.

Meanwhile, for which $\mathfrak X$ can a group be residually $\mathfrak X$, but not fully?

\begin{theorem}\label{thm:full}
Residually $\mathfrak X$ groups are fully residually $\mathfrak X$,
provided $\mathfrak X$ is closed under subgroups and (binary) products. 
\end{theorem}

\begin{proof}
Under the hypothesis, suppose $G$ is residually $\mathfrak X$, and
$G\setminus\{1\}$ contains $g_0$ and $g_1$.  Then $G$ has normal
subgroups $N_i$ such that $g_i\notin N_i$.  But $G/(N_0\cap N_1)$
embeds in $G/N_0\times G/N_1$. 
\end{proof}

In particular, residually finite groups are fully residually finite.
(So free groups are fully residually finite.) 
Champetier and
Guirardel \cite[\S2.4(e)]{MR2151593} show that
residually finite groups are limits of finite groups, by using the
Gromov--Hausdorff topology; but the claim is immediate from the definition,
understood as Theorem~\ref{thm:full-iff}. 

Theorem~\ref{thm:full} does not apply to residually free groups.
Indeed, the group
\begin{equation*}
  F_2\times\Z\namely\gppres{x,y,z}{[x,z],[y,z]},
\end{equation*}
is residually free, but not fully residually free: the three
generators, along with $[x,y]$, cannot be mapped nontrivially into a
free group.  The 
result is in the paper~\cite{MR0215903} of Benjamin
Baumslag based on his doctoral thesis of 1965 at London University.
The result is a consequence of his theorem that a residually
free group is fully residually free if and only if it is residually
free and \textbf{commutative transitive:}
\begin{equation*}
[x,y]=1\land[y,z]=1\land
y\neq1\lto[x,z]=1. 
\end{equation*}
Champetier and Guirardel repeat this as \cite[Thm~2.12]{MR2151593}.
Benjamin Baumslag is the younger brother of Gilbert Baumslag, who was Ali's
reference. 

Again, finitely presented limit
groups are fully residually free.  To show that all limit groups
are fully residually free (Theorem~\ref{thm:lim-frf}),
we shall use an application of
residualness to rings:  

\begin{theorem}[Hilbert's Nullstellensatz]\label{thm:0}
A finitely generated integral domain that includes a field $K$ is
fully residually algebraic over $K$.
\end{theorem}

\begin{proof}
Suppose
$K[x_0,\dots,x_{n-1}]$ is an integral domain,
and
\begin{equation*}
\{f_0(\tuple x), \dots, f_{p-1}(\tuple x)\}\included K[\tuple x]\setminus\{0\}.
\end{equation*}
By Hilbert's Basis Theorem,
\begin{equation*}
K[\tuple x]\cong K[\tuple X]/(g_0,\dots,g_{q-1})
\end{equation*}
for some $g_k$.  The system
\begin{equation*}
\bigwedge_{j<p}f_j(\tuple X)\neq0\land\bigwedge_{k<q}g_k(\tuple X)=0
\end{equation*}
is solved by $\tuple x$ in $K[\tuple x]$ and hence in $\alg{K[\tuple
    x]}$; therefore it has a solution $\tuple t$ in $\alg K$, since  
\begin{equation*}
\alg K\elsub\alg{K[\tuple x]}
\end{equation*}
by the model-completeness of $\acf$.  Then the rule $x_i\mapsto t_i$
determines a well-defined $K$-homomorphism $\phi$ from $K[\tuple x]$
into $\alg K$ such that
\begin{equation*}
\phi(f_j(\tuple x))\neq0.\qedhere
\end{equation*}
\end{proof}

Then we have the following \textbf{porism,} which is Champetier and Guirardel
\cite[Lemma 6.7]{MR2151593} (attributed to
Remeslennikov).  As Proclus \cite{MR1200456} writes,
\begin{quote}
`Porism' is a term applied to a certain kind of problem, such as those in the \emph{Porisms} of Euclid.  But it is used in its special sense when as a result of what is demonstrated some other theorem comes to light without our propounding it.  Such a theorem is therefore called a `porism',\footnote{From \gr{por'izw}, `furnish', `provide' [translator's note].} as being a kind of incidental gain resulting from the scientific demonstration.\hfill[212]

`Porism' is a geometrical term and has two meanings.  We call `porism' a theorem whose establishment is an incidental result of the proof of another theorem, a lucky find as it were, or a bonus for the inquirer.  Also called `porisms' are problems whose solution requires discovery, not merely construction or simple theory.\hfill[301]
\end{quote}
 
 \begin{porism}\label{por:Z}
A finitely generated sub-ring of $\upow{\Z}$ is fully residually $\Z$
(that is, infinite cyclic).
\end{porism}

\begin{proof}
The sub-ring is $\Z[x_0,\dots,x_{n-1}]$, and
\begin{equation*}
\Z\elsub\upow{\Z}.\qedhere
\end{equation*}
\end{proof}


To use this for the full residual freeness of limit groups, we relate free
groups to $\Z$ as follows. 

\section{A linear free group}

If $R$ is a ring, then the \textbf{special linear group}
$\SL R$ comprises the matrices
$\begin{pmatrix}a&b\\c&d\end{pmatrix}$
%$\begin{smallmatrix}a&b\\c&d\end{smallmatrix}$ 
over $R$
such that
\begin{equation*}
ad-bc=1.
\end{equation*}
The \textbf{projective special linear group}
$\PSL R$ is
$\SL R/\centr{\SL R}$.

In Robinson \cite{MR1357169}, Proposition 3.2.10 is that, when
$K$ is a
field and $n>1$, then $\SL[n]K$ is generated by the
\emph{transvections:} matrices $I+a\cdot E^i_j$, where every entry of
$E^i_j$ is $0$, but entry $(i,j)$ is $1$.  Left multiplication of a
matrix $X$ by $I+E^i_j$ effects the addition of $a$ times row $j$ of
$X$ to row $i$.  By such operations, elements of $\SL[n]K$ can be
reduced to $I$.  With this idea, we have: 

\begin{theorem}
$\SL{\Z}$ is generated by
\begin{align*}
&\begin{pmatrix}
1&1\\
0&1
\end{pmatrix},&
&\begin{pmatrix}
1&0\\
1&1
\end{pmatrix}.
\end{align*}
\end{theorem}

\begin{proof}
Call these $E_0$ and $E_1$.  Then $X\mapsto E_0\cdot X$ on $\SL{\Z}$
is adding the bottom row of $X$ to the top row; and $X\mapsto E_1\cdot
X$ is adding top to bottom.  We use these to perform the Euclidean
algorithm on the first column of elements of $\SL{\Z}$.  Indeed, say
\begin{equation*}
  \begin{pmatrix}
    a_0&*\\
    a_1&*
  \end{pmatrix}
\in\SL{\Z},
\end{equation*}
so $\gcd(a_0,a_1)=1$.
We obtain $(a_0,\dots,a_{n+1})$ for some $n$ in $\vnn$, and
$(k_0,\dots,k_{n-1})$, where, if $i<n$, then
\begin{align*}
  a_i&=a_{i+1}\cdot k_i+a_{i+2},&
\abs{a_{i+2}}\leq\frac{\abs{a_{i+1}}}2;
\end{align*}
also
\begin{align*}
  \abs{a_n}&=\gcd(a_0,a_1)=1,&
a_{n+1}&=0.
\end{align*}
Then
\begin{align*}
  \begin{pmatrix}
    a_0&*\\
    a_1&*
  \end{pmatrix}
&=E_0{}^{k_0}\cdot
\begin{pmatrix}
  a_2&*\\
a_1&*
\end{pmatrix}\\
&=E_0{}^{k_0}\cdot E_1{}^{k_1}\cdot
\begin{pmatrix}
  a_2&*\\
a_3&*
\end{pmatrix}\\
&=E_0{}^{k_0}\cdot E_1{}^{k_1}\cdot E_0{}^{k_2}\cdot
\begin{pmatrix}
  a_4&*\\
a_3&*
\end{pmatrix}\\
&\makebox[\mydots]{\dotfill}\\
&=E_0{}^{k_0}\cdot E_1{}^{k_1}\cdot E_0{}^{k_2}\dotsm E_1{}^{k_{n-1}}\cdot
\begin{pmatrix}
  \pm1&m\\
0&\pm1
\end{pmatrix}\\
&=E_0{}^{k_0}\cdot E_1{}^{k_1}\cdot E_0{}^{k_2}\dotsm
E_1{}^{k_{n-1}}\cdot E_0{}^{\pm m}\cdot
\begin{pmatrix}
  \pm1&0\\
0&\pm1
\end{pmatrix}
\end{align*}
if $n$ is even; but also
\begin{align*}
  \begin{pmatrix}
    -1&0\\
    0&-1
  \end{pmatrix}
&=E_1\cdot
  \begin{pmatrix}
    -1&0\\
    1&-1
  \end{pmatrix}\\
&=E_1\cdot E_0{}^{-2}\cdot
  \begin{pmatrix}
    1&-2\\
    1&-1
  \end{pmatrix}\\
&=E_1\cdot E_0{}^{-2}\cdot E_1\cdot
  \begin{pmatrix}
    1&-2\\
    0&1
  \end{pmatrix}\\
&=E_1\cdot E_0{}^{-2}\cdot E_1\cdot E_2{}^{-2}.
\end{align*}
If $n$ is odd, then
\begin{align*}
  \begin{pmatrix}
    a_0&*\\
    a_1&*
  \end{pmatrix}
&=  
E_0{}^{k_0}\cdot E_1{}^{k_1}\cdot E_0{}^{k_2}\dotsm
E_0{}^{k_{n-1}}\cdot
\begin{pmatrix}
  0&\mp1\\
\pm1&m
\end{pmatrix}\\
&=  
E_0{}^{k_0}\cdot E_1{}^{k_1}\cdot E_0{}^{k_2}\dotsm
E_0{}^{k_{n-1}}\cdot E_1{}^{\mp m}\cdot
\begin{pmatrix}
  0&\mp1\\
\pm1&0
\end{pmatrix},
\end{align*}
and
\begin{align*}
  \begin{pmatrix}
    0&\mp1\\
    \pm1&0
  \end{pmatrix}
&=E_0{}^{\mp1}\cdot
  \begin{pmatrix}
    1&\mp1\\
    \pm1&0
  \end{pmatrix}\\
&=E_0{}^{\mp1}\cdot E_1^{\pm1}\cdot
  \begin{pmatrix}
    1&\mp1\\
    0&1
  \end{pmatrix}\\
&=E_0{}^{\mp1}\cdot E_1{}^{\pm1}\cdot E_0{}^{\mp1}.\qedhere
\end{align*}
\end{proof}

\begin{corollary}
$\PSL{\Z}=\SL{\Z}/\gpgen{-I}$.
\end{corollary}

From the proof of the last theorem, we have the following:

\begin{porism}
The quotient map from $\Z$ to $\Zmod2$ induces a homomorphism $\phi$
from $\SL{\Z}$ to $\SL{\Zmod2}$, and $\ker(\phi)$ is generated by 
\begin{align*}
&\begin{pmatrix}
1&2\\
0&1
\end{pmatrix},&
&\begin{pmatrix}
1&0\\
2&1
\end{pmatrix},&
&-I.
\end{align*}
\end{porism}

\begin{proof}
Modify the Euclidean algorithm.  Given 
$\begin{pmatrix}
 a_0&*\\
 a_1&* 
\end{pmatrix}$
in $\SL{\Z}$, we find $(a_0,\dots,a_{n+1})$ and $(k_0,\dots,k_n)$ such
that
\begin{align*}
  a_i&=a_{i+1}\cdot 2k_i+a_{i+2},&
\abs{a_{i+2}}&\leq\abs{a_{i+1}},
\end{align*}
and also $(a_n,a_{n+1})$ is one of
\begin{align*}
  &(\pm1,0),&
&(1,1).
\end{align*}
Thus, using only 
$\begin{pmatrix}
1&2\\
0&1
\end{pmatrix}$ and 
$\begin{pmatrix}
1&0\\
2&1
\end{pmatrix}$,
we can reduce any element of $\SL{\Z}$ to one of
\begin{align*}
&\begin{pmatrix}
\pm1&m\\
0&\pm1
\end{pmatrix},&
&\begin{pmatrix}
0&\mp1\\
\pm1&m
\end{pmatrix},&
&\begin{pmatrix}
1&m\\
1&m+1
\end{pmatrix}.
\end{align*} 
The last two are not in $\ker(\phi)$; if the first is, then $m$ is
even, so the matrix reduces to $\pm I$.
\end{proof}

The following is given as an example in Robinson \cite[\S2.1]{MR1357169}.

\begin{lemma}
The subgroup of $\SL{\Z}$ generated by
\begin{align*}
&\begin{pmatrix}
1&2\\
0&1
\end{pmatrix},&
&\begin{pmatrix}
1&0\\
2&1
\end{pmatrix}&
\end{align*}
is free.
\end{lemma}

\begin{proof}
Identify the matrices with the M\"obius transformations
\begin{align*}
z&\mapsto z+2,&
z&\mapsto \frac z{2z+1}.
\end{align*}
Calling these $\alpha$ and $\beta$, and letting $1/z=\gamma(z)$, we have
\begin{gather*}
\beta\circ\gamma(z)=\frac1{2+z}=\gamma\circ\alpha(z),\\
\beta=\gamma\circ\alpha\circ\gamma\inv
=\gamma\circ\alpha\circ\gamma.
\end{gather*}
Then for all $k$ in $\Z\setminus\{0\}$:
\begin{itemize}
\item
$\alpha^k$ sends the unit disk $D$ into $\C\setminus D$;
\item
$\beta^k$ sends $0$ to $0$, and $\C\setminus D$ into $D\setminus\{0\}$;
\item
$\beta^k(1)=1/(2k+1)$;
\item
for all words $w(x,y)$ that are nontrivial in $x$,
\begin{equation*}
w(\alpha,\beta)(1)\neq1.\qedhere
\end{equation*}
\end{itemize}
\end{proof}

\begin{theorem}\label{thm:psl}
If now $\phi$ is the induced homomorphism from $\PSL{\Z}$ to
$\PSL{\Zmod2}$, then 
\begin{equation*}
\ker{\phi}\cong F_2,
\end{equation*}
 that is, we have an exact sequence
 \begin{equation*}
1\to F_2\to\PSL{\Z}\xrightarrow{\phi}\PSL{\Zmod2}\to 1.
\end{equation*}
\end{theorem}

Champetier and Guirardel \cite{MR2151593} say it is `well known' that,
if $p$ is an odd prime, then the kernel of the natural homomorphism
from $\SL{\Z}$ to $\SL{\Zmod p}$ is a nonabelian free group; but I do
not know how to prove this. 


\section{Full residual freeness of limit groups}

The following theorem is Champetier and Guirardel \cite[Proposition
  6.6]{MR2151593} and is attributed to Remeslennikov
(in the form of the proof).  According to Yves de Cornulier in
\emph{Mathematical Reviews,}
\begin{quote}
  The class of limit groups is known to coincide with the long-studied
  class of finitely generated fully residually free groups. The
  authors provide (Corollary 6.5 and Proposition 6.6) the first proof
  of this result not relying on the finite presentability of limit
  groups. 
\end{quote}
Again, for finitely presented groups, we have the converse of the following by Theorem~\ref{thm:full-iff} (basically the \emph{definition} of being fully residually free); and we have the theorem itself for finitely presented groups.

\begin{theorem}\label{thm:lim-frf}
Limit groups are fully residually free.
\end{theorem}

\begin{proof}
We show that a finitely generated subgroup $G$ of $\upow{F_2}$ is
residually free. 
Let $\phi$ be as in Theorem~\ref{thm:psl}.
Then we also have an exact sequence
\begin{equation*}
1\to\upow{F_2}\to\PSL{\upow{\Z}}\xrightarrow{\upow{\phi}}\PSL{\Zmod2}\to1.
\end{equation*}
(Here we use $\upow{\PSL{R}}\cong\PSL{\upow R}$, and also $\upow R\cong R$ when $R$ is finite.)
We may assume $G\sg\ker(\upow{\phi})$.  Since $G$ is finitely generated, we have then
\begin{equation*}
G\sg\PSL{\Z[x_0,\dots,x_{n-1}]}
\end{equation*}
for some $x_i$ in $\upow{\Z}$.  Say $\{g_0,\dots,g_{p-1}\}\included G\setminus\{1\}$.  
Each $g_j$ is a proper coset $M_j\cdot\gpgen{-I}$ of $\gpgen{-I}$, and $M_j$ has the form
\begin{equation*}
\begin{pmatrix}
2a_k(\tuple x)+1&2b_k(\tuple x)\\
2c_k(\tuple x)&2d_k(\tuple x)+1
\end{pmatrix}
\end{equation*}
for some $a_k$ etc.\ in $\Z[\tuple X]$,
because $g_j$ is a nontrivial element of $\ker(\upow{\phi})$.
Finally, $\Z[\tuple x]=\Z[\tuple X]/(f_0,\dots,f_{q-1})$ for some $f_k$.  As in the proof of Porism~\ref{por:Z}, since $\Z\pelsub\upow{\Z}$, we can find $\tuple t$ in $\Z$ such that
\begin{itemize}
\item
each $f_k(\tuple t)=0$, so
$x_i\mapsto t_i$ is a well-defined homomorphism from $\Z[\tuple x]$ into $\Z$,
\item
the induced homomorphism $\psi$ from $\PSL{\Z[\tuple x]}$ to $\PSL{\Z}$ takes the
$g_j$ to 
nontrivial elements.
\end{itemize}
We now have a commutative diagram as in Figure~\ref{fig:exact} (with top and bottom rows exact).  In particular, there is a homomorphism from $E$ to $F_2$ that is nontrivial at the $g_j$.
\begin{figure}[ht]
\begin{equation*}
\SelectTips{cm}{}
\xymatrix{
1\ar[r] & \upow{F_2}\ar[r] & \PSL{\upow{\Z}}\ar[r]^{\upow{\phi}} & 
\PSL{\Zmod2}\ar[r] & 1\\
        & E\ar @{>->}[u]\ar[r]\ar[d] & 
\PSL{\Z[\tuple x]}\ar @{>->>}[u]\ar[r]\ar[d]^{\psi} & 
\PSL{\Zmod2}\ar @{>->>}[u]\ar @{>->>}[d] & \\
1\ar[r] & F_2\ar[r] & \PSL{\Z}\ar[r]_{\phi} & \PSL{\Zmod2}\ar[r] & 1
}
\end{equation*}
\caption{Commutative diagram for full residual freeness of limit groups}\label{fig:exact}
\end{figure}
\end{proof}

Now, since a limit group $E$ is fully residually free, it is a limit of free groups in $\isoc E$ by Theorem~\ref{thm:full-iff}.  Therefore being a limit group is invariant under isomorphism.

\section{Finitude of maximal limit quotients}

This section corresponds to Champetier and Guirardel
\cite[\S6.4]{MR2151593}, which is said to be inspired by Zo{\'e}
Chatzidakis \cite{chatzidakis-limit}.

Every group $E$ has a unique maximal residually free quotient, namely $E/\tilde N$, where
\begin{equation*}
\tilde N=\bigcap\{N\colon E/N\text{ is free}\}.
\end{equation*}
We shall show that a finitely generated group has finitely many maximal limit quotients---equivalently, \emph{fully} residually free quotients.

\begin{lemma}\label{lem:chain}
Suppose $G$ is a finitely generated group, and $(N_k\colon k\in\vnn)$
is an increasing chain of normal subgroups of $G$ such that each
quotient $G/N_k$ is residually free.  Then the chain is eventually
constant.
\end{lemma}

\begin{proof}
Say $G$ is generated by $\tuple s$.  Let $V_k$ be the set of all
$\rho(\tuple s)$, where $\rho$ is a representation of $G/N_k$ in
$\SL{\C}$; that is, 
\begin{equation*}
V_k=\bigcap_{w(\tuple s)\in N_k}\{\tuple M\colon\tuple
M\in\SL{\C}^n\land w(\tuple M)=1\}. 
\end{equation*}
Then $(V_k\colon k\in\vnn)$ is a decreasing chain of algebraic
varieties; so it is eventually constant.  
  (The Hilbert Basis Theorem ensures that the corresponding increasing chain of ideals of polynomials that are zero on the varieties is eventually constant; then the Nullstellensatz, Theorem~\ref{thm:0} above, ensures that the chain of varieties must be eventually constant.)
However, 
\begin{equation*}
N_k\pincluded N_{k+1}\lto V_k\pincludes V_{k+1},
\end{equation*}
by the residual freeness of $G/N_k$.
Indeed, suppose $w(\tuple s)\in N_{k+1}\setminus N_k$.  There is a
homomorphism $\phi$ from $G/N_k$ to $F_2$ such that $\phi(w(\tuple
s))\neq1$.  But there is also an embedding $\psi$ of $F_2$ in
$\SL{\C}$.  Then
\begin{gather*}
	\psi(\phi(w(\tuple s)))\neq1,\\
	w(\psi(\phi(s_0),\dots,\phi(s_{n-1})))\neq1,
\end{gather*} 
or in short $w(\psi(\phi(\tuple s)))\neq1$,
and so $\psi\circ\phi(\tuple s)\in V_k\setminus V_{k+1}$. 
\end{proof}

\begin{lemma}\label{lem:rf-fp}
Every finitely generated residually free group is the maximal residually free quotient of a finitely presented group.
\end{lemma}

\begin{proof}
Suppose $G=\gppres{s_0,\dots,s_n}{w_0,w_1,\dots}$. 
There is an increasing chain $(N_k\colon k\in\vnn)$ of normal
subgroups of $F_n$, where $F_n/N_k$ is the maximal residually free quotient of $\gppres{\tuple s}{w_0,\dots,w_{k-1}}$.
By Lemma~\ref{lem:chain}, the sequence stabilizes at some $N_k$, and then $N_k$ contains each $w_{\ell}$, so
$F_n/N_k$ is a quotient of $G$, even the maximal residually free quotient of $G$.  If $G$ is
already residually free, then $G$ must be $F_n/N_k$, so it is the maximal residually free quotient of $\gppres{\tuple s}{w_0,\dots,w_{k-1}}$. 
\end{proof}

\begin{lemma}\label{lem:nbhd}
Every residually free group $G$ in $\isoc{F_n}$ has an open neighborhood whose every residually free element is in $\isoc G$.
\end{lemma}

\begin{proof}
By Lemma~\ref{lem:rf-fp}, $G$ is the maximal residually free quotient of some finitely presented group $E$.  Say
\begin{equation*}
E=\gppres{\tuple s}{w_0,\dots,w_{k-1}}.
\end{equation*}
Then $\isoc E$ is the open set $[\bigwedge_{i<k}w_i=1]$ of $\isoc{F_n}$.  This open set contains $G$, and every residually free element, being a residually free quotient of $E$, must be a quotient of $G$. 
\end{proof}

\begin{theorem}
Every finitely generated group has finitely many limit quotients.
\end{theorem}

\begin{proof}
Let $E$ be a finitely generated group.  The set $\mathscr L$ of limit
quotients of $E$ is a closed subset of $\isoc E$ (since limits of
limit groups are limit groups).  Therefore $\mathscr L$ is compact.
By Lemma~\ref{lem:nbhd}, for every $D$ in $\mathscr L$, the set $\isoc
D\cap\mathscr L$ is an open neighborhood of $D$ in $\mathscr L$.
Finitely many such neighborhoods over $\mathscr L$.  The maximal limit
quotients of $E$ are among the corresponding groups $D$. 
\end{proof}

\chapter{Limit groups 3}

Here are some results from \cite[\S 2.7]{MR2151593}.  Given a finitely generated group $E$, we work in the topological space $\isoc E$ of group quotients of $E$.
The \textbf{saturation} of a subset of $\isoc E$ is the set of all groups in $\isoc E$ that are isomorphic to some group in the subset.  The following is the first part of \cite[Lem.~2.17]{MR2151593}; note that the argument does not require a metric.

\begin{theorem}
The saturation of an open set is open.
\end{theorem}

\begin{proof}
Let $G$ and $G_1$ be groups marked by a finite set $S$ or $\{s_0,\dots,s_{n-1}\}$.  Suppose $\theta$ is an isomorphism from $G_1$ to $G$.  Then for some terms $w_i$ and $v_i$ of $\sig(S)$, we have
\begin{align*}
\theta(s_i{}^{G_1})&=w_i{}^G,& \theta\inv(s_i{}^G)=v_i{}^{G_1},
\end{align*}
so that
\begin{equation*}
s_i{}^G=\theta(v_i{}^{G_1})=v_i(\tuple w)^G,
\end{equation*}
that is,
\begin{equation}\label{eqn:sat}
G\models\bigwedge_{i<n}s_i=v_i(\tuple w).
\end{equation}
Moreover, for all terms $u$ of $\sig(S)$,
\begin{equation}\label{eqn:sat2}
G_1\models u=1\iff
G\models u(\tuple w)=1.
\end{equation}
Conversely, the latter condition~\eqref{eqn:sat2} ensures that there is a well-defined monomorphism $s_i{}^{G_1}\mapsto w_i{}^G$ from $G_1$ to $G$; if we have also~\eqref{eqn:sat} for some $v_i$, then this monomorphism is surjective.

Now let $\phi$ be a quantifier-free formula of $\sig$.  If $G_1\in[\phi(\tuple s)]$ and $G_1\cong G$, then 
\begin{equation*}
G\in[\phi(\tuple w)\land\bigwedge_{i<n}s_i=v_i(\tuple w)].
\end{equation*}
Conversely, if this holds for some choice of $w_i$ and $v_i$, and we define $G_1$ as $\gppres SR$, where
\begin{equation*}
u\in R\iff G\models u(\tuple w)=1,
\end{equation*}
then in particular $G_1\in[\phi(\tuple s)]$ and $G_1\cong G$.  Thus the saturation of $[\phi(\tuple s)]$ is the union of the collection of all of the open sets $[\phi(\tuple w)\land\bigwedge_{i<n}s_i=v_i(\tuple w)]$.
\end{proof}

\begin{theorem}
The closure of a saturated set is saturated.
\end{theorem}

\begin{proof}
Let $F$ ge saturated.
The saturation of the complement of the closure of $F$ is open, so if it contains a point of the closure of $F$, then it contains a point $G$ of $F$ itself---but then $G$ is isomorphic to a group in the complement of $F$, which is absurd.
\end{proof}

\begin{corollary}
The set of limit groups in $\isoc E$ is saturated.
\end{corollary}

\begin{proof}
It is the closure of the set of free groups in $\isoc E$, and this set is saturated.
\end{proof}

In particular, we have now a simpler proof that being a limit group is invariant under isomorphism.

If $G\in\isoc E$, we may denote by
\begin{equation*}
[G]_E
\end{equation*}
the set of groups in $\isoc E$ that are isomorphic to $G$.  That is, $[G]_E$ is the saturation of $\{G\}$ in $\isoc E$.

\begin{corollary}
If $1\leq k\leq n$, then 
the closure of $[\Z^k]_{\isoc{F_n}}$ is
\begin{equation*}
[\Z^k]_{\isoc{F_n}}\cup\dotsb\cup[\Z^n]_{\isoc{F_n}}.
\end{equation*}
\end{corollary}

\begin{proof}
If $p\leq n$, then $\Z^p\cong\gppres SR$, where $S=\{s_0,\dots,s_{n-1}\}$ and
\begin{equation*}
R=\{[s_i,s_j]\colon i<j<p\}\cup\{s_m\colon p\leq m<n\}.
\end{equation*}
If also $1\leq k\leq p$, then $\gppres SR$ is the limit of the groups
\begin{equation*}
\gppres S{R\cup\{s_0{}^rs_{\ell}{}\inv\colon k\leq\ell<p\}},
\end{equation*}
which are isomorphic to $\Z^k$.  This shows that the closure of $[\Z^k]_{\isoc{F_n}}$ includes $[\Z^p]_{\isoc{F_n}}$.

Conversely, the set $[\Z^k]_{\isoc{F_n}}\cup\dotsb\cup[\Z^n]_{\isoc{F_n}}$ is closed, since it is the intersection of the sets $[\sigma]$, where $\sigma$ is one of
\begin{align*}
[w,v]&=1,& w^{r+1}=1&\lto w=1, & \bigvee_{i<n}s_i&\neq w_i(v_0,\dots,v_{k-1}). \qedhere
\end{align*}
\end{proof}

Now we pass to \cite[Ch.~3]{MR2151593}.

\begin{theorem}
Every limit group in $\isoc{F_n}$ is of exactly one of three kinds:
\begin{enumerate}[1)]
\item
trivial, or
\item
a limit of free groups of rank $1$, that is, a nontrivial free abelian group, or
\item
a limit of free groups of rank $2$.
\end{enumerate}
\end{theorem}

\begin{proof}
Every limit group in $\isoc{F_n}$ is in the closure of some $[F_{\ell}]_{\isoc{F_n}}$.
Therefore, assuming $2\leq\ell\leq n$, we have to show $F_{\ell}$ is a limit of elements of $[F_2]_{\isoc{F_n}}$.  By induction, it is enough to show that, if $2\leq k<n$, then $F_{k+1}$ is a limit of elements of $[F_k]_{\isoc{F_n}}$.  But $F_{k+1}$ is a limit of the groups
\begin{equation*}
\gppres{s_0,\dots,s_k}{s_0{}^r\dotsm s_{k-1}{}^rs_k{}\inv}. \qedhere
\end{equation*}
\end{proof}

By Theorem~\ref{thm:seq-sub}, subgroups of limit groups are limit groups; also, by Theorem~\ref{thm:sub-lim}, a $2$-generated subgroup of a limit group is either $F_2$ or a free abelian group of rank $2$ or less.

Since we know by Theorem~\ref{thm:lim-frf} that limit groups are fully residually free, we can take some examples of non-free limit groups from B. Baumslag~\cite{MR0215903}.  The following is based on Lemma 7 (p.~412) of that paper.

\begin{lemma}
Let $F$ be a limit group with elements $f_0$, \dots, $f_{k-1}$, and $u$ such that $[f_i,u]\neq1$ in each case.  Then
\begin{equation*}
u^{n_0}f_0u^{n_1}f_1\dotsm f_{k-1}u^{n_k}\neq1
\end{equation*}
if the $n_i$ are integers large enough (in absolute value) when $1\leq i<k$, and also when $i$ is $0$ or $k$, unless in this case $n_i=0$.
\end{lemma}

\begin{proof}
Since $F$ is fully residually free, we may replace it with a free quotient in which the $[f_i,u]$ remain nontrivial.  We may also assume that $u$ is \emph{cyclically reduced,} that is, as a word, it does not begin with $g^{\pm1}$ and end with $g^{\mp1}$ for some generator $g$ of $F$.  

We shall show that, if $n$ is large enough, then $u^nfu^n$ and $u^nfu^{-n}$, as reduced words, begin with $u$, and they end with $u^{\pm1}$ respectively.
Consider first the case of $u^nfu^n$, where $n$ is positive.  If $n$ is large enough, then 
\begin{equation*}
u^nf=u_{\triangle}u^{n-1}f
\end{equation*}
in the notation introduced on page~\pageref{triangle}; that is, there is no cancellation between $u$ and $u^{n-1}f$.  Moreover, $u^{n-1}f\neq1$.  If $r$ is large enough and positive, then $u^{n-1}fu^r=u^{n-1}fu^{r-1}{}_{\triangle}u$.  Again, $u^{n-1}fu^{r-1}\neq1$.  Indeed we have
\begin{equation}\label{eqn:seg}
u^{n-1}fu^{r-1}=vgw,
\end{equation}
where $v$ is an initial, and $w$ a final, proper segment of $u$, and $g$ is a segment of $f$, or possibly one or two of them are trivial, but not all three.  If $vgw$ is not simply 
$v$ or $w$, then
\begin{equation*}
u^nfu^r=u_{\triangle}u^{n-1}fu^{r-1}{}_{\triangle}u;
\end{equation*}
but in any case,
\begin{equation}\label{eqn:seg-2}
u^{n+1}fu^{r+1}=u_{\triangle}u^nfu^r{}_{\triangle}u.
\end{equation}
If we go through the same steps with $r$ negative, instead of~\eqref{eqn:seg}, we get
\begin{equation*}
u^{n-1}fu^{r-1}=vgw\inv,
\end{equation*}
where now $w$ is a proper initial segment of $u$ or is trivial; but we still get~\eqref{eqn:seg-2}.

For each $i$ less than $k$, there is now a positive integer $m_i$ such that
\begin{align*}
u^{\pm(m_i+1)}fu^{\pm(m_i+1)}&=u^{\pm1}{}_{\triangle}u^{\pm m_i}fu^{\pm m_i}{}_{\triangle}u^{\pm1},\\
u^{\pm(m_i+1)}fu^{\mp(m_i+1)}&=u^{\pm1}{}_{\triangle}u^{\pm m_i}fu^{\mp m_i}{}_{\triangle}u^{\mp1}.
\end{align*}
We can now require
\begin{align*}
\abs{n_0}&>m_0,&\abs{n_i}&>m_{i-1}+m_i,&\abs{n_k}>m_k
\end{align*}
where $1\leq i<k$.
\end{proof}

\begin{theorem}
Let $F$ be a limit group with an element $u$ whose centralizer is $\gpgen u$, and let $A$ be the free abelian group on $\{x_0,\dots,x_{n-1}\}$.  Then the group
\begin{equation*}
F*_{u=x_0}A
\end{equation*}
(namely, $F*A/N$, where $N$ is the normal closure of $\{ux_0{}\inv\}$) is a limit group.
\end{theorem}

\begin{proof}
Define a homomorphism $\theta$ from $F*A$ to $F$ by requiring 
\begin{itemize}
\item
$\theta(f)=f$ for all $f$ in $F$,
\item
$\theta(x_0)=u$,
\item
$\theta(x_{i+1})=u^{p_i}$
\end{itemize}
for some $p_i$ to be determined.  We want $\theta$ to be nontrivial on some finite subset of $F*A\setminus N$, where $N$ is the normal closure of $\{x_0u\inv\}$.  We may assume that the elements of this finite subset have the form
\begin{equation*}
a_0f_0a_1\dotsm a_{n-1}f_{n-1}a_n
\end{equation*}
for some $f_j$ in $F\setminus\gpgen u$ and $a_j$ in $A\setminus\gpgen{x_0}$; but possibly $a_0$ or $a_n$ is trivial.  We can now pick the $p_i$ so that, by the lemma, each $\theta(a_j)$ is a power of $u$ with exponent large enough that $\theta$ is as desired.
\end{proof}

\appendix

\chapter{Schedule}

\begin{center}
  \begin{tabular}{rccc}
 &chapter         &date&speaker\\\hline
1&Free groups     &October 7  &Ali Nesin\\
 &''              &October 14 &''\\
2&Trees           &''         &''\\
3&Burnside problem&October 21 &Oleg Belegradek\\
4&Limit groups    &''         &Piotr Kowalski\\
 &''              &October 28 &''\\
 &''              &November 4 &''\\
5&Limit groups 2  &November 18&David Pierce\\
 &''              &December 2 &''\\
 &''              &December 9 &''\\
 &''              &December 16&''\\
6&Limit groups 3  &December 23&Ay\c se Berkman\\
 &''              &December 30&'' 
  \end{tabular}
\end{center}

There was no meeting on November 11 (because of the Feast of the Sacrifice).
Other talks, not recorded here:

\begin{itemize}
\item
C\'edric Milliet, `Definable envelopes around abelian, nilpotent or
soluble subgroups in a group with simple theory',  October 28 and
November 4 
\item
Oleg Belegradek, `Coset-minimal groups', November 18
\item
Salih Durhan, `Hahn fields', December 2
\item
\"Ozlem Beyarslan, `Algebraic closure in pseudofinite fields', December 16 and 23
\end{itemize}

\chapter{German letters}\label{app:german}

German letters are as follows; they are obtained by the
\verb+\mathfrak+ command in  \AmS-\LaTeX\ (specifically, in the
\url{amssymb} package, which apparently loads the \url{amsfonts}
package). 
\begin{gather*}
\begin{array}{ccccccccc}
\mathfrak A&\mathfrak B&\mathfrak C&\mathfrak D&\mathfrak E&\mathfrak
F&\mathfrak G&\mathfrak H&\mathfrak I\\\mathfrak J&\mathfrak
K&\mathfrak L&\mathfrak M&\mathfrak N&\mathfrak O&\mathfrak
P&\mathfrak Q&\mathfrak R\\\mathfrak S&\mathfrak T&\mathfrak
U&\mathfrak V&\mathfrak W&\mathfrak X&\mathfrak Y&\mathfrak Z& 
%  \end{array}
\\
\phantom{A}&&&&&&&&\\
%\begin{array}{ccccccccc}
\mathfrak a&\mathfrak b&\mathfrak c&\mathfrak d&\mathfrak e&\mathfrak
f&\mathfrak g&\mathfrak h&\mathfrak i\\\mathfrak j&\mathfrak
k&\mathfrak l&\mathfrak m&\mathfrak n&\mathfrak o&\mathfrak
p&\mathfrak q&\mathfrak r\\\mathfrak s&\mathfrak t&\mathfrak
u&\mathfrak v&\mathfrak w&\mathfrak x&\mathfrak y&\mathfrak z& 
  \end{array}
  \end{gather*}
  (The combined letters like \ss\ are apparently not available in math mode.)
A way to write German letters by hand is shown in Figure~\ref{fig:German},
\begin{sidewaysfigure}
\centering
%\includegraphics[width=417pt,height=292pt]{german-script-cropped.eps}
\includegraphics[width=350pt]{../Courses/Set-theory/german-script-cropped.eps}
\caption{The German alphabet by hand}\label{fig:German}
\end{sidewaysfigure}
which is taken from a old textbook: Roe-Merill S. Heffner, \emph{Brief
  German Grammar} (Boston: D.C. Heath and Company, 1931).  According
to this source, `The great German poets, philosophers, and scientists
usually wrote in German script.' 

\chapter{Stone spaces}\label{app:Stone}

The topologies on the spaces $\isoc E$ introduced on
page~\pageref{isoc} can be understood as instances of a general
construction, outlined here. 

For some positive $n$ in $\vnn$, we let $\tuple x$ be the $n$-tuple
$(x_0,\dots,x_{n-1})$ of letters, and we let $F_n$ be the free group
on $\tuple x$.  We also let $\tuple w$ be an $m$-tuple
$(w_0,\dots,w_{m-1})$ of elements of $F_n$, that is, reduced words on
$\tuple x$.  Then we obtain the finitely presented group 
\begin{equation*}
\gppres{\tuple x}{\tuple w},
%\gpgen{\tuple x\mathpunct{\mid}\tuple w},
\end{equation*}
which we call $E$.
We can understand $E$ as a structure in the signature $\sig(\tuple s)$, where $s_i$ is interpreted as the image of $x_i$ in $E$.
In this signature, let $T_E$ be
the theory of groups in which $w_i(\tuple s)=1$: this is the theory of groups $G$ for which there is a homomorphism from $E$ to $G$.

Let
$\Lb$ consist of the quantifier-free sentences of $\sig(\tuple s)$ \emph{modulo} equivalence in $T_E$.  
Then $\Lb$ is a Boolean algebra with respect to $\lor$ and $\land$; it is an example of a 
\textbf{Lindenbaum--Tarski algebra.} 
The top element $\top$ of this algebra is (the equivalence-class of) $s_0=s_0$; the bottom element, $\bot$, is $s_0\neq s_0$.  We can also understand $\Lb$ as a ring by defining
\begin{align*}
\sigma+\tau&=\lnot(\sigma\liff\tau),&\sigma\cdot\tau&=\sigma\land\tau,&
1&=\top,&0&=\bot.
\end{align*}
Then $\Lb$ is a called a \textbf{Boolean ring} because
\begin{equation}\label{eqn:Br}
\sigma\cdot\sigma=\sigma.
\end{equation}
Any ring meeting this condition is commutative and of characteristic $2$; but these features are already obvious for $\Lb$.

A \textbf{filter} of $\Lb$ is a proper nonempty subset $F$ of $\Lb$ such that
\begin{enumerate}[1)]
\item
if $\sigma$ and $\tau$ are in $F$, then $\sigma\land\tau$ is in $F$;
\item
if $\sigma\in F$, then $\sigma\lor\tau\in F$.
\end{enumerate}
Then a filter can be understood as a theory (in our case a quantifier-free theory) that includes the quantifier-free part of $T_E$.
More algebraically, a filter of $\Lb$ is a subset $\{\lnot\sigma\colon\sigma\in I\}$ for some ideal of $\Lb$, when this is considered as a ring.  In a word, filters are \textbf{dual} to ideals.  
We may refer to $\Lb$ as an \textbf{improper filter} of itself; then, for emphasis, a filter is a \textbf{proper filter.}

An \textbf{ultrafilter} is a maximal filter; equivalently, it is dual to a maximal ideal.  Now, if $\mathfrak m$ is a maximal ideal of $\Lb$, then the quotient $\Lb/\mathfrak m$ is a field.  This is a field in which every element satisfies~\eqref{eqn:Br}; so the field has only two elements, and therefore $\mathfrak m$ has index $2$ as a subgroup of $\Lb$.  
In particular, $\mathfrak m$ has only two cosets in $\Lb$: itself, and $1+\mathfrak m$.  But
\begin{equation*}
1+\sigma=\lnot\sigma.
\end{equation*}
Therefore an ultrafilter of $\Lb$ is a filter $F$ meeting the additional condition
\begin{enumerate}[1)]\setcounter{enumi}2
\item
$\sigma\in F$ if and only if $\lnot\sigma\notin F$.
\end{enumerate}
In particular, an ultrafilter of $\Lb$ can be understood as a complete
quantifier-free theory $T$ that includes the quantifier-free part of
$T_E$.  If $G\models T$, let $A$ be the subgroup of $G$ generated by
(the interpretation of) $\tuple s$.  Then $T$ can be understood as the
\textbf{Robinson diagram} of $A$ (although strictly this diagram is
the complete quantifier-free theory of $A$ in the signature
$\sig(A)$, not just $\sig(\tuple s)$).  Also, $A$ is isomorphic to a
quotient $E/N$ of $E$; and then $N$ is uniquely determined by $T$. 

The set of ultrafilters of $\Lb$ can be denoted by
\begin{equation*}
\Stone.
\end{equation*}
This is the \textbf{Stone space} of $\Lb$, considered as a Boolean
algebra; and it is the \textbf{Tarski space} of $\Lb$, considered in
particular as a Lindenbaum-Tarski algebra.\footnote{I have a memory of
  Angus Macintyre's using the term \emph{Tarski space} for the space of
  completions of a theory (the particular theory in question was that of
  algebraically closed fields).}  Again, 
for every $p$ in 
$\Stone$, there is a corresponding normal subgroup of $E$, namely the
set of $w(\tuple s)$ such that the sentence $w(\tuple s)=1$ is in $p$.
Then $p$ can be recovered from this normal subgroup. 

From $\Lb$ to the power-set $\pow{\Stone}$ of the Tarski space, there is a function $\sigma\mapsto[\sigma]$, given by
\begin{equation*}
[\sigma]=\{p\colon\sigma\in p\}.
\end{equation*}
If $\sigma$ and $\tau$ are distinct elements of $\Lb$, then one of
$\sigma\land\lnot\tau$ and $\tau\land\lnot\sigma$ is not $\bot$.  Say
$\sigma\land\lnot\tau$ is not $\bot$; then (by the Axiom of Choice) it
is a member of some $p$ in the Tarski space, and therefore 
\begin{align*}
\sigma&\in p,&\tau&\notin p.
\end{align*}
Thus the function $\sigma\mapsto[\sigma]$ is an embedding of sets.
It is an embedding of \emph{Boolean algebras} since
\begin{align*}
[\sigma\lor\tau]&=[\sigma]\cup[\tau],&
[\sigma\land\tau]&=[\sigma]\cap[\tau],
\end{align*}
and also
\begin{align*}
[\lnot\sigma]&=\Stone\setminus[\sigma],&
[\bot]&=\emptyset,&
[\top]&=\Stone.
\end{align*}
In particular, the collection of sets $[\sigma]$ is closed under
(finite) union and intersection, as well as complementation, so it is
a basis of closed sets and of open sets of the (same) topology on
$\Stone$. 

The topology on $\Stone$ is compact.  Indeed, suppose
$\{[\sigma]\colon\sigma\in A\}$ is a set of basic closed sets whose
every finite subset has nonempty intersection.  This just means that
the subset $A$ of $\Lb$ generates a proper filter.  By the Axiom of
Choice, this filter is included in an ultrafilter $p$, and then 
\begin{equation*}
p\in\bigcap_{\sigma\in A}[\sigma].
\end{equation*}
In an alternative approach to compactness,
we can understand $\Stone$ as a subset of $\pow{\Lb}$.  The latter is
in bijection with $2^{\Lb}$, namely the set of functions from $\Lb$
into $2$ (that is, $\{0,1\}$).  Suppose $2$ has the discrete topology,
which is compact since $2$ is finite.  Then $2^{\Lb}$ can be given the
product topology, which by Tychonoff's Theorem is compact.  Then
$\pow{\Lb}$ has the compact topology induced by the bijection.  The
topology on $\Stone$ that we defined above is just the subspace
topology, and $\Stone$ is a closed subset of $\pow{\Lb}$, so it is
compact. 

We can do all of the foregoing with $\Lb$ replaced by the algebra of
arbitrary or quantifier-free formulas in a given set of variables
\emph{modulo} equivalence in a given theory.   

We can also metrize the topology on $\Stone$.  
In this metric, the distance $\dist pq$ between distinct points $p$ and $q$ is 
$\me^{-M}$, where $M$ is the greatest $m$ such that, for all
reduced words $w$ belonging to $F_n$ of length $m$ or less, either both or neither of $p$ and $q$ belongs to $[w(\tuple s)=1]$.
  Note then
\begin{equation*}
\dist pr\leq\max\bigl(\dist pq,\dist qr\bigr).
\end{equation*}
The closed ball of radius $\me^{-M}$ about $p$ is the intersection of 
the sets $[w(\tuple s)=1]$, where the equation $w(\tuple s)=1$ belongs to $p$
and the length of $w$ is $M$ or less.  So the closed ball is indeed closed in the Stone topology.
In fact, since the number of such words
$w$ is finite, the ball is one of the basic closed sets.  
Conversely, suppose $U$ is an open neighborhood of $p$ in the Stone topology.  Then there is some quantifier-free sentence $\sigma$ such that
\begin{align*}
\sigma&\in p,&[\sigma]&\included U.
\end{align*}
We may assume further that $\sigma$ is a conjunction
\begin{equation*}
(w'_0(\tuple s)=1)^{\eps_0}\land\dotsb\land(w'_{\ell-1}(\tuple s)=1)^{\eps_{k-1}}
\end{equation*}
of word equations and inequations in $\tuple s$.  Let $\ell$ be the greatest length of one of the $w'_i$.  Then $U$ includes the closed ball of radius $\me^{-\ell}$ about $p$, which is also the open ball of radius $\me^{1-\ell}$ about $p$. 
So
the topology on $\Stone$ is indeed induced by the metric. 

Each $p$ in $\Stone$ determines a normal subgroup $N_p$ of $E$, namely the set of all elements $w(\tuple s)$ of $E$ such that $p\in[w(\tuple s)=1]$.  Then
\begin{equation*}
\dist pq=\dist{N_p}{N_q},
\end{equation*}
where the distance between normal subgroups of $E$---that is, between
elements of $\isoc E$---is the Gromov--Hausdorff distance as on
page~\pageref{GHE}. 

\chapter{Ultraproducts of groups}\label{app:Los}

Suppose $\seq G$ is an infinite sequence $(G_k\colon k\in\vnn)$ of groups.  The \textbf{direct product}
of $\seq G$ is the set of sequences $(g_k\colon k\in\vnn)$, where $g_k\in G_k$ in each case.  This product can be denoted by either of
\begin{align*}
&\prod_{k\in\vnn}G_k,&&\prod\seq G;
\end{align*}
it is a group in the obvious way.
We may write $(g_k\colon k\in\vnn)$ also as $g$.
Then the \textbf{support} of $g$ is the subset $\{k\colon g_k\neq1\}$
of $\vnn$; we may denote this by
\begin{equation*}
  \supp g.
\end{equation*}
The \textbf{direct sum} 
of $\seq G$ is the normal subgroup of $G$ comprising those elements
that have finite support; it can be denoted by either of 
\begin{align*}
&\sum_{k\in\vnn}G_k,&&\sum\seq G.
\end{align*}

By Appendix~\ref{app:Stone}, a maximal ideal of $\pow{\vnn}$ is a
subset $\mathfrak m$ such that, 
for all subsets $A$ and $B$ of $\vnn$,
\begin{gather}\label{eqn:cup}
A\in\mathfrak m\land B\in\mathfrak m\liff A\cup B\in\mathfrak
m,\\\label{eqn:comp} 
A\in\mathfrak m\liff\vnn\setminus A\notin\mathfrak m.
\end{gather}
We may then think of the elements of $\mathfrak m$ as the
\textbf{small} subsets of $\vnn$; and their complements in $\vnn$, as
\textbf{large.}   
Possibly there is an element $\ell$ of $\vnn$ such that a subset is
large if and only if it contains $\ell$; in this case, $\mathfrak m$
is the principal ideal $(\vnn\setminus\{\ell\})$.   
In any case, we define $N_{\mathfrak m}$ as the set of elements
of $\prod\seq G$ with small support.

\begin{theorem}
Assume no $G_k$ is trivial.
  The following are equivalent conditions on a subgroup of
  $\prod\seq G$:
  \begin{enumerate}
  \item 
It is maximal among the subgroups $H$ of $\prod\seq G$ such that
no element of $H$ has full support.
\item
It is $N_{\mathfrak m}$ for some maximal ideal $\mathfrak m$ of $\pow{\vnn}$.
  \end{enumerate}
The following are equivalent conditions on a maximal ideal $\mathfrak
m$ of $\pow{\vnn}$:
\begin{enumerate}
\item 
$\mathfrak m$ is nonprincipal.
\item
$\sum\seq G\sg N_{\mathfrak m}$.
\end{enumerate}
\end{theorem}

\begin{proof}
  For the first part, given $\mathfrak m$, suppose $g\in\prod\seq
  G\setminus N_{\mathfrak m}$.  Then $\supp g$ is large, so
  $N_{\mathfrak m}$ has an element $h$ such that $\supp
  h=\vnn\setminus\supp g$.  Then $gh\in\gpgen{N_{\mathfrak
      m}\cup\{g\}}$ and has full support.  This establishes maximality
  of $N_{\mathfrak m}$.

Conversely, suppose $N$ is maximal among the subgroups $H$ of
$\prod\seq G$ such that no element of $H$ has full support.  
Let 
\begin{equation*}
\mathfrak m=\{\supp g\colon g\in N\}.
\end{equation*}
Then $\mathfrak m$ is a nonempty proper subset of $\pow{\vnn}$.
If $g\in
N$, and $A\included\supp g$, then $h\in N$, where
\begin{equation*}
  h_k=
  \begin{cases}
    g_k,&\text{ if }k\in A,\\
      1,&\text{ if }k\in\vnn\setminus A,
  \end{cases}
\end{equation*}
so that $\supp h=A$.  
Thus $\mathfrak m$ contains all subsets of its elements.
In particular, suppose also $g'\in N$, and $A=\supp
g\cap\supp{g'}$.  With $h$ as above, we have $gh\inv g'\in N$, and its
support is $\supp g\cup\supp{g'}$.  So $\mathfrak m$ contains the
unions of pairs of members.  Therefore $\mathfrak m$ is a proper ideal
of $\pow{\vnn}$.  By maximality of $N$, the ideal must be maximal.
\end{proof}

Henceforth let $N=N_{\mathfrak m}$ for some nonprincipal ideal
$\mathfrak m$ of $\pow{\vnn}$.
The quotient $\prod\seq G/N$ is the \textbf{(nonprincipal)
  ultraproduct} of $\seq G$
with respect to $\mathfrak m$---or with respect to the dual
ultrafilter of $\mathfrak m$.  We have $g N=hN$ if and only if
$\{k\colon g_k\neq h_k\}$ is small, that is, $\{k\colon g_k=h_k\}$ is
large.  These conditions make sense if the $G_k$ are structures in an
arbitrary signature; so they allow ultraproducts to be defined in any
signature.  If the $G_k$ were fields, so that $\prod\seq G$ was a
commutative ring (in fact a von Neumann regular ring), then $N$ would
be a maximal \emph{ideal} of $\prod\seq G$.  In our case, $N$ just has
the maximality given in the theorem above. 

\begin{theorem}[\L o\'s]
For all sentences $\sigma$ of $\sig$,
\begin{center}
$\prod\seq G/N\models\sigma$ if and only if $\{k\colon G_k\models\sigma\}$ is large.
\end{center}
\end{theorem}

\begin{proof}
If $n\in\vnn$, the same element of $(\prod\seq G)^n$ can be denoted by $\tuple g$ and $(g^0,\dots,g^{n-1})$, where again $g^i=(g^i_k\colon k\in\vnn)$.  Then also $\tuple g_k$ stands for $(g^0_k,\dots,g^{n-1}_k)$.  Finally, $\tuple gN$ means $(g^0N,\dots,g^{n-1}N)$ in $(\prod\seq G/N)^n$.
We show by recursion that for all formulas $\phi$ of $\sig$,
\begin{center}
$\prod\seq G/N\models\phi(\tuple gN)$ if and only if $\{k\colon G_k\models\phi(\tuple g_k)\}$ is large.
\end{center}
\begin{asparaenum}
\item
The claim is true when $\phi$ is an atomic formula, that is, an equation, by definition of equality in $\prod\seq G/N$.
\item
If the claim is true when $\phi$ is $\psi$, then it is true when $\phi$ is $\lnot\psi$, simply because a subset of $\vnn$ is large if and only if its complement is not, by~\eqref{eqn:comp}.
\item
If the claim is true when $\phi$ is $\psi$ or $\chi$, then the claim is true when $\phi$ is $\psi\lor\chi$, by~\eqref{eqn:cup}.
\item
Suppose the claim is true when $\phi$ is $\psi(\tuple x,y)$.  The following are equivalent:
\begin{itemize}
\item
$\prod\seq G/N\models\Exists y\psi(\tuple gN,y)$;
\item
$\prod\seq G/N\models\psi(\tuple gN,hN)$ for some $h$ in $\prod\seq G$;
\item
$\{k\colon G_k\models\psi(\tuple g_k,h_k)\}$ is large for some $h$ in $\prod\seq G$.
\end{itemize}
Now, for all $h$ in $\prod\seq G$, we have
\begin{equation*}
\{k\colon G_k\models\psi(\tuple g_k,h_k)\}\included
\{k\colon G_k\models\psi(\tuple g_k,f_k)\text{ for some }f_k\text{ in }G_k\};
\end{equation*}
and the inclusion is an equation for \emph{some} choice of $h$.
Therefore the following are equivalent.
\begin{itemize}
\item
$\prod\seq G/N\models\Exists y\psi(\tuple gN,y)$;
\item
$\{k\colon G_k\models\psi(\tuple g_k,f_k)\text{ for some }f_k\text{ in }G_k\}$ is large;
\item
$\{k\colon G_k\models\Exists y\psi(\tuple g_k,y)\}$ is large.
\end{itemize}
Therefore the claim is true when $\phi$ is $\Exists y\psi(\tuple x,y)$.\qedhere
\end{asparaenum}
\end{proof}

\chapter{A summary}

This was prepared on December 10.
Here all groups are to be understood as finitely generated (though
this may not always be required).

The set of quotients of a group $E$ is given the `Tychonoff topology':
the weakest in which, for every $g$ in $E$, the set of quotients $E/N$ such
that $N$ contains $g$ is both open and closed.

By definition, a limit group is a limit of free groups in the space of
quotients of some group.

That space is a (closed) subspace of the space of quotients of some free group.

Therefore a limit group is just a limit of free quotients of some free group.

It is not immediate that being a limit group is invariant under isomorphism.

By definition, to be fully residually free is to be a limit of one's
own free quotients.

Thus fully residually free groups are limit groups.

The space of quotients of a finitely presented group is an open
neighborhood of the group (in any space of quotients that contains the
group).

Therefore finitely presented limit groups are fully residually free.

It is supposedly true that every limit group is finitely presented,
but we do not show this.

A limit group embeds in every ultraproduct of the free groups whose limit it is.

Since every free group embeds in the free group on two generators,
every limit group embeds in an ultrapower of this free group.

With some work, we show that every limit group is fully residually
free.  The ideas used in the proof are:
\begin{enumerate}
\item 
  The free group on two generators can be understood as a linear
group over the integers.
\item
  This allows us to interpret a limit group $E$ in an ultrapower of
the integers.
\item
 We need only a finitely generated sub-ring of this ultrapower
(since limit groups are finitely generated).
\item
 Then just as in the model-theoretic proof of Hilbert's
Nullstellensatz, we get a homomorphism from $E$ into a free group that
is non-trivial on a predefined finite set of nontrivial elements.
\end{enumerate}
So now we have that being a limit group and being a residually free
group are the same thing.

In particular, every limit group is a limit of its own free quotients.

Therefore being a limit group is indeed invariant under isomorphism.

Every group has a unique maximal residually free quotient.

We are going to show that every group has finitely many maximal
\emph{fully} residually free quotients---that is, limit quotients.

To this end, we have shown that no group has an infinite descending
chain of residually free quotients.

Again, this is connected to the Nullstellensatz, because a descending
chain of quotients corresponds to a certain descending chain of
varieties.

Because of this (as we shall show), every residually free group is the
maximal residually free quotient of a finitely presented group.

Therefore, in the space of limit quotients of a group, every element
has an open neighborhood consisting just of its own quotients.

But the space of limit quotients of a group is compact.

The finiteness of the set of maximal limit quotients will then follow.

%\bibliographystyle{amsplain}
%\bibliography{../references}

\def\cprime{$'$} \def\cprime{$'$} \def\cprime{$'$}
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
% \MRhref is called by the amsart/book/proc definition of \MR.
\providecommand{\MRhref}[2]{%
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}
\begin{thebibliography}{1}

\bibitem{MR0215903}
Benjamin Baumslag, \emph{Residually free groups}, Proc. London Math. Soc. (3)
  \textbf{17} (1967), 402--418. \MR{0215903 (35 \#6738)}

\bibitem{MR2151593}
Christophe Champetier and Vincent Guirardel, \emph{Limit groups as limits of
  free groups}, Israel J. Math. \textbf{146} (2005), 1--75. \MR{2151593
  (2006d:20045)}

\bibitem{chatzidakis-limit}
Zo{\'e} Chatzidakis, \emph{Limit groups, viewed by a logician}, December 2001,
  available at \url{http://www.logique.jussieu.fr/~zoe/papiers/limit.dvi}.

\bibitem{MR1200456}
Proclus, \emph{A commentary on the first book of {E}uclid's \emph{{E}lements}},
  Princeton Paperbacks, Princeton University Press, Princeton, NJ, 1992,
  Translated from the Greek and with an introduction and notes by Glenn R.
  Morrow, Reprint of the 1970 edition, With a foreword by Ian Mueller.
  \MR{MR1200456 (93k:01008)}

\bibitem{MR1357169}
Derek J.~S. Robinson, \emph{A course in the theory of groups}, second ed.,
  Graduate Texts in Mathematics, vol.~80, Springer-Verlag, New York, 1996.
  \MR{1357169 (96f:20001)}

\end{thebibliography}


\end{document}
