\documentclass{beamer} \usepackage{beamerthemesplit} \usepackage{amsmath} \usepackage{amssymb} \usepackage[all]{xy}\newcommand{\ww}{{\omega^\omega}} \usepackage{eepic} \usepackage{xcolor} \usepackage{comment} %\usepackage{tikz} \theoremstyle{theorem} \newtheorem*{thm}{Theorem} \newtheorem*{lem}{Lemma} \theoremstyle{definition} %\newtheorem*{fact}{Fact} \newtheorem*{defn}{Definition} \newtheorem*{ques}{Question} \newtheorem*{cor}{Corollary} \newtheorem*{conj}{Conjecture} \newtheorem*{rem}{Remark} \newtheorem*{ex}{Example} \newcommand{\res}{\restriction} \newcommand{\bg}{\boldsymbol{\Gamma}} \newcommand{\bgd}{\check{\boldsymbol{\Gamma}}} \newcommand{\bd}{\boldsymbol{\Delta}} \newcommand{\bs}{\boldsymbol{\Sigma}} \newcommand{\bp}{\boldsymbol{\Pi}} \newcommand{\on}{\text{On}} \newcommand{\sP}{\mathcal{P}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\lh}{\text{lh}} \newcommand{\mys}{\bigskip} \newcommand{\id}{\text{id}} \newcommand{\ac}{\mathsf{AC}} \newcommand{\sI}{\mathcal{I}} \newcommand{\sB}{\mathcal{B}} \begin{document} \setbeamercovered{dynamic} \title{Countable Borel Equivalence Relations, Markers, and Shift Equivalence} \author{S.\ Jackson} \institute{ Department of Mathematics\\ University of North Texas\\ %jackson@unt.edu } \date{{\color{red}Real Analysis 33}\\ June, 2009\\ Durant, Oklahoma} \begin{frame} \titlepage \end{frame} \section{Equivalence Relations} \subsection{Introduction} \begin{frame} %\subsection{Introduction} $X$, $Y$ will denote {\color{red} standard Borel spaces}. \mys An equivalence relation $E$ is {\color{red} countable} if all classes $[x]_E$ are countable. $E$ is {\color{red} Borel} if $E \subseteq X \times X$ is Borel. \mys $X/E$ is the {\color{red} quotient space} of equivalence classes. \mys \begin{ex} If $E=\id$, then $X/E \cong X$, a standard Borel space. \end{ex} \end{frame} \begin{frame} With $\ac$, every set has a cardinality, and those of size $c=2^\omega$ can be viewed as standard Borel spaces. \mys So, with $\ac$, for every countable $E$, $X/E$ is isomorphic to a standard Borel space. \mys However, we are interested in ``definable'' cardinalities, i.e., definable maps between spaces. Usually this means Borel. \mys Note that $X/\id \cong X$ by a Borel map, namely, $f=\id$. \end{frame} \begin{frame} \begin{defn} If $(X, E)$, $(Y, F)$ are Borel equivalence relations, we say $E \leq F$ ($E$ is {\color{red} reducible} to $F$) if there is a Borel function $f \colon X \to Y$ such that $$x\ E\ y \leftrightarrow f(x)\ F\ f(y).$$ \end{defn} \mys $X/E$ is Borel isomorphic to a standard Borel space iff $(X,E) \leq (\R, \id)$. \mys When $E$ is countable this equivalent to saying $E$ has a Borel {\color{red} selector}: \mys \begin{defn} $S \subseteq X$ is a selector for $E$ if for all $x$, $| S \cap [x]_E|=1$. \end{defn} \mys \end{frame} \begin{frame} \begin{defn} $E$ is {\color{red} smooth} or {\color{red} tame} if $E \leq \id$. \end{defn} \mys When $E$ is smooth, then $X/E$ is Borel isomorphic to a standard Borel space, and in this case the ``Borel cardinalities'' are completely understood. \mys Namely, if $A \subseteq X$ is Borel, then either $A$ is countable or contains a perfect subset. Any two Borel sets in a Polish space of the same cardinality are Borel isomorphic. \mys So, for countable $E$ on an uncountable Polish space $X$, there is up to Borel isomorphism only one smooth equivalence relation, $\id$. \end{frame} \begin{frame} \begin{thm}[Silver] If $E$ is a $\bp^1_1$ equivalence relation on a Polish space $X$, then $E$ has either countable many or perfectly many equivalence classes. \end{thm} \mys \begin{cor} If $E$ is a Borel equivalence relation with uncountably many classes, then $\id \leq E$. \end{cor} \mys Let $\{ n\}$ be a Borel equivalence relation with $n$ classes. Likewise for $\{ \omega\}$. \mys For general Borel $E$ we have the following initial segment of the equivalence relations: \mys $$ \{ 1\} \leq \{2\} \cdots \leq \{ \omega\} \leq \id$$ \mys For countable $E$, we have $\id$ at the bottom. \end{frame} \begin{frame} Let $E_0$ be the equivalence relation of eventual equality on $2^\omega$: \mys $$ x\ E_0\ y \leftrightarrow \exists n\ \forall n \geq n\ (x(m)=y(m)). $$ \begin{fact} $E_0$ is bireducible with the Vitali equivalence relation on $\R$. \end{fact} \mys \begin{thm}[Harrington-Kechris-Louveau] Let $E$ be a Borel equivalence relation on a Polish space $X$ Then either $E \leq \id$ or $E_0 \leq E$ (in fact $E_0 \sqsubseteq E$). \end{thm} \mys So, for general Borel $E$ we have: \mys $$ \{1\} \leq \{2 \} \leq \cdots \leq \{ \omega\} \leq \id \leq E_0. $$ \end{frame} \begin{frame} General Borel equivalence relations can arise in many different ways. \mys \begin{itemize} \item The {\color{red} orbit equivalence relation} from a Borel action of a Polish group $G$ on a Polish space $X$. For example, the {\color{red} logic action} of $S_\infty$ on the models of a countable theory. \item If $\sI$ is any Borel ideal on $\omega$, $x \equiv y$ iff $x \triangle y \in \sI$. \item $\sB$ a separable Banach space with basis $\{ e_1, e_2,\dots\}$. $X=\R^\omega$ with $x E y$ iff $x-y \in \sB$. For example $c_0, \ell_1, \ell_p, \dots, \ell_\infty$. \item $E_1$ on $(2^\omega)^\omega$: $\{ x_n\} E_1\ \{ y_n\}$ iff $\exists k\ \forall \ell \geq k\ (x_\ell =y_\ell)$. \item $(E_0)^\omega$, the countable product of $E_0$. \item $x =^+ y$ iff $\{ x_n\}=\{ y_n\}$. \end{itemize} \end{frame} \begin{frame} \begin{center} \setlength{\unitlength}{.3cm} \begin{picture}(20,25)(0,0) \put(10,1){\circle*{.3}} \put(12,0.2){\makebox(0,0)[b]{$\id(2^\omega)$}} \put(10,1){\line(0,1){3}} \put(10,4){\circle*{.3}} \put(11,2.8){\makebox(0,0)[b]{$E_0$}} \put(10,4){\line(-3,2){6}} \put(4,8){\circle*{.3}} \put(3,6.5){\makebox(0,0)[b]{$E_0^\omega$}} \put(10,4){\line(-1,2){2}} \put(8,8){\circle*{.3}} \put(7.5,6.5){\makebox(0,0)[b]{$E_\infty$}} \put(10,4){\line(1,2){2}} \put(12,8){\circle*{.3}} \put(12.5,6.5){\makebox(0,0)[b]{$\ell_1$}} \put(10,4){\line(3,2){6}} \put(16,8){\circle*{.3}} \put(16.2,6.5){\makebox(0,0)[b]{$E_1$}} \put(4,8){\line(0,1){6}} \put(4,14){\circle*{.3}} \put(3,13.8){\makebox(0,0)[b]{$=^+$}} \put(4,14){\line(2,-3){4}} \put(16,8){\line(0,1){6}} \put(16,14){\circle*{.3}} \put(17,13.2){\makebox(0,0)[b]{$\ell_\infty$}} \put(21.2,13.2){\makebox(0,0)[b]{(equivalence}} \put(21,12){\makebox(0,0){of bases)}} \put(16,14){\line(-2,-3){4}} \put(16,14){\line(-4,-3){8}} \put(10,23){\line(2,-3){6}} \put(10,23){\line(-2,-3){6}} \put(10,23){\circle*{.3}} \put(10.2,23){\makebox(0,0)[b]{$E_{{\bf\Sigma}^1_1}$}} \put(15.5,23){\makebox(0,0)[b]{(isomorphism)}} \put(12,8){\line(-2,3){6}} \put(6,17){\circle*{.3}} \put(5,17){\makebox(0,0)[b]{$E_G^\infty$}} \put(9.5,17){\makebox(0,0)[b]{(isometry)}} \end{picture} \end{center} \end{frame} \begin{frame} If $G$ is a countable group, then $2^G$ is a compact Polish space. \mys The {\color{red}(left) action} of $G$ on $2^G$ is given by: $$ g \cdot x (h)=x(g^{-1} h) $$ \mys Equivalently, $g \cdot A = gA=\{ g a \colon a \in A\}$, where $A \subseteq G$. \mys \begin{ex} $\Z^n$ acts by shifts on $2^{\Z^n}$. Equivalence classes can be viewed as $n$-dimensional grids of $0$s and $1$s (without specifying an origin). \end{ex} \end{frame} \subsection{Hyperfinite} \begin{frame} We consider henceforth countable Borel equivalence relations. \mys \begin{thm}[Feldman-Moore] If $E$ is a countable Borel equivalence relation, the $E$ is induced by the Borel action of a countable group $G$. \end{thm} \mys Thus, it makes sense to study countable equivalence relations ``group by group.'' \mys If $G$ is a finite group, then $E_G$ is smooth. \mys \begin{defn} $E$ is {\color{red} hyperfinite} if $E$ is an increasing union $E= \bigcup_n E_n$ where each $E_n$ is finite (i.e., all classes are finite). \end{defn} \end{frame} \begin{frame} Consider the simplest infinite group $\Z$. \mys \begin{thm}[Slaman-Steel] The following are equivalent. \mys \begin{enumerate} \item $E$ is hyperfinite. \item $E$ is induced by a Borel action of $\Z$. \item All the $E$ (infinite) classes can be uniformly $\Z$ ordered. \item $E \leq E_0$. \end{enumerate} \end{thm} \mys In particular, $\Z$-actions give rise to hyperfinite equivalence relations. \end{frame} \begin{frame} \begin{ques} For which countable groups $G$ are the Borel actions of $G$ necessarily hyperfinite? \end{ques} \mys \begin{thm}[Weiss] If $E$ is induced by a Borel action of $\Z^n$, then $E$ is hyperfinite. \end{thm} \mys $G$ is {\color{red}amenable} if $G$ has an invariant probability measure. Equivalent to the existence of a {\color{red}F\"{o}lner} sequence. \mys \begin{fact} If $G$ is {\color{red} non-amenable} then there is a free action of $G$ which is not hyperfinite. \end{fact} \end{frame} \begin{frame} \begin{conj}[Kechris] If $G$ is amenable, then every Borel action of $G$ is hyperfinite. \end{conj} The conjecture has some credibility due to the following results. \mys \begin{thm}[Connes-Feldman-Weiss] If $E$ is an equivalence relation induced by the action of an amenable group with an invariant probability measure $\mu$, then $E$ is hyperfinite $\mu$-almost everywhere. \end{thm} \mys \begin{thm}[Gao-J] Every Borel action of a countable abelian group is hyperfinite. \end{thm} \end{frame} \begin{frame} \section{New Hyperfiniteness Proofs} The proof of the abelian result gives new information, even in the simplest case of $G=\Z$. \mys \begin{thm} There is a {\color{red} continuous} embedding from $2^\Z$ into $E_0$. \end{thm} \mys In fact, we get: \begin{thm} There is a {\color{red} continuous} embedding $f$ from $2^\Z$ into $E_0$ such that if $y\in 2^\Z$ is a positive shift of $x$, then $f(y)$ is a positive shift under the odometer action of $f(x)$. \end{thm} \end{frame} \begin{frame} This generalized to $(\ww)^\Z$ which then shows: \mys \begin{cor} If $(X,E)$ is induced by the continuous action of $\Z$ on a $0$-dimensional Polish space $X$, then there is a continuous embedding from $(X,E)$ to $(2^\omega,E_0)$. \end{cor} \mys So, $E_0$ is {\color{red} universal} for continuous actions of $\Z$ on $0$-dimensional Polish spaces. \mys In fact: \begin{cor} Let $\pi$ be a free auto-homeomorphism of a $0$-dimensional Polish space $X$. Then $\pi$ is topologically isomorphic to the action of the odometer on a subspace of $2^\omega$. \end{cor} \end{frame} \subsection{Nice Markers} \begin{frame} Proof uses the construction of nice marker regions. \mys \begin{defn} A {\color{red} Marker set} for $(X,E)$ is a Borel set $M \subseteq X$ with $M \cap [x]_E\neq \emptyset$ for all $x \in X$. A set of {\color{red} marker regions} for $(X,E)$ is a Borel finite subequivalence relation $R \subseteq E$. $M$ is associated to $R$ if $|M \cap [x]_R|=1$ for all $x \in X$. \end{defn} \mys Note: Every set of marker regions has an associated marker set. \mys The proofs of the previous theorems use the construction of marker regions with nice geometric and definability properties. \end{frame} \subsection{Some Results} \begin{frame} These methods led to the following results. \mys \begin{thm} There is a continuous embedding from $2^{\Z^n}$ into $E_0$. Likewise for continuous action of $\Z^n$ on a $0$-dimensional Polish space. \end{thm} \begin{thm} There is a continuous embedding from the free part $F$ of $2^{\Z^{<\omega}}$ into $E_0$. \end{thm} \begin{thm} There is a Borel embedding from $2^{\Z^{<\omega}}$ into $E_0$. \end{thm} \begin{thm} Every equivalence relation generated by the Borel action of an abelian group is hyperfinite. \end{thm} \end{frame} \subsection{Marker Construction} \begin{frame} To illustrate the ideas, we sketch the proof in the simplest setting: show there is a continuous embedding from $F(2^\Z)$ into $E_0$. \mys First we get (relatively) clopen marker sets (we do this step for $\Z^n$): \begin{itemize} \item $S_0 \supseteq S_1 \supseteq S_2 \supseteq \cdots$, each $S_i$ relatively clopen in $F(2^\Z)$. \item There are distances $d_0 \gg d_1 \gg d_2 \gg \cdots$ such that: \begin{enumerate} \item $\forall x,y \in S_n\ \rho(x,y)> d_n$. \item $\forall x \in X\ \exists y \in S_n\ \rho(x,y) \leq d_n$. \end{enumerate} \end{itemize} The definition of $S_n$ is an $\omega$-length construction, constructing a maximal set $S_n=\bigcup_i S_n^i$ satisfying (1). \mys Sets are $S_n^i$ relatively open, so also is $S_n$. Maximality gives (2) which also shows $S_n$ is relatively closed. \end{frame} \begin{frame} From these clopen marker sets, one next constructs clopen marker regions which are rectangular. In fact, they can made almost the same size (side lengths of either $d_n$ or $d_n+1$). \mys \begin{ques} Can you get Borel marker regions for $F(2^{\Z^n})$ which are almost the same size and almost lined-up? \end{ques} \mys Construction of the marker regions from the marker sets uses the ``big marker-little marker'' method, and a finite sequence of successive adjustments. \mys In case of $\Z$, this step is rather trivial. \end{frame} \subsection{construction of embedding} \begin{frame} Next we modify the marker regions to anti-cohere. \mys At each step when we produce marker regions $R^n$, we also produce an ``orthogonal'' set of marker regions $\tilde{R}^n$: no face of an $\tilde{R}^n$ rectangle is close to a parallel face of an $R^n$ rectangle. \mys For $\Z$ this just says the endpoints of each $\tilde{R}^n$ interval are not close to those of an $R^n$ interval \mys Close here means some fixed fraction of $d_n$ (a geometrical constant depending only on $n$). \mys The $\tilde{R}^n$ are produced by the same adjustment process as the $R^n$. \end{frame} \begin{frame} We now use the $R^n$ and $\tilde{R}^n$ to produce the final clopen marker regions $Q^n$. \mys We start with $R^n_n=R^n$, and we define the marker regions $R^n_{n-1},\dots, R^n_0$, and we will set $Q^n=R^n_0$. \mys \begin{rem} In the $\Z^n$ case the $R^n_n, \dots, R^n_1$ become increasingly ``fractal.'' \end{rem} \mys In going from $R^n_{i+1}$ to $R^n_i$ we add or subtract an interval of $\tilde{R}^i$ from the ends of each interval in $R^n_{i+1}$. This ensures that the new endpoints of each $R^n_i$ interval are a fraction of $d_i$ away those of each $R^i$ interval. \mys We assume w.l.o.g.\ that $d_i \gg \sum_{jm$, the endpoints of each $Q^n$ interval are $d_m$ far from the endpoints of each $R^m$, and hence each $Q^m$ interval. \end{itemize} \mys Then for any $x \sim y$, there are only finitely many $n$ such that an endpoint of a $Q^n$ marker region separates $x$ from $y$ (this follows from (2) above). \mys Thus, $x \sim y$ iff for all large enough $n$ we have $x \sim_{Q^n} y$. This gives a continuous embedding into $E_0$. \mys Proof can be extended to handle non-free part of $2^\Z$ as well (and likewise for $2^{\Z^n}$. \end{frame} %\subsection{Questions} \begin{frame} \begin{ques} Does there exists a continuous embedding from $2^{\Z^{< \omega}}$ into $E_0$? Yes for free part. \end{ques} \mys \begin{ques} How far can these regular marker arguments be extended? \end{ques} \begin{ques} Are there more algebraic, less geometrical, versions of these arguments? \end{ques} \mys This may be important for extending these arguments further. \end{frame} \subsection{Technical question} \begin{frame} \frametitle{A Technical Question} \begin{itemize} \item In the Slaman-Steel (Borel) embedding from $2^\Z$ to $E_0$, Borel marker sets $M_0 \supseteq M_1 \supseteq \cdots$ are constructed such that $\bigcap_n M_n=\emptyset$. \item For the continuous embedding from $2^\Z$ to $E_0$ we use clopen marker sets (on $F(2^\Z)$) such that $|\bigcap_m M_n \cap [x] | =0$ or $1$ for all $x \in F(2^\Z)$. \end{itemize} \mys \begin{ques} Does there exists a sequence $M_0 \supseteq M_1 \supseteq \cdots$ of relatively clopen marker sets in $F(2^\Z)$ with $\bigcap_n M_n=\emptyset$? \end{ques} \end{frame} \section{Coloring Property} \begin{frame} \frametitle{A Coloring Property} This question led to the formulation of the following property. \mys \begin{defn} $c \colon G \to \{ 0,1\}$ is a {\color{red} $2$-coloring} if $$ \forall s \in G \ \exists T \in G^{< \omega}\ \forall g \in G\ \exists t \in T\ (c(gt) \neq c(gst)).$$ \end{defn} This definition was formulated independently by Pestov (c.f.\ paper of Glasner and Uspenski). \end{frame} \subsection{Consequences} \begin{frame} The following connects the coloring property with the dynamics of the shift action. \begin{thm} $x \in 2^G$ is a $2$-coloring iff $\overline{[x]} \subseteq F(2^G)$. \end{thm} \mys Note: Definition formulated independently by Pestov. \mys Also, the $2$-coloring property for $G$ gives a {\color{red} marker compactness property} for $F(2^G)$: \medskip \begin{thm}[MCP] Suppose $G$ has the coloring property. Let $S_0 \supseteq S_1 \supseteq S_2 \supseteq \cdots$ be relatively closed complete sections of $F(2^G)$. Then $\bigcap_n S_n \neq \emptyset$. \end{thm} \end{frame} \subsection{Main Theorem} \begin{frame} \frametitle{Main Theorem} \begin{thm}[Gao, J, Seward] Every countable group has the $2$-coloring property. \end{thm} \mys Note: Partial results were obtained independently also by Glasner and Uspenski. \mys \begin{rem} By different arguments first showed the coloring property for abelian, solvable, and free groups, and for every group $G$ with $\Z \unlhd G$. \end{rem} \end{frame} \begin{frame} The proof uses {\color{red}two idea}: \begin{itemize} \item Construct suitable marker regions for the group $G$. \item Exploit polynomial vs.\ exponential growth. \end{itemize} \medskip We first describe the construction of the marker regions. Recall $G$ is a countable infinite group. \end{frame} \begin{frame} We inductively define marker sets $\Delta_n \subseteq G$ and finite sets $F_n \subseteq G$ (with $1 \in F_n$). \medskip The $n$th level marker regions will be the translates $gF_n$ for $g \in \Delta_n$. \medskip Will have: \begin{itemize} \item $F_0 \subseteq F_1 \subseteq F_2 \subseteq \cdots$ \item $\bd_0 \supseteq \bd_1 \supseteq \bd_2 \supseteq \cdots$ \end{itemize} \medskip Each $F_n$ region will be a union of copies of $F_i$ for $i