\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>}[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_{rr. \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_{j1$, 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->}[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_{im_0,&\abs{n_i}&>m_{i-1}+m_i,&\abs{n_k}>m_k \end{align*} where $1\leq i