% LaTeX Report Template - customizing header and footer \documentclass{report} \usepackage{amssymb} \usepackage{latexsym} % Set left margin - The default is 1 inch, so the following % command sets a 1.25-inch left margin. %\setlength{\oddsidemargin}{0.25in} \setlength{\oddsidemargin}{0in} % Set width of the text - What is left will be the right margin. % In this case, right margin is 8.5in - 1.25in - 6in = 1.25in. %\setlength{\textwidth}{6in} \setlength{\textwidth}{6.5in} % Set top margin - The default is 1 inch, so the following % command sets a 0.75-inch top margin. \setlength{\topmargin}{-0.25in} % Set height of the header \setlength{\headheight}{0.3in} % Set vertical distance between the header and the text \setlength{\headsep}{0.2in} % Set height of the text \setlength{\textheight}{9in} % Set vertical distance between the text and the % bottom of footer \setlength{\footskip}{0.1in} % Set height of the header \setlength{\headheight}{0.3in} % Set vertical distance between the header and the text \setlength{\headsep}{0.2in} %\markboth{TFA groups}{TFA groups} % Set the beginning of a LaTeX document \begin{document} \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\V{{\Bbb V}} \def\N{{\Bbb N}} \def\Q{{\Bbb Q}} \def\Z{{\Bbb Z}} \def\C{{\Bbb C}} \def\F{{\Bbb F}} \def\o{{\cal O}} \def\e{\epsilon} \def\h{{\hat{X}}} \def\b{{\cal B}} \def\n{\noindent} \def\p{{\cal P}} \def\t{{\cal T}} \def\l{{\cal L}} % Redefine "plain" pagestyle \makeatletter % `@' is now a normal "letter' for LaTeX \renewcommand{\ps@plain}{% \renewcommand{\@oddhead}{\textrm{Your Header}\hfil\textrm{\thepage}}% \renewcommand{\@evenhead}{\@oddhead}% \renewcommand{\@oddfoot}{}% empty footer \renewcommand{\@evenfoot}{\@oddfoot}} \makeatother % `@' is restored as a "non-letter" character \Huge \title{\Huge {\Huge Borel equivalence relations}} \author{{\Huge Greg Hjorth}\\{\LARGE greg@math.ucla.edu}} % Enter your name between curly braces \date{\huge September 2003, Barcelona} \maketitle \pagestyle{myheadings} \markright{\large Borel} % Set to use the "plain" pagestyle %\pagestyle{plain} {\bf $\S$1. Definitions. Examples} \bigskip \bigskip \bigskip \bigskip \n {\bf Definition} A \centerline{{\it Polish space}} \n is a completely metrizable separable space. \bigskip \bigskip \n Its \centerline{{\it Borel sets}} \n are those appearing in the $\sigma$-algebra generated by the open sets. \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \n $(X, \b)$ is a \centerline{{\it standard Borel space}} \n if $\b$ is the collection of Borel sets for some Polish topology on $X$. \bigskip \bigskip \bigskip \bigskip %Sometimes there is a canonical %standard Borel structure, but no canonical choice of a Polish topology. \newpage \n {\bf E.g. 1} $\R$ and $\C$ are Polish. Any compact metric space is Polish. \bigskip \n {\bf E.g. 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$. \bigskip \newpage \n {\bf E.g. 3} Any Borel subset of a Polish space is a standard Borel space in the inherited Borel structure (see e.g. Kuratowski's {\it Topology}). \bigskip \bigskip \bigskip \bigskip \n {\bf E.g. 4} The Borel probability measures on a standard Borel space themselves again form a standard Borel space. \bigskip \bigskip \bigskip \bigskip \n {\bf E.g. 5} Consider the collection of subsets of $\N\times\N\times \N$ which form the graph of 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. \bigskip \bigskip \bigskip \newpage \n {\bf Definition} A function \[f: X\rightarrow Y\] is said to be {\it Borel} if $f^{-1}[B]$ is Borel for any Borel set $B\subset Y$. An equivalence relation $E$ on $X$ is said to be {\it Borel} if it is Borel as subset of $X\times X$. \bigskip \bigskip \bigskip \bigskip \n {\bf Definition} Given $E$ and $F$ Borel equivalence relations on standard Borel $X$ and $Y$, we write \[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);\] \bigskip \bigskip \bigskip \bigskip \n in other words, $f$ pushes down to injective map \[\bar{f}: X/E \rightarrow Y/F\] between the quotient spaces. \newpage \n {\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)$. \bigskip \bigskip \bigskip \bigskip \bigskip \n {\bf Another remark} If $f$ witnesses $E\leq_B F$ it may be the case that $f$ is much more complicated than $E$ and $F$. That is okay. We don't care about the complexity of $f$ as long as it is reasonable. $E\leq_B F$ does not necessarily mean that $E$ is simpler than $F$. \bigskip \bigskip \newpage {\bf $\S$2. Examples} \bigskip \bigskip \n {\bf E.g. 1} For $X$ a standard Borel space, id$(X)$ is the identity relation on $X$. \bigskip \bigskip \n {\bf Fact} (Classical) If $X$ is an uncountable standard Borel space then \[ {\rm id}(X)\sim_B{\rm id}(\R).\] \bigskip \bigskip That is to say, each is Borel reducible to the other. \bigskip \bigskip \n {\bf Theorem}(Silver) If $E$ is Borel, then either: \leftskip 0.6in \n (I) $E\leq_B$ id$(\N)$; or \n (II) id$(\R)\leq_B E$. \leftskip 0in \bigskip \bigskip \bigskip \newpage \n {\bf E.g. 2} Let $E_v$ be the coset equivalence relation of $\Q$ in $\R$: \bigskip $r_1 E_v r_2$ if \[r_1- r_2\in \Q.\] \bigskip \bigskip \bigskip Let $E_0$ be defined on $\p(\N)$ by $A E_0 B$ if their symmetric difference, \[A\Delta B=_{\rm df} (A-B)\cup (B- A),\] is finite. \bigskip \bigskip \bigskip \bigskip \bigskip \n {\bf Fact:} $E_0\sim_B E_v$. \bigskip (I.e. each is $\leq_B$ reducible to the other.) \bigskip \bigskip id$(\R)<_B E_0$. \bigskip (I.e. reduction in one direction but not the other.) \bigskip \newpage \n {\bf E.g. 3} Let $\l$ be the language generated by $\aleph_0$ many unary predicates. Let Mod$(\l)$ be the $\l$-structures with underlying set $\N$ and let \[F_2\] be the isomorphism relation \[\cong|_{{\rm Mod}(\l)}\] on these structures. \bigskip \bigskip \bigskip Even though from the point of model theorists the classification problem for a language with countably many unary predicates is usually considered to be relatively easy, one already has: \bigskip \[{\rm id}(\R)<_B E_0 <_B F_2.\] \newpage \n {\bf E.g. 4} Let $U_\infty$ be the unitary group on $\ell_2$, consisting of linear isometries of $\ell_2$ onto $\ell_2$. Let $\sim_{U_\infty}$ be the conjugacy equivalence relation on operators in $U_\infty$ -- so two unitary operators are $\sim_{U_\infty}$ if and only if they are look the same up to a unitary ``reshuffling" of $\ell_2$. \bigskip \bigskip Let $M([0,1])$ be the collection of all probability measures on the unit interval. Let $\sim^*$ be the equivalence relation of mutually continuity -- that is to say, $\mu \sim^* \nu$ if they have the same null sets. \bigskip \bigskip \bigskip \bigskip \n {\bf Theorem} (In effect, Gelfand) \[\sim^*\leq_B \sim_{U_\infty}\] \[\sim_{U_\infty}\leq_B \sim^*.\] \bigskip \bigskip \n {\bf Theorem} (Kechris) \[F_2 <_B \sim^*.\] \newpage \n {\bf E.g. 5} Let $\cong_n$ be the isomorphism relation on rank $n$ torsion free abelian groups. (Up to isomorphism, these are all subgroups of $\Q^n$.) \bigskip \bigskip \n {\bf Theorem} (In effect, Baer; early 1900's) \bigskip $\cong_1\sim_B E_0$. \bigskip \bigskip That is to say, each is Borel reducible to the other. \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \n {\bf Theorem} (Thomas, c. 2001) For {\it all } $n$ \[\cong_n <_B \cong_{n+1}.\] \newpage \n {\bf E.g. 6} Let $\equiv_T$ be Turing equivalence on subsets of $\N$ -- that is to say, set $A \equiv_T B$ if each is computable from the other. \bigskip \bigskip Very little is known about the precise position about $\equiv_T$ beyond a few initial facts such as \[E_0 <_B \equiv_T <_B F_2.\] \bigskip \bigskip In a paper from the 80's Slaman and Steel ask for something along the lines of the following:- \bigskip \bigskip \bigskip \n {\bf Question} Let $\F$ be a countable non-abelian free group. Does there exist a free action of $\F$ by isometries on a compact metric space with the resulting equivalence relation $E_\F$ having \[E_\F\leq_B \equiv_T?\] \newpage {\bf $\S$3. The picture so far} \bigskip \bigskip At the very bottom of the picture we have Silver's theorem. \bigskip \bigskip \n {\bf Theorem} (Silver, 1970's) If $E$ is Borel, then either: \leftskip 0.6in \n (I) $E\leq_B$ id$(\N)$; or \n (II) id$(\R)\leq_B E$. \leftskip 0in \bigskip \bigskip Then: \bigskip \bigskip \n {\bf Theorem} (Harrington-Kechris-Louveau, 1989) If $E$ is Borel, then either: \leftskip 0.6in \n (I) $E\leq_B$ id$(\R)$; or \n (II) $E_0\leq_B E$. \leftskip 0in \newpage \n {\bf ASIDE:} \bigskip Both these theorems turn into theorems about $L(\R)$ cardinality under determinacy assumptions. \bigskip \bigskip For instance (Woodin) with Silver's theorem we obtain that any set in $A\in L(\R)$ is either wellorderable in $L(\R)$ or has \[|2^\N|_{L(\R)}\leq_{L(\R)} |A|_{L(\R)}\] in the sense of their being an injection in $L(\R)$ of $2^\N$ into $A$. \bigskip \bigskip Harrington-Kechris-Louveau turns into the statement that for any $A\in L(\R)$ either we have some ordinal $\alpha$ with \[|A|_{L(\R)}\leq_{L(\R)} |{{\mathcal P}}(\alpha)^{L(\R)}|_{L(\R)}\] or \[|{\mathcal P}(\N)/{\rm Fin}|_{L(\R)}\leq _{L(\R)} |A|_{L(\R)}.\] \newpage After this there are no outright dichotomy theorems of exactly this form (that is to say, of the form {\it either $E$ is below some canonical example or it is above some other canonical example}). There are at least some immediate successor nodes to $E_0$. \bigskip \bigskip \bigskip \bigskip \n {\bf Definition} For \[\vec x=(x_1, x_2,...)\in (2^\N)^\N,\] \[\vec y=(y_1, y_2,...)\in (2^\N)^\N,\] set $\vec x E_1 \vec y$ if for all sufficiently large $n$ we have \[x_n=y_n.\] Set $\vec x (E_0)^\N \vec y$ if at {\it every $n$} \[x_n E_0 y_n.\] \bigskip \bigskip Here we have $E_0<_B E_1$ and $E_0<_B (E_0)^\N$, and moreover these are both immediate successors. \newpage \bigskip \bigskip \bigskip \n {\bf Theorem} (Kechris-Louveau, 1992) If $E\leq_B E_1$ then either \leftskip 0.6in \n (I) $E\leq_B E_0$, or \n (II) $E_1\leq_B E$. \leftskip 0in \bigskip \bigskip \bigskip \n {\bf Theorem} (H-Kechris, 1996) If $E\leq_B (E_0)^\N$ then either \leftskip 0.6in \n (I) $E\leq_B E_0$, or \n (II) $(E_0)^\N\leq_B E$. \leftskip 0in \bigskip \bigskip \bigskip These are the only immediate successors to $E_0$ known at the present time. \bigskip \bigskip Following work of Ilijas Farah, who produced examples motivated by ideas in Banach space theory, it appears that there are promising candidates for continuum many immediate successors. \bigskip \newpage One can also try for ``local dichotomy" theorems: \bigskip \bigskip \n {\bf Theorem} (1999) If $E$ is Borel reducible to the isomorphism relation on some countable structures, then either: \leftskip 0.6in \n (I) $E$ is Borel reducible to some equivalence relation all of whose classes are countable; or \n (II) $(E_0)^\N\leq_B E$. \leftskip 0in \bigskip \bigskip %There is at least one other faintly plausible candidate for a theorem of this %nature. %\newpage %\n {\bf Question} If $E$ is Borel, must it be the case that %either %\leftskip 0.6in %\n (I) $E\leq E_G$ where $E_G$ arises from the continuous action %of some Polish group\footnote{That is to say, a topological group which %is separable and completely metrizable.} on some Polish space $X$, or %\n (II) $E_1\leq_B E$? %\leftskip 0in %\bigskip %\bigskip %\bigskip %It was shown by Louveau and Kechris that $E_1$ is never Borel reducible to some %such $E_G$, so this is a bit like asking whether $E_1$ is the canonical obstruction %to being reducible to a Polish group action. \newpage \n {\bf Recent work on countable equivalence relations} \bigskip \bigskip \n {\bf Definition} A Borel equivalence relation is {\it countable} if all of its equivalence classes are countable. It is {\it essentially countable} if it is $\leq_B$-reducible to some countable equivalence relation. \bigskip \bigskip It turns out that these are in some sense distinct notions up to Borel reducibility. Just over summer it was realized that: \bigskip \bigskip \n {\bf Theorem} There is an essentially countable Borel equivalence relation $E$ such that for no countable Borel equivalence relation $F$ do we have \[E \sim_B F.\] \newpage A countable Borel equivalence relation is said to be {\it treeable} if there is a Borel way to assign a tree structure (without any distinguished root) to each equivalence class -- thus, $E$ on $X$ is treeable if there is a Borel graph \[G\subset X\times X\] such that $G$ has no loops and its connected components are the $E$-equivalence classes. \newpage \n {\bf E.g.1} $E_0$ is countable. \bigskip \bigskip \bigskip \bigskip \n {\bf E.g. 2} The various $\cong_n$'s (isomorphism on finite rank torsion free abelian groups) are essentially countable. \bigskip \bigskip \bigskip \bigskip \n {\bf E.g. 3} Any free, Borel action of $\F_2$ (the free group on two generators) gives rise to a treeable orbit equivalence relation. \newpage \n {\bf A strange empirical fact} \bigskip Practically all known constructions of countable Borel equivalence relations which are $\leq_B$-distinguishable involve ergodic theoretic techniques. They come down to finding \[E_G, \: \: \: E_H\] arising from ergodic (that is to say, any invariant measurable set is null or conull), measure preserving actions of countable groups $G, H$ on standard Borel probability spaces \[(X, \mu), \:\:\: (Y, \nu)\] such that on {\it any} invariant measure one \[X_0\subset X\] we have that the induced orbit equivalence relation $E_G^{X_0}$ is not Borel reducible to $E_H$. \bigskip \bigskip In particular $E_G$ and $E_H$ are not {\it orbit equivalent}. \bigskip \bigskip \bigskip \bigskip \newpage \n {\bf Definition} Two equivalence relations $E$ and $F$ on standard Borel probability spaces $(X, \mu)$ and $(Y, \nu)$ are said to {\it orbit equivalent} if there is a measure preserving bijection \bigskip \[\theta: X\rightarrow Y\] \bigskip such that for $\mu$-a.e. $x_1$ we have for all $x_2$ \bigskip \[x_1 E x_2 \Leftrightarrow \theta(x_1) F \theta(x_2).\] \bigskip Two actions are {\it orbit inequivalent} if the equivalence relations they induce are orbit inequivalent. \bigskip \bigskip \newpage It is already somewhat non-trivial to find orbit inequivalent equivalence relations of the indicated form. \bigskip \bigskip \bigskip \bigskip \bigskip \n {\bf Theorem} (Dye; 1950's) Any two ergodic, free, measure preserving actions of $\Z$ on standard Borel probability spaces are orbit equivalent. \bigskip In fact, any two ergodic, free, measure preserving actions of any two infinite abelian groups on any two standard Borel probability spaces are necessarily orbit inequivalent. \bigskip \bigskip \bigskip \newpage In the 80's Zimmer used techniques from algebraic groups to obtain infinitely many orbit inequivalent ergodic measure preserving actions of distinct groups. Around the end of the century Adams and Kechris imported these techniques into the study of the Borel reducibility ordering. \bigskip \bigskip \bigskip \n {\bf Theorem} (Adams-Kechris; 1999) There are continuum many countable Borel equivalence relations, $(E_r)_{r\in 2^{\aleph_0}}$, such that for $r\neq s$ we have $E_r$ not Borel reducible to $E_s$. \bigskip \bigskip \bigskip \bigskip \bigskip \newpage Their examples arise from specific groups acting in a measurable manner, and the incomparability of the examples is in a part a reflection of the groups being distinct -- that is to say, they have fixed groups $(G_r)_{r\in 2^{\aleph_0}}$ for which we can take each $E_r$ to be {\it any} orbit equivalence relation induced by a free, ergodic, measure preserving action of $G_r$. The examples are non-treeable. \bigskip \bigskip The pattern of these results is to suggest that different equivalence relations are associated with different groups. \bigskip \bigskip \bigskip Recently attention has turned to finding an analog of the Adams-Kechris examples for the treeable equivalence relations. This seems to turn into a problem about actions of the free group. \newpage \bigskip \bigskip \bigskip \n {\bf Fact} If $E$ is a countable, Borel, treeable equivalence relation on a standard Borel probability space $(X, \mu)$ which satisfies certain further mild assumptions (e.g. it arises from a free, ergodic, measure preserving action of some group $G$), then there is a non-null set \[A\subset X\] such that \[E|_A\] is given by a free, ergodic, measure preserving action of either $\Z$ (hence $E\leq_B E_0$ a.e.), or \[\F_2\] (the free group on two generators), or \[\F_\infty\] (the free group on $\aleph_0$ many generators). \bigskip \bigskip \bigskip This seems to put us into the situation of needing to find many orbit inequivalent actions of the free group, a problem known in ergodic theory which remained open until only a couple of months ago: \newpage \n {\bf Theorem} (Gaboriau-Popa; 2003) There are continuum many non-orbit equivalent free, ergodic, measure preserving actions of $\F_2$ on standard Borel probability spaces. \bigskip \bigskip \bigskip \bigskip Unlike the techniques of Zimmer, their argument appears to give no hint of how it might be adapted for $\leq_B$-incomparability. \bigskip \bigskip \bigskip \bigskip At the present time very little is known about the structure of the treeable equivalence relations under $\leq_B$-reducibility. \newpage Kechris and Louveau established that there is a ``universal" treeable equivalence relation $E_{\t\infty}$ which is strictly above $E_0$. \bigskip \bigskip \bigskip Then last year it was shown by unrelated techniques that there is a third example which is strictly between -- so that we have as our sum total of known treeable, countable, Borel equivalence relations \[ E_0 <_B E <_B E_{\t\infty}.\] \bigskip \bigskip \bigskip Nothing more is known beyond this. \newpage \bigskip \bigskip \bigskip \bigskip % Set the ending of a LaTeX document \end{document}