\documentclass{book}

\usepackage{handbook}

\usepackage{amssymb}

\usepackage{amsmath}







% Set the beginning of a LaTeX document

\title{Handbook of Set Theory}

\author{Foreman, Kanamori, and Magidor (eds.)}





\makeindex



\begin{document}





\maketitle





\tableofcontents





%\newtheorem{theorem}{Theorem}[section]

%\newtheorem{lemma}[theorem]{Lemma}

%\newtheorem{corollary}[theorem]{Corollary}

%\newtheorem{proposition}[theorem]{Proposition}

%\newtheorem{claim}[theorem]{Claim}

     

     



 %\newenvironment{proof}[1][Proof]{\begin{trivlist}

  %   \item[\hskip \labelsep {\bfseries #1}]}{\hfill$\Box$\end{trivlist}}

   %  \newenvironment{definition}[1][Definition]{\begin{trivlist}

    % \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}

%     \newenvironment{example}[1][Example]{\begin{trivlist}

 %    \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}

    % \newenvironment{remark}[1][Remark]{\begin{trivlist}

%     \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}

 %    \newenvironment{notation}[1][Notation]{\begin{trivlist}

  %   \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}

   %  \newenvironment{question}[1][Question]{\begin{trivlist}

    % \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}

%\newenvironment{examples}[1][Examples]{\begin{trivlist}

 %    \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}

     

%\newcommand{\forces}{\mbox{\logic\char'015}}

\newcommand{\forces}{\mathord{|}\mathord{\vdash}}

%\newcommand{\restrict}{\mbox{\logic\char'026}}

%\newcommand{\restrict}{\mbox{\char'026}}

\newcommand{\qin}{\mathord{``}\mathord{\in}\mathord{"}}

\newcommand{\qnin}{\mathord{``}\mathord{\not\in}\mathord{"}}

\newcommand{\qeq}{\mathord{``}\mathord{=}\mathord{"}}

\newcommand{\restrict}{\mathord{\upharpoonright}}

\newcommand{\less}{\mathord{<}}

\newcommand{\thing}{\mathord{-}}

\newcommand{\pmax}{\mathbb{P}_{max}}

\newcommand{\qsmax}{\mathbb{Q}^{*}_{max}}

\newcommand{\qmax}{\mathbb{Q}_{max}}

\newcommand{\ns}{NS_{{\omega}_{1}}}

\newcommand{\pn}{\mathcal{P}(\omega_{1})/NS_{{\omega}_{1}}}

\newcommand{\poi}{\mathcal{P}(\omega_{1})/I}

\def\underTilde#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\sim$}}}{}}

\def\undertilde#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\scriptscriptstyle\sim$}}}{}}

\newcommand{\delot}{\undertilde{\delta}^{1}_{2}}

\newcommand{\zfcdot}{ZFC$^{\circ}$}

\newcommand{\zfcdots}{ZFC$^{\circ}\text{ }$}

\newcommand{\stst}{($^{*}_{*}$)}

\newcommand{\ststs}{($^{*}_{*}$)$\text{ }$}







\def\Ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\sim$}}}{}}

\def\ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\scriptscriptstyle\sim$}}}{}}

\def\R{{\Bbb R}}

\def\C{{\Bbb C}}

\def\V{{\Bbb V}}

\def\N{{\Bbb N}}

\def\Z{{\Bbb Z}} 

\def\Q{{\Bbb Q}}

\def\F{{\Bbb F}}

\def\l{{\mathcal L}}

\def\n{{\mathcal N}}

\def\m{{\mathcal M}}

\def\p{{\mathcal P}} 

\def\f{{\mathcal F}}

\def\t{{\mathcal T}}

\def\no{\noindent} 



\chapter{Borel equivalence relations}{Greg Hjorth} 













This chapter is setting out to achieve an impossibility, 
namely to survey the rapidly 
exploding field of Borel equivalence relations as 
found in descriptive set theory and 
the connections with areas entirely outside logic. 
The choice of content and emphasis is 
inevitably molded by this author's own prejudices and 
research history; others may have 
a radically 
different vision of the subject. For instance I have 
somewhat arbitrarily chosen to say nothing 
about the study of equivalence relations arising in 
Borel ideals, as found in papers such 
as \cite{solecki}, 
\cite{kechrisideals}, \cite{farahmazur}, or the 
parallel theory of Borel linear orderings 
as found in say \cite{kanovei}, \cite{hamash}, 
or the still unpublished work of 
Hugh Woodin's and of Richard Ketchersid's  
on the cardinality of certain Borel equivalence 
relations under strong determinacy 
assumptions, the work on general $\Ubf{\Sigma}^1_1$ 
equivalence relations as found in 
\cite{beckercompact}, or the topological Vaught conjecture 
as discussed in \cite{sami}, 
\cite{hjorthsolecki}, \cite{beckervaught}, \cite{hjorthvaught}. 
Moreoever the discussion of 
Borel equivalence relations is organized around the 
Borel reducibility order, 
$\leq_B$, rather than notions such as orbit equivalence, 
as found in say \cite{gaboriau}, 
\cite{furman}, \cite{gaboriaupopa}, \cite{popa}, 
\cite{hjorthdye}, 
or notions of isomorphism, as discussed in 
\cite{dokelo}. Without a super-human effort to 
the contrary, it is easy to 
slip in to discussing what I know best, which, 
regretfully perhaps, are the papers I 
have written. 
Finally I should admit to being much more 
conversant with the mathematics of the 
subject than the history, and since my main 
concern is to communicate the most vibrant ideas 
with a certain immediacy undoubtedly some 
important citations have been 
overlooked. 



Thus I stand impeached with prejudice, ignorance, arbitrariness, arrogance, 
and discourtesy. 





But as unfortunate as these failings may be, they are 
inevitable, and I say all of this 
simply so the 
reader will understand that this is a project doomed to at 
least partial failure and 
nevertheless worth pursuing in the hope of partial success. 
A similar but rather different 
point of view can be found \cite{kechrissurvey}. The reader 
might also look at \cite{beckerkechris} 
for a closer examination of some of the issues surrounding 
actions induced by Polish group 
actions, or at \cite{hjorthvaught} for a discussion 
of the Vaught conjecture, or 
\cite{kechrismiller} for orbit equivalence. 
Another survey is given in \cite{hjorthlogic}, but 
in fact I am unable to even point to 
any small set of papers which would be fully adequate. 











\section{Definitions} 



Before moving on to the theory of Borel equivalence 
relations it would be 
helpful to discuss Borel sets in general. A thorough 
and more complete account 
can be found in \cite{kechrisclassical}. 



\begin{definition}  A {\it Polish space} is a separable 
topological space which admits a \index{Polish space} 
compatible complete metric. The {\it Borel} subsets of a 
Polish space are those appearing 
in the $\sigma$-algebra generated by the open sets -- 
that is to say, if we begin with the 
open sets and continue applying the operations of countable 
union, countable intersection, and 
complementation, then the Borel sets are those 
appearing in the collection which thereby arises. 






Inside the Borel sets we make further distinctions. Thus a set is 
$\Ubf{\Sigma}^0_1$ if it is open, and after that we define recursively a set to be 
$\Ubf{\Pi}^0_\alpha$ if its complement is 
$\Ubf{\Sigma}^0_\alpha$, 
and to be 
$\Ubf{\Sigma}^0_\alpha$ if it is a countable union of Borel 
sets each of which are 
$\Ubf{\Pi}^0_\beta$ for some $\beta<\alpha$. It is easily shown 
that $\Ubf{\Pi}^0_\alpha\subseteq \Ubf{\Sigma}^0_{\alpha +1}$ 
and every Borel set 
will be $\Ubf{\Sigma}^0_\alpha$ for 
some $\alpha<\omega_1$. 
At the bottom level of this hierarchy there are 
alternate notations used by 
analysts -- for instance a $\Ubf{\Pi}^0_2$ set 
is also called \index{$G_\delta$} 
$G_\delta$ and a 
$\Ubf{\Sigma}^0_2$ set is also called $F_\sigma$. 





For much of the time we are unconcerned with the 
topological structure of a Polish space, 
focusing instead on its Borel structure. 
Accordingly a set $X$ equippped with a 
$\sigma$-algebra ${\cal B}$ is a \index{standard Borel space} 
{\it standard Borel space} if there is some Polish topology 
on $X$ which gives rise to 
${\cal B}$ as the collection of Borel sets. 



\end{definition} 









\begin{example}

{\bf 1} $\R$ and $\C$ are Polish. 
Any compact metric space is Polish. 

 

{\bf 2} There is a natural way to think 
of the collection of all subsets 
of the natural numbers as a Polish space. 
By associating with each 
set its characteristic function, or 
indicator function, 
we can identify the power set 
of $\N$, 
denoted by $\p (\N)$, with 
\[\{0, 1\}^\N=_{\rm df} 2^\N,\] 
which is a compact space in the 
product topology. 
Similarly $\p(\N\times\N)$ or 
$\p(S)$ any countable set $S$. 



{\bf 3} Any Borel subset of a Polish 
space is a standard Borel space 
in the inherited Borel structure 
(see \cite{kuratowski}, 13.4 \cite{kechrisclassical}). 



{\bf 4} The Borel probability 
measures on a standard 
Borel space 
themselves again form a 
standard Borel space 
(this ultimately follows from the 
Riesz representation theorem; compare 17.23 \cite{kechrisclassical}). 



{\bf 5} Consider the 
collection of subsets of 
$\N\times\N\times \N$ which form the graph of 
a function 
\[\bullet : \N\times \N\rightarrow \N\] 
providing a finite rank torsion free 
abelian group structure on $\N$. This 
collection in the natural Borel 
structure is a standard Borel space, since it is 
a Borel subset of the Polish 
space $\N\times\N\times \N$. 



{\bf 6} Given a countable 
language we can form two possible Polish topologies on the 
space of $\l$-structures on $\N$. 
For simplicity assume the 
language is relational, though the more general case of 
$\l$ having function 
symbols is only slightly more complicated. \index{Mod$(\l)$} 
We let Mod$(\l)$ be the set of all 
$\l$-structures with the natural numbers as their 
underlying set. 



The first of the topologies is $\tau_{qf}$. 
For $\psi(\vec x)$ a 
formula in $\l$ and $\vec a=(a_1,..., a_n)$ a 
sequence in $\N$, we let 
$U(\psi(\vec x), \vec a)$ be the 
collection of all $\n\in$ Mod$(\l)$ with 
\[\n\models \psi(\vec a),\] 
and then $\tau_{qf}$ is the collection 
the topology with basis consisting of 
all the sets of the form $U(\psi(\vec x), \vec a)$, 
as $\psi$ ranges over the 
quantifier free formulas. If $\l$ consists of relations 
$R_1, R_2,...$, each 
$R_i$ and $n(i)$-ary relation, then it is easily seen that 
$({\rm Mod}(\l), 
\tau_{qf})$ is isomorphic to $\prod_{i\in\N}\N^{2^{n(i)}}$ 
in the product topology. 
Since the class of Polish spaces is closed under product 
(see $\S$2.1 \cite{hjorthclassification}) 
we have that $({\rm Mod}(\l), 
\tau_{qf})$ is Polish. 



The more subtle topology is $\tau_{fo}$, 
with basis consisting of all 
$U(\psi(\vec x), \vec a)$ as $\psi$ ranges 
over first order formulas. This is a again 
a Polish topology, though the proof of this, 
say as found at 2.42 \cite{hjorthclassification}, 
is less obvious. 



While these are divergent choices in topology, 
there is really one reasonable choice of 
{\it Borel structure} on this space. Since 
$\tau_{fo}\supset \tau_{qf}$ and both are 
Polish topologies, they give rise to the 
same Borel structure. (This follows from 
18.10, 18.14 \cite{kechrisclassical}).  



\end{example} 



\begin{definition} 

Given a Polish space $X$, we let $\f(X)$ 
be the collection of all closed subsets of 
$X$, equipped with the $\sigma$-algebra 
generated by sets of the form 
$\{F\in \f(X): U\cap F\neq\emptyset\}$ for 
$U$ open. 

\index{Effros Borel structure}   

This is known as the {\it Effros Borel structure} 
on the closed subsets of $X$. It is not hard 
to show that $\f(X)$ equipped with this 
Borel structure is indeed a 
standard Borel space -- see for instance 
$\S$2 \cite{hjorthclassification} or 
\cite{kechrisclassical}. 

\end{definition} 







The reader should definitely consult 
\cite{kechrisclassical} for a more 
reasonable introduction to the theory of 
Borel sets. This is the 
smallest sketch. 





\begin{definition} 

A function 
\[f: X\rightarrow Y\] 
is said to be {\it Borel} if $f^{-1}[B]$ is 
Borel for any Borel 
set $B\subseteq Y$. 

An equivalence relation $E$ on $X$ 
is said to be {\it Borel} 
if it is Borel as subset of $X\times X$. 
We then use 
$[x]_E$ to denote the equivalence class 
of $x$ for any 
$x\in X$ -- that is to say, the set 
$\{y\in X: xEy\}$. 

\end{definition} 







\begin{definition} Given $E$ and $F$ 
Borel equivalence relations 
on standard Borel $X$ and $Y$, 
we write \index{$\leq_B$} \index{Borel reducible} 
\[E\leq_B F,\] 
$E$ is {\it Borel reducible to} $F$, if there 
is a Borel $f:X\rightarrow Y$ 
such that for all $x_1, x_2\in X$ 
\[x_1 E x_2 \Leftrightarrow f(x_1) F f(x_2);\] 



\noindent in other words, $f$ pushes down 
to injective map 
\[\bar{f}: X/E \rightarrow Y/F\] 
between the quotient spaces. 



After this we naturally set $E<_B F$ if there is a 
Borel reduction from $E$ to 
$F$ but not $F$ to $E$. We set $E\sim_B F$ 
if each is Borel reducible to the other. 

\end{definition} 





Note that the order $\leq_B$ is transitive, 
since the composition of two 
Borel functions is again Borel. 

\bigskip 



{\bf Remark} This definition is only for Borel 
$f$, but one can of course 
consider more general classes of functions 
if this seems too stingy -- 
for instance, $C$-measurable functions, 
projective functions, $L(\R)$ functions. 
In virtually all cases this makes 
no difference -- the failures of reducibility 
for Borel functions persist 
to these wider classes. 
Indeed, appropriately understood most of the 
theorems about Borel 
equivalence relations turn into theorems 
about cardinality in $L(\R)$. 
See $\S$4 below. 



It should also be admitted that there are 
other ways in which we can compare 
Borel equivalence relations, for instance 
asking that there be isomorphisms of the 
underlying spaces that conjugate the 
relations, or in the presence of a measure we 
can ask for measure preserving isomorphisms 
between the spaces which conjugate the 
equivalence relations almost everywhere; 
indeed this second notion is the subject of 
extensive study in areas such as operator 
algebras (for instance \cite{popa}), 
geometric group theory (for instance 
\cite{gaboriau}, \cite{monodshalom}), and the 
rigidity theory in the sense of Zimmer (\cite{zimmer}). 
For the purposes of descriptive 
set theory, I incline to the view that $\leq_B$ is 
the central notion. Indeed some kind of 
defense of the philosophical significance of 
$\leq_B$ is given in $\S$4. 



\bigskip 



\begin{example} 

{\bf 1} For $X$ a Polish space, we let 
 id($X$) be the identity relation 
on the space $X$. Since any two uncountable 
standard Borel spaces are isomorphic (15.6 
\cite{kechrisclassical}), it follows that for 
any uncountable $X$ we have 
\[{\rm id}(X)\leq_B {\rm id}(\R).\] 



{\bf 2} We let $E_0$ be the equivalence \index{$E_0$} 
relation of eventual agreement on infinite binary 
sequences. Thus for 
$\vec x=(x_0, x_1,...), \vec y =(y_0, y_1,...)\in 2^\N$, we set 
\[\vec x E_0\vec y\] if and only 
if there exists some $N\in\N$ with 
\[\forall n>N(x_n=y_n).\] 



Here we have 
\[{\rm id}(2^\N)<_B E_0.\] 



To see that there is a Borel reduction from 
id$(2^\N)$ to $E_0$ is routine. It follows 
simply because there is perfect set in 
Cantor space consisting of mutually generic reals. 



The failure of reducibility in the other 
direction is more subtle. First one observes that 
$E_0$ is given by the continuous 
action of the countable group 
\[\bigoplus_\N \Z/2\Z\] 
with $(g_0, g_2,...)\cdot (x_0, x_1,...)=(g_0+ x_0 {\rm mod} 2, g_1 + x_1 {\rm mod} 2,...)$. 
Then given a supposed Borel reduction $f$ of 
$E_0$ to the identity relation on 
$2^\N$ we can find a comeager set $C$ on which 
$f$ is continuous. Then we can take 
\[\bigcap_{\vec g\in \bigoplus \Z/2\Z} \vec g\cdot C,\] 
which will still be comeager and now invariant. 
Taking any $\vec x$ in this set we obtain 
that $f$ will be constant on $[\vec x]_{E_0}$. 
Since this equivalence class is dense, 
$f$ will constant on the entire set 
$\bigcap_{\vec g} \vec g\cdot C$. Since this set is 
uncountable, it contains many equivalence classes 
with a contradiction. (For a more detailed 
and general argument, see 3.2 \cite{hjorthclassification}). 



{\bf 3} We let $E_1$ be the equivalence relation 
of eventual agreement on infinite sequences 
of reals. Here one has \index{$E_1$}  
\[E_0<_B E_1.\]  
(See \cite{kechrislouveau}, or even \cite{hjorthclassification}). 



{\bf 4} Given a countable group $\Gamma$, we let 
$2^\Gamma$ be the collection of all 
functions 
\[f: \Gamma\rightarrow \{0, 1\}\] 
with the product topology. We let $\Gamma$ act on 
$2^\Gamma$ with 
\[\gamma\cdot f(\delta)=f(\gamma^{-1}\delta),\] 
the left shift action. We then let $E_G$ be the 
resulting equivalence relation. 



In the case that we start with $G=\F_2$, the free 
group on two generators, one has 
\[E_0<_B E_{\F_2}.\] 
(See for instance appendix A of 
\cite{hjorthkechrisrigidity} for a survey of stronger and 
more general results one can prove in this direction.) 



{\bf 5} An example of historical importance is the 
{\it Vitali equivalence relation}, 
$E_v$. For $r, s\in \R$ set 
\[r E_v s\] 
if and only if 
\[r-s\in \Q.\] 
The classical argument that this 
equivalence relation has no measurable selector 
can be modified to show that 
${\rm id}(\R)<_B E_v$; alternatively one may appeal to 
a variation of 
the Baire category argument at example 2 just above. 



On the other hand, at the level of Borel reducibility there is no distinction 
between $E_0$ and $E_v$. (See for instance 
the argument after 1.5 \cite{hjorthorbitcardinals} 
for a short proof that $E_0\sim_B E_v$.) 



{\bf 6} Let $X_2$ be the space of all  
$h\in 2^{\N\times\N}$, where at each $n\neq m$ there 
exists a $k$ with $h(n, k)\neq h(m, k)$. 
In other words, if we set $h_n\in 2^\N$ to be given 
by $h_n(k)=h(n, k)$ then for $n\neq m$ 
we have $h_n\neq h_m$. 

\index{${\cal T}_2$} 

Then define ${\cal T}_2$ on $X_2$ by 
$h^1 {\cal T}_2 h^2 $ if and only if the corresponding countable sets 
in $2^\N$ 
are equal -- that is to say, 
\[\{h^1_n: n\in \N\}=\{h_n^2: n\in \N\}.\] 
Thus if we let $S_\infty$ be the group 
all permutations of $\N$, acting on 
$X_2$ by  
\[\sigma\cdot h(n, k)=h(\sigma^{-1}(n), k),\] 
then ${\cal T}_2$ is the resulting equivalence relation. 



It is well known that for any $E_G$ as above, 
arising from a countable group $G$ acting on 
$2^G$, one has 
\[E_G <_B {\cal T}_2.\] 
(See for instance 2.64 \cite{hjorthclassification}.) 

\end{example} 



\bigskip  



\begin{definition}

An equivalence relation $E$ 
on standard Borel \index{smooth equivalence relation} 
$X$ is said to be {\it smooth} or {\it tame} if 
$E\leq_B {\rm id}(\R)$. 

\end{definition} 





Smoothness amounts to asserting the existence 
of a countable algebra $\{B_n: n\in\N\}$ 
of $E$-invariant 
Borel sets which separates points -- which is to say 
\[xEy\Leftrightarrow \forall n(x\in B_n \Leftrightarrow y\in B_n).\] 
This in turn is equivalent to saying that 
$X/E=\{[x]_E: x\in X\}$ in the quotient Borel 
structure consisting of all $E$-invariant Borel sets is a 
subset of a standard Borel space. (See \cite{hakelo}, \cite{jakelo}.) 





\begin{definition} 

A 
Borel equivalence relation $E$ on a 
standard Borel space $X$ 
is said to be {\it countable} if every 
equivalence class is countable. 
It is {\it essentially countable} if there 
is some other countable 
Borel equivalence relation $F$ with $E\leq_B F$. 

\end{definition} 



\begin{example} 

Let $\F_2$ be the 
free group on two generators 
and let $E_{\infty}$ arise from 
action of 
$\F_2$ on $2^{\F_2}$. Then 
this is countable, since the responsible group is 
countable. 

\end{example} 



It is known from \cite{jakelo} 
that this equivalence relation is 
{\it universal} among the countable 
equivalence relations, in the sense 
that for every countable Borel 
equivalence relation $E$ one has 
\[E\leq_B E_\infty.\] 
We will not get ensnarled in the 
details of this argument here, but it might 
be helpful to point out that the proof 
depends on the Feldman-Moore theorem, 
which in some sense reduces to the 
study of countable Borel equivalence relations 
to the study of the orbit equivalence 
relations induced by countable groups. 















\begin{theorem}
[Feldman, Moore, \cite{feldmanmoore}] 
 \label{feldmanmoore} 
If $E$ 
is a countable Borel equivalence relation on 
$X$, then there is a Borel group of automorphisms 
whose orbits equal the $E$-equivalence 
classes.
\end{theorem} 



\begin{proof}

Following the Lusin-Novikov uniformization 
theorem (18.10, 18.15 \cite{kechrisclassical}) 
we can find a sequence of Borel functions 
$(f_n)_{n\in \N}$ such that $[x]_E$ always 
equals $\{f_n(x): n\in\N\}$. We can find Borel 
sets $B_n$ consisting of exactly the 
points on which $f_n(x)\neq x$. We can 
then find a partition of 
$B_n$ into Borel sets $\{C_{n, i}: i\in \N\}$ 
with $f_n[C_{n, i}]$ disjoint from $C_{n, i}$ 
and $f|_{C_{n, i}}$ one-to-one.  
We then let $g_{n, i}$ be the function which 
is the identity off of $f_n[C_{n, i}]\cap C_{n, i}$, equal to $f_n$ on 
$C_{n, i}$, and to 
$f^{-1}_n$ on $f[C_{n,i}]$. It follows by Lusin-Novikov again that each 
$g_{n, i}$ is Borel. 



Letting $G$ be the countable group of automorphisms 
generated by $\{g_{n, i}: i,n\in \N\}$ we 
obtain $E=E_G$, the orbit equivalence relation induced by $G$. 
\end{proof} 





\begin{lemma} A countable Borel equivalence 
relation is smooth if and only if it has a 
Borel selector -- that it so say, a Borel set which 
meets every equivalence class in exactly 
one point. 
\end{lemma} 



\begin{proof} This follows rapidly from the 
Lusin-Novikov uniformization theorem. 
See for instance \cite{jakelo}, or \cite{burgessselection} for far more general results. 
\end{proof} 



This lemma fails for general equivalence relations. 
For instance if we take $C\subseteq \N^\N\times 
\N^\N$ with the projection $\{x: \exists y((x, y)\in C)\}$ non-Borel, 
and set $(x, y) E (x', y')$ on $C$ 
exactly when $x=x'$, then a Borel selector would result in the 
projection being Borel, since the 
one-to-one image of any Borel set under a Borel function is 
Borel. 



\begin{definition} 

\index{hyperfinite equivalence relation} 
An equivalence relation $E$ is {\it hyperfinite} if there 
is a sequence of Borel 
equivalence relations, $(F_n)_{n\in \N}$, with each 
$F_n$ having all its equivalence 
classes finite, each $F_n\subseteq F_{n+1}$, and 
$E=\bigcup_{n\in \N} F_n$. 

\end{definition} 



\begin{lemma} 
[\cite{jakelo}]
\label{hyperfinite}   
A countable Borel equivalence relation $E$ on 
$X$ is hyperfinite if and only if 
$E\leq_B E_0$. 

\end{lemma} 



%\begin{proof} The if direction follows rather routinely from the observation that $E_0$ 

%is hyperfinite, so suppose instead that $E=\bigcup_{n\in\N} F_n$, each $F_n$ Borel with finite 

%classes, $F_n\subseteq F_{n+1}$. 



%The collection of all closed subsets of $X$ is a standard Borel space in the 

%Effros Borel structure, and so we can find at each $n$ a Borel function 

%\[f_n: X\rightarrow 2^\N\] 

%with $x F_n y$ if and only if $f_n(x)=f_n(x)$, and then let 

%\[f(x)=(f_0(x), f_1(x), f_2(x),...).\] 

%This function witnesses $E\leq_B E_0$. 

%\end{proof} 





\begin{definition}


\index{treeable equivalence relation} 
An equivalence 
relation $E$ on a standard Borel space $X$ is 
{\it treeable} if its classes form the components 
of a Borel treeing on $X$ -- that is to say, there is 
$\t\subseteq X\times X$ which is Borel with respect 
to the product Borel structure, is symmetric, acyclic, 
loopless, and for which we have $xEy$ if and only if 
there is a finite chain $x_0=x, x_1, x_2,..., x_n=y$, 
each $(x_i, x_{i+1})\in \t$. (So here one has in mind 
the notion of tree prevelant in certain branches of 
combinatorics or computer science, rather than 
descriptive set theory -- an acyclic graph, with no distinguished 
root in the various connected components). 

\end{definition} 



\begin{definition} 

Let $\F_2$ be the free group on 
two generators. Let $F(2^{\F_2})$ be the free part 
of the shift action of $\F_2$ on $2^{\F_2}$ -- that is 
to say, the set of $h: \F_2\rightarrow \{0,1\}$ 
such that for all $\sigma\in\F_2$ there exists $\tau$ 
with $h(\sigma^{-1}\tau)
\neq h(\tau)$, equipped with the action 
$(\sigma\cdot h)(\gamma)=h(\sigma^{-1}\gamma)$.  
We then let $E_{{\cal T}\infty}$ be the 
orbit equivalence arising from this action of $\F_2$ on 
$F(2^{\F_2})$.  

\end{definition} 





In most cases treeable equivalence relations 
have been studied simply in the case that $E$ is 
already countable. 
Here one has an analogue of \ref{hyperfinite}. 



\begin{lemma} [See \cite{jakelo} or 
\cite{hjorthproduct}]  
A countable equivalence relation is treeable if and only 
if it is Borel reducible to 
$E_{\t\infty}$. 
\end{lemma} 



Although this survey is primarily concerned with 
Borel equivalence relations, one must naturally 
connect this study with the analysis of those lying 
just outside this class. 



\begin{definition} 

A subset of a standard Borel 
space is {\it analytic} or 
$\Ubf{\Sigma}^1_1$ if it is the image under a 
Borel function of a Borel set.  
\end{definition} 



\begin{definition}  

\index{Polish group} \index{Polish $G$-space} 
\index{standard Borel $G$-space} 
A {\it Polish group} is a 
topological group which is Polish as a space. 
Given a Polish group $G$, a {\it Polish $G$-space} 
is a Polish space equipped with a 
continuous action of $G$; a {\it standard Borel 
$G$-space} is a standard Borel space 
equipped with a Borel action by $G$. 



In either case, if $X$ is the space we use 
$E_G^X$, or even just $E_G$ when there is 
no doubt to $X$, to denote the resulting 
orbit equivalence relation, and $[x]_G$ to 
denote the orbit of a point $x$. 

\end{definition} 



The equivalence relations arising from the Borel 
action of a Polish group are always 
$\Ubf{\Sigma}^1_1$, but frequently non-Borel. As noted in 
\cite{beckerkechris}, for any such 
$E^X_G$ we can write $X$ as an $\aleph_1$ 
union of invariant Borel sets, 
\[X=\bigcup_{\alpha<\omega_1} X_\alpha,\] 
and $E_G^X$ restricted to each $X_\alpha$ Borel. 



\begin{example}

{\bf 1} Let $S_\infty$ be the group of all infinite 
 permutations of the natural 
numbers equipped with the topology of pointwise 
convergence -- that is to say, a basic open set 
has the form 
$\{\sigma\in S_\infty: \sigma(n_0)=k_0,..., \sigma(n_\ell)=k_\ell\}$. 
or $\l$ a countable language we 
let $S_\infty$ act on Mod$(\l)$ 
in the natural way -- 
\[(\sigma\cdot \m)\models R(n_0,..., n_\ell)\]
if and only if 
\[\m\models R(\sigma^{-1}(n_0),..., \sigma^{-1}(n_\ell).\] 
The resulting equivalence relation is nothing other than 
isomorphism on this class of structure, and 
for any reasonably rich one has $E_{S_\infty}$ 
is $\Ubf{\Sigma}^1_1$ but non-Borel.



{\bf 2} Given $\l$ as above, and $\varphi\in \l_{\omega_1, \omega}$, 
a countably 
infinitary formula, we let Mod$(\varphi)$ be the structures in 
Mod$(\l)$ which satisfy 
$\varphi$. Since this is a Borel subset of a Polish 
space, it is a standard Borel space in 
its own right, and in the induced action a standard 
Borel $S_\infty$-space. 



Here one should see \cite{beckerkechris} for further 
details. The first paper to 
consider these examples seriously from the point of 
the view of the $\leq_B$ ordering 
is \cite{friedmanstanley}. 



{\bf 3} Given a Polish group $G$ we can let it act on 
itself by conjugation -- 
\[\sigma\cdot \rho=\sigma^{-1}\rho\sigma.\] 


In many cases this corresponds naturally to some 
kind of classification problem. 
For instance, if $M_\infty$ is the group of all 
measure preserving transformations of 
the unit interval considered up to agreement 
almost everywhere, then this group is indeed 
Polish in the natural topology and the equivalence 
relation arising from its conjugation 
action is the equivalence relation of isomorphism of 
measure preserving transformations. 
Or if we let $U_\infty$ be the unitary group on infinite 
dimensional Hilbert space, we 
are find ourselves confronted with the classification 
up to unitary equivalence of 
unitary operators. Or one may consider Hom$([0,1])$, 
the homeomorphism group of the unit 
interval, for the classification problem for homeomorphisms 
of the unit interval up to 
topological similarity. 
All these examples are discussed at length in \cite{hjorthclassification}. 

\end{example} 





\bigskip  



\section{A survey of structure theorems} 



\subsection{Structure} 



At the base level of the $\leq_B$ there is a sharp 
structure. The first of these 
results is due to Jack Silver. Although it was 
proved sometime prior to the general 
study of Borel equivalence relations, it may be 
paraphrased in modern terminology as 
follows. 



\begin{theorem} [Silver, \cite{silver}]  If $E$ is a Borel equivalence relation, then 
exactly one of: 



\leftskip 0.4in 



(I) $E\leq_B {\rm id}(\N)$; 



(II) ${\rm id}(\R)\leq_B E$. 



\leftskip 0in 



\end{theorem} 





In some ways this belongs to the prehistory of the subject. 
Momentum only began in ernest following the seminal dichotomy theorem of 
Leo Harrington, Alexander Kechris, and
Alain Louveau. This is sometimes known as the 
{\it Glimm-Effros dichotomy}, since the 
forerunners of this theorem 
were proved by Glimm and then later Effros, 
who had the result in the 
case that $E$ is an $F_\sigma$ equivalence 
relation induced by the continuous action 
of a Polish group. 

\index{Glimm-Effros dichotomy} 


\begin{theorem}
[Harrington-Kechris-Louveau, \cite{hakelo}] 
 \label{hakelo}
If $E$ is a Borel equivalence relation, then 
exactly one of: 



\leftskip 0.4in 



(I) $E\leq_B {\rm id}(\R)$; 



(II) $E_0\leq_B E$. 



\leftskip 0in 

\end{theorem}





\begin{proof} (Sketch only) 
We describe some of the combinatorics under the 
drastic assumption that $E$ is a 
{\it countable} Borel equivalence relation. This 
is misleading as to the difficulty 
of the proof, since then the vast majority of the 
mathematical issues simply evaporate. It should 
also be pointed out that the theorem in this case 
was already known to Glimm and Effros, 
\cite{glimm}, \cite{effros}. 



First we can appeal to \ref{feldmanmoore} to obtain a 
countable group $G$ acting by Borel 
transformations on the Polish space $X$ with 
$E_G=E$. Applying a change of topology argument, 
as found in say $\S$13 \cite{kechrisclassical}, we 
may assume $G$ acts by homeomorphisms. 



Now there are two possibilities. 



First of all we may have that for any $x\neq y\in X$ 
we have the closures of their orbits, 
$\overline{[x]_G}, \overline{[y]_G}$, distinct. In that case one defines a map 
\[X\rightarrow \f(X),\] 
\[x\mapsto \overline{[x]_G},\]
from $X$ to the space of all closed subsets of $X$ 
with the standard Borel structure. 
It is easily seen that this map is Borel, and so we 
obtain a reduction of $E$ to id$(\f(X))$. 
Since any two uncountable Borel spaces are Borel 
isomorphic, this is as good as a reduction 
to id$(\R)$. 



The other case is that there are distinct orbits with the 
same closure. We will now work 
entirely inside some $X_0\subseteq X$ consisting of 
all $y$ with $\overline{[y]_G}=C$ for 
some closed $C$. $X_0$ is a $G_\delta$ subset of 
$X$, and hence Polish in its own right. 
(See for instance $\S$2.1 \cite{hjorthclassification}.) 
At this stage we 
are assuming that $X_0$ contains more than 
one orbit for the purpose of deriving a contradiction. We 
let $\{g_n: n\in \N\}$ enumerate the group $G$. 
Now note that $E_G$ is $F_\sigma$, and our 
assumptions on $X_0$ imply that both it and its complement 
are dense in $X_0\times X_0$. 



We then construct non-empty 
open neighborhoods $(U_s)_{s\in 2^{<\N}}$ in $X_0$ 
and $(g_s)_{s\in 2^{<\N}}$



\leftskip 0.4in 



\no (i) $\overline{U_s}\subseteq U_t$ for $s$ a 
strict extension of $t$; 



\no (ii) with respect to a compatible complete metric on 
$X_0$, the diameter of each $U_s$ is less than 
$2^{-n}$ for $s\in 2^n$; 



\no (iii) $g_{s^\smallfrown 0}=g_s$;  $g_{s^\smallfrown 1}
=g_sg_{\langle 0,0,...0\rangle^\smallfrown 1}$; 
$g_{\langle 0,0,...0\rangle}=e$, the identity 
of the group; 



\no (iv) $g_s\cdot U_{\langle 0,0,..0\rangle}=U_s$, 
where $\langle 0,0,..., 0\rangle$ is 
the constantly zero sequence of the same length as $s$; 



\no (v) if $s, t\in 2^{n+1}$ and $s(n)\neq t(n)$, then 
for all $i\leq n$ we have 
$g_i\cdot U_s\cap U_t=\emptyset$. 



\leftskip 0in 



Assuming we can effect this elaborate arrangement, the conclusion is brief. (iv) will guarantee 
that for each $s, t\in 2^n$ we have 
\[g_tg_s^{-1}\cdot U_{s}=U_{t},\]  
and then repeated applications of (iii) ensures for 
any $w\in 2^{<\N}$ 
\[g_tg_s^{-1}\cdot U_{s^\smallfrown w}=U_{t^\smallfrown w}.\] 
Thus for any $x\in 2^\N$ there will be a 
unique point 
\[\theta(x)\in \bigcap U_{x|_n},\] 
and if $x(n)=y(n)$ all $n\geq N$, then 
\[g_{x|_n}g_{y|_n}^{-1}(\theta(y))=\theta(x),\] 
whilst if $x(n)\neq y(n)$ for infinitely many 
$n$ then (v) guarentees $E_G$-inequivalence. 



So suppose we have done this up to some level. 
We have $(U_s)_{s\in 2^n}, (g_s)_{s\in 2^n}$. 
By the density of the complement of $E_G$ we can 
find some $x, y\in U_{\langle 0,0,...0\rangle}$ 
which are inequivalent. We can then let 
$x_s=g_s\cdot x$, $y_s=g_s\cdot y$. We form small enough 
open sets $W, V$ around $x, y$ so that if 
$W_s=g_s\cdot W$, 
$V_s=g_s\cdot V$, then $g_i\cdot V_s\cap W_t=\emptyset $, 
$g_i^{-1}\cdot V_s\cap W_t=\emptyset$. 



We then find a point $x'\in [x]_G\cap V_{\langle 0,0,...0\rangle}$ by the density of the 
orbits. We let $g_{\langle 0,0,...0\rangle^\smallfrown 1}$ 
be a 
group element moving $x$ to $x'$. We let 
$g_{s^\smallfrown 1}$ 
be $g_sg_{\langle 0,0,...0\rangle^\smallfrown 1}$. 
We then build a sufficiently small set 
$U^*\subseteq W$ so that if we let $U_t=g_t\cdot U^*$ 
for each $t\in 2^{n+1}$ then 
for $i\leq n$ we have 
ensured (i), (ii), and (v). 
\end{proof} 



The argument for 
general Borel $E$ is far harder, and uses the 
Gandy-Harrington topology. There is no known proof 
of \ref{hakelo} which does not use ideas from logic. 



Therefore at the base of the picture one obtains the 
Borel equivalence relations with 
finitely many classes, followed by any Borel equivalence 
relation with exactly 
$\aleph_0$ many classes, then the identity relation on 
the reals, and then $E_0$, or, 
equivalently when considered up to Borel reducibility, the 
Vitali equivalence relation. 



It should be mentioned that Harrington-Kechris-Louveau 
implies Silver's theorem. If $f: 2^\N\rightarrow 
X$ witnesses $E_0\leq_B E$ then we can find a comeager set 
on which this function is continuous, 
and then inside this comeager we can find a compact perfect set 
of $E_0$-inequivalent reals. On the 
other hand if $E\leq {\rm id}(\R)$ then the equivalence classes of 
$E$ can be identified with a 
$\Ubf{\Sigma}^1_1$ subset of a Polish space, whereapon Silver's 
theorem reduces to the 
perfect set theorem for $\Ubf{\Sigma}^1_1$ sets. 



Immediately after this one obtains a splintering. It is known from
 \cite{kechrislouveau} 
that there are no other Borel equivalence relations $E$ such that 
for any other Borel $F$ one 
has either $E\leq_B F$ or $F\leq_B E$. Instead we have: 



\begin{theorem} [Kechris-Louveau; \cite{kechrislouveau}] 
Let $E$ be a Borel equivalence relation with 
$E\leq_B E_1$. Then exactly one of the 
following holds: 



\leftskip 0.4in 



(I) $E\leq_B E_0$; or, 



(II) $E_1\leq_B E$. 



\leftskip 0in

 

\end{theorem}



\begin{definition}  

Let $E_0^\N$ be the equivalence 
relation on $(2^\N)^\N$ given by 
\[\vec x E_0^\N \vec y\] 
if and only if 
\[\forall n (x_n E_0 y_n);\] 
that is to say, we have $E_0$-equivalence at every 
coordinate. 

\end{definition} 



\begin{theorem} [Hjorth-Kechris; \cite{hjorthkechristhird}]
Let $E$ be a Borel equivalence relation with 
$E\leq_B E_0^\N$. Then exactly one 
of the following holds: 



\leftskip 0.4in 



(I) $E\leq_B E_0$; 



(II) $E_0^\N\leq_B E$. 



\leftskip 0in

 

\end{theorem}





There are no other known immediate successors to 
$E_0$, but Ilijas Farah in 
\cite{farahtsirelson} has proposed a continuum of plausible 
examples which are 
inspired by ideas in Banach space theory. What he does 
show is that these examples 
are incomparable, and that any equivalence relation 
strictly below any of them is 
essentially countable. The gnawing technical difficulty 
at the end of his argument 
is our inability to determine which countable equivalence 
relations are hyperfinite. 
Very recently, in a spectacular and unpublished 
piece of work,  
Su Gao and Steve Jackson showed all equivalence relations 
arising from 
the Borel actions of countable abelian groups are hyperfinite, 
and on this basis we 
might hope for further clarification in the coming years. 





Although we are at a loss to provide further global dichotomy 
theorems, there is something 
more that can be said if we restrict ourselves to the region of 
equivalence relations 
which are below isomorphism of countable structures. 



\begin{definition}  

For $\l$ a countable language, we let 
$\cong_{{\rm mod}(\l)}$ be 
isomorphism on the standard Borel space of 
$\l$-structures with underlying set $\N$. For 
$\psi\in \l_{\omega_1, \omega}$ we 
let $\cong_{{\rm mod}(\psi)}$ be the restriction of 
this equivalence relation to 
models of $\psi$. 

\end{definition} 



\begin{lemma} [Becker-Kechris; \cite{beckerkechris}] 
Let $E$ be Borel. Then the following are equivalent: 





\leftskip 0.4in 



\no (I) $E\leq_B\cong_{{\rm mod}(\l)}$ for some countable 
language $\l$ 



\no (II) $E\leq_B E_{S_\infty}$, where $E_{S_\infty}$ arises 
from the continuous action of a 
$S_\infty$ on a Polish space. 



\leftskip 0in

 

\end{lemma}



\begin{definition} 

If either of these equivalent conditions hold, 
then we say that 
$E$ {\it admits classification by countable structures}. 

\end{definition} 



In the still unpublished \cite{hjorthdichotomy} a dichotomy theorem 
was recently announced for 
equivalence relations admitting classification by countable structures. 
It should be emphasised 
that this proof is long and has not been refereed, and accordingly the 
result has a provisional 
status. 



\begin{theorem} [Hjorth; \cite{hjorthdichotomy}]
Let $E$ be a Borel equivalence relation admitting classification 
by countable 
structures. Then exactly one of 



\leftskip 0.4in 



(I) $E\leq E_\infty$, that is to say, $E$ is essentially 
countable; 



(II) $E_0^\N\leq_B E$. 



\leftskip 0in

 

\end{theorem}





\subsection{Anti-structure} 



The last section represented the good news. Now for the evil. 



Refining an earlier result of Hugh Woodin's, Alain Louveau and 
Boban Velickovic embedded ${\cal P}(\N)/{\rm Fin}$ 
into the 
Borel equivalence relations considered up to Borel reducibility. 


\begin{theorem} 
[Louveau-Velickovic, \cite{louveauvelickovic}] 
\label{louveauvelickovic} 
There is an assignment 
\[A\mapsto E_A\] 
of $\Ubf{\Pi}^0_3$ equivalence relations to subset of $\N$ 
such that 
\[E_{A_1}\leq_B E_{A_2}\] 
if and only if $A_2\setminus A_1$ is finite. 
\end{theorem} 



Therefore there is no global structure theorem 
for the $\leq_B$ ordering. 



Given the dichotomy theorems of \cite{kechrislouveau} and 
\cite{hjorthkechristhird} we might at least hope for some 
kind of basis of immediate 
successors to $E_0$, but even this seems unlikely. 
In \cite{farahdescending} 
Farah obtains an infinite descending chain in $\leq_B$ 
which is {\it unlikely} to 
be above an immediate successor to $E_0$. I say unlikely, 
though it is hard to make 
a fast guess at this point. Literally  Farah obtains the existence 
of a sequence 
$(F_n)_{n\in \N}$ with each $F_{n+1}<_B F_n$, none of them 
essentially countable, and with the 
further property that 
any equivalence relation $E\leq_B F_n$ at every $n$ must be 
essentially countable. 
Since the $F_n$'s arise in a very simple form, in particular the 
continuous action of an 
abelian Polish group, there is some grounds for thinking the 
only countable equivalence 
relations reducible to one of these will be reducible 
to $E_0$. 



Farah's work also disproves the existence of a dichotomy 
theorem for being classifiable 
by countable structures in many dramatic ways. For instance 
he obtains an uncountable 
sequence of Borel equivalence relations, $(E_x)_{x\in 2^\N}$, 
which are not classifiable 
by countable structures, and such that for any $x\neq y$ and Borel $E$ with 
\[E\leq_B E_x, E_y\] 
we have $E$ classifiable by countable structures. 





\subsection{Beyond good and evil} 



There are slender few candidates for outright Borel dichotomy 
theorems in the 
style of \ref{hakelo}, and \ref{louveauvelickovic} and the later 
results of Farah would seem 
to rush hopes for a global analysis of the $\leq_B$ ordering. 
On the other hand there still 
seems that there are results which would help us understand 
when equivalence relations 
fall on some side of a key divide. 



A distinction of philosophical interest is when we can classify 
by countable structures, which 
has clear parallels in broader mathematical practise. Here 
one has in mind for instance certain branches 
of topology, where one seeks complete algebraic invariants, 
and in effect one is trying to 
classify a certain equivalence relation by a countable algebraic 
structure considered up to 
isomorphism. The introduction of \cite{hjorthclassification} surveys 
several examples along these 
lines from a variety of different mathematical areas. 



\begin{definition} 

Let $G$ be a Polish group and $X$ a Polish $G$-space. 
For $U\subseteq G$ an open 
neighborhood of the identity, $V\subseteq X$ an open 
neighborhood of a point $x$, the 
{\it local $U$-$V$-orbit of $x$}, written ${\cal O}(x, U, V)$, 
is the set of all $y$ such that there 
exists a finite sequence of points $x_0=x, x_1, x_2,..., x_n=y$ 
in $U$ with each 
$x_{i+1}\in V\cdot x_i$ -- that is to say, we can move from $x_i$ 
to $x_{i+1}$ using some 
group element in $V$. 

\index{turbulence} 
\index{local orbit} 


Then we say that the action of $G$ on $X$ is {\it turbulent} 
if the following three 
things hold: 



\leftskip 0.4in 



\no (I) every orbit $[x]_G$ is dense in $X$; 



\no (II) every orbit $[x]_G$ is meager in $X$; 



\no (III) given $x, y\in X$, 
$U$ an open neighborhood of $y$, $V$ an open neighborhood 
of the identity in 
$G$, there is some $x'\in [x]_G\cap U$ with $y$ in 
the closure of 
the local orbit ${\cal O}(x', U, V)$. 



\leftskip 0in 



\end{definition}





\begin{theorem} [Hjorth; \cite{hjorthclassification}] If $E_G$ arises 
from a turbulent action of 
$G$ on the Polish $G$-space $X$ and $\l$ is a countable language, 
then $E_G$ is not Borel reducible 
to $\cong_{{\rm mod}(\l)}$. 
\end{theorem} 



\begin{proof} (Sketch) We present the argument in a simple 
case with a 
number of simplifying assumptions. 
Consider the example of an $S_\infty$ action given before, 
where the space is $X_2$, consisting of all  $h\in 2^{\N\times\N}$, 
where at each $n\neq m$ there 
exists a $k$ with $h(n, k)\neq h(m, k)$. 
Then define ${\cal T}_2$ on $X_2$ by $h^1 {\cal T}_2 h^2 $ 
if and only if the corresponding countable sets 
in $2^\N$ are equal. This is the orbit equivalence relation arising 
from the $S_\infty$ action 
\[(\sigma\cdot h)(m, n) =h(\sigma^{-1}(m), n).\] 



We assume for a contradiction  $\theta:X\rightarrow X_2$ 
witnesses $E_G\leq_B {\cal T}_2$. 


Every Borel function is continuous on a comeager set, so 
let us actually make the simplifying 
assumption that $\theta$ is continuous everywhere. 



\medskip



{\bf Claim:} For any $n$ there is a comeager collection of $x\in X$ 
which have some basic open neighborhood 
$V_{x, n}$ of the identity in $S_\infty$ for which there is a comeager 
collection of $\sigma\in 
V_{x,n}$ having 
\[(\theta(x))(n, \cdot)=(\theta(\sigma\cdot x))(n, \cdot).\]  



\medskip 



{\bf Proof of Claim:} For each individual point $x$ and $m$ we 
consider the Borel 
function 
\[f_x^m: G\rightarrow \N\] 
which assigns to $g\in G$ the natural number $f(g)$ with 
$\theta(x)(m, \cdot) =\theta(g\cdot x)(f(g), \cdot)$. 
Each Borel set has the property of Baire, hence we can find 
open sets $(O_n^m)_{n\in \N}$ 
with dense union in $G$ such that $O_n\Delta f^{-1}(n)$ is 
meager at every $n$. Then for any 
\[g\in \bigcap_m \bigcup_n O_n^m\] 
we have at each $\ell$ 
some basic open $V\subset G$ such that for a comeager 
collection of $h\in V$ 
\[\theta(g\cdot x)(\ell, \cdot) =\theta(hg\cdot x)(\ell, \cdot).\] 



Thus we have show that inside each orbit the collection of 
$g\in G$ for which $g\cdot x$ has the 
required property is comeager. Now the conclusion of the 
claim follows by Kuratowski-Ulam. 

\medskip 









Let us make the additional and rather radical assumption 
that 
\[x\mapsto V_{x, n}\]
is defined everywhere, and ``continuous" in the sense that 
given any basic open 
$V$ and $n$ the collection of $x$ with $V_{x, n}=V$ 
is open. 



Let $x, y\in X$. Consider some $n$. It suffices to show that there is a representative of 
the orbit of $x$, 
\[x'\in [x]_G,\] 
which has $\theta(x')(n, \cdot)=\theta(y)(n,\cdot)$. 
By the above simplifying assumptions we can 
find a basic open neighborhood of $U$ of $y$ 
and $V$ a basic open neighborhood of the 
identity in the group which has 
\[(\theta(z))(n, \cdot)=(\theta(\sigma\cdot z))(n, \cdot)\] 
all $z\in U, \sigma\in V$. 



Now if we take $x'\in [x]_G$ with 
\[y\in \overline{{\cal O}(x', U, V)}\] 
then we can find a sequence of points 
$(z_i)_{i\in \N}$, each $z_i\in 
{{\cal O}(x', U, V)}$ with 
\[z_i\rightarrow y.\] 

By the assumptions on $U$ and $V$ we 
have $\theta(z_i)(n,\cdot)=\theta(x')(n,\cdot)$ at 
all $n$, and hence 
$\theta(x')(n, \cdot)=\theta(y)(n,\cdot)$, 
as required. 
\end{proof} 



 



As a practical matter \cite{hjorthclassification} 
suggests turbulence to be the key phenomena in 
determining whether an equivalence relation is 
classifiable by countable structures. This has been 
supported in various examples and practical 
investigations, such as \cite{gaokechris}, 
\cite{kechrissofronidis}, as well as some partial 
results given in \cite{hjorthclassification}. 
The correct theorem was not established 
until a few years later. 



\begin{theorem} [Hjorth; \cite{hjorthturbulence}] 
Let $G$ be a Polish group and $X$ a Polish 
$G$-space. Suppose $E_G^X$ is Borel. Then 
exactly one of the following hold: 



\leftskip 0.4in 



\no (I) $E_G^X$ admits classification by countable 
structures; or 



\no (II) there is a turbulent Polish $G$-space $Y$ 
with $E_G^Y\leq E_G^X$. 



\leftskip 0in



\end{theorem} 



\section{Countable Borel equivalence relations} 





The subject of countable Borel equivalence 
relations is notable for its interactions with 
such diverse fields as geometric group theory, 
the ergodic theory of non-amenable groups, 
operator algebras, and superrigidity in the sense 
of Zimmer. There is a sense in which this 
interaction has been largely one way, since one 
finds logicians borrowing from 
these other fields rather than these areas being 
serviced by logic. 



In the course of this period it is perhaps unsurprising 
that  logicians 
have made a few notable contributions to the benefit of 
the other fields. However in almost 
every case the applications do not consist in applying 
deep ideas from logic, as found 
in say the work of Hrushovski, \cite{hrushovski}, but 
rather the natural result of mathematicians 
from one field rethinking the problems from another and 
approaching with a different 
point of view. 







\subsection{The global structure} 



In some form or another almost every argument which 
distinguishes countable Borel equivalence 
relations in the $\leq_B$ ordering uses measure theory. At 
the very base level we can use 
Baire category arguments to show id$(\R)<_B E_0$ but 
beyond this there is a fundamental 
obstruction. 



\begin{theorem} [Sullivan, Weiss, Wright; \cite{suwewr}] 
Let $E$ be a countable Borel equivalence relation on a 
Polish space 
$X$. Then there is a comeager set on which $E$ 
is hyperfinite. 
\end{theorem} 



\begin{proof} (Sketch; this draws from Segal's thesis, 
\cite{segal}; see also 
\cite{kechrismiller}.) 
$E$ is induced by a countable group $G$ acting by Borel 
automorphisms. Let us make the simplifying 
assumptions that $G$ acts by homeomorphisms and 
the space is zero-dimensional -- 
these assumptions are harmless, but we will 
skip over this point in the interest of 
keeping the argument short. 



Let ${\cal B}$ be a countable basis for $X$ consisting of clopen sets. 
Let $(g_n)_{n\in \N}$ enumerate 
the countable group $G$. 



At each $n$ let $Y_n$ be the collection of 
sequences 
\[\vec A=(A_0, A_1,..., A_n),\] 
where each $A_i$ is a finite subset of ${\cal B}$. 
Given such a sequence we let 
$R_{\vec A}$ be the graph on $X$ given by 
\[x R_{\vec A}x'\] 
if there is some $i\leq n$, $V, V'\in A_i$, with $x\in V, x'\in V'$ and 
\[g_i\cdot x=x'.\] 
We let $E_{\vec A}$ be the equivalence relation 
arising from the connected components 
of $R_{\vec A}$. 



We then let $Y^*_n$ be the subset of $Y_n$ for which the 
induced equivalence relation 
$E_{\vec A}$ has all its equivalence classes finite. 
Given ${\vec A}=(A_0,..., A_n)\in Y^*_n$, 
${\vec B}=(B_0,..., B_m)\in Y^*_n$ where $m\geq n$, we say that $\vec B$ 
{\it extends} $\vec A$ if every at every $i\leq n$ 
\[A_i\subseteq B_i.\] 



\medskip 



\no {\bf Claim:} 
Given any $x, y=g_i\cdot x, n\geq i$ and 
\[\vec A\in Y_n^*\] 
we can find an extension $\vec B\in Y_n^*$ with 
\[x R_{\vec B} y.\] 



\medskip 



\no {\bf Proof of Claim:} 
The point is that we can add to $A_i$ a small enough 
open set $W$ around $x$ that 
will specify $x$ with sufficient exactness to ensure 
that for any 
$x'\in W$, the $E_{\vec A}$ equivalence class of 
$x$ consists of 
$\{h_i\cdot x': i\leq \ell\}$ for some finite sequence 
$h_0,..., h_{\ell -1}$ of group elements. 
(This is where we use zero-dimensionality.) Then 
we can find $V\in {\cal B}$ that 
specifies $x$ with sufficient precision to ensure that for any $x'\in V$ and 
$z E_{\vec A} x'$ we have either $z=x'$ or $z\notin V$. 
Similarly we can do the same for $y$ with some $V'$. 
Then if we were to 
take the simple extension $\vec B$ which has $B_i=A_i\cup \{V, V'\}$ 
but $B_j=A_j$ at $j\neq i$, then $E_{\vec A}$ has index at most 
two in $E_{\vec B}$. 
\hfill (Claim$\square$) 



\medskip 



We then let $Y$ be the space of all infinite sequences 
\[(\vec A^n)_{n\in \N}\in \prod_{n\in \N} Y^*_n\] 
where each $\vec A^{n+1}$ extends $A_n$. Any such 
$(\vec A^n)_{n\in \N}\in 
Y$ gives rise to an increasing sequence of Borel 
equivalence relations with 
finite classes, taking $F_n^{(\vec A^n)_{n\in \N}}$ 
to be 
$E_{\vec A^n}$. 
$\prod_{n\in \N} Y^*_n$ comes with a natural product 
topology, under which it 
is Polish. $Y$ is a closed subset of this product space, 
and hence Polish 
in its own right. The above claim shows that for all $x\in X$ 
there is a comeager 
collection of $(\vec A^n)_{n\in \N}\in Y$ with 
\[[x]_E=\bigcup_{n\in \N}[x]_{F_n^{(\vec A^n)_{n\in \N}}}.\] 
Thus by Kuratowski-Ulam (see \cite{kechrisclassical}), there is a comeager 
collection of $(\vec A^n)_{n\in \N}\in Y$ for which there is a comeager 
collection of $x$ with 
$[x]_E=\bigcup_{n\in \N}[x]_{F_n^{(\vec A^n)_{n\in \N}}}$. 
Taking any such $(\vec A^n)_{n\in \N}\in Y$ 
and corresponding comeager set, 
we are done. 

\end{proof} 



On the other hand the subject of countable Borel 
equivalence relations considered up 
to Borel reducibility might collapse into a kind of 
death by heat dispersal if all these 
examples were hyperfinite. It turns that in the 
presence of an invariant probability measure, 
{\it non-amenable} groups give rise to equivalence 
relations which are not hyperfinite. 



\begin{definition} 

\index{amenable group} 

A countable group $\Gamma$ is {\it amenable} 
if for any finite $F\subseteq \Gamma$ 
and $\epsilon>0$ there is a finite, non-empty $A\subseteq \Gamma$ 
such that for all $\sigma\in F$ 
\[\frac{|A\Delta \sigma A|}{|A|}<\epsilon.\] 

\end{definition} 



As a word on the notation, we use $|B|$ to denote the 
cardinality of the set $B$ and 
$B\Delta C$ to denote the symmetric difference of the sets 
$B$ and $C$. Thus amenability 
amounts to the existence of something like ``almost invariant" 
subsets of the group -- given 
any finite collection of group elements, 
any tolerance ($\epsilon>0$), we can find a finite set which when 
translated by any of the group 
elements differs from its original position on a relatively 
small number of elements. 



\begin{example} 

{\bf 1} ${\Bbb Z}$ is amenable. Given $F=\{k_1,..., k_\ell\}$ 
in the group and $\epsilon>0$, 
we let $k={\rm max}(|k_1|, ..., |k_\ell|)$, the max of the 
absolute values, and then let 
\[N> \frac{2(k+1)}{\epsilon}.\] 
The set $A=\{-N, -N+1, -N+2,..., 0, 1, ..., N-1, N\}$ 
is as required. 



{\bf 2} On the other hand, $\F_2=\langle a, b\rangle$, 
the free group on two generators, 
is most famously non-amenable. Just take $\epsilon=1/10$, 
$F=\{a, b, a^{-1}, b^{-1}\}$. 
We can see this by dividing the non-identity elements of 
$\F_2$ into four regions, 
$C_a, C_b, C_{a^{-1}}, C_{b^{-1}}$, where a (reduced) 
word is in the region $C_u$ if 
it begins with $u$. 



Consider some putative set $A$ that is trying to 
witness amenability for $1/10$ and 
$\{a, b, a^{-1}, b^{-1}\}$. For $u= a, b, a^{-1},$ or 
$ b^{-1}$, $n\in\N$, if at least 
$n$ of $A$'s elements are {\it not} in 
$C_{a^{-1}}, C_{b^{-1}}, C_a,$ or $C_b$, 
respectively, then at least $n$ of $u\cdot A$'s 
elements are in 
$C_a, C_b, C_{a^{-1}},$ or $C_{b^{-1}}$ 
respectively. Therefore we 
can clearly find two distinct 
$u_1, u_2$ with at least three fifths of 
$u_i\cdot A$'s 
elements in $C_{u_i}$. One of these sets must 
differ from $A$ by at least 
$\frac{1}{10}|A|$. 



Note that there is nothing special here about 
the use of {\it almost invariant} 
sets in $\F_2$. We would obtain a similar contradiction 
if we considered 
almost invariant {\it functions} in $\ell^1(\F_2)$. G
iven $f\in \ell^1(\F_2)$ and 
$u\in \{a, b, a^{-1}, b^{-1}\}$ we could look at the norm 
of the corresponding 
$f_u$ defined by $f_u(\sigma)=f(\sigma)$ if 
$\sigma \in C_u$, $f_u(\sigma)=0$ otherwise. 

\end{example} 



\begin{definition}  

A {\it standard Borel probability space} 
is a standard Borel 
space $X$ equipped with an atomless $\sigma$-additive 
probability measure $\mu$ on its 
Borel sets. 

\end{definition} 





\def\nh{|\!|}



\begin{theorem} \label{nonamenable} 
Let $\Gamma$ be a countable non-amenable group. Suppose 
$\Gamma$ acts freely and 
by measure 
preserving transformations on a standard Borel probability space 
$(X, \mu)$. 
Then $E_{\Gamma}$ is not hyperfinite. 
\end{theorem} 



\begin{proof} We sketch the argument just in the case that $G=\F_2$. 



For a contradiction suppose 
$E_{\F_2}=\bigcup_{n\in \N} F_n$, where 
each $F_n$ is finite, Borel, and has 
$F_n\subseteq F_{n+1}$. At each 
$x\in X$ we define 
\[f_{n, x}: \F_2\rightarrow \R\] 
with 
\[f_{n, x}(\sigma)=\frac{1}{|[x]_{F_n}|}\] 
if $\sigma^{-1}\cdot x F_n x$, 
\[f_{n, x}(\sigma)=0\]  
otherwise. 
Let 
\[f_n(\sigma)=\int_X f_{n,  x}(\sigma)d\mu.\] 
For any $x$ we have $\nh f_{n, x}\nh_{\ell^1}=1$, 
and so certainly $\nh f_n\nh_{\ell^1}=1$, and in 
fact for any measurable 
set $A\subseteq X$ 
\[\sum_\sigma\int_A f_{n,  x}(\sigma)d\mu\leq \mu(A).\] 





\medskip 







\no {\bf Claim:} For any $\gamma\in \F_2$, 
as $n\rightarrow \infty$ 
\[{\nh f_n-\gamma\cdot f_n\nh_{\ell^1}}\rightarrow 0.\] 



\medskip 



\no {\bf Proof of Claim:} Note that if 
$x F_n \gamma\cdot x$ then 
\[\gamma\cdot f_{n,x}=f_{n,\gamma\cdot x},\] 
since for any $\sigma$ we have 
\[\gamma\cdot f_{n, x}(\sigma)=f_{n, x}(\gamma^{-1}\sigma)=\frac{1}{|[x]_{F_n}|}(=
\frac{1}{|[\gamma\cdot x]_{F_n}|})\] 
if and only if $\sigma^{-1}\gamma\cdot x F_n x$, 
which, by the assumption 
$x F_n \gamma\cdot x$, amounts to saying 
if and only if 
\[f_{n, \gamma\cdot x}(\sigma)=
\frac{1}{|[\gamma\cdot x]_{F_n}|}.\] 



Thus if we let $A_{n, \gamma}=\{x\in X: x F_n \gamma\cdot x\}$, 
then 
\[\int_{A_{n, \gamma}} \gamma\cdot f_{n,  x}(\sigma)d\mu =
\int_{\gamma\cdot A_{n,\gamma}} f_{n,  x}(\sigma)d\mu,\] 
and hence 
\[{\nh f_n-\gamma\cdot f_n\nh_{\ell^1}}\leq 2\sum_{\sigma} \int_{X\setminus A_{n, \gamma}} 
f_{n, x}(\sigma)\] 
\[= 2 \int_{X\setminus A_{n, \gamma}} \sum_{\sigma}
f_{n, x}(\sigma)=2\mu(X\setminus A_{n, \gamma}).\] 
Since $\mu(A_{n,\gamma})\rightarrow 1$ as $n\rightarrow\infty$, 
we are done. 
\hfill (Claim$\square$) 



Now we have established the existence of almost invariant functions in 
$\ell^1(\F_2)$, and this can be refuted by the same kind of argument as 
used to show the non-amenability of $\F_2$. 
\end{proof} 







For the longest while there was only a small finite 
number of countable 
Borel equivalence 
relations known to be distinct in the $\leq_B$ ordering. 
It was a notorious 
open problem to establish even the existence of $\leq_B$-incomparable examples. 
This was finally settled by: 



\begin{theorem} 
[Adams, Kechris,  \cite{adamskechris}]  
\label{adamskechris} 
There exists an assignment of countable 
Borel equivalence relations to 
Borel subsets of $\R$, 
\[B\mapsto E_B,\] 
such that 
$E_B\leq_B E_C$ if and only if $B\subseteq C$. 
\end{theorem} 



Formally their result relied on the superrigidity 
theory of Zimmer for lattices 
in higher rank lie groups, \cite{zimmer}, and 
thus in turn had connections with 
earlier work of Margulis and Mostow. I will say 
nothing about Zimmer's work as such, but instead 
try to describe some of the engine which 
drives the theory. 



\begin{definition}  

For a compact metric space 
$K$ we let $M(K)$ denote the probability 
measures on $K$. By the Riesz representation theorem 
this can be identified with a closed subset of a 
the dual of $C(K)$, and thus is a Polish space in its own 
right. Note that the homeomorphism group 
of $K$ acts on $M(K)$ in a natural way: 
\[(\psi\cdot \mu)(f)=\mu(\psi^{-1}\cdot f),\] 
where $\psi^{-1}\cdot f$ is defined by 
$(\psi^{-1}\cdot f)(x)=f(\psi(x))$. 

\end{definition}



\begin{definition}  

Given a group $\Gamma$ acting on 
a space $X$ and another group $H$ we say that 
\[\alpha: \Gamma \times X\rightarrow H\] 
is a 
{\it cocycle} if for all $\gamma_1, \gamma_2\in \Gamma, x\in X$ 
\[\alpha(\gamma_2, \gamma_1\cdot x)\alpha(\gamma_1, x)=\alpha(\gamma_1\gamma_2, x).\] 

\end{definition}



Here is a typical situation in which a cocycle arises. Given 
$\Gamma$ a group of Borel automorphisms 
of standard Borel space $X$, $H$ a countable group acting 
freely and in a Borel manner on a standard Borel space 
$Y$, if 
\[\theta: X\rightarrow Y\] 
witnesses $E_\Gamma^X\leq_B E_H^Y$, then 
we obtain a Borel cocycle by letting $\alpha(\gamma, x)$ be the 
unique $h\in H$ with 
\[h\cdot \theta(x)=\theta(\gamma\cdot x).\] 



\begin{lemma}
[Furstenberg, Zimmer, \cite{furstenberg}, \cite{zimmer}] 
 \label{furstenberg} 
If $\Delta$ is a 
countable amenable group 
acting in a Borel manner on a standard Borel probability space 
$(X,\mu)$ and 
\[\alpha: \Delta\times X\rightarrow {\rm Hom}(K)\] 
is a cocyle into the homeomorphism group of a compact metric space 
$K$, then we can find 
a measurable assignment of measures 
\[x\mapsto \nu_x,\]
\[X\rightarrow M(K),\] 
which is almost everywhere equivariant; that it is to say 
\[\forall^\mu x\forall \gamma(\alpha(\gamma, x)\cdot \nu_x=\nu_{\gamma\cdot x}.\] 

\end{lemma} 



The applications of this lemma and its forerunners are much too 
involved to be discussed here. 
Some understanding of what is going on can be given by the 
following simple lemma. In fact, the 
hypotheses of the lemma can never be realized, and indeed the 
real theorem is that  
equivalence relations of the form $E^X_{\Gamma\times \Z}$ are 
never treeable, but I simply want 
to give a short illustration of some key ideas. 



\begin{lemma} 
Suppose $\Gamma$ is a non-amenable 
countable group. Let $X=\{0,1\}^{\Gamma\times\Z}$ 
and let 
$\mu$ be the product measure on this space. 
Let $\Gamma\times\Z$ act in the natural way on this space: 
\[\sigma\cdot f(\tau)=f(\sigma^{-1}\tau)\] 
for any $f\in X$, $\sigma, \tau\in \Gamma\times \Z$. 



Suppose 
$\F_2$ acts freely and by Borel automorphisms on standard Borel probability space 
$Y$. Suppose 
\[\theta: X\rightarrow Y\] 
witnesss $E^X_{\Gamma\times \Z}\leq_B E^Y_{\F_2}$. 



Then there is homomorphism $\rho: \Gamma\rightarrow \F_2$ 
and an alternative reduction 
\[\hat{\theta}: X\rightarrow Y,\] 
which is equivalent in the sense that 
\[\hat{\theta}(x) E_{\F_2}^Y \theta(x)\] 
all $x\in X$ and 
whose resulting cocycle accords with $\rho$ almost 
everywhere, 
in the sense that 
\[\forall^\mu x \forall \gamma (\rho(\gamma)\cdot \hat{\theta}(x)=\hat{\theta}(\gamma\cdot x).\] 
\end{lemma} 



\begin{proof} (Sketch) 
Let 
\[\alpha: (\Gamma\times\Z)\times X\rightarrow \F_2\] 
be the induced cocycle. 


Let $\partial(\F_2)$ denote the {\it infinite} 
reduced words from $\{a, b, a^{-1}, b^{-1}\}$. 
This is a compact metric space on 
which $\F_2$ acts by homeomorphisms. 
(See Appendix C \cite{hjorthkechrisrigidity}.) 
Following \ref{furstenberg} we can find a measurable 
assignment 
\[X\rightarrow M(\partial(\F_2)),\]
\[x\mapsto \mu_x,\] 
with 
\[\alpha(e, \ell)\cdot\mu_x=\mu_{(e, \ell)\cdot x}\] 
for all $\ell\in \Z$ and a.e. $x\in X$. 
(We will use $e$ for the identity in $\Gamma$ and 
0 for the identity in 
$\Z$.) 



\medskip 



\no {\bf Claim:} We can choose this assignment so 
that the measures 
$\mu_x$ concentrate almost everywhere on more 
than two points. 



\medskip



\no {\bf Proof of Claim:} (Sketch only; see Appendix 
C of 
\cite{hjorthkechrisrigidity} for a completely precise 
argument for a more general 
claim.) Suppose instead that every such $\Z$-equivariant 
assignment of measures concentrates on at most 
two points. 



The key observation here is that if 
\[x\mapsto \mu_x\] 
is such an assignment of measures then for any 
$\gamma\in \Gamma$ so 
is 
\[x\mapsto \alpha(\gamma, 0)^{-1}\cdot \mu_{(\gamma, 0)\cdot x}.\] 
Thus to prevent a situation in which we could simply 
pile on more and more of these 
measures, passing from say $x\mapsto \mu_x$ to 
\[x\mapsto \frac{\mu_x + \alpha(\gamma, 0)^{-1}\cdot \mu_{(\gamma, 0)\cdot x}}{2}\] 
we must be able to obtain an assignment which is actually 
$\Gamma$-equivariant. 



Using certain strong ergodicity properties of the shift action of 
$\Gamma$ on $X$ (see Appendix A \cite{hjorthkechrisrigidity}) 
and the hyperfiniteness of the 
action of $\F_2$ on $\partial(\F_2)$ (see Appendix 
C \cite{hjorthkechrisrigidity}) 
we obtain that 
there is a single measure $\nu_0$ such that for 
almost all $x$ we have some 
$\sigma_x\in \F_2$ with 
\[\sigma_x\cdot \mu_x=\nu_0.\] 
Thus replacing $\theta$ with the reduction 
\[\hat{\theta}: x\mapsto \sigma_x\cdot \theta(x)\] 
we obtain a reduction of $E_{\Gamma\times \Z}^X$ 
to $E_H^X$ where $H$ is the subgroup of $\F_2$ 
corresponding which stabilizes the measure $\nu_0$. 
This subgroup will be amenable (see Appendix 
C \cite{hjorthkechrisrigidity}), which in turn provides a 
contradiction to the non-amenability of $\Gamma\times \Z$ 
(see Appendix A \cite{hjorthkechrisrigidity} 
again). 
\hfill (Claim$\square$) 



\medskip 





So now we obtain an assignment of measures that 
concentrates on at least three points 
almost everywhere. Here an observation of Russ 
Lyons (the rough idea is that a measure on 
$\partial(\F_2)$ concentrating on more than three 
points can be assigned a 
{\it center} in an $\F_2$-equivariant manner -- again, 
see Appendix 
C \cite{hjorthkechrisrigidity}) gives us a measurable map 
\[\eta: X\rightarrow \F_2\] 
such that 
\[\eta((e, \ell)\cdot x)=\alpha((e, \ell), x)\cdot \eta(x)\] 
almost everywhere. Replacing 
$\theta: X\rightarrow Y$ by 
\[\hat{\theta}: X\rightarrow Y,\]
\[x\mapsto \eta(x)^{-1}\cdot \theta(x)\] 
we obtain a reduction with an 
induced cocycle 
\[\hat{\alpha}: (\Gamma\times \Z)\times X\rightarrow \F_2\] 
with $\hat{\alpha}((e, \ell), x)=e$ almost everwhere. 



Then, as at the proof of 2.2 \cite{hjorthkechrisrigidity}, the ergodicity of the 
action of $\Z$ on $X$ gives that for any $\gamma\in \Gamma$, 
\[x\mapsto \hat{\alpha}((\gamma, 0), x)\] 
is a.e. invariant. From this it is easily seen that we obtain the required 
homomorphism into $\F_2$. 
\end{proof} 



Arguments of this form can be found very clearly in 
papers by Scot Adams such as 
\cite{adams}, though in truth the ideas trace back to 
Margulis and Mostow by the 
way of Zimmer's \cite{zimmer}. 



\cite{hjorthkechrisrigidity} gives a self contained proof of 
the existence of many 
$\leq_B$-incomparable countable Borel equivalence relations 
using arguments along these 
lines, but something similar is implicit in the superrigidity 
results of 
\cite{zimmer} to which Adams and Kechris appeal in the 
course of proving 
\ref{adamskechris}. In that case one is dealing not with the 
compact space $\partial(\F_2)$ but 
certain compact quotients of an algebraic group (see for instance 
page 88 \cite{zimmer}) 
or the measures on projective space over a locally compact field 
(see 3.2.1 \cite{zimmer}). 
The appearance of product group actions is more subtle, but present; 
superrigidity typically 
on works for groups of matrices of rank greater than two, when we 
can hope to find a 
subgroup which indeed has the form $\Gamma\times \Z$ for 
$\Gamma$ non-amenable. 



In passing it should also be mentioned that there are applications of 
Furstenberg lemma to the 
theory of the homeomorpism group of the circle. In \cite{ghys} the 
combinatorial properties of 
$M(S^1)$ play a role in understanding what kinds of homomorphisms 
are possible into 
Homeo$(S^1)$. 



\subsection{Treeable equivalence relations} 



The situation with the countable Borel equivalence relations can in some 
sense be viewed as resolved. 
It is a giant mess, with many incomparable examples, but we know it to be 
the ghastly mess that it is. 


The situation with treeable countable Borel equivalence relations is far different. 



\def\t{{\cal T}}



It is well known that 
not all treeable equivalence relations are hyperfinite. If one take the 
free part of the shift action 
of $\F_2$ on $2^{\F_2}$ then the resulting equivalence relation, 
$E_{\t\infty}$, is treeable -- we define a Borel treeing by 
$x \t x'$ if there is a generator of $\F_2$ which moves $x$ to $x'$. 
The equivalence relation is 
not hyperfinite,  as shown for instance in 
\cite{hjorthkechrisrigidity}, since the product measure concentrates on the 
free part and 
is $\F_2$-invariant.



It is also known that there is a maximal countable treeable equivalence 
relation. \cite{jakelo} 
shows that for any treeable countable Borel equivalence relation 
$E$ one has $E\leq_B E_{\t\infty}$. 



After that precious little is known. \cite{hjorthdye} gives the existence of a treeable 
equivalence relation $E$ with $E_0<_B E <_B E_{\t\infty}$, but at the time of writing 
it is still open whether there are exactly two non-hyperfinite 
treeable countable Borel equivalence relations up 
to Borel reducibility. 



\subsection{Hyperfiniteness}



One of the enduring problems in this field is to determine which countable 
Borel equivalence relations 
are hyperfinite. Nowadays this is almost always asked in the Borel 
context, since the measure 
theoretic setting is completely understood. 



\begin{theorem} [Connes-Feldman-Weiss; \cite{cofewe}] 
Let $G$ be a countable amenable group acting by measure preserving 
transformations on a 
standard Borel probability space $(X, \mu)$. 
Then there is a conull set on which the orbit equivalence relation 
is hyperfinite. 

\end{theorem} 



Equivalently, we can find a {\it measurable} reduction of 
$E_G$ to $E_0$. 



Even this result for very simple groups remains inscrutiatingly 
difficult in the Borel setting. 



\begin{theorem} [Jackson-Kechris-Louveau, \cite{jakelo}] Let 
$G$ be a finitely generated group 
with a nilpotent subgroup $H$ with $[G:H]$, the index of $H$ in 
$G$, finite. 
If $G$ acts by 
Borel automorphisms on a standard Borel space $X$, then the 
resulting equivalence relation 
$E_G$ is hyperfinite. 

\end{theorem} 



There was a considerable pause until quite recently it was shown: 



\begin{theorem} 
[Gao-Jackson, \cite{bogaja}] 
\label{bogaja} 
Let $G$ be a countable 
abelian group. 
If $G$ acts by 
Borel automorphisms on a standard Borel space $X$, 
then the resulting equivalence relation 
$E_G$ is hyperfinite. 

\end{theorem}



To give an idea of how difficult these problems have proved, 
it was not until 
\ref{bogaja}, despite considerable efforts, we even knew that 
the commensurability 
equivalence relation on $\R\setminus \{0\}$, 
\[r E_c s\Leftrightarrow r/s\in \Q\] 
was hyperfinite. 

It would be natural to conjecture all $E_G$'s arising from the 
Borel action of an 
countable 
amenable group on a standard Borel space are hyperfinite. 
This conjecture is presently far out of reach, and actually has 
little in the way of 
supporting evidence. 





\section{Effective cardinality} 



One way in which to look at the theory of Borel reducibility is as a 
kind of theory of 
{\it Borel cardinality}, and in this sense there are definitely roots in 
papers by 
Harvey Friedman such as \cite{friedman}. If we were to truly embrace 
a mathematical ontology 
consisting solely of Borel objects, then we would also be naturally 
led to consider certain 
kinds of quotients arising from Borel equivalence relations and to make 
any comparison along the 
lines of {\it cardinality} it seems we would use something like Borel reducibility. 



In this sense I am more inclined to consider the theory of $\leq_B$ 
as something like a 
theory of cardinality, as opposed to a theory of reducibility of 
information, as one finds in 
the theory of Turing reducibility. In fact there are close parallels 
between the structure of 
the $\leq_B$-ordering on Borel equivalence relations and the 
cardinality theory of $L(\R)$ under 
suitable determinacy assumptions. 



\begin{definition}  

For $A, B\in L(\R)$ write 
\[|A|_{L(\R)}\leq |B|_{L(\R)},\] 
the $L(\R)$ {\it cardinality of $A$ does not exceed that of $B$}, 
if there is an injection 
\[i:A\hookrightarrow B\] 
in $L(\R)$. 
\end{definition} 



\begin{lemma} 
[Folklore, but see \cite{hjortheffective}.] 
Assume {\rm AD}$^{L(\R)}$. 
Let $E, F$ be Borel equivalence relations on $\R$. 
If 
\[|\R/E|_{L(\R)}\leq |\R/F|_{L(\R)}\] 
then there is a function 
\[f:\R\rightarrow \R\] 
in $L(\R)$ with for all $x_1, x_2\in \R$ 
\[x_1 E x_2 \Leftrightarrow f(x_1) F f(x_2).\] 
\end{lemma} 



Then in parallel to Silver's theorem Woodin has shown: 



\begin{theorem} [Woodin] 
Let $A\in L(\R)$. Then exactly one of: 



\leftskip 0.4in 



\no (I) There is an ordinal $\alpha$ with 
$|A|_{L(\R)}\leq |\alpha|_{L(\R)}$ -- in other 
words, $A$ is well orderable; or 



\no (II) $|\R|_{L(\R)}\leq |A|_{L(\R)}$. 



\rightskip 0in 



\end{theorem} 



And for Harrington-Kechris-Louveau: 



\begin{theorem} [Hjorth, \cite{hjorthdichotomydefinable}] 
Assume {\rm AD}$^{L(\R)}$.  
Let $A\in L(\R)$. Then exactly one of: 



\leftskip 0.4in 



\no (I) There is an ordinal $\alpha$ with 
$|A|_{L(\R)}\leq |2^\alpha|_{L(\R)}$ -- 
in other 
words, $A$ has a well orderable separating family; or 



\no (II) $|\R/E_v|_{L(\R)}\leq |A|_{L(\R)}$. 



\end{theorem} 



In (II) we can equivalently say that ${\cal P}(\omega)/{\rm Fin}$ 
embeds into $A$. 



The theory of effective cardinality, whether we choose to 
explicate it using 
Borel functions and objects or the more joyously playful 
world of $L(\R)$, 
can also be compared with the idea of 
{\it classification difficulty}. If the effective cardinality of 
$A$ is below that of 
$B$, then any objects which suceed as complete invariants for 
$B$ do as well for 
$A$. Here one could even begin certain kinds of wild 
speculations, to the effect that 
subconsciously part of the mathematical activity of vaguely 
searching for some kind of 
ill defined {\it classification theorem} for a class of objects 
is in fact a query as 
to its effective cardinality. 



Even if circumspection draws us back from grand 
fantasies along these lines, 
calculations of Borel cardinality undoubtedly say 
{\it something} about classification 
difficulty. A non-reduction result, saying $E$ not 
Borel reducible to $F$, will inform 
as to which kinds of objects would be {\it insufficient}, 
in the Borel 
category at least, to act as complete invariants for 
$E$. 



Finally, in the context of $L(\R)$ there is a curious 
refinement of the usual Borel 
hierarchy theorem. 



\begin{theorem} [Hjorth, \cite{hjorthborel}] 
Assume  {\rm AD}$^{L(\R)}$. Then for every 
$\alpha<\beta<\omega_1$ 
\[ |\Ubf{\Pi}^0_\alpha|_{L(\R)} < |\Ubf{\Pi}^0_\beta|_{L(\R)}.\] 
\end{theorem} 



Thus, not only is $\Ubf{\Pi}^0_\alpha$ strictly included in 
$\Ubf{\Pi}^0_\beta$, it is 
also smaller in effective cardinality. Sharper results are possible here. 
\cite{anhjne} determines the exact levels of the Wadge degrees which 
provide new cardinals in $L(\R)$. 


\section{Classification problems} 





Until this point our discussion has largely been 
concerned with the 
{\it structural} properties of the $\leq_B$ ordering. 
However in the sum total 
of papers on the subject, the majority deal not with the 
abstract issues of 
this partial order, but instead with the specific problems 
of placing certain 
natural occurring equivalence relations in this 
hierarchy. 



Here one pictures specific levels of classification 
difficulty, and 
for an example ``from the wild" we ask whether 
it is {\it smooth}, 
or {\it classifiable by countable structures,} or 
{\it universal for countable Borel equivalence relations}, 
and 
so on. 



\subsection{Smooth versus non-smooth} 



At the very base, we have the distinction between smooth 
and non-smooth. If $E\leq_B 
{\rm id}(\R)$ then we can classify the $E$-classes by 
points in a concrete space. 



\def\h{{\cal H}}



The very first 
writings dealing at all with attempting to understand the 
classification 
difficulty of mathematical problems as a kind of 
science in and of itself 
are due to George W. Mackey, for instance in 
\cite{mackey}. Very specifically 
he was concerned with understanding which 
groups have {\it smooth duals}. 
Here given $U(\h)$, the unitary group of a 
separable Hilbert space, 
and irreducible representations 
\[\sigma_1, \sigma_2:\Gamma\rightarrow U(\h),\] 
we set $\sigma_1\sim\sigma_2$ if there is some unitary 
$T\in U(\h)$ with 
\[T^{-1}\circ \sigma_1(\gamma)\circ T=\sigma_2(\gamma)\] 
all $\gamma\in \Gamma$. For $\Gamma$ countable, 
the space of unitary representations 
is a Polish space, since it is a closed subset of 
\[U(\h)^\Gamma,\] 
and then the irreducible representations are a 
$G_\delta$ subset of those, 
and hence again Polish in the subspace topology 
(see for instance \cite{effros}). 
We say that the group $\Gamma$ has {\it smooth dual} 
if the equivalence relation 
$\sim$ on the irreducibles is smooth. 
Ultimately it was determined in \cite{thoma} that the 
countable groups with 
smooth duals are exactly the abelian by finite. 



Another example is the equivalence relation of 
matrices over 
$\C$ considered up to similarity. As remarked 
in \cite{hakelo}, 
this equivalence relation is smooth, since we 
can assign to a matrix 
its canonical Jordan form as a 
complete invariant. 



Some authors following on from this have drawn out 
from Mackey's writings the entirely 
general view that in all branches of mathematics the 
dividing line between classifiable 
and non-classifiable is given by the smooth versus 
non-smooth distinction. Indeed the author 
of \cite{effros} appears to flirt with such a opinion. For a 
rather different take one might 
look at the introduction of \cite{hjorthclassification}; 
indeed this work cites many 
apparent classification theorems -- Baer's analysis of 
rank one torsion free abelian 
groups, the von Neumann-Halmos analysis of discrete 
spectrum transformations, the spectral 
theorem for infinite dimensional unitary operators -- for 
equivalence relations which are 
non-smooth. 



\subsection{Universal for Polish group actions} 



It is well known -- probably first due to Leo Harrington, 
but for a proof see \cite{hjkelo} --  that there is no 
{\it universal} Borel 
equivalence relation: For every Borel equivalence 
relation $E$ there is another Borel 
equivalence relation $F$ which does not Borel reduce to
 $E$. On the other hand there is a 
universal $\Ubf{\Sigma}^1_1$ equivalence relation, 
which we might in some sense think of 
as sitting on the throne above all our examples. 



As a practical matter almost all the equivalence relations 
which seem to have independent 
interest arise as, or are reducible to, orbit equivalence 
relations induced by the 
continuous action of a Polish group on a Polish space. 
{\it Among these} there is an 
upermost example: $E_{G_\infty}^{X_\infty}$, induced by 
the continuous action of a Polish 
group $G_\infty$ on a Polish space $X_\infty$. Although 
we are stepping slightly outside 
the subject of Borel equivalence relations as such, 
$E_{G_\infty}^{X_\infty}$ can be viewed 
as a kind of extreme, at the opposite end to id$(\R)$, of an 
equivalence relation with 
maximal complexity. 



In unpublished work Alexander Kechris and Slawek Solecki 
showed that in the natural 
Borel structure compact metric spaces considered up to 
homeomorphism are $\sim_B $ with, 
bi-Borel reducible with, $E_{G_\infty}^{X_\infty}$. A recent 
and published example is 
given by \cite{gaokechris}, where they show that complete 
separable metric spaces considered 
up to isometry is $\sim_B$ to $ E_{G_\infty}^{X_\infty}$, as 
are closed subsets of the 
Uyrsohn space under the orbit equivalence relation induced 
by the isometry group of this 
space. 





\subsection{Universal for $S_\infty$} 



As shown in \cite{beckerkechris}, for each 
Polish group $G$ there is a 
corresponding Polish $G$-space $X$ with 
$E^X_G$ universal for orbit equivalence 
relations of $G$, moreover in the case of $G=S_\infty$ 
we can take $X$ to be 
${\rm Mod}(\l)$ for any $\l$ which contains at 
least one relation of 
arity two or higher. For future reference 
let us fix some such 
universal space for $S_\infty$ orbit 
equivalence relations and 
denote the corresponding equivalence 
relation by 
$E_{\infty S_\infty}$. Again this is 
$\Ubf{\Sigma}^1_1$ but not 
Borel. 



The study of which equivalence relations 
lie at the level of 
$E_{\infty S_\infty}$ go right back to the first 
work of logicians on 
the $\leq_B$ ordering.\footnote{I choose these words 
warily. Although the notion 
of $\leq_B$ does not appear explicitly in the 
writings of Mackey, and was first formally 
isolated in the late 80's, in some form the idea 
is already implicit, both in Mackey 
and in other authors such as \cite{feldman}.} One 
finds $\leq_B$ defined independently, 
quite by accident with the exact same notation 
and terminology, in 
\cite{hakelo} and \cite{friedmanstanley}. The first of 
these papers deals with the 
structural result of \ref{hakelo}, and the second 
almost entirely with specific issues 
of which classes of isomorphism are $\sim_B$ 
with $E_{\infty S_\infty}$. More 
generally, given any $E$ which admits 
classification by countable structures, 
we automatically have 
$E\leq_B E_{\infty S_\infty}$ and we can go 
on to ask when in fact the reverse 
$\geq_B$ holds as well. 



\cite{friedmanstanley} demonstrate, among 
other examples, that isomorphism of 
countable groups, countable fields, and 
countable linear orderings, are all 
$\sim_B E_{\infty S_\infty}$. (In general, 
given any $\psi\in \l_{\omega_1, \omega}$, the 
set of $\m\in {\rm Mod}(\l)$ satisfying $\psi$ is Borel, 
and hence forms a 
standard Borel space in its own right.) 
More recently \cite{gaocamerlo} show 
countable boolean algebras up to isomorphism 
are universal in this class. 



In general most of the questions in this area 
which can be reasonably posed 
have been answered. However one wound 
remains with us from \cite{friedmanstanley}: 



\bigskip 



{\bf Question} (Friedman-Stanley) Is isomorphism 
on countable torsion free abelian groups 
$\sim_B$ to $ E_{\infty S_\infty}$? 





\bigskip 





This question remains open despite several 
efforts to give it closure. 



\subsection{$E_\infty$} 



If $E$ is a countable equivalence 
relation then 
\ref{feldmanmoore} shows $E$ is 
induced by the 
Borel action of a countable group, 
$G$. Any countable group is realizable 
as a closed subgroup of $S_\infty$, 
and so by \cite{beckerkechris} we 
have that $E$ admits classification 
by countable structures. 



Thus the countable Borel equivalence 
relations form a subclass of 
the equivalence relations admitting 
classification by countable structures, with 
a top most example $E_\infty$. 
The subclass is proper, since $\t_2$ 
from our earlier examples, corresponding 
to equality on countable sets of reals, 
is $<_B$ above $E_\infty$. 
In fact, the lesson we take away 
from say 
\cite{hjkelo} is that the countable 
Borel equivalence relations 
are only a tiny part of the totality of 
equivalence 
relations admitting classification 
by countable structures. 



Nevertheless many important examples lie 
in the class of countable Borel 
equivalence relations, and on the whole this 
has proved to be one of the 
hardest and most exciting parts of the 
discipline. In general terms a class of 
countable structures tends to be 
$\leq_B E_\infty$, that is to say, 
{\it essentially countable}, if there 
is some notion of finite rank. 

Simon Thomas and Boban 
Velickovic, \cite{thomasvelickovic}, 
in answer to questions raised in 
\cite{hjorthkechrismodels}, 
show that isomorphism on finitely 
generated groups and fields of finite transcendence 
degree are $\sim_B E_\infty$. 



\subsection{$E_0$} 



If the diagram has a well described bottom, 
id$(\R)$, then it equally has a well defined 
second rung, that of $E_0$. Implicitly in the 
classical literature on this 
subject there is a classification theorem in 
terms of hyperfiniteness. 



\begin{theorem} [Baer, in effect; see \cite{fuchs}] 
Isomorphism on rank one 
torsion free abelian groups is hyperfinite. 
\end{theorem} 



In fact, Baer's original result dates back to the 1920's and is not stated in this 
form. Rather he explicitly associates to each rank one torsion free group a kind of 
{\it type}, consisting of a description of orders considered up to finite difference, 
and goes on to show that the type is a complete invariant. This has generally been 
considered a satisfactory classification of the rank one torsion free groups, and 
Fuchs in \cite{fuchs} asks the vague but earnest question whether the rank two torsion 
free abelian groups can be ``classified". 


\index{classification of torsion free abelian groups} 




\begin{definition} 

For each $n$ let $S_n$ be the 
subgroups of $(\Q^n, +)$. Let 
$\cong_n$ be the isomorphism relation on these 
groups. 

\end{definition} 



Every rank $n$ torsion free abelian group appears 
as a subgroup of $\Q^n$, and in turn 
these subgroups all have rank $\leq n$. Moreover 
two subgroups of $\Q^n$ are isomorphic 
if and only if there is a linear transformation over the 
rationals which sends one to the 
other, and thus the equivalence relation $\cong_n$ 
has countable classes -- and thus 
$\leq_B E_\infty$. 



The authors of 
\cite{hjorthkechrismodels} observe that Baer had 
implicitly shown $\cong_1\leq_B E_0$ 
and went on to suggest as a possible explication 
of Fuchs' question whether 
$\cong_2\leq_B E_0$. With absolutely no evidence, 
and armed only with the arrogance of 
ignorance, \cite{hjorthkechrismodels} conjectured 
that $\cong_2\sim_B E_\infty$. 



This conjecture was refuted by Thomas in a 
spectacular sequence of papers. There have several 
papers around the subject of isomorphism on 
finite rank torsion free abelian groups, most of 
which are surveyed in \cite{thomassurvey}



\begin{theorem} [Thomas; \cite{thomasincreasing}] 
At every $n$ 
\[\cong_n<_B \cong_{n+1}.\] 
\end{theorem} 



\bibliographystyle{plain}

\bibliography{hjorth}

\input{hjorth.ind}














\end{document}