%% Process this file twice with LaTeX 2.e %% using the AMS-LaTeX styles. \documentclass[12pt]{amsart} \usepackage{amsmath,amssymb,amsthm} \usepackage[all]{xy} \CompileMatrices \usepackage{verbatim} \marginparwidth 0pt \oddsidemargin 0pt \evensidemargin 0pt \marginparsep 0pt \topmargin 0pt \textwidth 6.3in \textheight 8.5in \title{Conjugacy equivalence relation on subgroups} \author{Alessandro Andretta} \author{Riccardo Camerlo} \address{Dip.\ di Matematica, Universit\`a di Torino, Italy} \email{andretta@dm.unito.it \qquad camerlo@dm.unito.it} \author{Greg Hjorth} \address{Department of Mathematics, University of California at Los Angeles} \email{greg@math.ucla.edu} \thanks{The first author would like to thank the UCLA Math department for hospitality and support during the 1998--1999 academic year, when the results were obtained. The third author gratefully acknowledges support of grant DMS-9970403 and a generous fellowship from the Sloan foundation.} \keywords{Countable Borel equivalence relations, Subgroup conjugacy} \subjclass{03E15,20E05,20F05} \theoremstyle{plain} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{sublemma}{Sublemma}[theorem] \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{remark}[theorem]{Remark} \newtheorem{question}[theorem]{Question} \newcommand{\dom}{\mathrm{dom}} \newcommand{\rng}{\mathrm{rng}} \newcommand{\R}{\mathbb R} \newcommand{\lh}{\operatorname{lh}} \newcommand{\Mid}{\boldsymbol\mid} \begin{document} \begin{abstract} If $G$ is a countable group containing a copy of ${\bf F}_2$ then the conjugacy equivalence relation on subgroups of $G$ attains the maximal possible complexity. \end{abstract} \maketitle \section{Introduction} This paper is primarily directed towards the study of subgroups of countable groups and the complexity of the conjugacy equivalence relation, $E_{\rm c} ( G , {\rm Sgr} ( G ) )$, on the space of these subgroups ${\rm Sgr} ( G )$. It had previously been shown that: \begin{lemma}[Stuck, Zimmer, see \cite{stuckzimmer} 3.9] \label{stuckinthemud} The conjugacy equivalence relation on subgroups of ${\bf F}_2$, the free group on two generators, is not smooth. \end{lemma} We give the precise definition of smooth below in \S 2. Roughly speaking \ref{stuckinthemud} states that there is no Borel function assigning elements of $\R$ as complete invariants to the equivalence classes of $E_{\rm c} ( {\bf F}_2 , {\rm Sgr} ( {\bf F}_2 ) )$. This was recently strengthened in \cite{thomasvelickovic}: \begin{theorem}[Thomas, Veli\v ckovi\'c] \label{thomasthecat} $E_{\rm c} ( {\bf F}_2 , {\rm Sgr} ( {\bf F}_2 ) )$ is a universal countable Borel equivalence relation. \end{theorem} Again the exact definitions can be found in \S 2. In essence \ref{thomasthecat} states that $E_{\rm c} ( {\bf F}_2 , {\rm Sgr} ( {\bf F}_2 ) )$ attains the maximal possible complexity. In \cite{Gao} Su Gao showed $E_{\rm c} ( G, {\rm Sgr} ( G ) )$ to be universal for a variety of finitely generated groups, including ${\bf F}_2$, all of which contained ${\bf F}_2$ as a subgroup. In this present paper we obtain a completely general result: \begin{theorem} \label{ourtheorem} For $G$ a countable group containing ${\bf F}_2$ as a subgroup, $E_{\rm c} ( G, {\rm Sgr} ( G ) )$ is universal. \end{theorem} For instance Theorem \ref{ourtheorem} implies that the conjugacy equivalence relation on $SL_2 ( \mathbb Z )$ is universal since, as noted in \cite{Wagon}, $SL_2 ( \mathbb Z )$ contains a copy of ${\bf F}_2$. The universality of this specific conjugacy relation does not seem to follow from the arguments of Gao or Thomas and Veli\v ckovi\'c. The proof of \ref{ourtheorem} came about as a result of thinking about the following still open and seemingly difficult problem. \begin{question} \label{one} Must any countable Borel equivalence relation including a universal countable Borel equivalence relation itself be universal? \end{question} It is easily seen that $E_{\rm c} ( {\bf F}_2 , {\rm Sgr} ( {\bf F}_2 ) )$ includes a universal countable Borel equivalence relation, and hence so too does $E_{\rm c} ( G, {\rm Sgr} ( G ) )$ whenever ${\bf F}_2 \subseteq G$. The proof of \ref{ourtheorem} below demonstrates universality of $E_{\rm c} ( G , {\rm Sgr} ( G ) )$ by going to a subspace of ${\rm Sgr} ( G )$ on which the universal equivalence relation included in $E_{\rm c} ( G , {\rm Sgr} ( G ) )$ exactly equals $E_{\rm c} ( G , {\rm Sgr} ( G ) )$; in other words, we restrict to a subspace on which the extra parts of $E_{\rm c} ( G , {\rm Sgr} ( G ) )$ are killed off and only the universal countable equivalence relation remains. In some sense the proof can be thought of as a kind of trial effort to affirmatively answer the above open question, but using all the extra information given by the specific context. The proof of \ref{ourtheorem} also uses the following improvement of a theorem by Dougherty and Kechris: \begin{theorem}\label{Rec} For $G$ a countable group of permutations including the recursive permutations, $\cong^5_G$ is universal. \end{theorem} Here $\cong^5_G$ is the equivalence relation on $5^{\mathbb N}$ arising from the natural shift action on this space. Previously it was shown: \begin{theorem}[Dougherty, Kechris, see \cite{Doughertykechris}] \label{DK} For $G$ a countable group of permutations including the recursive permutations, $\cong^{\mathbb N} _G$ is universal. \end{theorem} These results came as an attempt to settle the following open problem. \begin{question}\label{two} Is $\equiv_{\rm T}$, the relation of Turing equivalence on $\mathbb N^\mathbb N$ (or equivalently $2^\mathbb N$), universal among countable Borel equivalence relations? \end{question} An affirmative answer to \ref{one} together with \ref{DK} would yield an affirmative answer to \ref{two} which in turn would refute in a very strong way a conjecture of Martin's in recursion theory---see the Appendix in \cite{cabal}. \section{Notation and definitions} We give a stick figure sketch of the most of the definitions and notation. The reader is referred to \cite{Kechris} for basic facts on descriptive set theory, while more extensive introductions to the theory of Borel equivalence relations can be found in \cite{DJK} or \cite{hjorthkechris}. A topological space $X$ is said to be Polish if it is separable and completely metrizable. For example $k^{\mathbb N}$ and ${\mathbb N}^{\mathbb N}$ are both Polish with the topology of pointwise convergence. (Here and below we adopt the usual convention of identifying an integer $k$ with the set of all of its predecessors $\{ 0 , \dots , k - 1 \}$ and $A^B$ with the set of all functions from $B$ to $A$.) We say that $B \subseteq X$ is Borel if it appears in the smallest $\sigma$-algebra containing the open sets. A function $f : X \to Y$ between Polish spaces is Borel if $f^{-1} [ U ]$ is Borel for any open $U \subseteq Y$. An equivalence relation $E$ on $X$ is {\em Borel} if is Borel as a subset of $X \times X$. For $E$ and $F$ Borel equivalence relations on Polish spaces $X$ and $Y$ we say that $E$ is {\em Borel reducible} to $F$, written $E\leq_{\rm B} F$, if there is a Borel function $f : X \to Y$ which embeds $E$ in $F$, in the sense that for all $x_1, x_2\in X$ \[ x_1 \, E \, x_2 \iff f ( x_1 ) \, F \, f ( x_2 ). \] We say that $E$ on $X$ is {\em smooth\/} if $E \leq_{\rm B} \Delta ( \R )$, the equality equivalence relation on $\R$. We say that $E$ on $X$ is {\em countable} if all of its equivalence classes are countable. A countable Borel equivalence relation $E$ is said to be {\em universal} if for any other countable Borel equivalence relation $F$ we have $F \leq_{\rm B} E$. It is a somewhat non-trivial fact that there is a universal countable Borel equivalence relation. We work towards giving an example due to Dougherty, Jackson, and Kechris. Let $G$ be an infinite countable group. Then $G$ acts on $2^G$ by {\em left} shift, namely we define $G \times 2^G \to 2^G$, $( g , x ) \mapsto g . x$, to be \[ \forall h \in G \left ( ( g . x ) ( h ) = x ( g^{ - 1} h ) \right ) . \] We then denote the resulting orbit equivalence relation on $2^G$ by $E ( G , 2 )$. Note that $2^G$ is Polish, being homeomorphic to $2^\mathbb N$, and that $E ( G , 2 )$ is countable Borel. \begin{theorem}[Dougherty, Jackson, Kechris, see \cite{DJK}] \label{universalF2} $ E ( {\bf F}_2, 2 )$ is universal. \end{theorem} For $G$ a countable group, we let ${\rm Sgr} ( G )$ be the collection of all subgroups of $G$. Under the natural identification of ${\mathcal P}(G)$ with $2^G$ we obtain that ${\rm Sgr} ( G )$ is a closed subset of $2^G$, and hence a Polish space in its own right. We then let $G$ act on Sgr$(G)$ by conjugation and define $E_{\rm c} (G, {\rm Sgr} ( G ) )$ to be the resulting orbit equivalence relation. Thus for $H_1, H_2 \subseteq G$ we have \[ H_1 \, E_{\rm c} ( G, {\rm Sgr} ( G ) ) \, H_2 \iff \exists g \in G \left ( g H_1 g^{-1} = H_2 \right ) . \] For $X$ a set ${\rm Sym} ( X )$ is the group of all permutations of $X$. ${\rm Sym} ( \mathbb N )$ is usually denoted by $S_\infty$. We let $S_\infty$ act on the {\em right\/} on $k^{\mathbb N}$, by $k^{\mathbb N} \times S_\infty \to k^{\mathbb N}$, $( x , g ) \mapsto x \circ g$. We then obtain for any subgroup $G \subseteq S_\infty$ the corresponding equivalence relation $\cong_G^k$ \[ x \cong^k_G y \iff \exists g \in G \left ( x \circ g = y \right ) . \] Similarly we define $\cong_G^{\mathbb N}$ on ${\mathbb N}^{\mathbb N}$. \section{Groups of permutations} We now prove Theorem \ref{Rec}. In fact we will prove a slightly stronger assertion. \begin{theorem} \label{rec} There is a countable group of recursive permutations $G_0 \subseteq S_\infty$ such that $G_0 \cong {\bf F}_2$, and for every countable group $G$ with $G_0 \subseteq G \subseteq S_\infty$, the equivalence relation $\cong^5_G$ on $5^{\mathbb N}$ is universal among countable Borel equivalence relations. In particular this holds when $G = {\rm Rec}$, the group of recursive bijections. \end{theorem} \begin{proof} Rather than working with subgroups of $S_\infty$ we will look at subgroups $G$ of ${\rm Sym} ( M )$, where $M = {\bf F}_2 \times {\mathbb N}^2$. The set $M$ is best visualized as ${\bf F}_2$-many copies of the square $\mathbb N \times \mathbb N$ \[ \underbrace{ \quad \cdots \quad \mbox{\framebox{\rule[-.9cm]{0cm}{1.9cm} \rule{.5cm}{0cm}$\mathbb N \times \mathbb N$\rule{.6cm}{0cm}}} \quad \cdots \quad \mbox{\framebox{\rule[-.9cm]{0cm}{1.9cm} \rule{.5cm}{0cm}$\mathbb N \times \mathbb N$\rule{.6cm}{0cm}}} \quad \cdots \quad \mbox{\framebox{\rule[-.9cm]{0cm}{1.9cm} \rule{.5cm}{0cm}$\mathbb N \times \mathbb N$\rule{.6cm}{0cm}}} \quad \cdots \quad }_{{\bf F}_2} \] A generic element of $M$ is denoted by $( w , n , k )$ with $n$ ranging on the $x$-axis and $k$ ranging on the $y$-axis of the $w$-th square. Thus a set of the form $\{ ( w , n , k ) \in M \mid k_0 \leq k \leq k_1 \}$ is called a {\em horizontal strip\/} of $M$. For every $w \in {\bf F}_2$ let $\hat{w} \in {\rm Sym} ( M )$ be defined by \[ \hat{w} ( v , n , k ) = ( v w , n , k ) \] and let $G_0 = \{ \hat{w} \Mid w \in {\bf F}_2 \}$. (Note that the map ${\bf F}_2 \to G_0$, $w \mapsto \widehat{w^{- 1}}$, is an isomorphism.) An element of the form $\hat{w}$ acts by right multiplication on the ${\bf F}_2$-coordinate, leaving the other two coordinates unchanged. Let $G$ be a countable group with $G_0 \subseteq G \subseteq {\rm Sym} ( M )$. If $G$ were equal to $G_0$ then we would be done by \ref{universalF2} and $E ( G_0 , 2 ) \leq_{\rm B} {\cong^5_{G_0}}$. So we try to analyze how different from an element of $G_0$ can an element of $G$ be. Fix an enumeration $( g_i )_{i > 0}$ of $G$. (For notational reasons it is more convenient to avoid 0 as an index here.) An element $g \in G$ is called a {\em quasi-shift above $\ell$} iff \begin{multline*} \forall ( w , n , k ) \in M \big [ k > \ell \implies \\ g ( w , n , k ) = ( \varphi ( w , n , k ) , n , k ) \ \&\ g ^{- 1} ( w , n , k ) = ( \psi ( w , n , k ) , n , k ) \big ] \end{multline*} for some functions $\varphi , \psi : M \to {\bf F}_2$. In other words, a quasi-shift respects pointwise the second and third coordinates of $M$. If the functions $\varphi , \psi$ above depend on ${\bf F}_2$ only, i.e., $g ( w , n , k ) = ( \varphi ( w ) , n , k )$ and $g^{-1} ( w , n , k ) = ( \psi ( w ) , n , k )$, then $g$ is a shift. Elements of $G_0$ are particular types of shifts. An increasing sequence of integers $( \ell_i )_ {i \in {\mathbb N}}$ is defined inductively. Set $\ell_0 = {- 1}$ and suppose $\ell_{i - 1}$ has been defined for some $i \geq 1$. We now distinguish two cases: \bigskip $\bullet$\quad $g_i$ is not a quasi-shift above $\ell_{i - 1}$, i.e., there is a $w_0 \in {\bf F}_2$ and there are $( n_0 , k_0 ) \in \mathbb N^2$ such that $g_i ( w_0 , n_0 , k_0 ) = ( w_0 ' , n_0 ', k_0 ')$ and $( n_0 , k_0 ) \neq ( n_0 ', k_0 ')$, with $k_0 > \ell_{i - 1}$ or $k_0 ' > \ell_{i - 1}$. Then we have the following possibilities: \begin{enumerate} \item[(i)] $g_i ( w_0 , n_0 , k_0 ) = ( w'_0 , n'_0 , k'_0 )$, for some $( w_0 , n_0 , k_0 ) , ( w'_0 , n'_0 , k'_0 ) \in M$ with $k_0 > \ell_{i - 1}$ and $k_0 > k'_0$; \item[(ii)] $g_i^{- 1} ( w_0 , n_0 , k_0 ) = ( w'_0 , n'_0 , k'_0 )$, for some $( w_0 , n_0 , k_0 ) , ( w'_0 , n'_0 , k'_0 ) \in M$ with $k_0 > \ell_{i - 1}$ and $k_0 > k'_0$, and (i) fails; \item[(iii)] $g_i ( w_0 , n_0 , k_0 ) = ( w'_0 , n'_0 , k_0 )$, for some $( w_0 , n_0 , k_0 ) , ( w'_0 , n'_0 , k_0 ) \in M$ with $k_0 > \ell_{i - 1}$ and $n_0 \neq n'_0$, and both (i) and (ii) fail. \end{enumerate} Then set $\ell_i = k_0$, for the least possible $k_0$ as above. \bigskip $\bullet$\quad Otherwise, that is: $g_i$ is a quasi-shift above $\ell_{i - 1}$. Then set $\ell_i = \ell_{i - 1} + 1$. \bigskip Suppose $g_i$ is a quasi-shift above $\ell_{i - 1}$. Then $g_i$ shuffles the $\ell_i$-th rows among the various squares, and, in particular, $\forall n \in \mathbb N \, \exists w \in {\bf F}_2 \left ( g_i ( 1_{{\bf F}_2} , n , \ell_i ) = ( w , n , \ell_i ) \right )$. We say that $g_i$ is {\em good\/} if there is an increasing sequence of natural numbers $( n_m )_m$ and a fixed $w_\infty \in {\bf F}_2$ such that \[ \forall m \in {\mathbb N} \left ( g_i ( 1_{{\bf F}_2} , n_m , \ell_i ) = ( w_\infty , n_m , \ell_i ) \right ) . \] If $g_i$ is not good then it is called {\em bad.\/} In this case we can find an increasing sequence of natural numbers $( n_m )_m$ and a sequence of distinct $( w_m )_m$ in ${\bf F}_2$ such that \[ \forall m \in {\mathbb N} \left ( g_i ( 1_{{\bf F}_2} , n_m , \ell_i ) = ( w_m , n_m , \ell_i ) \right ) . \] Let also $z_{m + 1} = w_{m + 1} w_m^{- 1}$ and define $\mu : 2^{{\bf F}_2} \to \{ 1 , 2 , \dots , \infty \}$ \[ \mu ( x ) = \begin{cases} \mbox{ the least $m \geq 1$ such that } z_m . x \neq x \, , \\ \ \infty \quad \mbox{ if } \forall m \geq 1 \left ( z_m . x = x \right ) . \end{cases} \] We record a few simple facts about $\mu$ whose proof is left to the reader. \begin{claim} \label{facts} $\forall j < \mu ( w_0 . x ) \left ( w_j . x = w_0 . x \right )$, and if $\mu ( w_0 . x ) < \infty$ then $\mu ( w_{\mu ( w_0 . x )} . x ) \leq \mu ( w_0 . x )$. \end{claim} Obviously all of the above ($n_m$'s, $w_m$'s, $z_m$'s, $\mu$) depend on $i$ so we should really write $n_m^{( i )}$, $w_m^{( i )}$, etc. We shall define a Borel map $2^{{\bf F}_2} \to 5^M$, $x \mapsto x^*$, witnessing the reduction $E ( {\bf F}_2 , 2 ) \leq_{\rm B} {\cong^5_G}$. The map $x^* : M \to 5$ assigns to each element of $M$ a {\em colour\/}, i.e., an integer between 0 and 4. The colouring of $x^*$ will encode $x$ in a sufficiently \lq \lq rigid" way so that for all $x , y \in 2^{{\bf F}_2}$ \begin{enumerate} \item $\forall w \in {\bf F}_2 \left ( w . x = y \implies x^* \circ \hat{w} = y^* \right )$, hence $x \, E ( {\bf F}_2 , 2 ) \, y \implies x^* \cong^5_G y^*$, \item $\forall g \in G \, \exists w \in {\bf F}_2 \left ( x^* \circ g = y^* \implies w . x = y \right )$, and hence $x^* \cong^5_G y^* \implies x \, E ( {\bf F}_2 , 2 ) \, y$. \end{enumerate} The function $x^* : M \to 5$ will be defined on the horizontal strips \[ \{ ( w , n , k ) \in M \Mid \ell_{i - 1} < k \leq \ell_i \} \] by induction on $i \geq 1$ in such a way that if $g_i$ is not a quasi shift then the value of $x^*$ is independent of $x$, i.e., \begin{multline*} g_i \mbox{ not a quasi shift } \implies \\ \forall x , y \in 2^{{\bf F}_2} \, \forall ( w , n , k ) \left ( \ell_{i - 1} < k \leq \ell_i \implies x^* ( w , n , k ) = y^* ( w , n , k ) \right ) . \end{multline*} The horizontal strip $\{ ( w , n , k ) \in M \Mid \ell_{i - 1} < k \leq \ell_i \}$ is used to \lq \lq kill" the $g_i$'s which are not quasi-shifts, i.e., it is used to make sure that $\forall x , y \in 2^{{\bf F}_2} \left ( x^* \circ g_i \neq y^* \right )$. If instead $g_i$ is a quasi-shift, then $\ell_{i - 1} + 1 = \ell_i$ and the set $\{ ( w , n , \ell_i ) \Mid n \in {\mathbb N} \}$ is used either to kill $g_i$ or else to encode $w . x$. Also the map $x \mapsto \{ ( w , n , k ) \Mid x^* ( w , n , k ) = 4 \}$ will be constant, that is, whether or not $x^* ( w , n , k ) = 4$ will not depend on $x$ but on $( w , n , k )$ only. Now the details. We will consider two cases depending on whether or not $g_i$ is a quasi-shift. \bigskip \framebox{\bf $g_i$ is a quasi-shift above $\ell_{i - 1}$.} Then $\ell_{i - 1} + 1 = \ell_i$ and we only have to define $x^* ( w , n , \ell_i )$ for $w \in {\bf F}_2$ and $n \in {\mathbb N}$. Let $( n_m )_m$ be as in the definition of good/bad quasi-shift. Fix an enumeration without repetitions $( u_m )_m$ of ${\bf F}_2$. \begin{enumerate} \item[{\bf (0)}] For $n \notin \{ n_m \Mid m \in {\mathbb N} \}$ set $x^* ( w , n , \ell_i ) = 0$. \item[{\bf (1)}] If $g_i$ is good then set for every $w \in {\bf F}_2$ and $m \in \mathbb N$ \[ x^* ( w , n_m , \ell_i ) = ( w . x ) ( u_m ) \in \{ 0 , 1 \} \, . \] In other words, we are encoding $w . x$ on the sequence $( n_m )_m$ in the $w$-th square. Therefore $\forall ( w , m ) \in {\bf F}_2 \times \mathbb N$ \begin{align*} x^* ( w , n_m , \ell_i ) & = ( w . x ) ( u_m ) \\ & = ( w . x )^* ( 1_{{\bf F}_2} , n_m , \ell_i ) \end{align*} and thus $\forall w \in {\bf F}_2 \, \forall n \in \mathbb N \left ( x^* ( w , n , \ell_i ) = ( w . x )^* ( 1_{{\bf F}_2} , n , \ell_i ) \right )$ by {\bf (0)}. \item[{\bf (2)}] If $g_i$ is bad and $\mu ( w . x ) = \infty$ then set, for every $m \in \mathbb N$, \begin{align*} x^* ( w , n_0 , \ell_i ) & = 0 \, , \\ x^* ( w , n_1 , \ell_i ) & = 3 \, , \\ x^* ( w , n_{m + 2} , \ell_i ) & = ( w . x ) ( u_m ) \, . \end{align*} Also in this case $w.x$ is encoded on $( n_m )_m$ in the $w$-th square, but a \lq\lq flag" $03$ is attached at the very beginning. Again it is easy to check that $\forall w \in {\bf F}_2 \, \forall n \in \mathbb N \left ( x^* ( w , n , \ell_i ) = ( w . x )^* ( 1_{{\bf F}_2} , n , \ell_i ) \right )$. \end{enumerate} So we may assume $g_i$ is bad and $0 < \mu ( w . x ) < \infty$. We will need the following result which is an immediate consequence of Proposition 4.6 of \cite{KST}. \begin{lemma} Let $T : X \to X$ be a Borel transformation on a standard Borel space $X$. There are pairwise disjoint Borel sets $X^{( 0 )}$, $X^{( 1 )}$, $X^{( 2 )}$ such that $X^{( 0 )} \cup X^{( 1 )} \cup X^{( 2 )} = X$ and such that for all $x \in X$ and $j \in \{ 0 , 1 , 2 \}$ \[ \left ( x \neq T ( x ) \ \& \ x \in X^{( j )} \right ) \implies T ( x ) \notin X^{( j )} \, . \] That is to say: if $x$ is not a fixed point of $T$ then $x$ and $T ( x )$ belong to different pieces of the partition $\{ X^{( 0 )} , X^{( 1 )} , X^{( 2 )} \}$. \end{lemma} For every $m \in \mathbb N$ the map $T_m : 2^{{\bf F}_2} \to 2^{{\bf F}_2}$, $x \mapsto z_m . x$ is a Borel transformation, where $( z_m )_m$ is as in the definition of bad quasi-shift. Let $X^{( 0 )}_m$, $X^{( 1 )}_m$, and $X^{( 2 )}_m$ be as in the lemma, with $T = T_m$. Then set \[ J_m ( x ) = \mbox{ the unique $j \in \{ 0 , 1 , 2 \}$ such that } x \in X^{( j )} _m \, . \] (Note that the definition of $J_m$ depends on $z_m$ and hence on the index $i$.) \begin{enumerate} \item[{\bf (3)}] If $g_i$ is bad and $0 < \mu ( w . x ) < \infty$ then \[ x^* ( w , n_m , \ell_i ) = \begin{cases} 3 & \quad \mbox{ if } m < \mu ( w . x ) - 1 , \\ J_{\mu ( w . x )} ( w . x ) & \quad \mbox{ if } m = \mu ( w . x ) - 1 \mbox{ or } m = \mu ( w . x ) , \\ 3 & \quad \mbox{ if } m > \mu ( w . x ) . \end{cases} \] In this case $x^*$ is {\em not\/} encoding $w . x$ on $\{ ( w , n_m , \ell_i ) \Mid m \in \mathbb N \}$: the particular definition of $x^* ( w , n_m , \ell_i )$ will be used to show that $x^* \circ g_i \neq y^*$, for any $y \in 2^{{\bf F}_2}$. \end{enumerate} We now want to check that the behaviour of $x^*$ on the set $\{ ( 1_{{\bf F}_2} , n_m , \ell_i ) \Mid m \in \mathbb N \}$ determines whether we are in case {\bf (1)}, {\bf (2)}, or {\bf (3)} above. \begin{claim} \label{coding} Let $i \geq 1$ be such that $g_i$ is a quasi-shift above $\ell_{i - 1}$ and let $x , y \in 2^{{\bf F}_2}$ be such that $\forall m \left ( x^* ( 1_{{\bf F}_2} , n_m , \ell_i ) = y^* ( 1_{{\bf F}_2} , n_m , \ell_i ) \right )$. Suppose the definition of $x^*$ on the set $\{ ( 1_{{\bf F}_2} , n_m , \ell_i ) \Mid m \in \mathbb N \}$ is as in case \[ {\bf (1)}, \quad {\bf (2)} , \quad \text{or} \quad {\bf (3)}, \] then also the definition of $y^*$ on $\{ ( 1_{{\bf F}_2} , n_m , \ell_i ) \Mid m \in \mathbb N \}$ is as in case \[ {\bf (1)}, \quad {\bf (2)} , \quad \text{or} \quad {\bf (3)} , \] respectively. Moreover the sequence $( x^* ( 1_{{\bf F}_2} , n_m , \ell_i ) )_m$ is of the form: \begin{itemize} \item an element of $2^{\mathbb N}$, if $x^*$ is defined as in {\bf (1)}, \item $03$ followed by an element of $2^{\mathbb N}$, if $x^*$ is defined as in {\bf (2)}, \item $( 3 , \dots , 3 , n , n , 3 , 3 , \dots )$ starting with a possibly empty sequence of $3$'s then two consecutive $n$'s with $n \in \{ 0 , 1 , 2 \}$, at position $\mu ( x ) - 1$ and $\mu ( x )$, and then $3$ from now on. This happens when $x^*$ is defined as in {\bf (3)}. \end{itemize} \end{claim} \begin{proof} If $x^*$ on $\{ ( 1_{{\bf F}_2} , n_m , \ell_i ) \Mid m \in \mathbb N \}$ is defined as in {\bf (1)} then $g_i$ must be good, hence also $y^*$ is defined as in {\bf (1)}. For the other cases notice that if $x^* ( 1_{{\bf F}_2} , n_0 , \ell_i ) \in \{ 1 , 2 , 3 \}$ then $x^*$ (and hence $y^*$) is defined as in {\bf (3)}, while if $x^* ( 1_{{\bf F}_2} , n_0 , \ell_i ) = 0$ then either $x^* ( 1_{{\bf F}_2} , n_1 , \ell_i ) =0$ and we are in case {\bf (3)} with $\mu = 1$ or else $x^* ( 1_{{\bf F}_2} , n_1 , \ell_i ) = 3$ and we are in case {\bf (2)}. \end{proof} \begin{remark} \label{Remark} The only reason for using the flag 03 before the sequence coding $w . x$ in {\bf (2)} is to be able to distinguish, assuming $g_i$ is bad, whether $( x^* ( 1_{{\bf F}_2} , n_m , \ell_i ) )_m$ is defined as in {\bf (2)} or {\bf (3)} only by looking at its first 2 elements. Had we been less stingy with the number of colours and used, say, 5 and 6 instead of 0 and 1 in {\bf (2)} then we could have avoided using the flag 03. \end{remark} We now consider the other case, namely \bigskip \framebox{\bf $g_i$ is not a quasi-shift above $\ell_{i - 1}$.} Let $w_0$, $n_0$, $k_0$, $w_0 '$, $n_0 '$, $k_0 '$ be as in cases (i)--(iii). We must define $x^* ( w , n , k )$ for all $w \in {\bf F}_2$, $n \in \mathbb N$ and $\ell_{i - 1} < k \leq \ell_i$. \medskip Suppose case (i) holds. If $k'_0 \leq \ell_{i - 1}$ then set \[ x^* ( w , n , k ) = \begin{cases} 0 & \quad \mbox{ if } x^* ( w' _0 , n' _0 , k' _0 ) = 4 , \\ 4 & \quad \mbox{ if } x^* ( w' _0 , n' _0 , k' _0 ) \leq 3 . \end{cases} \] (This is the only way for $x^*$ to achieve value 4.) If $\ell_{i - 1} < k'_0$ then set \[ x^* ( w , n , k ) = \begin{cases} 1 & \mbox{ if } k = k' _0 , \\ 0 & \mbox{ if } k \neq k' _0 . \end{cases} \] \medskip If case (ii) holds then proceed as in case (i). \medskip If case (iii) holds then set \[ x^* ( w , n , k ) = \begin{cases} 1 & \mbox{ if } n = n' _0 . \\ 0 & \mbox{ if } n \neq n' _0 , \end{cases} \] This concludes the definition of $x^*$. \bigskip We must check that $x \mapsto x^*$ is indeed a reduction. As the value of $x^* ( w , n , k )$ is independent of $x$ and $w$, when $\ell_{i - 1} < k \leq \ell_i$ and $g_i$ is not a quasi-shift, or else depends on $w . x$ only (when $g_i$ is a quasi-shift), then it is straightforward to check that \[ \forall v \in {\bf F}_2 \ \forall ( w , n , k ) \in M \left ( ( v . x )^* ( w , n , k ) = x^* \circ \hat{v} ( w , n , k ) \right ) . \] We will now show that \[ \exists i \left ( y^* = x^* \circ g_i \right ) \implies \exists v \in {\bf F}_2 \left ( y = v . x \right ) \] and hence $x \mapsto x^*$ is a reduction. The reader may find useful to refer to Figure 1 while checking the details. \begin{figure} \[ \xymatrix@C=10pt{ & &*+[F]{y^* = x^* \circ g_i} \ar@{-}[dl] \ar@{-}[dr] & & \\ & *+[F]{\txt{$g_i$ is a\\ quasi-shift}} \ar@{-}[dl] \ar@{-}[dr] & & *+[F]{\txt{$g_i$ is not\\ a quasi-shift}} \ar@{=>}[d] \\ *+[F]{\txt{$g_i$ is good}} \ar@{=>}[d] & &*+[F]{\txt{$g_i$ is bad}} \ar@{-}[dl] \ar@{-}[dr] & *+[F]{\txt{$x^* \circ g_i$ is not\\ in the range of\\ the reduction:\\ a contradiction!}} \\ *+[F]{y = w_\infty . x} &*+[F]{\mu ( w_0 . x ) \neq \infty} \ar@{=>}[d] & &*+[F]{\mu ( w_0 . x ) = \infty} \ar@{=>}[d] \\ &*+[F]{\txt{$x^* \circ g_i$ is not\\ in the range of\\ the reduction:\\ a contradiction!}} & & *+[F]{y = w_0 . x}} \] \caption{Plan of the Proof of Theorem \ref{rec}} \end{figure} Suppose $y^* = x^* \circ g_i$. \begin{claim} $g_i$ is a quasi-shift above $\ell_{i - 1}$. \end{claim} \begin{proof} Deny. Let $w_0$, $n_0$, $k_0$, $w_0'$, $n_0'$, and $k_0'$ be as in (i)--(iii) above. Notice that their choice as well as the decision as to which of (i)--(iii) we fall into as well as the definition of $x^* ( w , n , k )$ for $\ell_{i - 1} < k \leq k_0$ are independent of $x$. In particular $x^*$ and $y^*$ agree on $( w_0 , n_0 , k_0 )$. If we are in case (i) then \[ y^* ( w_0 , n_0 , k_0 ) = x^* ( w_0 ' , n_0 ' , k_0 ' ) \neq x^* ( w_0 , n_0 , k_0 ) \, , \] and if we are in case (ii) then \[ x^* ( w_0 , n_0 , k_0 ) = y^* ( w_0 ' , n_0 ' , k_0 ' ) \neq y^* ( w_0 , n_0 , k_0 ) \, , \] in both cases reaching a contradiction. If we are in case (iii) then \[ 0 = y^* ( w_0 , n_0 , \ell_i ) = x^* ( w_0 ' , n_0 ' , \ell_i ) = 1 \] a contradiction again. \end{proof} Therefore we may assume that \[ \framebox{$g_i$ is a quasi-shift.} \] Again we take cases. Suppose $w_\infty \in {\bf F}_2$ and $( n_m )_m \subseteq \mathbb N$ witness that $g_i$ is good. Then \begin{align*} y^* ( 1_{{\bf F}_2} , n_m , \ell_i ) & = x^* \circ g_i ( 1_{{\bf F}_2} , n_m , \ell_i ) \\ & = x^* ( w_\infty , n_m , \ell_i ) \\ & = ( w_\infty . x )^* ( 1_{{\bf F}_2} , n_m , \ell_i ) \, . \end{align*} As $g_i$ is good then both $( w_\infty . x )^*$ and $y^*$ are defined on $\{ ( 1_{{\bf F}_2} , n_m , \ell_i ) \Mid m \in \mathbb N \}$ as in {\bf (1)}, hence $\forall m \left ( y ( u_m ) = ( w_\infty . x ) ( u_m ) \right )$. Therefore \[ \framebox{$g_i \mbox{ is good } \implies y = w_\infty . x$.} \] So we may assume that $g_i$ is bad and let $( w_m )_m \subseteq {\bf F}_2$ and $( n_m )_m \subseteq \mathbb N$ witness this so that \[ \forall m \in \mathbb N \left ( y^* ( 1_{{\bf F}_2} , n_m , \ell_i ) = x^* \circ g_i ( 1_{{\bf F}_2} , n_m , \ell_i ) = x^* ( w_m , n_m , \ell_i ) \right ) . \] Suppose first $\mu ( w_0 . x ) = \infty$. Then by Claim \ref{facts} $\forall m ( ( w_m . x )^* = ( w_0 . x )^* )$ hence \[ x^* ( w_m , n_m , \ell_i ) = ( w_m . x )^* ( 1_{{\bf F}_2} , n_m , \ell_i ) = ( w_0 . x )^* ( 1_{{\bf F}_2} , n_m , \ell_i ) \, . \] As $( w_0 . x ) ^*$ is defined on $\{ ( 1_{{\bf F}_2} , n_m , \ell_i ) \Mid m \in \mathbb N \}$ as in {\bf (2)} then $y^*$ is defined on $\{ ( 1_{{\bf F}_2} , n_m , \ell_i ) \Mid m \in \mathbb N \}$ as in {\bf (2)} and hence $\forall m \left ( y ( u_m ) = w_0 . x ( u_m ) \right )$. Therefore \[ \framebox{$\mu ( w_0 . x ) = \infty \implies y = w_0 . x$.} \] Suppose now $1 \leq \mu ( w_0 . x ) = m < \infty$. Then by Claim \ref{facts} \[ \forall j < m \left ( \mu ( w_j . x) = m \ \&\ J_m ( w_j . x ) = J_m ( w_0 . x ) \right ) \quad \mbox{and} \quad \mu ( w_m . x ) \leq m \, . \] Using {\bf (3)}, the first $m$ elements of the sequence $( x^* \circ g_i ( 1_{{\bf F}_2} , n_j , \ell_i ) )_j$ are $( 3 , \dots , 3 , J_m ( w_0 . x ) )$. If $m > 1$ (so that the sequence starts with 3) or if $J_m ( w_0 . x ) \neq 0$ then by Claim \ref{coding} the next element must be \[ x^* ( w_m , n_m , \ell_i ) = J_m ( w_0 . x ) \in \{ 0 , 1 , 2 \} \, . \] If $m = 1$ and $J_m ( w_0 . x ) = 0$ then the sequence starts with 0 hence the next element can only be 0 or 3, i.e., \[ x^* ( w_m , n_m , \ell_i ) \in \{ 0 , 3 \} \, . \] In order to compute this value and eventually reach a contradiction we must consider two cases. Suppose $\mu ( w_m . x ) = m$. Since $w_0 . x = w_{m - 1} . x$ and $z_m . w_0 . x = w_m .x$ are distinct, they belong to different $X_m^{( j )}$'s and therefore, using {\bf (3)}, \[ x^* ( w_m , n_m , \ell_i ) = J_m ( w_m . x ) \notin \{ J_m ( w_0 . x ) , 3 \} \, , \] a contradiction. Suppose $0 < \mu ( w_m . x ) < m$. Then $m > 1$ and by {\bf (3)} \[ x^* ( w_m , n_m , \ell_i ) = 3 \neq J_m ( w_0 . x ) \, , \] a contradiction. Therefore we have shown that \[ \framebox{$1 \leq \mu ( w_0 . x ) < \infty \implies x^* \circ g_i$ is not in the range of the reduction.} \] This concludes the proof. \end{proof} Notice that for $k \geq 5$ or $k = \mathbb N$ and $G$ as in the theorem, the inclusion map $5^{\mathbb N} \hookrightarrow k^{\mathbb N}$ witnesses $\cong^k_G$ is universal. Focusing on Rec, the group of recursive permutations, one can show that \[ \cong^{\mathbb N} _{\rm Rec} \restriction \{ x \in {\mathbb N} ^{\mathbb N} \Mid x : \mathbb N \twoheadrightarrow \mathbb N \mbox{ is onto}\} \] is universal. To see this assign to each non-empty subset $S \subseteq 5 = \{ 0 , \dots , 4 \}$ an integer $\rho ( S ) > 0$, and consider the map $5^{\mathbb N} \to \{ x \in {\mathbb N} ^{\mathbb N} \Mid x : \mathbb N \twoheadrightarrow \mathbb N \mbox{ is onto}\}$, $x \mapsto x^*$, defined as follows: on the even integers we copy $x$, i.e., $\forall n \left ( x^* ( 2 n ) = x ( n ) \right )$ and on the odd integers we start with $\rho ( \mbox{range} ( x ) )$-many $5$'s followed by the increasing enumeration of $\mathbb N \setminus ( \mbox{range} ( x ) \cup \{ 5 \} )$. It is easy to check that $x^*$ is indeed onto and that $x \mapsto x^*$ is Borel. If $x \circ f = y$ for some recursive $f$ then letting $g ( 2 n + 1 ) = 2 n + 1$ and $g ( 2 n ) = 2 f ( n )$ we have that $x^* \circ g = y^*$. Suppose instead $x^* \circ f = y^*$ for some recursive bijection $f$. Since the number of 5's in $x^*$ and in $x^* \circ f = y^*$ are the same, then $\mbox{range} ( x ) = \mbox{range} ( y )$ hence $f$ restricted to the even numbers must be a bijection. Letting $h ( n ) = \frac{1}{ 2} f ( 2 n )$ we see that $x \circ h = y$. Therefore $x \mapsto x^*$ is a reduction of $\cong^5_{\rm Rec}$ to $\cong_{\rm Rec} ^{\mathbb N} \restriction \{ x \in {\mathbb N} ^{\mathbb N} \Mid x : \mathbb N \twoheadrightarrow \mathbb N \mbox{ is onto}\}$. By extracting the salient features of Rec used above we get \begin{corollary} Let $G_0 \subseteq G \subseteq S_\infty$ be as in the theorem. Suppose $G$ has the following closure property: \begin{enumerate} \item[-] if $f \in G$ then $g \in G$ where $g ( 2 n + 1 ) = 2 n + 1$ and $g ( 2 n ) = 2 f ( n )$, \item[-] if $f \in G$ and $f$ is a bijection when restricted to the set of even numbers (i.e., $\forall n \, \exists m \left ( f ( 2 m ) = 2 n \right )$ and $\forall n \, \exists m \left ( f ( 2 n ) = 2 m \right )$) then $h \in G$ where $h ( n ) = \frac{1}{ 2} f ( 2 n )$. \end{enumerate} Then $\cong_G^{\mathbb N} \restriction \{ x \in {\mathbb N} ^{\mathbb N} \Mid x : \mathbb N \twoheadrightarrow \mathbb N \mbox{ is onto}\}$ is universal. \end{corollary} Let ${\mathcal L}$ be a language consisting of one binary relation symbol and let $X_{\mathcal L} = 2^{\mathbb N ^2}$ be the space of all $\mathcal L$-structures with universe $\mathbb N$. Let ${\rm Eq} ( k ) \subseteq X_{\mathcal L}$ be the set of all structures which are models for equivalence relations whose equivalence classes are of size at most $k$, that is $x \in {\rm Eq} ( k )$ iff the relation $E^x$ on $\mathbb N$ defined by \[ n E^x m \iff x ( n , m ) = 1 \] is an equivalence relation on $\mathbb N$ and $\forall n \in \mathbb N \left ( | [ n ]_{E^x} | \leq k \right )$. For $x , y \in X_{\mathcal L}$ set $x \cong^{\mathcal L} _G y$ just in case the models $\langle \mathbb N , E^x \rangle$ and $\langle \mathbb N , E^y \rangle$ are isomorphic via a bijection in $G$. For $G \subseteq S_\infty$ let $\sim_G$ denote the conjugation relation on $S_\infty$ via elements in $G$ \[ x \sim_G y \iff \exists g \in G \left ( g^{- 1} \circ x \circ g = y \right ) . \] Let also ${\sim_G^k} = {}\sim_G \restriction \{ x \in S_\infty \Mid x$ is a product of cycles of length $\leq k \}$. A group $G \subseteq S_\infty$ is {\em closed under pairing\/} if there is a pairing function, i.e., a bijection $j : \mathbb N ^2 \to \mathbb N$ with inverses $( j ( n , m ) )_0 = n$ and $( j ( n , m ) )_1 = m$ such that: For every $g \in G$ the bijection $h \in S_\infty$ defined by \[ h ( j ( n , m ) ) = j ( g ( n ) , m ) \] is in $G$, and if \[ f ( n ) = ( g ( j ( n , 0 ) ) )_0 \] is a bijection, then $f$ is also in $G$. For example ${\rm Rec}$ is closed under pairing. \begin{proposition} Let $G \subseteq S_\infty$ be a countable group closed under pairing. Then \[ {\cong^k_G} \ \sqsubseteq _{\rm c} \ {\cong^{\mathcal L} _G \restriction {\rm Eq} ( k + 1 )} \] that is to say: the equivalence relation given by the right action of $G$ on $k^{\mathbb N}$ is continuously embeddable into the $G$-isomorphism relation between equivalence relations on $\mathbb N$ with equivalence classes of size $\leq k + 1$. Similarly $\cong^k_G$ continuously embeds into conjugacy on $S_\infty$ via elements of $G$ restricted to products of cycles of size $\leq k + 1$: \[ {\cong^k_G} \ \sqsubseteq_{\rm c} \ {\sim_G^{k + 1}} \, . \] In particular for all $G_0 \subseteq G \subseteq S_\infty$ as in the theorem $\cong^{\mathcal L}_G \restriction {\rm Eq} ( 6 )$ and $\sim_G^6$ are both universal. \end{proposition} \begin{proof} Let $\vartheta : k^{\mathbb N} \to {\rm Eq} ( k + 1 )$ be defined by \[ j ( n , m ) E^{\vartheta ( x ) } j ( n' , m' ) \quad \iff \quad n = n' \ \&\ \left ( m = m' \ \vee\ m , m' \leq x ( n ) + 1 \right ) \] where $j$ is the pairing function for $G$. (It is most convenient to visualize $E^{\vartheta ( x )}$ as the equivalence relation on $\mathbb N^2$ obtained by connecting on each vertical line $\{ ( n , m ) \Mid m \in \mathbb N \}$ all the points $\leq x ( n ) + 1$.) It is immediate to check that $\vartheta ( x ) \in {\rm Eq} ( k + 1 )$ and that $\vartheta$ is continuous and injective. Suppose first $x , y \in k^{\mathbb N}$ and $x \circ g = y$ for some $g \in G$. Let $h \in G$ be defined by $h ( j ( n , m ) ) = j ( g ( n ) , m )$. Then \begin{align*} h ( j ( n , m ) ) E^{\vartheta ( x )} h ( j ( n' , m' ) ) & \iff j ( g ( n ) , m ) E^{\vartheta ( x )} j ( g ( n' ) , m' ) \\ & \iff j ( n , m ) E^{\vartheta ( y )} j ( n' , m' ) \end{align*} that is $\vartheta ( y ) \cong^{\mathcal L} _G \vartheta ( x )$ via $h$. Conversely suppose $\vartheta ( y ) \cong^{\mathcal L} _G \vartheta ( x )$ via some $g \in G$. Let $f \in G$ be defined by $f ( n ) = ( g ( j ( n , 0 ) ) )_0$. We must show that $x \circ f = y$. Fix $n \in \mathbb N$. Since $[ j ( n , 0 ) ]_{E^{\vartheta ( y )}}$ has $y ( n ) +1$-many elements and $g$ is an isomorphism between $E^{\vartheta ( y )}$ and $E^{\vartheta ( x )}$ then $[ g ( j ( n , 0 ) ) ]_{E^{\vartheta ( x )}}$ has also $y ( n ) +1$-many elements. In particular $[ g ( j ( n , 0 ) ) ]_{E^{\vartheta ( x )}}$ is not a singleton. But $g ( j ( n , 0 ) ) = j ( f ( n ) , \ell )$ for some $\ell$, so $[ j ( f ( n ) , \ell ) ]_{E^{\vartheta ( x )}} = [ j ( f ( n ) , 0 ) ]_{E^{\vartheta ( x )}}$ has $x ( f ( n ) ) + 1$-many elements. Therefore $y ( n ) = x ( f ( n ) )$, which is what we had to prove. For $\sim_G^{k + 1}$ we use essentially the same reduction: for $x \in k^{\mathbb N}$ let $\varphi ( x ) \in S_\infty$ be defined by $\varphi ( x ) = \prod_n c _ n ( x )$ where $ c_n ( x )$ is the cycle \[ \xymatrix{ j ( n , 0 ) \ar@{|->}[r] & j ( n , 1 ) \ar@{|->}[r] & {\ \cdots \ } \ar@{|->}[r] & j ( n , x ( n ) + 1 ) \ar@/^1pc/@{|->} [lll]} . \] \medskip \noindent It is immediate to check that $x \cong ^k _G y \iff \varphi ( x ) \sim_G ^{k + 1} \varphi ( y )$. \end{proof} Even if the theorem holds for $k = 2$ (as we conjecture) the proposition above does not yield any information about the universality of $\cong^{\mathcal L}_G \restriction {\rm Eq} ( 2 )$. We can still though relate this equivalence relation to $\sim_G$. For $x \in {\rm Eq} ( 2 )$ let $x^* \in S_\infty$ be defined by \[ x^* ( n ) = \begin{cases} m & \quad \mbox{ if } [ n ]_{E^x} = \{ n , m \} \mbox{ and } n \neq m , \\ n & \quad \mbox{ if } [ n ]_{E^x} = \{ n \} . \end{cases} \] Then $x^* \in I =^{\rm def} \{ f \in S_\infty \Mid f \circ f = {\rm id}\}$, the set of all involutions, and the map ${\rm Eq} ( 2 )\to I$, $x \mapsto x^*$, is clearly a Borel bijection. Moreover if $G \subseteq S_\infty$ is a subgroup, $g \in G$, and $x , y \in {\rm Eq} ( 2 )$ then $g : \langle \mathbb N , E^x \rangle \to \langle \mathbb N , E^y \rangle$ is an isomorphism iff $g \circ x^* \circ g^{- 1} = y^*$. Therefore we have proved \begin{proposition} Let $G \subseteq S_\infty$ be a subgroup. The logic action of $G$ on ${\rm Eq} ( 2 )$ is isomorphic to the conjugacy of $G$ on elements of $I$. In particular \[ {\cong^{\mathcal L}_G \restriction {\rm Eq} ( 2 )} \ \cong_{\rm B} \ {\sim_G \restriction I} \, . \] \end{proposition} \section{Conjugacy of subgroups} We will now prove Theorem \ref{ourtheorem}. The proof will use a combination of the techniques used in proving \ref{rec} together with a few facts about free groups. Let ${\bf F} ( X )$ be the free group on the set $X \neq \emptyset$, let $x \in X$ and let $w \in {\bf F} ( X )$. Let $x_1^{k_1} \cdots x_n ^{k_n}$ be the unique reduced word for $w$. Then we say that $w$ {\em starts\/} with $x_1$ and {\em ends\/} with $x_n$. Whenever we write \lq\lq $vw$ is a reduced word" we mean that both $v$ and $w$ are already written as reduced words, and for no $x \in X$, $v$ ends with $x$ and $w$ starts with $x$. We say that {\em $x^k$ occurs in $w$,\/} ($k \in \mathbb Z \setminus \{ 0 \}$) if $w = v_0 x^k v_1$ and $v_0 x^k v_1$ is a reduced word, i.e., $v_0$ and $v_1$ are reduced and neither $v_0$ ends with $x$ nor $v_1$ begins with $x$. If $x^k$ occurs in $w$ then we say that $x$ is a generator in $w$. It is easy to see that if $x$ is a generator in $w$, then it is a generator in every $w^n$, for $n \neq 0$. A word $w$ is symmetric if it can be written in reduced form as $w = v_0 x^k v_0 ^{- 1}$; otherwise it is asymmetric. \begin{lemma} \label{limsup} If $w \in {\bf F} ( X )$ is asymmetric then there is a fixed bound $M$ depending on $w$ such that if $x^k$ occurs in any $w^n$ then $| k | \leq M$, i.e., \[ \exists M > 0 \, \forall x \in X \, \forall k \in \mathbb Z \setminus \{ 0 \} \, \forall n \left ( x^k \mbox{ occurs in } w^n \implies | k | \leq M \right ) . \] \end{lemma} \begin{proof} It is enough to show that for any $x \in X$ which is a generator of $w$ there is an $M_x$ such that if $x^h$ occurs in $w^n$, then $| h | \leq M_x$, so that we can set \[ M = \sup \{ M_x \Mid x \mbox{ is a generator in } w \} \, . \] Let $x$ be a generator in $w$ so that $w = v_0 x^k v_1$ is a reduced word and $v_1 \neq v_0^{- 1}$. Then the reduced form of $v_1 v_0$ cannot start and end with $x$ since otherwise either $v_1$ would have to start with $x$ or $v_0$ would have to end with $x$, hence $v_0 x^k v_1$ would not be reduced. Consider the product \[ w^n = v_0 \fbox{$x^k$} v_1 \cdot v_0 \fbox{$x^k$} v_1 \cdots v_0 \fbox{$x^k$} v_1 \, . \] After the reduction: \begin{enumerate} \item[-] if $v_1 \cdot v_0$ in reduced form does not start or end with $x$, then the boxed occurrences of $x^k$ remain unchanged, so let \[ M_x = \max \left ( | k | , \sup \{ | h | \Mid x^h \mbox{ occurs in $v_0$, or in $v_1$, or in } v_1 v_0 \} \right ) , \] \item[-] if $v_1 \cdot v_0$ in reduced form is $u x^h$ or $x^h u$, then the first (respectively: the last) boxed occurrence of $x^k$ remains unchanged, so let \[ M_x = \max \left ( | k | , | k + h | , \sup \{ | j | \Mid x^j \mbox{ occurs in $v_0$, or in $v_1$, or in } u \} \right ) . \] \end{enumerate} This completes the proof. \end{proof} We now start proving theorem \ref{ourtheorem}. \begin{proof} Since inside every free group on two generators there is a copy of the free group on three generators, pick $a , b , c \in G$ independent elements so that $\langle a , b , c \rangle$ is a free group on 3 generators. Let ${\bf F}_3 = \langle a , b , c \rangle$ be this particular realization of the free group on 3 generators and let ${\bf F}_2 = \langle a , b \rangle \subset {\bf F}_3$. We want to construct copy of ${\bf F}_\omega$, the free group of rank $\aleph_0$, inside ${\bf F}_3$. We need the following lemma. \begin{lemma} \label{4.2} Let $w_1 , \dots , w_n \in {\bf F}_2$ be distinct. Then \[ \langle w_1 c w_1 ^{- 1} , \dots , w_n c w_n ^{- 1} \rangle \] is a free group on $n$ generators. In particular if $( w_n )_n \subseteq {\bf F}_2$ are all distinct then $\langle w_1 c w_1 ^{- 1} , w_2 c w_2 ^{- 1} , \dots \rangle$ is a free group of rank $\aleph_0$. \end{lemma} \begin{proof} Choose new letters $\sigma_1$, \dots , $\sigma_n$, and let $\langle \sigma_1 , \dots , \sigma_n \rangle$ be the free group of rank $n$ generated by them. It is enough to show that ${\rm ker} (\varphi )$ is null, where $\varphi : \langle \sigma_1 , \dots , \sigma_n \rangle \twoheadrightarrow \langle w_1 c w_1 ^{- 1} , \dots , w_n c w_n ^{- 1} \rangle$ is the epimorphism induced by the map $\sigma_i \mapsto w_i c w_i^{- 1}$. Let $v = \sigma_{i_1} ^{k_1} \sigma_{i_2} ^{k_2} \cdots \sigma_{i_m} ^{k_m}$ be a reduced word of $\langle \sigma_1 , \dots , \sigma_n \rangle$. If \[ \varphi ( v ) = w_{i_1} c ^{k_1} w_{i_1}^{- 1} \cdot w_{i_2} c ^{k_2} w_{i_2}^{- 1} \cdots w_{i_m} c ^{k_m} w_{i_m}^{- 1} = 1_{{\bf F}_2} \] and $m > 1$, then $w_{i_j} = w_{i_{j + 1}}$ for all $1 \leq j < m$, hence $\sigma_{i_j} = \sigma_{i_{j + 1}}$. Therefore $m = 1$, $v = \sigma_{i_1}^{k_1}$ and hence $\varphi ( v ) = w_{i_1} c^{k_1} w_{i_1}^{- 1} = 1_{{\bf F}_2}$ implies $k_1 =0$. This contradicts the assumption that $v$ is reduced. \end{proof} Define also the free group on two generators $\tilde{\bf F}_2 = \langle a^2 , b^2 \rangle \subset {\bf F}_2$, and let $w \mapsto \tilde{w}$ be the isomorphism ${\bf F}_2 \to \tilde{\bf F}_2$ given by $a \mapsto a^2$ and $b \mapsto b^2$. For any $w \in {\bf F}_2$ and $n \in {\mathbb Z}$ let \[ \gamma ( w , n ) = \tilde{w}^{-1} b a^{2n} c a^{- 2n} b^{- 1} \tilde{w} \in {\bf F}_3 \, . \] Let $\Gamma = \bigcup_{w \in {\bf F}_2} \Gamma_w \subset {\bf F}_3$, where $\Gamma_w = \{ \gamma ( w , n ) \Mid n \in {\mathbb Z} \}$. Suppose $\gamma ( w , n ) = \gamma ( z , m )$. Then \[ \tilde{w}^{- 1} b a^{2 n} c a^{- 2 n} b^{- 1} \tilde{w} = \tilde{z}^{- 1} b a^{2 m} c a^{- 2 m} b^{- 1} \tilde{z} \, . \] As there is only one occurrence of $c$ in both sides of the equation then \[ \tilde{w}^{- 1} b a^{2 n} = \tilde{z}^{- 1} b a^{2 m} \, . \] As $\tilde{w} , \tilde{z} \in \tilde{\bf F}_2$ then it is easy to see that $w = z$ and $n = m$. Therefore \[ \forall w , z \in {\bf F}_2 \left ( w \neq z \implies \Gamma_z \cap \Gamma_w = \emptyset \right ) . \] Since $\gamma ( w , n ) = ( \tilde{w} ^{-1} b a^{2n} ) c ( \tilde{w} ^{-1} b a^{2n} )^{- 1}$ and $\tilde{w} ^{-1} b a^{2n} \in {\bf F}_2$, then \ref{4.2} implies that $\Gamma$ is a countable set of independent elements and \[ {\bf F}_\omega = \langle \Gamma \rangle \subset {\bf F}_3 \subseteq G \] is a free group on $\aleph_0$-many generators. We now concentrate on subgroups of ${\bf F}_\omega$ and from now on {\em words\/} will mean {\em words built from elements in $\Gamma$}.\/ Notice that in our set-up ${\bf F}_2 \not\subseteq {\bf F}_\omega$. The plan is to associate, in a Borel way, to each $x \in 2^{{\bf F}_2}$ a group $H ( x ) \subseteq {\bf F}_\omega$ such that $H ( x ) \cong {\bf F}_\omega$ and \begin{align*} & \forall w \in {\bf F}_2 \, \forall x \in 2^{{\bf F}_2} \left ( H ( w . x ) = \tilde{w} H ( x ) \tilde{w}^{- 1} \right ) \\ & \forall g \in G \, \forall x , y \in 2^{{\bf F}_2} \left ( H ( y ) = g H ( x ) g^{- 1} \implies \exists w \in {\bf F}_2 ( w . x = y ) \right ) . \end{align*} This implies that the shift action of ${\bf F}_2$ on $2^{{\bf F}_2}$ is reducible to $E_{\rm c} ( G , {\rm Sgr} ( G ) )$, proving the universality of the latter. The group $H ( x )$ will be given via an infinite set ${\mathcal G} ( x )$ of generators so that \begin{enumerate} \item[(1)] ${\mathcal G} ( x )$ is an independent set of elements of ${\bf F}_\omega$ and $ \langle {\mathcal G } ( x ) \rangle = H ( x ) \cong {\bf F}_\omega$. \end{enumerate} In order to define the ${\mathcal G} ( x )$'s we need to re-arrange the enumeration of $\Gamma$ a bit: fix a bijection $j : \mathbb N ^2 \to \mathbb Z$ and set \[ \alpha ( w , n , m ) = \gamma ( w , j ( n , m ) ) \, . \] The third component of the indexing gives the {\em level\/} of the elements of $\Gamma$, so we say that $\alpha ( w , n , m )$ is of level $m$. Fix for every $i > 0$ an infinite set $S_i \subseteq {\mathbb P}=$ the set of all primes, such that $i \neq j \implies S_i \cap S_j = \emptyset$. As in the proof of \ref{rec} an increasing sequence of integers $( \ell_i )_{i \in \mathbb N}$ with $\ell_0 = - 1$ will be defined inductively. At stage $i$ the only elements added to ${\mathcal G} ( x )$ will be of the form $\gamma^p$, where $\gamma \in \Gamma$ is of level between $\ell_{i - 1}$ and $\ell_i$ and $p$ is some unique element of $S_i$; moreover some such element should be added at this stage: \begin{enumerate} \item[(2)] $\begin{array}[t]{r} \forall z \in {\mathcal G } ( x ) \, \exists \alpha ( w , n , m ) \in \Gamma \, \exists p \left ( \alpha ( w , n , m )^p = z \ \&\ \left ( \ell_{i - 1} < m \leq \ell_i \implies p \in S_i \right ) \right ) \\ \&\ \forall \gamma \in \Gamma \, \forall p , q \in \mathbb P ( \gamma^p , \gamma^q \in {\mathcal G} ( x ) \implies p = q ) \, . \end{array}$ \item[(3)] $\exists \alpha ( w , n , m ) \in \Gamma \, \exists p \in S_i \left ( \ell_{i - 1} < m \leq \ell_i \ \&\ \alpha ( w , n , m )^p \in {\mathcal G} ( x ) \right )$. \item[(4)] $\forall w \in {\bf F}_2 \left ( \tilde{w} {\mathcal G} ( x ) \tilde{w}^{- 1} = {\mathcal G} ( w . x ) \right )$. \item[(5)] If $w \in H ( x )$ and $\alpha ( w , n , m ) ^k$ occurs in $w$ and $\ell_{i - 1} < m \leq \ell_i$ then \[ \exists p \in S_i \left ( p | k \ \&\ \alpha ( w , n , m )^p \in {\mathcal G } ( x ) \right ) . \] In particular $\Gamma \cap {\mathcal G} ( x ) = \emptyset$. By (2) the prime $p$ is unique. \item[(6)] If $vw$ is a reduced word then $vw \in H ( x ) \implies v , w \in H ( x )$. \end{enumerate} Notice that Properties (2) and (3) imply Properties (1) and (5), Property (6) follows from Property (5), and as $\tilde{z}^{- 1} \gamma ( w , n )^k \tilde{z} = \gamma ( w z , n )^k$ for any $z , w \in {\bf F}_2$ and $n , k \in \mathbb Z$, then Property (4) will hold. We now start the construction. In analogy with the proof of \ref{rec}, say that an element $g \in G$ is a {\em quasi-shift above $\ell$} if \begin{multline*} \forall w , n \big ( g^{- 1} \cdot \alpha ( w , n , \ell + 1 ) \cdot g \in {\bf F}_\omega \ \&\ \text{every generator from } \Gamma \text{ in } g^{- 1} \cdot \alpha ( w , n , \ell + 1) \cdot g \\ \text{ is either of the form }\alpha ( z , m , k ) \text{ with $k \leq \ell$ or else of the form } \alpha ( z , n , \ell + 1 ) \\ \&\ \exists z \, \alpha ( z , n , \ell + 1 ) \text{ is a generator in } g^{- 1} \cdot \alpha ( w , n , \ell + 1 ) \cdot g \big ) \, . \end{multline*} Fix an enumeration $( g_i )_{i \geq 1}$ of $G$. Set $\ell_0 = {- 1}$ and suppose $\ell_{i - 1}$ has been defined for some $i \geq 1$. We now distinguish two cases: \bigskip $\bullet$\quad $g_i$ is not a quasi-shift above $\ell_{i - 1}$. Then letting $k_0 = \ell_{i - 1} + 1$, we have the following possibilities: \begin{enumerate} \item[(i)] $\exists w_0 , n_0 \left ( g_i ^{- 1} \cdot \alpha ( w_0 , n_0 , k_0 ) \cdot g_i \notin {\bf F}_\omega \right )$. \item[(ii)] Case (i) fails and \[ \exists w_0 , n_0 , w_0 ' , n_0 ' , k_0 ' \big ( k_0 ' > k_0 \ \&\ \alpha ( w_0 ' , n_0 ' , k_0 ' ) \mbox{ is a generator in } g_i ^{- 1} \cdot \alpha ( w_0 , n_0 , k_0 ) \cdot g_i \big ) \, . \] \item[(iii)] Cases (i) and (ii) fail and \[ \exists w_0 , n_0 , w_0 ' , n_0 ' \big ( n_0 \neq n_0 ' \ \&\ \alpha ( w_0 ' , n_0 ' , k_0 ) \mbox{ is a generator in } g_i ^{- 1} \cdot \alpha ( w_0 , n_0 , k_0 ) \cdot g_i \big ) \, . \] \item[(iv)] Cases (i), (ii), and (iii) fail and \[ \exists w_0 , n_0 \, \forall w_0 ' , n_0 ' , k_0 ' \big ( \alpha ( w_0 ' , n_0 ' , k_0 ' ) \mbox{ is a generator in } g_i ^{- 1} \cdot \alpha ( w_0 , n_0 , k_0 ) \cdot g_i \implies k_0 ' < k_0 \big ) \, . \] \end{enumerate} Then set $\ell_i = \max ( k_0 , k_0 ' )$. (Notice that if $g_i$ is not a quasi-shift above $\ell_{i - 1}$ because of (iv) then all of the generators of $g_i^{- 1} \cdot \alpha ( w_0 , n_0 , k_0 ) \cdot g_i$ are of level $< k_0$.) \bigskip $\bullet$ \quad Otherwise, that is: $g_i$ is a quasi-shift above $\ell_{i - 1}$. In this case set $\ell_i = \ell_{i - 1} + 1$. \bigskip Suppose $g_i$ is a quasi-shift above $\ell_{i - 1}$. We say that $g_i$ is {\em good\/} if there is an increasing sequence of natural numbers $( n_m )_m$ and a $w_\infty \in {\bf F}_2$ such that \[ \alpha ( w_\infty , n_m , \ell_i ) \mbox{ is a generator in } g_i ^{- 1} \cdot \alpha ( 1_{{\bf F}_2} , n_m , \ell_i ) \cdot g_i \, . \] If $g_i$ is not good then it is called {\em bad.\/} In this case there is an increasing sequence of natural numbers $( n_m )_m$ and a sequence of distinct $( w_m )_m$ in ${\bf F}_2$ such that \[ \forall m \in {\mathbb N} \left ( \alpha ( w_m , n_m , \ell_i ) \mbox{ is a generator in } g_i ^{- 1} \cdot \alpha ( 1_{{\bf F}_2} , n_m , \ell_i ) \cdot g_i \right ) . \] Let also $( z_m )_{m \geq 1}$, $\mu$ and $J_m$ be defined as in the proof of \ref{rec}. Finally we define the map $ x \mapsto {\mathcal G} ( x )$, and hence the reduction $H : 2^{{\bf F}_2} \to {\rm Sgr} ( G )$, $x \mapsto H ( x )$, so that Properties (1)--(6) hold. \bigskip \framebox{\bf $g_i$ is not a quasi-shift above $\ell_{i - 1}$.} Let $w_0$, $n_0$, $k_0$, $w_0 '$, $n_0 '$, $k_0 '$ be as in cases (i)--(iv). \medskip Suppose case (i) holds. Then $\ell_i = k_0$. Let $r$ be the least positive integer such that $g_i ^{- 1} \cdot \alpha ( w_0 , n_0 , k_0 ) ^r \cdot g_i \in {\bf F}_\omega$, if such integer exists, or $r = 0$ otherwise. Let $p = \min ( S_i \setminus \{ r \} )$ be the least element of $S_i$ different from $r$. We now require in our construction that \[ \forall x \in 2^{{\bf F}_2} \, \forall w \in {\bf F}_2 \left ( \alpha ( w , n_0 , \ell_i ) ^p \in {\mathcal G} ( x ) \right ) . \] \medskip Suppose case (ii) holds. Then $k_0 = \ell_{i - 1} + 1 < \ell_i$. Let $p = \min ( S_i )$ and set \[ \forall x \in 2^{{\bf F}_2} \, \forall w \in {\bf F}_2 \left ( \alpha ( w , n_0 , k_0 ) ^p \in {\mathcal G} ( x ) \right ) . \] \medskip Suppose case (iii) or (iv) holds. Let $p = \min ( S_i )$ and set \[ \forall x \in 2^{{\bf F}_2} \, \forall w \in {\bf F}_2 \left ( \alpha ( w , n_0 , \ell_i ) ^p \in {\mathcal G} ( x ) \right ) . \] For $k \in ( \ell_{i - 1} , \ell_i ]$ and $n \in \mathbb N$, $p \in \mathbb P$ place $\alpha ( w , n , k ) ^p$ in ${\mathcal G} ( x )$ only if required by the cases above. We now consider the other case, namely \bigskip \framebox{\bf $g_i$ is a quasi-shift above $\ell_{i - 1}$.} There are two possibilities. \bigskip $\bullet$ For some $\alpha ( w_0 , n_0 , \ell_i ) \in \Gamma$, the reduced word $v$ obtained from $g_i ^{- 1} \cdot \alpha ( w_0 , n_0 , \ell_i ) \cdot g_i$ is {\em either\/} asymmetric {\em or else\/} it is symmetric of the form $v_1 \cdot \alpha ( w_0' , n_0' , k )^m \cdot v_1^{-1}$ with $k < \ell_i$ and $m \neq 0$. In either case, by Lemma \ref{limsup} or by inspection, there is $M$ such that \[ \forall r \left ( \alpha ( z , n_0 , \ell_i )^k \mbox{ occurs in } v^r \implies | k | \leq M \right ) . \] When this happens $g_i$ is said to be {\bf bounded}. Let $p$ be the least element in $S_i$ larger than $M$ and set \[ \forall x \in 2^{{\bf F}_2} \, \forall w \in {\bf F}_2 \left ( \alpha ( w , n_0 , \ell_i )^p \in {\mathcal G} ( x ) \right ) . \] \bigskip $\bullet$ Otherwise $\forall w \in {\bf F}_2 \, \forall n \in {\mathbb N} \, \exists z \in {\bf F}_2 \, \exists u \in {\bf F}_\omega$ such that \[ g_i ^{- 1} \cdot \alpha ( w , n , \ell_i ) \cdot g_i = u \cdot \alpha ( z , n , \ell_i )^{r ( w , n )} \cdot u ^{- 1} \] where $r ( w , n ) \in {\mathbb Z} \setminus \{ 0 \}$. In this case $g_i$ is said to be {\bf unbounded}. \medskip {\bf Case 1:} $\exists w_0 , n_0 \left ( | r ( w_0 , n_0 ) | > 1 \right )$, that is, for some $w_0 , n_0 , z , u$ \[ g_i ^{- 1} \cdot \alpha ( w_0 , n_0 , \ell_i ) \cdot g_i = u \cdot \alpha ( z , n_0 , \ell_i )^r \cdot u ^{- 1} \] with $r = r ( w_0 , n_0 )$ and $| r | > 1$. Then let $p = \min (S_i )$ and set \[ \forall x \in 2^{{\bf F}_2} \, \forall w \in {\bf F}_2 \left ( \alpha ( w , n_0 , \ell_i )^p \in {\mathcal G} ( x ) \right ) . \] \medskip {\bf Case 2:} $\forall w \in {\bf F}_2 \, \forall n \in {\mathbb N} \left ( | r ( w , n ) | = 1 \right )$, that is \[ \forall w \in {\bf F}_2 \, \forall n \in {\mathbb N} \, \exists z \in {\bf F}_2 \, \exists u \in {\bf F}_\omega \left ( g_i ^{- 1} \cdot \alpha ( w , n , \ell_i ) \cdot g_i = u \cdot \alpha ( z , n , \ell_i )^{\pm 1} \cdot u ^{- 1} \right ) . \] Then we can mimic the construction of \ref{rec}. Fix an enumeration without repetitions $( u_m )_m$ of ${\bf F}_2$. Let $p_0 , \dots , p_5$ be the first six elements of $S_i$. We distinguish three possibilities. \medskip $\bullet$ $g_i$ is good. Then $\exists w_\infty \, \exists ( n_m )_m \, \exists ( v_m )_m $ such that $( n_m )_m$ is increasing and $g_i ^{- 1} \cdot \alpha ( 1_{{\bf F}_2} , n_m , \ell_i ) \cdot g_i = v_m \cdot \alpha ( w_\infty , n_m , \ell_i )^{\pm 1} \cdot v_m ^{-1}$. By thinning down the sequence we may assume that the exponent is constant, say $=1$. Set \begin{align*} \alpha ( w , n_m , \ell_i )^{p_1} \in {\mathcal G} ( x ) & \iff w . x ( u_m ) = 1 \\ \alpha ( w , n , \ell_i )^{p_0} \in {\mathcal G} ( x ) & \iff ( n = n_m \ \&\ w . x ( u_m ) = 0 ) \vee n \notin \{ n_m \Mid m \in {\mathbb N} \} \, . \end{align*} \medskip So we may assume that $g_i$ is bad hence $\exists ( w_m )_m \, \exists ( n_m )_m \, \exists ( v_m )_m$ such that the $n_m$'s are increasing, the $w_m$'s are distinct, and $g_i ^{- 1} \cdot \alpha ( 1_{{\bf F}_2} , n_m , \ell_i ) \cdot g_i = v_m \cdot \alpha ( w_m , n_m , \ell_i ) ^{\pm 1}\cdot v_m ^{-1}$. Again by thinning down we may assume that the exponent is $= 1$. \medskip $\bullet$ $g_i$ is bad and $\mu ( w . x ) = \infty$. Set \begin{align*} \alpha ( w , n_m , \ell_i )^{p_1} \in {\mathcal G} ( x ) & \iff w . x ( u_n ) = 1 \\ \alpha ( w , n , \ell_i )^{p_0} \in {\mathcal G} ( x ) & \iff ( n = n_m \ \&\ w . x ( u_n ) = 0 ) \vee n \notin \{ n_m \Mid m \in {\mathbb N} \} \, . \end{align*} \medskip $\bullet$ $g_i$ is bad and $\mu ( w . x ) < \infty$. Then set \[ \alpha ( w , n , \ell_i )^{p_j} \in {\mathcal G} ( x ) \, , \] where \[ j = \begin{cases} 0 & \text{if } n \notin \{ n_m \Mid m \in \mathbb N \} \, , \\ 2 & \text{if $n = n_m$ and $m < \mu ( w . x ) - 1$ or } m > \mu ( w . x ) \, , \\ J_{\mu ( w . x )} ( w . x ) + 3 & \text{if $n = n_m$ and } m \in \{ \mu ( w . x ) , \mu ( w . x ) - 1 \} \, . \end{cases} \] Finally, no $\gamma^p$ not mentioned in the above is allowed in ${\mathcal G} ( x )$. This concludes the definition of $x \mapsto {\mathcal G} ( x )$. \bigskip It is straightforward to check that Properties (1)--(6) hold and therefore \[ \forall x \in 2^{{\bf F}_2} \, \forall w \in {\bf F}_2 \left ( H ( w . x ) = \tilde{w} H ( x ) \tilde{w}^{- 1} \right ) . \] The following Claim, whose proof is left to the reader, is the analogue of \ref{coding}. \begin{claim} \label{recoding} Suppose $g_i$ is an unbounded quasi-shift satisfying case 2, i.e., \[ \forall w \in {\bf F}_2 \, \forall n \in \mathbb N \, \exists z \in {\bf F}_2 \, \exists u \in {\bf F}_\omega \left ( g_i^{-1} \cdot \alpha ( w , n , \ell_i ) \cdot g_i = u \cdot \alpha ( z , n , \ell_i )^{\pm 1} \cdot u ^{- 1}\right ) . \] Suppose also $( w_m )_m$, $( n_m )_m$, and $( v_m )_m$ witness that $g_i$ is bad. Then for all $x \in 2^{{\bf F}_2}$ \[ \mu ( x ) = \infty \iff \forall m \left ( \alpha ( 1_{{\bf F}_2} , n_m , \ell_i )^{p_0} \in {\mathcal G} ( x ) \vee \alpha ( 1_{{\bf F}_2} , n_m , \ell_i )^{p_1} \in {\mathcal G} ( x ) \right ) \] and if $\mu ( x ) < \infty$ and $\alpha ( 1_{{\bf F}_2} , n_m , \ell_i )^p \in {\mathcal G} ( x )$ then \[ p = \begin{cases} p_2 & \quad \mbox{ if } m \notin \{ \mu ( x ) - 1 , \mu ( x ) \} \\ p_j & \quad \mbox{ if } m \in \{ \mu ( x ) - 1 , \mu ( x ) \} \mbox{ and } j = J_{\mu ( x )} ( x ) + 3 \, . \end{cases} \] \end{claim} We will now show that \[ \exists i \left ( g_i H ( x ) g_i^{- 1} = H ( y ) \implies \exists w \in {\bf F}_2 \left ( y = w . x \right ) \right ) . \] The reader may find it useful to refer to Figure 2 while checking the details. \begin{figure} \[ \xymatrix@=10pt{ & &*+[F]{H ( y ) = g_i H ( x ) g_i^{- 1}} \ar@{-}[dl] \ar@{-}[dr] & & \\ & *+[F]{\txt{$g_i$ is a\\ quasi-shift}} \ar@{-}[dl] \ar@{-}[d] & & *+[F]{\txt{$g_i$ is not\\ a quasi-shift}} \ar@{=>}[d] \\ *+[F]{\txt{$g_i$ is bounded}} \ar@{=>}[d] &*+[F]{\txt{$g_i$ is unbounded}} \ar@{-}[dr] \ar@{-}[d] & & *+[F]{\txt{$g_i H ( x ) g_i^{- 1}$ is not\\ in the range of $H$:\\ a contradiction!} } \\ *+[F]{\txt{$g_i H ( x ) g_i^{- 1}$ is not\\ in the range of $H$:\\ a contradiction!} } & *+[F]{| r | > 1} \ar@{=>}[d] & *+[F]{| r | = 1} \ar@{-}[dr] \ar@{-}[d] \\ & *+[F]{\txt{$g_i H ( x ) g_i^{- 1}$ is not\\ in the range of $H$:\\ a contradiction!} } &*+[F]{\txt{$g_i$ is bad}} \ar@{-}[dl] \ar@{-}[d] & *+[F]{\txt{$g_i$ is good}} \ar@{=>}[d] \\ &*+[F]{\mu ( w_0 . x ) \neq \infty} \ar@{=>}[d] &*+[F]{\mu ( w_0 . x ) = \infty} \ar@{=>}[d] & *+[F]{y = w_\infty . x} \\ &*+[F]{\txt{$g_i H ( x ) g_i^{- 1}$ is not\\ in the range of $H$:\\ a contradiction!} } & *+[F]{y = w_0 . x}} \] \caption{Plan of the Proof of Theorem \ref{ourtheorem}} \end{figure} Assume that \[ H ( y ) = g_i H ( x ) g_i ^{-1} \, . \] \bigskip Suppose $g_i$ is not a quasi-shift, and let $w_0 , n_0 , k_0 , w_0' , n_0' , k_0'$ be as in (i)--(iv). \smallskip If (i) holds then $k_0 = \ell_i$ and $\alpha ( w_0 , n_0 , k_0 )^p \in {\mathcal G} ( y )$, where $p = \min ( S_i \setminus \{ r \} )$ and $r > 0$ is least such that $g_i ^{- 1} \cdot \alpha ( w_0 , n_0 , k_0 )^r \cdot g_i \in {\bf F}_\omega$, if such $r$ exists, or $r = 0$ otherwise. Since $\alpha ( w_0 , n_0 , k_0 )^p \in H ( y )$ then \[ g_i ^{- 1} \cdot \alpha ( w_0 , n_0 , k_0 )^p \cdot g_i \in H ( x ) \subseteq {\bf F}_\omega \] hence $r > 0$. As $r$ and $p$ are relatively prime let $\lambda , \nu \in \mathbb Z$ be such that $\lambda r + \nu p = 1$ so that \[ g_i ^{- 1} \cdot \alpha ( w_0 , n_0 , k_0 ) \cdot g_i = \left ( g_i ^{- 1} \cdot \alpha ( w_0 , n_0 , k_0 )^r \cdot g_i \right )^\lambda \cdot \left ( g_i ^{- 1} \cdot \alpha ( w_0 , n_0 , k_0 )^p \cdot g_i \right )^ \nu \in {\bf F}_\omega \] contradicting our assumption case. \smallskip If (ii) holds then $\ell_{i - 1} + 1 = k_0 < \ell_i = k_0 '$, $\alpha ( w_0 , n_0 , k_0 ) ^p \in {\mathcal G} ( y )$, where $p = {\min ( S_i )}$, and \[ \forall w , n , r \ \alpha ( w , n , k_0 ' )^r \notin {\mathcal G} ( x ) \, . \] By case hypothesis $\alpha ( w_0' , n_0' , k_0' )$ is a generator in $g_i ^{- 1} \cdot \alpha ( w_0 , n_0 , k_0 )^p \cdot g_i \in H ( x )$, hence by (5) above, $\alpha ( w_0' , n_0' , k_0 ' )^q \in {\mathcal G} ( x )$ for some $q \in S_i$ such that $q | p$. A contradiction. \smallskip If (iii) holds then $k_0 = \ell_i$, $\alpha ( w_0 , n_0 , \ell_i ) ^{\min ( S_i )} \in {\mathcal G} ( y )$, and $\alpha ( w_0 ' , n_0 ' , \ell_i )^r \notin {\mathcal G} ( x ) $, for any $r$. But $g_i ^{- 1} \cdot \alpha ( w_0 , n_0 , \ell_i )^{\min ( S_i )} \cdot g_i \in H ( x )$ implies by (5) that $\alpha ( w_0' , n_0' , \ell_i )^q \in {\mathcal G} ( x )$ for some appropriate $q \in S_i$. A contradiction. \smallskip So suppose (iv) holds. Then $k_0 = \ell_i$, $\alpha ( w_0 , n_0 , \ell_i ) ^ p \in {\mathcal G} ( y ) \subseteq H ( y )$, where $p = \min ( S_i )$, and all generators of $g_i ^{- 1} \cdot \alpha ( w_0 , n_0 , \ell_i ) \cdot g_i$ are of level $< \ell_i$. For notational ease let $v = g_i ^{- 1} \cdot \alpha ( w_0 , n_0 , \ell_i ) \cdot g_i$ so that $v^p \in H ( x )$. If we show that $v \in H ( x )$ then we will reach the desired contradiction, since this would imply that $\alpha ( w_0 , n_0 , \ell_i ) = g_i \cdot v \cdot g_i^{-1} \in H ( y )$, against (5). If $v$ were a generator then, by case assumption, its level would be between $\ell_{j - 1}$ and $\ell_j$, with $j < i$, so since $v^p \in H ( x )$ and using (5), there should be a $q \in S_j$ such that $q | p$, which is absurd. Therefore we may assume that $v \notin \Gamma$. If $v \cdots v$ is in reduced form (in other words: if $v$ starts and ends with different generators) then we are done by (6), so we may assume otherwise. Let $v_0$ be the longest initial segment of the word $v \in {\bf F}_\omega$ such that $v$ ends with $v_0^{- 1}$, and let $v = v_0 \cdot v_1 \cdot v_0^{-1}$. Suppose first $v_0$ is non-empty. Then either \begin{enumerate} \item[(a)] $v_0 \cdot v_1 \cdot v_0^{-1}$ is a reduced word, or else \item[(b)] $v_0$ ends with the same generator that starts $v_1$, or else \item[(c)] $v_1$ ends with the same generator that starts $v_0^{-1}$, and (b) fails. \end{enumerate} If $v_0$ is empty, then \begin{enumerate} \item[(d)] $v = \gamma^h \cdot u \cdot \gamma^k$ with $\gamma \in \Gamma$, $h , k \in \mathbb Z \setminus \{ 0 \}$, $h + k \neq 0$, and $u$ does not start or end with $\gamma$. \end{enumerate} Note that cases (a), (b), (c), and (d) are mutually exclusive. Let us deal with case (d) first. Then \[ v^p = \gamma^h \cdot u \cdot \gamma^{h + k} \cdot u \cdots u \cdot \gamma^{h + k} \cdot u \cdot \gamma^k \] is a reduced word, so by (6) $\gamma^h , u , \gamma^k \in H ( x )$ and therefore $v = \gamma^h \cdot u \cdot \gamma^k \in H ( x )$. If case (a) holds then we have two cases. Either $v_1 \cdots v_1$ is in reduced form so that $v^p$ can be written in reduced form as \[ v^p = v_0 \cdot {\underbrace{v_1 \cdots v_1}_p} \cdot v_0^{- 1} \, , \] and hence by (6) $v_0 , v_1 \in H ( x )$, and thus $v \in H ( x )$. Or else $v_1$ starts and ends with the same generator, so by (6) and case (d) applied to $v_1$, \[ v_0 \cdot v_1^p \cdot v_0^{-1} \in H ( x ) \implies v_0 , v_1^p \in H ( x ) \implies v_0 , v_1 \in H ( x ) \, , \] hence $v \in H ( x )$. If case (b) holds, let $\gamma \in \Gamma$ be such that $v_0 = z \cdot \gamma^h$ and $v_1 = \gamma^k \cdot u$ are both reduced words. By case assumption, $z$ does not end with $\gamma$, and $h , k \in \mathbb Z \setminus \{ 0 \}$ have the same sign. Then \[ v^p = z \cdot \gamma^{h + k} \cdot u \cdot \gamma^k \cdot u \cdots \gamma^k \cdot u \cdot \gamma^{- h} \cdot z \] is in reduced form, so by (6) $z , u , \gamma^k , \gamma^{- h} \in H ( x )$ and therefore \[ v = ( z \cdot \gamma^h ) \cdot ( \gamma^k \cdot u ) \cdot ( z \cdot \gamma^h )^{- 1} \in H ( x ) \, . \] Case (c) is similar and left to the reader. Therefore in all cases $v \in H ( x )$, reaching a contradiction. Thus \[ \framebox{$g_i$ is not a quasi-shift above $\ell_{i - 1}\ \implies g_i H ( x ) g_i^{- 1}$ is not in the range of $H$.} \] \medskip So we may assume from this point on that $g_i$ is a quasi-shift above $\ell_{i - 1}$. Suppose $g_i$ is bounded and let $\alpha ( w_0 , n_0 , \ell_i )$ witness this. Let also $\alpha ( z , n_0 , \ell_i )$ be a generator in $v = g_i ^{- 1} \cdot \alpha ( w_0 , n_0 , \ell_i ) \cdot g_i$. Since $\alpha ( w_0 , n_0 , \ell_i )^p \in H ( y )$, then $g_i ^{- 1} \cdot \alpha ( w_0 , n_0 , \ell_i )^p \cdot g_i = v^p \in H ( x )$ hence its generators to some appropriate prime powers must be in $\mathcal G ( x )$. In particular this must be true of $\alpha ( z , n_0 , \ell_i )$: by Property (1) and (5) there is $q \in S_i$ and $k$ such that $\alpha ( z , n_0 , \ell_i )^k $ occurs in $v^p$, $q | k$ and $\alpha ( z , n_0 , \ell_i )^q \in {\mathcal G} ( x )$. But by definition of $\mathcal G$ when $g_i$ is bounded, $q = p > | k |$: a contradiction. Thus \[ \framebox{$g_i$ is bounded $\implies g_i H ( x ) g_i^{- 1}$ is not in the range of $H$.} \] \medskip So we may assume that $g_i$ is unbounded. Suppose case 1 holds: let $g_i ^{- 1} \cdot \alpha ( w _0 , n_0 , \ell_i ) \cdot g_i = v = u \cdot \alpha ( z , n_0 , \ell_i ) ^r \cdot u^{- 1}$ and $r = r ( w_0 , n_0 )$, $| r | > 1$. Since $\alpha ( w_0 , n_0 , \ell_i )^p \in H ( y )$ and $v^p = v_0 \cdot \alpha ( z , n_0 , \ell_i ) ^{rp} \cdot v_0 ^{- 1} \in H ( x )$ is reduced, then $v_0 , \alpha ( z , n_0 , \ell_i )^p \in H ( x )$ by Properties (5) and (6). Therefore $v_0 \cdot \alpha ( z , n_0 , \ell_i )^p \cdot v_0 ^{ - 1} \in H ( x )$ and computing in $H ( y )$ \begin{align*} \left ( g_i \cdot v_0 \cdot \alpha ( z , n_0 , \ell_i ) ^p \cdot v_0 ^{- 1} \cdot g_i ^{- 1} \right )^r & = g_i \cdot v_0 \cdot \alpha ( z , n_0 , \ell_i ) ^{pr} \cdot v_0 ^{- 1} \cdot g_i ^{- 1} \\ & = g_i \cdot v^p \cdot g_i ^{- 1} \\ & = \alpha ( w_0 , n_0 , \ell_i ) ^p \end{align*} a contradiction, since $\alpha ( w_0 , n_0 , \ell_i )^p \in {\mathcal G} ( y )$ is a generator of $H ( y )$ hence it is not the $r$-th power of any element. Thus \[ \framebox{$g_i$ is unbounded $\&\ | r | > 1 \implies g_i H ( x ) g_i^{- 1}$ is not in the range of $H$.} \] \medskip Therefore we may assume we are in case 2, that is $\forall w \in {\bf F}_2 \, \forall n \ | r ( w , n ) | = 1$. Suppose $g_i$ is good, so that $g^{- 1}_i \cdot \alpha ( 1_{{\bf F}_2} , n_m , \ell_i ) \cdot g_i = v_m \cdot \alpha ( w_\infty , n_m , \ell_i ) ^{r ( 1_{{\bf F}_2} , n_m )} \cdot v_m^{- 1}$. Then, by Property (6), for $e = 0 , 1$ \begin{align*} y ( u_m ) = e & \iff \alpha ( 1_{{\bf F}_2} , n_m , \ell_i )^ {p_e} \in H ( y ) \\ & \iff v_m \cdot \alpha ( w_\infty , n_m , \ell_i )^ {p_e \cdot r ( 1_{{\bf F}_2} , n_m )} \cdot v_m^{- 1} \in H ( x ) \\ & \implies \alpha ( w_\infty , n_m , \ell_i )^ {p_e} \in H ( x ) \\ & \iff w_\infty . x ( u_m ) = e \end{align*} that is $w_\infty . x = y$. \[ \framebox{$g_i$ is good $\implies y = w_\infty . x$.} \] \medskip Therefore we may assume $g_i$ is bad, hence $g_i ^{- 1} \cdot \alpha ( 1_{{\bf F}_2} , n_m ,\ell_i ) \cdot g_i = v_m \cdot \alpha (w_m , n_m , \ell_i )^{r ( 1_{{\bf F}_2} , n_m )} \cdot v_m ^{-1}$. Suppose $\mu ( w_0 . x ) = \infty$. Then by Claim \ref{facts} in the proof of \ref{rec} $\forall m ( w_m . x = w_0 . x )$ hence \[ \forall m \left ( \mu ( w_m . x ) = \infty \quad \mbox{ and } \quad H ( w_m . x ) = H ( w_0 . x ) \right ) . \] For $p \in S_i$ and using Property (6) and the fact that $r ( 1_{{\bf F}_2} , n_m ) = \pm 1$ \begin{align*} \alpha ( 1_{{\bf F}_2} , n_m , \ell_i )^p \in H ( y ) & \iff v_m \cdot \alpha ( w_m , n_m , \ell_i )^ {p \cdot r ( 1_{{\bf F}_2} , n_m )} \cdot v_m ^{- 1} \in H ( x ) \\ & \implies \alpha ( w_m , n_m , \ell_i )^ {p} \in H ( x ) \\ & \iff \alpha ( 1_{{\bf F}_2} , n_m , \ell_i )^ p \in H ( w_m . x ) = H ( w_0 . x ) \\ & \implies p = p_0 \vee p = p_1 \, . \end{align*} By Claim \ref{recoding} $\mu ( y ) = \infty$ hence, for $e = 0 , 1$, \begin{align*} y ( u_m ) = e & \iff \alpha ( 1_{{\bf F}_2} , n_m , \ell_i )^ {p_e} \in H ( y ) \\ & \implies \alpha ( 1_{{\bf F}_2} , n_m , \ell_i )^ {p_e} \in H ( w_0 . x ) \\ & \iff w_0 . x ( u_m ) = e \end{align*} that is $w_0 . x = y$. Thus \[ \framebox{$g_i$ is bad $\&\ \mu ( w_0 . x ) = \infty \implies w_0 . x = y$.} \] \medskip Suppose $\mu ( w_0 . x ) = m < \infty$. Then by \ref{facts} \[ \forall j < m \left ( \mu ( w_j . x ) = m \ \&\ J_m ( w_j . x ) = J_m ( w_0 . x ) \right ) \qquad \mbox{and} \qquad \mu ( w_m . x ) \leq m \, . \] Let $e_j \in \{ 0 , \dots , 5 \}$ be the unique value such that \[ \alpha ( w_j , n_j , \ell_i )^{p_{e_j}} \in {\mathcal G} ( x ) \, . \] Then the first $m$-many elements of $( e_j )_j$ are $( 2 , \dots , 2, J_m ( w_0 . x ) + 3 )$ and by Claim \ref{recoding} the next element must be $J_m (w_0 . x ) + 3$. Suppose $\mu ( w_m . x ) = m$. Since $w_0 . x = w_{m - 1} . x$ and $z_m . w_0 . x = w_m . x$ are distinct, $J_m ( w_0 . x ) \neq J_m ( w_m . x )$, a contradiction. Suppose $\mu ( w_m . x ) < m$. Then $e_m = 2 \neq J_m ( w_0 . x ) + 3$, a contradiction again. Thus \[ \framebox{$g_i$ is bad $\&\ \mu ( w_0 . x ) < \infty \implies g_i H ( x ) g_i^{- 1}$ is not in the range of $H$.} \] This concludes the proof. \end{proof} \begin{thebibliography}{99} \bibitem{DJK} {\sc R.\ Dougherty, S.\ Jackson}, and {\sc A.\ S.\ Kechris}, The structure of hyperfinite Borel equivalence relations, {\em Transactions of the American Mathematical Society\/} {\bf 341} (1994), 193--225. \bibitem{Doughertykechris} {\sc R.\ Dougherty} and {\sc A.\ S.\ Kechris}, How many Turing degrees are there?, to appear in Proceedings of the AMS Summer Research Conference on Computability Theory and Applications, Boulder, Colorado, June 1999. \bibitem{Gao} {\sc S.\ Gao}, Coding subset shift by subgroup conjugacy, to appear in the {\em Bulletin of the London Mathematical Society}. \bibitem{hjorthkechris} {\sc G.\ Hjorth} and {\sc A.\ S.\ Kechris}, Borel equivalence relations and classifications of countable models, {\em Annals of Pure and Applied Logic} {\bf 82} (1996), 221--272. %\bibitem{JKL} {\sc S.\ Jackson, A.\ S.\ Kechris}, and {\sc A. Louveau}, %Countable Borel equivalence relations, %(in preparation). \bibitem{cabal} {\sc A.\ S.\ Kechris} and {\sc Y.\ N.\ Moschovakis}, Cabal Seminar 76-77, LNM 689, Springer Verlag, 1978. \bibitem{KST} {\sc A.\ S.\ Kechris, S.\ Solecki}, and {\sc S.\ Todor\v cevi\'c}, Borel chromatic numbers, {\em Advances in Mathematics\/} {\bf 141} (1999), 1--44. \bibitem{Kechris} {\sc A.\ S.\ Kechris}, Classical Descriptive Set Theory, Springer Verlag, 1995. \bibitem{stuckzimmer} {\sc G.\ Stuck} and {\sc R.\ J.\ Zimmer}, Stabilizers for ergodic actions of higher rank semi-simple groups, {\em Annals of Mathematics} {\bf 139} (1994), 723--747. \bibitem{thomasvelickovic} {\sc S.\ Thomas} and {\sc B.\ Veli\v ckovi\'c}, On the complexity of the isomorphism relation for finitely generated groups, {\em Journal of Algebra\/} {\bf 217} (1999), 352--373. \bibitem{Wagon} {\sc S.\ Wagon}, The Banach Tarski Paradox, Encyclopedia of Mathematics and its Applications, 24. Cambridge University Press, 1985. \end{thebibliography} \end{document}