%% 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}

