% LaTeX Article Template - using defaults \documentclass{article}[12pt] \usepackage{amssymb} \usepackage{latexsym} \pagestyle{myheadings} \markright{Essentially countable} \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.15in} % 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}{6.5in} % Set top margin - The default is 1 inch, so the following % command sets a 0.75-inch top margin. \setlength{\topmargin}{-0.1in} % Set height of the header \setlength{\headheight}{0.3in} % Set height of the text \setlength{\textheight}{8.1in} % Set vertical distance between the text and the % bottom of footer \setlength{\footskip}{0.8in} % Set the beginning of a LaTeX document \begin{document} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{counterexample}[theorem]{Counterexample} \newtheorem{mess}[theorem]{Messy Fact} \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{pcounterexample}[1][Counterexample]{\begin{trivlist} \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}} \def\Ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\sim$}}}{}} \def\ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\scriptscriptstyle\sim$}}}{}} \def\R{{\mathbb R}} \def\C{{\mathbb C}} \def\V{{\mathbb V}} \def\N{{\mathbb N}} \def\Z{{\mathbb Z}} \def\K{{\mathbb K}} \def\B{{\mathbb B}} \def\F{{\mathbb F}} \def\Q{{\mathbb Q}} \def\o{{\omega}} \def\oo{{\omega^{\omega}}} \def\lo{{\omega^{<\omega}}} \def\d{{\dot{\bigcup}}} \def\h{{\cal H}} \def\no{\noindent} \def\a{{\mathcal A}} \def\b{{\mathcal B}} \def\l{{\mathcal L}} \def\n{{\mathcal N}} \def\m{{\mathcal M}} \def\p{{\mathcal P}} \def\h{{\mathcal H}} \def\co{{\mathcal O}} \def\t{{\mathcal T}} \def\c{{\mathcal C}} \def\m{{\mathcal M}} \def\nh{|\!|} \title{\huge Bi-Borel reducibility of essentially countable Borel equivalence relations\footnote{Key words and phrases: Equivalence relation, Borel reducibility, near hyperbolic group, rigidity. 2000 Mathematics Subject Classifications: Primary 03E15. Secondary 20F67, 37A20.}} \author{Greg Hjorth\footnote{ Partially supported by NSF grant DMS 0140503}} % Enter your name between curly braces %\date{\today} % Enter your date or \today between curly braces \maketitle %\section{Introduction} This note answers a questions from \cite{jacksonkechrislouveau} by showing that considered up to Borel reducibility, there are more essentially countable Borel equivalence relations than countable Borel equivalence relations. Namely: \begin{theorem} There is an essentially countable Borel equivalence relation $E$ such that for {\rm no} countable Borel equivalence relation $F$ (on a standard Borel space) do we have \[E\sim_B F.\] \end{theorem} %Here $E\sim_B F$ is an abbreviation for $E\leq_B F \leq_B E$. The proof of the result is short. It does however require an extensive rear guard campaign to extract from the techniques of \cite{hjorthkechris} the following \begin{mess} There are countable Borel equivalence relations $(E_x)_{x\in 2^\N}$ such that:- \leftskip 0.4in \noindent (i) each $E_x$ is defined on a standard Borel probability space $(X_x, \mu_x)$; each $E_x$ is $\mu_x$-invariant and $\mu_x$-ergodic; \noindent (ii) for $x_1\neq x_2$ and $A$ $\mu_{x_1}$-conull, we have $E_{x_1}|_A$ not Borel reducible to $E_{x_2}$; \noindent (iii) if $f: X_x\rightarrow X_x$ is a measurable reduction of $E_x$ to itself, then $\mu_x({\rm im}(f))>0$; \noindent (iv) \[\bigcup_{x\in 2^\N}\{x\}\times X_x\] is a standard Borel space on which the projection function \[(x, z)\mapsto x\] is Borel and the equivalence relation $\hat{E}$ given by \[(x, z) \hat{E} (x', z')\] if and only if $x=x'$ and $zE_x z'$ is Borel; \noindent (v) \[2^\N\rightarrow M(\bigcup_{x\in 2^\N}\{x\}\times X_x)\] \[x\mapsto \delta_x\times \mu_x\] is Borel. \label{messy} \end{mess} We first prove the theorem granted this messy fact. We then prove the fact. (iv) and (v) are messy and unpleasant to state precisely, but are intended to express the idea that we have an effective parameterization of countable Borel equivalence relations by points in a standard Borel space. Examples along these lines appear already in the Adams-Kechris constructions; the new feature is (iii). Simon Thomas has pointed out to me that in light of theorem 4.4 \cite{thomas} the Gefter-Golodets examples of section 5 \cite{thomas} also satisfy the conclusion of \ref{messy}. None the less I think it is worth including the construction below, since it ultimately relies on the far more elementary techniques of \cite{hjorthkechris}. \medskip \noindent{\bf Acknowledgments:} I am exceedingly grateful to an anonymous referee for a thorough and critical reading of the original version of this paper and for making many helpful comments. \medskip \section{Introduction} We include a few of the main definitions, some notational conventions, and facts about measure theory in the context of descriptive set theory. A more complete introduction to the theory of Borel equivalence relations can be found in \cite{hjorthkechris}, \cite{jacksonkechrislouveau}, or \cite{thomas}. \begin{definition} For equivalence relations $E, F$ defined on Polish spaces $X, Y$ we write \[E\leq_B F\] if there is a Borel function $f:X\rightarrow Y$ with \[x_1 E x_2\Leftrightarrow f(x_1) F f(x_2).\] We write $E\sim_B F$ if $E\leq_B F$ and $F\leq_B E$. We say that $E$ is {\it countable} if every equivalence class is countable and {\it Borel} if it is Borel as a subset of $X\times X$. We say that it is {\it essentially countable} if there is some countable, Borel $F$ with $E\leq_B F$. \end{definition} \def\m{{\mathcal M}} \begin{definition} For $X$ a Polish space we denote by $\m(X)$ the collection of Borel probability measures on $X$. This is given the $\sigma$-algebra generated by sets of the form \[\{\mu:a< \int fd\mu 0$ the sets \[\{(y, \mu)\in Y\times \m(X): \mu(\{x: (x, y)\in A\})\}>a\] \[\{(y, \mu)\in Y\times \m(X): \mu(\{x: (x, y)\notin A\})\}>a\] are both $\Ubf{\Sigma}^1_1$, which follows from 29.26 \cite{kechris}. \end{proof} \begin{definition} For a group $G$ acting on a set $X$ and $F\subset X$ we use stab$_F$ to denote the {\it set wise stabilizer} -- that is to say, the collection of $g\in G$ such that $\{g\cdot x: x\in F\}=F$. Thus in particular, for $x\in X$, stab$_{\{x\}}$ denotes the group elements leaving $x$ fixed. In the case that $G$ acts on a set $X$ we will use $[X]^n$ to denote the size $n$ subsets of $X$ equipped with the natural action \[g\cdot \{x_1,..., x_n\}=\{g\cdot x_1, ..., g\cdot x_n\}.\] We use $[X]^{<\infty}$ to denote the union of the $[X]^n$'s. \end{definition} \begin{lemma} The action of $G$ on its finite subsets, $[G]^{<\infty}$, is free if and only if $G$ is torsion free. \end{lemma} \begin{proof} If $g$ has infinite order, then for any $h\in G$, $\{g^n\cdot h: n\in \N\}$ is infinite, and thus there is no $g$-invariant finite subset of $G$. Conversely, if $H$ is a finite subgroup of $G$ then it is a fixed point in $[G]^{<\infty}$ for any $h\in H$. \end{proof} \begin{lemma} If $G$ acts freely on $X$, then there is a $G$-map from $X$ to $G$. \end{lemma} \begin{proof} There is no requirement that this $G$-map be Borel, and thus we can select from each orbit $[x]_G$ a unique point $x_0\in [x]_G$. From this we obtain a well defined map by letting $\theta(g\cdot x_0)=g$. \end{proof} We will at some later point need the following corollary. \begin{corollary} \label{map} If $G$ is a torsion free group then there is a $G$-map from $[G]^{<\infty}$ to $G$. \end{corollary} \begin{definition} For $X$ a standard Borel space, we let $\m_{\leq n}(X)$ be the probability measures which concentrate on at most $n$ points and $\m_{\geq n}(\m)$ the measures which do {\it not} concentrate on at most $n-1$ points. Thus $\m_{\geq n}(X)=\m(X)\setminus \m_{\leq n-1}(X)$. \end{definition} The next lemma is a routine generalization of the argument given at C2.3 \cite{hjorthkechris} along with credit to Lyons. \begin{lemma} \label{lyons} Suppose that $G$ is a group, $X$ is a standard Borel $G$-space, $Y$ is a countable $G$-space, and there is a Borel $G$-map from $[X]^n$ to $Y$. Then there is a Borel $G$-map from $\m_{\geq n}(X)$ to $[Y]^{<\infty}$. \end{lemma} \begin{proof} Let $\phi$ be the Borel $G$-map from $[X]^n$ to $Y$. Let $\{*\}$ be some single point not in $Y$ and form the space $Y^*=Y\dot{\bigcup} \{*\}$. Define the Borel map \[\eta: X^n\rightarrow Y^*\] by $\eta(x_1, x_2,..., x_n)=\phi(\{x_1, x_2,..., x_n\})$ if the points are distinct, and equal to the default value $*$ otherwise. For $\mu\in \m_{\geq n}(X)$ we let $\mu^*$ be the measure on $Y^*$ which has at each $y_0\in Y^*$ \[\mu^*(\{y_0\})=\mu^n(\{(x_1,...x_n): \eta(x_1,...x_n)=y_0\}).\] The assumption that $\mu\in \m_{\geq n}(X)$ gives that $\mu^*$ does not concentrate entirely on the new point $*$ of $Y^*$, and thus we can select the {\it finitely} many points in $Y$ for which $\mu^*(\{y_0\})$ realizes the maximum value. It is routinely seen that this assignment is Borel. \end{proof} \section{Proof of theorem granted messy fact} We begin with a collection of $(E_x, X_x, \mu_x)$ as described there. Let $A\subset 2^\N$ be $\Ubf{\Sigma}^1_1$ non-Borel. Let $C\subset \N^\N\times 2^\N$ be closed with the canonical projection function \[p_2: \N^\N\times 2^\N\rightarrow 2^\N\] \[(z, x)\mapsto x\] having \[p_2[C]=A;\] so $C$ is our witness to $A\in\Ubf{\Sigma}^1_1$. We let $\hat{X}$ be the set of $(z, x, w)$ which have $(z, x)\in C$ and $w\in X_x$. We give $\hat{X}$ the standard Borel structure it inherits as a Borel subset of \[\N^\N\times \bigcup_{x\in 2^\N}\{x\}\times X_x.\] For $\vec v_1=(z_1, x_1, w_1), \vec v_2=(z_2, x_2, w_2)\in \hat{X}$, we set \[\vec v_1 E \vec v_2\] if and only if $x_1=x_2$ and $w_1 E_{x_1} w_2$. This is clearly an essentially countable equivalence relation. For a contradiction suppose $F$ is a countable Borel equivalence relation on a standard Borel space $Y$ and \[\theta: \hat{X}\rightarrow Y\] \[\rho: Y\rightarrow \hat{X}\] witness \[E\sim_B F.\] Let $\bar{\rho}: Y\rightarrow \bigcup_{x\in 2^\N}\{x\}\times X_x$ be obtained by setting $\bar{\rho}(y)=(p_2(\rho(y)), p_3(\rho(y)))$ -- so if $\rho(y)=(z, x, w)$ then $\bar{\rho}(y)=(x, w)$. \begin{claim} \label{claim1} If $w_0\in X_x$ then $\{y: \bar{\rho}(y)=(x, w_0)\}$ is countable. \end{claim} \begin{proof} For any $y_0$ with $\bar{\rho}(y_0)=(x, w_0)$ we have that for all other $y$ with \[\bar{\rho}(y)=(x, w_0)\] that $y F y_0$; thus the claim follows from $F$ being countable. \end{proof} \begin{claim} \label{claim2} If $x\in A$ then \[\{x\}\times X_x\cap {\rm im}(\bar{\rho})\] is non-null in \[(\{x\}\times X_x, \delta_x\times \mu_x).\] \end{claim} \begin{proof} We let $z$ be such that $(z, x)\in C$. We define \[\gamma_{z, x}: X_x\rightarrow Y\] by $\gamma_{z, x}(w)= \theta(z, x, w)$; the assumptions on $\theta$ entail that $\gamma_{z, x}$ witnesses $E_x\leq_B F$. By composition we have \[\rho\circ \gamma_{z, x}: X_x\rightarrow \hat{X}\] witnessing $E_x\leq_B E$. And then by $\mu_x$-ergodicity of $E_x$ we have some single $x_0$ such that \[\forall^{\mu_x}w \in X_x(\bar{\rho}(\gamma_{z, x}(w))\in \{x_0\} \times X_{x_0}).\] Postcomposing with the projection to the second coordinate we obtain a reduction \[\bar{\gamma}_{z, x}=p_2\circ \rho\circ \gamma_{z, x}\] \[X_x\rightarrow X_{x_0}\] on a conull subset of $E_x$ to $E_{x_0}$, and hence $x=x_0$ by part (ii) of our messy fact. And then by part (iii) $\mu_x({\rm im }(\bar{\gamma}_{z, x}))>0$, and, after unraveling the definitions, im$(\bar{\rho})$ non-null in $\{x\}\times X_x$. \end{proof} Putting together these claims we have \[\begin{array}{ll}x\in A& \Leftrightarrow \exists ^{\mu_x}w\in X_x( (x, w)\in {\rm im}(\bar{\rho}))\\ & \Leftrightarrow \exists ^{\delta_x\times\mu_x}(x', w') \in \bigcup_{y\in 2^\N}\{y\}\times X_{y} ( (x', w')\in {\rm im}(\bar{\rho})) \end{array}.\] $\bar{\rho}$ is countable to one, and so it has Borel image by Lusin-Novikov (see 18.10 \cite{kechris}). Applying lemma \ref{measurelemma} we have $A$ is Borel with a contradiction. \def\gp{{\Gamma_{\vec p}}} \section{Messy fact} \begin{notation} For $\vec p=(p_1, p_2,...)$ a sequence of distinct primes, let $\Q_{\vec p}$ be the subgroup of $\Q$ generated by \[\{(p_i)^{-n}: i, n \in \N\}\] (so that we have infinite divisibility in $\Q_{\vec p}$ by each prime on the list). Then let \[\Gamma_{\vec p}=H_{\vec p} * G_{\vec p}\] where $H_{\vec p}$ and $G_{\vec p}$ are disjoint copies of $\Q_{\vec p}$. Following $\S$C3 of \cite{hjorthkechris} we let $[S_{\gp}]$ be the collection of all infinite sequences \[(a_0, a_1, a_2,...a_n,...)\] such that at each $i$ we have $a_i\in H_{\vec p}$ iff $a_{i+1}\in G_{\vec p}$ iff $a_{i}\notin G_{\vec p}$; we let $\gp$ act in the natural way on $[S_\gp]$ -- concatenate and reduce. \end{notation} \begin{lemma} \label{2.1} (a) If $w, a\in \Gamma_{\vec p}$ with $g^2 = w^\smallfrown a^\smallfrown w^{-1}$ then $g$ is in the cyclic subgroup generated by $wc w^{-1}$ for any $c$ with $c^2 = a$. (b) If a non-identity element $h$ of $\Gamma_{\vec p}$ is infinitely divisible by a prime $q$, then $q$ appears in the sequence $\vec p$ and $h$ has the form \[h=w a w^{-1}\] for some $a\in G_{\vec p}\cup H_{\vec p}$. \end{lemma} \begin{proof} (a) Suppose $h, g\in \gp$ and $g^2 =h$. In general we will measure the {\it length} of a word in $\Gamma_{\vec p}$ by looking at the number of times it alternates between $G_{\vec p}$ and $H_{\vec p}$. We write $h$ as a reduced word in the form \[h=w^\smallfrown (a^k)^\smallfrown w^{-1}\] where $w$ is as long as possible and $a$ is as short as possible. We write $g$ as a reduced word \[g=v^\smallfrown b^\smallfrown v^{-1}\] where again $v$ is as long as possible. Then it follows that \[g^2 = v^\smallfrown (b^2)^\smallfrown v^{-1},\] and hence $v=w$, $b^2 =a^k$. Now there are two cases. In one case we have $a\notin G_{\vec p}\cup H_{\vec p}$, when indeed if follows that $b$ appears as an initial string in $a^k$, and hence, by minimization of $a$, that $2$ divides $k$, and we have $g=w^\smallfrown (a^{k/2})^\smallfrown w^{-1}$ as required. The second case is $a\in G_{\vec p}\cup H_{\vec p}$. Assume $a\in G_{\vec p}$. Then since $G_{\vec p}$ is torsion free we have again that $b=a^{k/2}$ is the unique element with $b^2=a^k$. (b) If we have a prime $q$ and $h, g\in \gp$ with $g^q=h$ then as above either \leftskip 0.4in \noindent (i) for some $\bar{h}, \bar{g}$ either both in $G_{\vec p}$ or both in $H_{\vec p}$ and some $w\in \gp$ we have \[h = w^\smallfrown \bar{h} ^\smallfrown w^{-1},\] \[g = w^\smallfrown \bar{g} ^\smallfrown w^{-1},\] as reduced words and \[\bar{g} +\bar{g}+...(q \: {\rm times}) ...+ \bar{g}=\bar{h}\] in the respective copy of $\Q_{\vec p}$; or \noindent (ii) for some $b, w\in \gp, b\notin G_{\vec p}\cup H_{\vec p}$ with $w^\smallfrown b^\smallfrown w^{-1}$ reduced we have \[h=w^\smallfrown (b^q)^\smallfrown w^{-1},\] \[g= w^\smallfrown b ^\smallfrown w,\] and as a reduced word \[b^q=b^\smallfrown b^\smallfrown...(q\: {\rm times}) ...^\smallfrown b.\] \leftskip 0in The only possibility for infinite divisibility by $q$ is the first case, when we indeed have to have $q$ on the $\vec p$ sequence. \end{proof} \def\hv{{H_{\vec p}}} \def\gv{{G_{\vec p}}} \begin{lemma} \label{2.2} If $e\in [S_\gp]$, $g\in \gp$, $g\cdot e =e$ (i.e. $g\in {\rm stab}\{e\}$), $g$ not the identity, then for some $w, a\in \gp$, $i\in\Z$, $i\neq 0$, \[e=w^\smallfrown a^\smallfrown a^\smallfrown...\] \[g=w^\smallfrown (a^i)^\smallfrown w^{-1}.\] \end{lemma} \begin{proof} It is easily seen that $e$ is eventually periodic, and so for some $a, w$ \[e= w^\smallfrown a^\smallfrown a^\smallfrown...\] Note then that \[g\cdot w^\smallfrown a^\smallfrown a^\smallfrown...= w^\smallfrown a^\smallfrown a^\smallfrown...\] if and only if \[w^{-1}gw\cdot a^\smallfrown a^\smallfrown... =a^\smallfrown a^\smallfrown...\] Thus we may as well assume that $e$ is outright periodic and suppose that $e$ has period $n$ -- where the {\it period} is the least $n$ for which it is it is $n$-periodic. We may also assume without loss that there are $g_i$'s in $G_{\vec p}$ and $h_i$'s in $H_{\vec p}$ with \[a=g_1^\smallfrown h_2^\smallfrown g_3^\smallfrown...^\smallfrown h_n.\] We suppose $g\cdot e = e$ with \[g=k_1^\smallfrown k_2^\smallfrown ...^\smallfrown k_\ell,\] where, as usual, $k_i\in H_{\vec p}$ iff $k_{i+1}\in G_{\vec p}$ iff $k_{i}\notin G_{\vec p}$. Then by considering the fact that $g\cdot e =e $ still has period $n$ either we obtain $k_\ell\in \hv$ and $k_\ell=h_n$, and then $k_{\ell -1}=g_{n-1}$, $k_{\ell -2}=h_{n-2}$, and so on, until in the final end we have $g=a^i$ some $i>0$, or we obtain $k_\ell\in \gv$ and $k_{\ell} = g_1^{-1}$, and then $k_{\ell-1}=h_2^{-1}$, and it all unravels to the end with $g=a^{-i}$ some $i>0$. \end{proof} \begin{corollary} \label{2.3} If $e_1, e_2\in [S_\gp]$, then {\rm stab}$\{e_1, e_2\}$ is abelian. \end{corollary} \begin{proof} Whenever $g\in$ stab$\{e_1, e_2\}$ we have $g^2$ is in stab$\{e_1\}$ and thus we may appeal to \ref{2.2} to write $e_1$ as \[e_1=w^\smallfrown a^\smallfrown a^\smallfrown...\] where $lh(a)=$ period of $e_1$ and $g^2$ as \[g^2=w^\smallfrown (a^i) ^\smallfrown w^{-1}.\] Then by \ref{2.1} we have that any such $g$ will be in the cyclic subgroup generated $w^\smallfrown a^\smallfrown w^{-1}$. \end{proof} \begin{lemma} \label{2.4} There is a Borel $\gp$ map \[\varphi: [S_\gp]^3\rightarrow \gp.\] \end{lemma} \begin{proof} Since $\hv$, $\gv$ are torsion free there are, by \ref{map}, respective $\hv$- and $\gv$-maps \[\theta_H: [\hv]^3\rightarrow \hv,\] \[\theta_G:[\gv]^3\rightarrow \gv.\] Now for any $\{f_1, f_2, f_3\}\in [S_\gp]^3$ we follow C3.2 \cite{hjorthkechris} and consider a split in cases. \medskip {\bf Case(a)} There is a reduced word $v$ such that any two of the ends agree exactly up to $v$. \medskip Thus we may write these as \[f_1=v^\smallfrown k_1^\smallfrown k_1'^\smallfrown...\] \[f_2=v^\smallfrown k_2^\smallfrown k_2'^\smallfrown...\] \[f_3=v^\smallfrown k_3^\smallfrown k_3'^\smallfrown...\] where at each $i$ we have $k_i\in H_{\vec p}$ iff $k_{i}'\in G_{\vec p}$ iff $k_{i}\notin G_{\vec p}$. We then let \[\varphi(\{f_1, f_2, f_3\})=v\theta(\{k_1, k_2, k_3\})\] where $\theta=\theta_G$ or $\theta=\theta_H$ depending on which group the $k_i$'s exist in. \medskip {\bf Case(b)} Two of the ends agree with one another more than either does with the third. \medskip So we may write $\{e_1, e_2, e_3\}=\{f_1, f_2, f_3\}$ with \[e_1=u^\smallfrown w^\smallfrown k_1...\] \[e_2=u^\smallfrown w^\smallfrown k_2...\] \[e_3=u^\smallfrown \hat{w}^\smallfrown ...\] as reduced words and $w$, $\hat{w}$ having no initial segment in common. We then let \[\varphi(\{f_1, f_2, f_3\})=(u^\smallfrown w)\theta(\{k_1, k_2, 0\})\] where $\theta$ is again either $\theta_G, \theta_H$ and $0$ is the zero (abelian group identity) in the respective copy of $\Q_{\vec p}$. \medskip Note that case(b) can be converted into case(a) by acting on the triple by any reduced group element of the form \[g=v^\smallfrown k^\smallfrown (w^{-1})^\smallfrown u^{-1},\] where $k$ is in the same copy of $\Q_{\vec p}$ as $k_1, k_2$ but is not equal to either $k_1^{-1}, k_2^{-1}$. Thus to verify that $\varphi$ is indeed a $\gp$-map it suffices to check the invariance property for $g$ in this form. But here one has \[\varphi(\{g\cdot f_1, g\cdot f_2, g\cdot f_3\}) =\varphi(v^\smallfrown (k k_1)^\smallfrown..., v^\smallfrown (k k_2)^\smallfrown..., v^\smallfrown k ^\smallfrown (w^{-1})^\smallfrown \hat{w}^\smallfrown...)\] \[=v\cdot \theta(\{kk_1, k k_2, k \}) = v^\smallfrown k \cdot \theta(\{k_1, k_2, 0\})\] \[=v^\smallfrown k\cdot((w^{-1})^\smallfrown u^{-1}\cdot(u^\smallfrown w\cdot \varphi(\{k_1, k _2, 0\}))) = v^\smallfrown k ^\smallfrown (w^{-1})^\smallfrown u^{-1} \cdot \theta(\{e_1, e_2, e_3\}),\] as required. \end{proof} \begin{definition} Let $H^\infty_{\vec p}$ and $G^\infty_{\vec p}$ be the respective one point compactifications of $H_{\vec p}$ and $G_{\vec p}$. So $H^\infty_{\vec p}$ consists of $H_{\vec p}$ along with a new point $\infty_{H}$, and the open sets are all sets which do {\it not} contain the point $\infty_H$ along with all cofinite sets which do contain $\infty_H$. Similarly $G_{\vec p}^\infty$ contains the new point $\infty_G$. We let $H_{\vec p}$ and $G_{\vec p}$ act on their one point compactifications so that the action extends the usual action on themselves by left translation and the new point at infinity becomes a fixed point -- so \[h\cdot a= h+a\] for $h, a\in H_{\vec p}$, whilst \[h\cdot \infty_H = \infty_H\] for $h\in H_{\vec p}$, and similarly on the $G_{\vec p}$ side. \end{definition} It is easily checked that these actions are continuous. \begin{definition} We let $\gp^*$ consist of all finite sequences \[a_0^\smallfrown a_1 ^\smallfrown...a_n\] where the $a_i$'s, $i0$, $a_0\in H_{\vec p}$, $a_0\neq -h$, then \[h\cdot w=((h+a_0)^\smallfrown a_1^\smallfrown...a_n);\] \noindent (iv) if $n>0$ and $a_0=-h$, then \[h\cdot w=(a_1^\smallfrown a_2^\smallfrown...a_n).\] \leftskip 0in \noindent The action by $G_{\vec p}$ is the obvious analog, and we then obtain an action by the free product $\gp=G_{\vec p}* H_{\vec p}$. \end{definition} \begin{lemma} \label{further3.3} The stabilizers of points in the action of $\gp$ on $\gp^*$ are abelian. \end{lemma} \begin{proof} Consider some point $w=a_0^\smallfrown a_1^\smallfrown...a_n\in \gp^*$. We let $u=a_0^\smallfrown a_1...a_{n-1}$, then the stabilizer of $w$ in the action of $\gp$ on $\gp^*$ equals $uH_{\vec p} u^{-1}$ or $uG_{\vec p} u^{-1}$ depending on whether $a_n$ equals $\infty_H$ or $\infty_G$. \end{proof} \def\ss{[S_{\gp}]^{*\infty}} \begin{definition} We let $\ss$ be the union of $[S_{\Gamma_{\vec p}}]$ and $\Gamma_{\vec p}^*$; thus it consists in all finite sequences alternating between $G_{\vec p}^\infty, H_{\vec p}^\infty$ and only taking the respective $\infty_G$ or $\infty_H$ at the final point along with all infinite sequences that alternate between $G_{\vec p}$ and $H_{\vec p}$. We endow it with a topology as follows. Given a finite sequence $\vec a=a_0^\smallfrown a_1^\smallfrown...^\smallfrown a_n$ in ${\gp}$ and $V$ an open subset of either $H_{\vec p}^\infty$ or $G_{\vec p}^\infty$, depending on whether $a_n$ is in $G_{\vec p}$ or $H_{\vec p}$ respectively, we let \[{\cal O}(V, \vec a)\] be the set of all $\vec b\in [S_{\gp}]\cup \gp^*$ where \[b_i = a_i\] all $i\leq n$, and \[b_{n+1}\in V.\] We then equip $\ss$ with the topology generated by taking the collection of all such ${\cal O}(V, \vec a)$ as our basis. \end{definition} \begin{lemma} $\ss$ is a compact metric space. \end{lemma} \begin{proof} It is an easy exercise to check sequential compactness of the space directly by hand, which then suffices by second countability of the space; alternatively we may observe that $\ss$ is the continuous image of a closed subset of the compact space \[(H^\infty_{\vec p}\cup G^\infty_{\vec p})^\N.\] This second argument also serves to show that the space is separable. Since $\ss$ is zero dimensional and compact, any two disjoint closed sets can be separated by a clopen sets. As the space is obviously Hausdorff, we may then use Urysohn's criterion to determine that the space is metrizable. \end{proof} \begin{lemma} $\gp$ is near-hyperbolic (in the sense of \cite{hjorthkechris}). \end{lemma} \def\m{{\cal M}} \begin{proof} Following C3.3 \cite{hjorthkechris} we consider the action on the compact metric space $\ss$. The equivalence relation induced on $[S_\gp]$ is hyperfinite since it is included in the tail equivalence relation, and there are only two orbits in the action of $\gp$ on $\gp^*$. Thus certainly the induced orbit equivalence relation on the whole space $\ss$ is hyperfinite and hence amenable, as is the induced orbit equivalence relation on $\m_{\leq 2}(\ss)$. From \ref{2.3} and \ref{further3.3} we have that the stabilizers of points in $\m_{\leq 2}(\ss)$ are abelian, and so certainly amenable. From \ref{2.4} and \ref{lyons} we obtain a Borel $\Gamma_{\vec p}$-map \[\eta:\m_{\geq 3}(\ss)\rightarrow [\Gamma_{\vec p}]^{<\infty}.\] Since $\Gamma_{\vec p}$ is torsion free we have from \ref{map} that that the stabilizers of the action on $[\Gamma_{\vec p}]^{<\infty}$ and hence $\m_{\geq 3}(\ss)$ are trivial. It also follows that the induced orbit equivalence relation $E_{\gp}^{\m_{\geq 3}(\ss)}$ is smooth, since $\{\eta^{-1}[F]: F\in [\Gamma_{\vec p}]^{<\infty}\}$ partitions the space into countably many Borel pieces, each of which meets a given orbit at most once. \end{proof} \def\Gp{{K_{\vec p}}} \def\Gq{{K_{\vec q}}} \begin{lemma} \label{2.6} Suppose $\vec p, \vec q$ are sequences of primes, $\gp, \Gamma_{\vec q}$ are constructed as above, $X_{\vec p}$, $X_{\vec q}$ are standard Borel spaces, and that $K_{\vec p}=\gp\times\gp$, $K_{\vec q}=\Gamma_{\vec q}\times\Gamma_{\vec q}$ act freely and in a mixing and measure preserving manner on $X_{\vec p}$, $X_{\vec q}$, with the action of any non-amenable subgroup being $E_0$-ergodic. Then $E_{\Gp}\leq_B E_\Gq$ implies $\vec p$ is included in $\vec q$. \end{lemma} \begin{proof} We consider the induced \[E_{\gp\times\Z}\subset E_{\Gp}\] obtained by finding a copy of $\Z$ inside the right hand copy of $\Gp$. The reduction of $E_\Gp$ to $E_\Gq$ induces a countable to one homomorphism $f$ of $E_{\gp\times\Z}$ to $E_\Gq=E_{\Gamma_{\vec q}\times\Gamma_{\vec q}}$ and we obtain induced cocycles \[\alpha_1: (\gp\times \Z)\times X_{\vec p}\rightarrow \Gamma_{\vec q},\] \[\alpha_2: (\gp\times \Z)\times X_{\vec p}\rightarrow \Gamma_{\vec q},\] by considering the two copies of $\Gamma_{\vec q}$ which underpin $E_{\Gq}$. Note that we cannot have both of these cocycles equivalent to cocycles into amenable subgroups of $\Gamma_{\vec q}$ since $E_{\Gamma_{\vec p}\times \Z}$ is $E_0$-ergodic. The action of $K_{\vec p}=\Gamma_{\vec p}\times \Gamma_{\vec p}$ is mixing, and therefore every infinite subgroup acts ergodically. In particular for $\Z$ in the subgroup $\Gamma_{\vec p}\times \Z$ we have that $\Z$ acts in an ergodic fashion. \[ [f(x)]_{\Gamma_{\vec q}\times \Gamma_{\vec q}}\] is not a.e. constant. Thus 2.2 \cite{hjorthkechris} applied to $\Gamma=\Gamma_{\vec p} \times \Z$, $\Delta=\Z \triangleleft \Gamma$ yields that one of $\alpha_1, \alpha_2$ is equivalent to a cocycle induced by a homomorphism $\pi: \Gamma_{\vec p}\times \Z\rightarrow \Gamma_{\vec q} \times \Gamma_{\vec q}$ with non-amenable image. Since the image is in particular non-trivial it follows that there is some $g\neq 0$ in $G_{\vec p}\cup H_{\vec q}$ with $\pi(g)\neq 0$. However $g$ is divisible by every power of every prime on the $\vec p$ sequence, and hence so is $\pi(g)$. Thus the lemma follows by \ref{2.1}. \end{proof} In the following lemma \[p_1, p_2: \gp\times \gp\rightarrow \gp\] are the respective projections to the first and second copies of $\gp$. \begin{lemma} \label{2.7} Suppose $\Gp=\gp\times\gp$ acts freely and in a measure preserving and mixing manner on the standard Borel probability space $(X, \mu)$ and the action of each non-amenable subgroup is $E_0$-ergodic. Let \[\alpha:\Gp\times X\rightarrow \Gamma_{\vec p}\times \Gamma_{\vec p} (=\Gp)\] be a Borel cocycle such that its restriction to any non-amenable subgroup is not equivalent to a cocycle taking values in an amenable subgroup of $\Gp$. Then there is an infinite cyclic subgroup $\Delta$ of $K_{\vec p}$ such that the \ restricted cocycle \[\alpha:\Delta\times X\rightarrow \Gamma_{\vec p}\times\Gamma_{\vec p}\] is equivalent to a cocycle \[\hat{\alpha}:\Delta\times X\rightarrow \Gamma_{\vec p}\times\Gamma_{\vec p}\] such that \leftskip 0.4in \noindent (i) $p_1\circ \hat{\alpha}:\Delta\times X\rightarrow \Gamma_{\vec p}$ given by a non-trivial homomorphism of $\Delta$ into $\Gamma_{\vec p}$ a.e; \noindent (ii) $p_2\circ \hat{\alpha}: \Delta\times X\rightarrow \Gamma_{\vec p}$ is trivial a.e. (that is to say, $p_2\circ\hat{\alpha}(\delta, x)$ is the identity $\mu$ a.e. $x$). \leftskip 0in \end{lemma} \begin{proof} We find some copy $\F_2=\langle a, b\rangle$ of the free group inside $\gp$ and consider the induced cocycles \[\alpha_{1,j}=p_j\circ \alpha|_{(\F_2\times\langle a\rangle)\times X}: (\F_2\times \langle a\rangle )\times X\rightarrow \Gamma_{\vec p},\] \[\alpha_{2,j}=p_j\circ \alpha|_{(\langle a\rangle\times \F_2)\times X}: (\langle a\rangle\times \F_2 )\times X\rightarrow \Gamma_{\vec p},\] into the $j^{\rm th}$ copy of $\Gamma_{\vec p}$, for $j=1, 2$. We let \[\beta_{1,j}= \alpha_{1, j}|_{(\{1\}\times\langle a\rangle)\times X}: (\{1\}\times \langle a\rangle )\times X\rightarrow \Gamma_{\vec p},\] \[\beta_{2,j}=p_j\circ \alpha_{2, j}|_{(\langle a\rangle\times \{1\})\times X}: (\langle a\rangle\times \{1\} )\times X\rightarrow \Gamma_{\vec p},\] be the respective restrictions. \medskip \noindent {\bf Claim(1):} For either $j=1$ or $j=2$ we have that the cocycle \[\beta_{1,j}:(\{1\}\times \langle a\rangle ) \times X\rightarrow \Gamma_{\vec p}\] is equivalent to a trivial cocycle (a.e.). \medskip \noindent {\bf Proof of claim:} Or else 2.2 \cite{hjorthkechris} gives that the induced cocycles \[\alpha_{1,j}|_{(\F_2\times \{1\})\times X}: (\F_2\times \{1\} )\times X\rightarrow \gp,\] $(j=1, 2)$, are both equivalent a.e. to cocycles into amenable subgroups of $\gp$ and hence the restricted cocycle \[\alpha|_{(\F_2\times \{1\})\times X}: (\F_2\times \{1\} )\times X\rightarrow \Gp,\] is equivalent to a cocycle a.e. into an amenable group, in contradiction to assumptions of lemma. \hfill ($\square$Claim) \medskip \noindent{\bf Claim(2):} For either $\ell=1$ or $\ell=2$ \[\alpha_{2,\ell}: (\langle a\rangle \times \F_2)\times X\rightarrow \gp\] is equivalent to a homomorphism with non-amenable image in $\gp$. \medskip \noindent {\bf Proof of claim:} Again by 2.2 \cite{hjorthkechris}. \hfill ($\square$Claim) \medskip %Note then by 3.10 \cite{hjorthkechris} we have $\ell\neq j$ and the homomorphism from %$\langle a\rangle\times\F_2$ will be injective on $\{1\}\times \langle a\rangle$ since %$\gp$ is torsion free. \noindent{\bf Claim(3):} Given $j$ as in claim(1) and $\ell$ as in claim(2), $\ell\neq j$. \medskip \noindent{\bf Proof of Claim:} Suppose instead $\ell =j$. Then $\beta_{1,\ell}$ is equivalent to the trivial cocycle, which always returns the identity element of the group $\Gamma_{\vec p}$. On the other hand, the assumption on $j=\ell$ gives that \[\beta_{1,\ell}=\alpha_{2, \ell} |_{(\{1\}\times \langle a\rangle)\times X}\] is equivalent to a cocycle by a non-trivial homomorphism, which will then necessarily be injective since $\Gamma_{\vec p}$ is torsion free. Thus we have established that $\beta_{1,\ell}$ is simultaneously equivalent to the trivial cocycle and a cocycle given by an injective homomorphism, and this directly contradicts 3.5 \cite{hjorthkechris}. \hfill ($\square$Claim) Thus we get an induced cocycle \[\alpha|_{(\{1\}\times \langle a\rangle)\times X} =(\beta_{1,1}, \beta_{1, 2}): (\{1\}\times \langle a\rangle)\times X\rightarrow \gp\times\gp\] as required. \end{proof} We these lemmas in place we can complete the proof of the messy fact. \begin{lemma} For any infinite string of primes $\vec p$ there is a corresponding standard Borel probability space space \[(X_{\vec p}, \mu_{\vec p})\] on which $K_{\vec p}$ acts in a mixing, measure preserving manner, with every non-amenable subgroup having an $E_0$-ergodic action and every infinite cyclic subgroup acting in a uniquely ergodic manner. This can be done so that \[\bigcup_{\vec p}\{\vec p\}\times X_{\vec p}\] is a standard Borel space, the projection function \[(\vec p, x)\mapsto \vec p\] is Borel, and the assignment of measures \[\vec p\mapsto \delta_{\vec p}\times \mu_{\vec p}\] is Borel as a function from infinite sequences of primes to $\m(\bigcup_{\vec p}\{\vec p\}\times X_{\vec p})$. \end{lemma} \begin{proof} From A6.1, A4.1, and 3.7 of \cite{hjorthkechris}, but we do need to see that this assignment of $X_{\vec p}$ to $\vec p$ is effective. For each sequence of primes $\vec p$ let $X_{\vec p}\subset 2^{\Gp}$ be the collection of all \[f:\Gp\rightarrow \{0,1\}\] such that for all infinite cyclic groups $\langle\sigma\rangle\subset \Gp$ and clopen $U\subset 2^\Gp$ we have \[{\rm lim}_{n\rightarrow\infty}\frac{1}{2n+1}|\{i: -n\leq i \leq n , \sigma^i\cdot f\in U\}| =\mu_{\vec p}(U),\] where $\mu_{\vec p}$ is the usual Bernoulli ``coin flipping" measure on $2^\Gp$. Thus by the ergodic theorem $(X_{\vec p}, \mu_{\vec p})$ is uniquely ergodic on all infinite subgroups. By A4.1 \cite{hjorthkechris} every non-amenable subgroup gives rise to an $E_0$-ergodic equivalence relation. By A6.1 \cite{hjorthkechris} the action is mixing. The various conditions about the assignment of the space and the measure being suitably Borel in $\vec p$, as stated above in the lemma, are routinely verified since $X_{\vec p}$ is a Borel subset of $2^{K_{\vec p}}$ uniformly in $\vec p$. \end{proof} For $x\in 2^\N$ we use almost disjoint coding to assign continuously an infinite sequence ${\vec p}(x)$ of distinct primes such that for $x\neq y$ we have ${\vec p}(x)$ and ${\vec p}(y)$ eventually disjoint. We let \[(X_x, \mu_x, E_x)= (X_{\vec p(x)}, \mu_{{\vec p}(x)}, E_{{K}_{{\vec p}(x)}});\] we need to verify conditions (i)-(v) of the messy fact. (i), (iv), and (v) are all immediate from the construction. (ii) follows from \ref{2.6}. For (iii), we suppose $f:X_x\rightarrow X_x$ is a homomorphism of $E_x$ to $E_x$. Then \ref{2.7} gives some infinite cyclic $\langle \sigma\rangle, \langle \tau\rangle\subset K_{{\vec p}(x)}$ and measurable \[\theta: X_x\rightarrow K_{{\vec p}(x)}\] with \[\theta(\sigma\cdot x)\cdot f(\sigma\cdot x)= \tau\cdot\theta(x)\cdot f(x).\] Thus if we define \[\hat{f}: X_x\rightarrow X_x,\] \[x\mapsto \theta(x)\cdot f(x)\] then this gives a measurable map which conjugates the action of $\sigma$ with that of $\tau$, and hence, by our unique ergodicity assumption, we have \[\mu_x({\rm im}(\hat{f}))>0,\] \[\therefore \mu_x({\rm im}(f))>0.\] \section{Is the notion of near hyperbolic interesting?} The definition of {\it near hyperbolic} was formulated in \cite{hjorthkechris} as a purely ad hoc measure to help organize the proofs, and the example discussed there were in fact {\it hyperbolic}. In the present paper the examples given are not hyperbolic, and yet they would seem to natural instances of near hyperbolic groups. %The method from the last section along with %\cite{hjorthkechris} %can adapted to obtain a relatively broad class of near %hyperbolic groups. %\begin{lemma} Let $A$ and $B$ be amenable groups. Then the %free product %\[A*B\] %is near hyperbolic. %\end{lemma} %It is also not true that every %group is near hyperbolic. It follows from the %rigidity theorems of \cite{hjorthkechris} %that products of near hyperbolic groups give %rise to actions which are very different to those %produced by near hyperbolic groups themselves, and %in particular, ${\mathbb F}_2\times {\mathbb F}_2$ %is not near hyperbolic. Given that the methods of \cite{hjorthkechris} work exactly for the class of groups which are near hyperbolic, it might be interesting to determine which groups lie inside that class, just as it might be interesting to determine which groups allow the kinds of rigidity theorems found in either \cite{hjorthkechris} or \cite{monodshalom}. In particular, we do not know what relationship exists between the class of near hyperbolic groups and the classes ${\mathcal C}$ and ${\mathcal C}_{\rm reg}$ of Monod and Shalom in \cite{monodshalom}. They prove that every group embeds into one in ${\mathcal C}_{\rm reg}$ However while the notion of near hyperbolic goes down to subgroups, groups such as ${\mathbb F}_2\times {\mathbb F}_2$ can not be near hyperbolic since, for instance, they do not satisfy the kinds of rigidity theorems shown in \cite{hjorthkechris} for this class, and thus, by Monod and Shalom, not every ${\mathcal C}_{\rm reg}$ group is near hyperbolic. This leaves open the reverse inclusion, just as they leave open whether ${\mathcal C}_{\rm reg}$ is strictly included in ${\mathcal C}$, and indeed the real task at this stage would seem to be to characterize the groups having varying levels of rigidity for their actions. Here it is tempting to ask the following audacious question: \begin{question} Let $\Gamma_1$ and $\Gamma_2$ be torsion free infinite groups, and let $\Gamma_1\times \Z$ and $\Gamma_2\times \Z$ act in a mixing and measure preserving manner on standard Borel probability spaces $X_1$ and $X_2$. If $E_{\Gamma_1}$ is orbit equivalent to $E_{\Gamma_1}$, must there exist a homomorphism from $\Gamma_1$ to $\Gamma_2$ with amenable kernel? \end{question} This, along with a great deal more, certainly holds when $\Gamma_1, \Gamma_2$ are in the class of near hyperbolic by \cite{hjorthkechris} or when they are in ${\mathcal C}$ by 2.23 \cite{monodshalom}. However it is hard to imagine that the answer to the above question could possibly be affirmative, since the methods used in the known cases are so specific. \begin{thebibliography}{99} %\bibitem{cost} G. Hjorth, {\it A lemma for cost obtained,} %preprint, %available at %\texttt{http://www.math.ucla.edu/\~{}greg/research.html}. \bibitem{hjorthkechris} G. Hjorth, A.S. Kechris, {\it Rigidity theorems for actions of product groups and countable Borel equivalence relations,} to appear in the {\bf Memoirs of the American Mathematical Society}, available at {\texttt{http://www.math.caltech.edu/people/kechris.html}}. \bibitem{kechris} A.S. Kechris, {\bf Classical Descriptive Set Theory,} Graduate Texts in Mathematics, 156, Springer-Verlag, New York, 1994. \bibitem{jacksonkechrislouveau} S. Jackson, A.S. Kechris, A. Louveau, {\it Countable Borel equivalence relations}, {\bf Journal of Mathematical Logic,} vol. 2(2002), pp. 1-80. %\bibitem{kechris} A.S. Kechris, {\it Lectures on cost of equivalence relations and %groups,} %available at {\texttt{http://www.math.caltech.edu/people/kechris.html}}. %\bibitem{monod} N. Monod, {\bf Lectures on bounded cohomology,} %Springer-Verlag. \bibitem{monodshalom} N. Monod, Y. Shalom, {\it Orbit equivalence and bounded cohomology,} to appear in the {\bf Annals of Mathematics,} available at {\texttt{http://www.math.uchicago.edu/\~{}monod/publications.html}}. \bibitem{thomas} S. Thomas, {\it Superrigidity and countable Borel equivalence relations,} {\bf Annals of Pure and Applied Logic}, vol. 120 (2003), pp. 237-262. \end{thebibliography} \end{document}