# Equivalence of generics

Iian B. Smythe  Department of Mathematics, Rutgers, The State University of
New Jersey, 110 Frelinghuysen Road, Piscataway, NJ, 08854
<EMAIL_ADDRESS>
###### Abstract.

Given a countable transitive model of set theory and a partial order contained
in it, there is a natural countable Borel equivalence relation on generic
filters over the model; two are equivalent if they yield the same generic
extension. We examine the complexity of this equivalence relation for various
partial orders, with particular focus on Cohen and random forcing. We prove,
amongst other results, that the former is an increasing union of countably
many hyperfinite Borel equivalence relations, while the latter is neither
amenable nor treeable.

###### Key words and phrases:

Borel equivalence relations, forcing, orbit equivalence relations

###### 2010 Mathematics Subject Classification:

Primary 03E15, 03E40; Secondary 37A20

##  1\. Introduction

Given a countable transitive model $M$ of $\mathsf{ZFC}$ and a partial order
$\mathbb{P}$ in $M$, we can construct $M$-generic filters
$G\subseteq\mathbb{P}$ and their corresponding generic extensions $M[G]$ using
the method of forcing. We say that two such $M$-generic filters $G$ and $H$
are _equivalent_ , written $G\equiv^{\mathbb{P}}_{M}H$, if they produce the
same generic extension, that is:

$G\equiv^{\mathbb{P}}_{M}H\quad\text{if and only if}\quad M[G]=M[H].$

It is this equivalence relation that we aim to study.

The countability of $M$ and the definability of the forcing relation imply
that $\equiv^{\mathbb{P}}_{M}$ is a _countable Borel equivalence relation_
(Lemma 2.6), that is, each equivalence class is countable and
$\equiv^{\mathbb{P}}_{M}$ is a Borel set of pairs in some appropriately
defined space of $M$-generic filters for $\mathbb{P}$. The general theory of
countable Borel equivalence relations affords us a broad set of tools for
analyzing the relative complexity of each $\equiv^{\mathbb{P}}_{M}$; see the
surveys [12] and [29]. In turn, each $\equiv^{\mathbb{P}}_{M}$ provides a
natural, well-motivated example.

To briefly review the general theory, for Borel equivalence relations $E$ and
$F$ on Polish, or standard Borel, spaces $X$ and $Y$, a _Borel reduction_ of
$E$ to $F$ is a Borel measurable function $f:X\to Y$ satisfying

$x\,E\,y\quad\text{if and only if}\quad f(x)Ef(y)$

for all $x,y\in X$. If such an $f$ exists, we say that $E$ is _Borel
reducible_ to $F$, written $E\leq_{B}F$. The relation $\leq_{B}$ gives a
measure of complexity amongst Borel equivalence relations. If $E\leq_{B}F$ and
$F\leq_{B}E$, then we say that $E$ and $F$ are _Borel bireducible_ ; they have
the same level of complexity. If $f$ only satisfies the forward implication in
the displayed line above, we say that $f$ is a _Borel homomorphism_ of $E$ to
$F$. A bijective Borel reduction from $E$ to $F$ is called a _Borel
isomorphism_ , in which case we say that $E$ and $F$ are _Borel isomorphic_
and write $E\cong_{B}F$.

The simplest Borel equivalence relations, called _smooth_ , are those Borel
reducible to the equality relation $\Delta(\mathbb{R})$ on the reals. A
benchmark example of a non-smooth countable Borel equivalence relation is
eventual equality of binary strings, denoted by $E_{0}$:

$x\,E_{0}\,y\quad\text{if and only if}\quad\exists m\forall n\geq
m(x(n)=y(n)),$

for $x,y\in 2^{\omega}$.

Amongst the countable Borel equivalence relations, those Borel reducible to
$E_{0}$ are exactly those which are _hyperfinite_ , that is, equal to an
increasing union of countably many Borel equivalence relations, each with
finite classes. These also coincide with orbit equivalence relations of Borel
actions of $\mathbb{Z}$ (see Theorem 5.1 in [4]).

Every hyperfinite equivalence relation is _(Fréchet) amenable_ , see [12] for
the (somewhat technical) definition. In fact, every orbit equivalence relation
induced by a countable amenable group is amenable (Proposition 2.13 in [12]),
while it remains open whether the converse holds, and whether amenability and
hyperfiniteness coincide for equivalence relations.

More generally, every countable Borel equivalence relation can be realized as
the orbit equivalence relation of a Borel action of some countable group
(Theorem 1 in [5]). Consequently, much of the theory consists of analyzing the
dynamics of group actions. Of particular importance are the _Bernoulli shift
actions_ : Given a countably infinite group $\Gamma$, $\Gamma$ acts on the
space $2^{\Gamma}$ by:

$(\gamma\cdot x)(\delta)=x(\gamma^{-1}\delta)$

for $x\in 2^{\Gamma}$, $\gamma,\delta\in\Gamma$. The corresponding orbit
equivalence is denoted by $E(\Gamma,2)$. The _free part_ of this action,

$(2)^{\Gamma}=\\{x\in 2^{\Gamma}:\forall\gamma\in\Gamma(\gamma\neq
1\Rightarrow\gamma\cdot x\neq x)\\},$

is a $\Gamma$-invariant Borel set on which the action is free, and is easily
seen to be conull with respect to the usual product measure on $2^{\Gamma}$.
Denote by $F(\Gamma,2)$ the restriction of $E(\Gamma,2)$ to $(2)^{\Gamma}$.

When $\Gamma=F_{2}$, the free group on $2$ generators, $E(F_{2},2)$ and
$F(F_{2},2)$ are not amenable, and thus not hyperfinite (cf. Proposition 1.7
in [12] and [24]). $E(F_{2},2)$ is _universal_ , every countable Borel
equivalence relation is Borel reducible to it (Proposition 1.8 in [4]).
$F(F_{2},2)$ is _treeable_ , meaning there is a Borel acyclic graph on the
underlying space whose connected components are exactly the equivalence
classes of $F(F_{2},2)$. Every hyperfinite Borel equivalence relation is
treeable, while no universal one is (see [12]).

One precursor to the present work is the recent paper [2] on the
classification of countable models of $\mathsf{ZFC}$ up to isomorphism. While
much of [2] is concerned with ill-founded models, the proof of Theorem 3.2
therein, that $E_{0}$ Borel reduces to the isomorphism relation for countable
well-founded models, makes essential use of the the fact that
$\equiv^{\mathbb{C}}_{M}$, for $\mathbb{C}$ Cohen forcing, is not smooth. This
observation was a starting point for our work here.

This paper is arranged as follows: Section 2 consists of general results which
apply to an arbitrary partial order $\mathbb{P}$ in $M$. We describe spaces of
$M$-generic objects for $\mathbb{P}$, prove Borelness of
$\equiv^{\mathbb{P}}_{M}$ on these spaces, verify that the Borel complexity of
$\equiv^{\mathbb{P}}_{M}$ is independent of different presentations of
$\mathbb{P}$, and discuss automorphisms of $\mathbb{P}$ and their relationship
to $\equiv^{\mathbb{P}}_{M}$. We show that, for many of the partial orders one
encounters in forcing, $\equiv^{\mathbb{P}}_{M}$ is not smooth (Theorem 2.12).

Section 3 is devoted to Cohen forcing $\mathbb{C}$. We prove that
$\equiv^{\mathbb{C}}_{M}$ is an increasing union of countably many hyperfinite
equivalence relations and is thus amenable (Theorem 3.1).

In Section 4, we consider random forcing $\mathbb{B}$. For groups $\Gamma\in
M$, we establish a connection between $F(\Gamma,2)$ and
$\equiv^{\mathbb{B}}_{M}$ (Theorem 4.3), and use this to show that
$\equiv^{\mathbb{B}}_{M}$ is not amenable (Theorem 4.4), not treeable (Theorem
4.7), and in particular, not hyperfinite. We also produce partial results
concerning whether $\equiv^{\mathbb{B}}_{M}$ can be induced by a free action
(Theorem 4.9) and whether it is universal (Theorem 4.11).

Section 5 concludes the paper with a series of further questions which we hope
will motivate continued study of the equivalence relations
$\equiv^{\mathbb{P}}_{M}$.

### Acknowledgements

I would like to thank Samuel Coskey, Joel David Hamkins, Andrew Marks, and
Simon Thomas for many helpful conversations and correspondences.

##  2\. General results

Fix throughout a countable transitive model $M$ of $\mathsf{ZFC}$.111To avoid
metamathematical concerns, one may, as always, work with a model of a large
enough finite fragment of $\mathsf{ZFC}$. Nor do we really need $M$ to be
countable; for a given partial order $\mathbb{P}$, it suffices that
$\mathcal{P}(\mathbb{P})\cap M$ is countable (in $\mathbf{V}$). In particular,
we could allow $M$ to be a transitive class in $\mathbf{V}$, such as when
$\mathbf{V}$ is a generic extension of $M$ after sufficient collapsing, or
$M=\mathbf{L}$ under large cardinal hypotheses. In such cases, only the proofs
of Lemma 2.6 and 2.9 need alteration, instead relying on Theorem 2.16. When we
assert that “$\mathbb{P}$ is a partial order in $M$”, or just “$\mathbb{P}\in
M$”, we mean that $\mathbb{P}$ is a set partially ordered by $\leq$, and both
$\mathbb{P}$ and $\leq$ are elements of $M$. $\mathbb{P}$ will always be
assumed infinite, and thus, countably infinite in $\mathbf{V}$. These
conventions also apply to Boolean algebras in $M$. We say that a Boolean
algebra $\mathbb{A}$ is “complete in $M$” if $M\models\text{``$\mathbb{A}$ is
a complete Boolean algebra''}$.

###  2.1. Spaces of generics

Recall that a filter $G\subseteq\mathbb{P}$ is _$M$ -generic_ if it intersects
each dense subset of $\mathbb{P}$ which is contained in $M$. Since $M$ is
countable, such filters always exist (Lemma VII.2.3 in [16]).

######  Definition 2.1.

For a partial order $\mathbb{P}$ in $M$, the _space of $M$-generics for
$\mathbb{P}$_, denoted by $\mathrm{Gen}^{\mathbb{P}}_{M}$, is

$\mathrm{Gen}^{\mathbb{P}}_{M}=\\{G\subseteq\mathbb{P}:G\text{ is an
$M$-generic filter}\\},$

We identify $\mathrm{Gen}^{\mathbb{P}}_{M}$ as a subspace of $2^{\mathbb{P}}$
with the product topology.

######  Lemma 2.2.

$\mathrm{Gen}^{\mathbb{P}}_{M}$ is a $G_{\delta}$ subset of $2^{\mathbb{P}}$,
and thus a Polish space.

###### Proof.

Note that for any $p\in\mathbb{P}$, the sets $\\{F\subseteq\mathbb{P}:p\in
F\\}$ and $\\{F\subseteq\mathbb{P}:p\notin F\\}$ are clopen. Enumerate the
dense subsets of $\mathbb{P}$ in $M$ as $\\{D_{n}:n\in\omega\\}$. Then,

$\mathrm{Gen}^{\mathbb{P}}_{M}=\\{F\subseteq\mathbb{P}:F\text{ is a
filter}\\}\cap\bigcap_{n\in\omega}\\{F\subseteq\mathbb{P}:F\cap
D_{n}\neq\emptyset\\}.$

For each $n\in\mathbb{N}$,

$\\{F\subseteq\mathbb{P}:F\cap D_{n}\neq\emptyset\\}=\bigcup_{p\in
D_{n}}\\{F\subseteq\mathbb{P}:p\in D\\},$

and these sets are open, so $\bigcap_{n\in\omega}\\{F\subseteq\mathbb{P}:F\cap
D_{n}\neq\emptyset\\}$ is $G_{\delta}$.

$F\subseteq\mathbb{P}$ is a filter if and only if
$F\in\mathcal{F}_{1}\cap\mathcal{F}_{2}$, where

$\displaystyle\mathcal{F}_{1}$ $\displaystyle=\\{F\subseteq\mathbb{P}:\forall
p,q\in\mathbb{P}((p\in F\land p\leq q)\rightarrow q\in F)\\},$
$\displaystyle\mathcal{F}_{2}$ $\displaystyle=\\{F:\forall p,q((p,q\in
F)\rightarrow\exists r(r\in F\land r\leq p,q))\\}.$

Observe that

$\mathcal{F}_{1}=\bigcap_{p\leq
q\in\mathbb{P}}\left(\\{F\subseteq\mathbb{P}:p\notin
F\\}\cup\\{F\subseteq\mathbb{P}:q\in F\\}\right),$

which is $G_{\delta}$, while

$\mathcal{F}_{2}=\bigcap_{p,q\in\mathbb{P}}\left(\\{F\subseteq\mathbb{P}:p\notin
F\\}\cup\\{F\subseteq\mathbb{P}:q\notin F\\}\cup\bigcup_{r\leq
p,q}\\{F\subseteq\mathbb{P}:r\in F\\}\right)$

which is also $G_{\delta}$. Thus, $\mathrm{Gen}^{\mathbb{P}}_{M}$ is
$G_{\delta}$. ∎

The following will simplify arguments involving the topology of
$\mathrm{Gen}^{\mathbb{P}}_{M}$.

######  Lemma 2.3.

The topology on $\mathrm{Gen}^{\mathbb{P}}_{M}$ has a basis consisting of
clopen sets of the form

$N_{p}=\\{G\in\mathrm{Gen}^{\mathbb{P}}_{M}:p\in G\\}$

for $p\in\mathbb{P}$.

###### Proof.

Since $\mathrm{Gen}^{\mathbb{P}}_{M}$ has the subspace topology it inherits
from $2^{\mathbb{P}}$, the sets $N_{p}$ above are clopen. Suppose we are given
a non-empty basic open set

$U=\\{G\in\mathrm{Gen}^{\mathbb{P}}_{M}:p_{0},\ldots,p_{n}\in G\text{ and
}q_{0},\ldots,q_{m}\notin G\\},$

for $p_{0},\ldots,p_{n},q_{0},\ldots,q_{m}\in\mathbb{P}$. Since $M$-generic
filters for $\mathbb{P}$ are, in particular, maximal, we may find conditions
$q_{0}^{\prime},\ldots,q_{m}^{\prime}\in\mathbb{P}$ so that

$U^{\prime}=\\{G\in\mathrm{Gen}^{\mathbb{P}}_{M}:p_{0},\ldots,p_{n},q_{0}^{\prime},\ldots,q_{m}^{\prime}\in
G\\}$

is non-empty and contained in $U$. Taking $p$ to be a common lower bound of
$p_{0},\ldots,p_{n},q_{0}^{\prime},\ldots,q_{m}^{\prime}$, which exists since
$U^{\prime}\neq\emptyset$, we have $\emptyset\neq N_{p}\subseteq U^{\prime}$.∎

Recall that a partial order $\mathbb{P}$ is _atomless_ if for any
$p\in\mathbb{P}$, there are $q,r\leq p$ with $q\perp r$ (i.e., they have no
common lower bound). In all cases of interest, $\mathrm{Gen}^{\mathbb{P}}_{M}$
will be uncountable, a consequence of the following lemma.

######  Lemma 2.4.

$\mathrm{Gen}^{\mathbb{P}}_{M}$ has no isolated points if and only if
$\mathbb{P}$ is atomless.

###### Proof.

($\Leftarrow$) Suppose that $\mathbb{P}$ is atomless. Take
$G\in\mathrm{Gen}^{\mathbb{P}}_{M}$. By Lemma 2.3, it suffices to consider a
basic open set $N_{p}$ containing $G$, for $p\in\mathbb{P}$. Since
$\mathbb{P}$ is atomless, there are $q,r\leq p$ with $q\perp r$. Take
$G^{\prime}$ and $G^{\prime\prime}$ to be $M$-generic filters containing $q$
and $r$, respectively. Then $G^{\prime},G^{\prime\prime}\in N_{p}$, and at
least one of them must be unequal to $G$, showing that $G$ is not isolated.

($\Rightarrow$) Suppose that $\mathrm{Gen}^{\mathbb{P}}_{M}$ has no isolated
points. Take $p\in\mathbb{P}$, and let $G$ be an $M$-generic filter containing
$p$. Since $\mathrm{Gen}^{\mathbb{P}}_{M}$ has no isolated points, there is a
filter $G^{\prime}\in N_{p}$ distinct from $G$, say with $p^{\prime}\in
G^{\prime}\setminus G$. As $G$ is maximal, there is a $q\in G$, which we may
assume is $\leq p$, with $q\perp p^{\prime}$. But $p\in G^{\prime}$, so there
is also a $r\leq p,p^{\prime}$, and thus $q\perp r$. ∎

######  Definition 2.5.

For $\mathbb{P}$ a partial order in $M$, define $\equiv^{\mathbb{P}}_{M}$ on
$\mathrm{Gen}^{\mathbb{P}}_{M}$ by

$G\equiv^{\mathbb{P}}_{M}H\quad\text{if and only if}\quad M[G]=M[H].$

By the minimality of generic extensions (Lemma VII.2.9 in [16]),
$G\equiv^{\mathbb{P}}_{M}H$ if and only if $G\in M[H]$ and $H\in M[G]$.

######  Lemma 2.6.

$\equiv^{\mathbb{P}}_{M}$ is a countable Borel equivalence relation.

###### Proof.

For $G\in\mathrm{Gen}^{\mathbb{P}}_{M}$, the $\equiv^{\mathbb{P}}_{M}$-class
of $G$ is a subset of $M[G]$, which is countable as there are only countably
many $\mathbb{P}$-names in $M$. To see that $\equiv^{\mathbb{P}}_{M}$ is
Borel, note that $G\in M[H]$ if and only if there is a $\mathbb{P}$-name
$\tau\in M$ such that for every $p\in\mathbb{P}$,

$p\in G\quad\text{if and only if}\quad\exists q\in
H(q\mathrel{\Vdash}\check{p}\in\tau).$

Since the forcing relation is arithmetic in a code for the model $M$, and both
$M$ and $\mathbb{P}$ are countable, this is a Borel condition on $G$ and $H$.∎

The next lemma verifies that the Borel complexity of $\equiv^{\mathbb{P}}_{M}$
is invariant for forcing-equivalent presentations of $\mathbb{P}$.

######  Lemma 2.7.

Suppose that $\mathbb{P}$ and $\mathbb{Q}$ are partial orders in $M$.

  1. (a)

If $i:\mathbb{P}\to\mathbb{Q}$ is a dense embedding in $M$, then
$\equiv^{\mathbb{P}}_{M}\;\cong_{B}\;\equiv^{\mathbb{Q}}_{M}$.

  2. (b)

If $\mathbb{P}$ and $\mathbb{Q}$ have isomorphic Boolean completions in $M$,
then $\equiv^{\mathbb{P}}_{M}\;\cong_{B}\;\equiv^{\mathbb{Q}}_{M}$.

###### Proof.

(a) Define
$\widehat{i}:\mathrm{Gen}^{\mathbb{Q}}_{M}\to\mathrm{Gen}^{\mathbb{P}}_{M}$ by
$\widehat{i}(H)=i^{-1}(H)$. By standard results (Theorem VII.7.11 in [16]),
$\widehat{i}$ is a well-defined bijection with inverse

$\widehat{i}^{-1}(G)=\\{q\in\mathbb{Q}:\exists p\in G(i(p)\leq q)\\},$

and satisfying $M[H]=M[\widehat{i}(H)]$ for all
$H\in\mathrm{Gen}^{\mathbb{Q}}_{M}$. Thus

$M[H_{0}]=M[H_{1}]\quad\text{if and only if}\quad
M[\widehat{i}(H_{0})]=M[\widehat{i}(H_{1})]$

for all $H_{0},H_{1}\in\mathrm{Gen}^{\mathbb{Q}}_{M}$, showing that
$\widehat{i}$ is a reduction. To see that $\widehat{i}$ is Borel, given
$N_{p}\subseteq\mathrm{Gen}^{\mathbb{P}}_{M}$, for $p\in\mathbb{P}$, a basic
clopen as in Lemma 2.3,

$\displaystyle\widehat{i}^{-1}(N_{p})$
$\displaystyle=\\{H\in\mathrm{Gen}^{\mathbb{Q}}_{M}:p\in\widehat{i}(H)\\}$
$\displaystyle=\\{H\in\mathrm{Gen}^{\mathbb{Q}}_{M}:i(p)\in H\\},$

which is clopen in $\mathrm{Gen}^{\mathbb{Q}}_{M}$. Thus, $\widehat{i}$ is
continuous, and in particular, Borel.

(b) Follows immediately from (a) by composing Borel isomorphisms. ∎

Every Borel set in $M$ is _coded_ by a real $\alpha$ in $M$; we denote the
interpretation of this code in a model $N\supseteq M$ by $B_{\alpha}^{N}$, a
Borel set in $N$, omitting the superscript when $N=\mathbf{V}$. We will often
just refer to a Borel set $B$ coded in $M$, without reference to the code
itself. Likewise for Borel functions coded in $M$, identified with their Borel
graphs. The basic properties of Borel codes can be found in [13] or [25].

Many partial orders whose generic extensions are generated by adjoining a
single real can be presented as _idealized forcings_ [32], that is, as the set
$P_{I}$ of all Borel subsets of $2^{\omega}$ not in $I$, ordered by inclusion,
where $I$ is a non-trivial $\sigma$-ideal of Borel sets.

Given an $M$-generic filter $G$ for an idealized forcing $P_{I}$ in $M$, there
is a unique (Proposition 2.1.2 in [32]) real $x_{G}\in 2^{\omega}$ in $M[G]$
such that

$\\{x_{G}\\}=\bigcap\\{B^{M[G]}:B^{M}\in G\\}=\bigcap\\{B:B^{M}\in G\\},$

called an _$M$ -generic real_ for $P_{I}$. Since $G$ is computed from $x_{G}$
in any model $N\supseteq M$ containing it as

$G=\\{B^{M}\in P_{I}:x_{G}\in B^{N}\\},$

we have that $M[G]=M[x_{G}]$.

Given an idealized forcing $P_{I}$ in $M$, let $\mathcal{G}^{P_{I}}_{M}$ be
the set of all $M$-generic reals for $P_{I}$. Abusing notation, we define
$\equiv^{P_{I}}_{M}$ in the obvious way on $\mathcal{G}^{P_{I}}_{M}$.

######  Lemma 2.8.

$\mathcal{G}^{P_{I}}_{M}$ is a Borel subset of $2^{\omega}$, and thus a
standard Borel space.

###### Proof.

$x$ is an $M$-generic real for $P_{I}$ if and only if

$x\in\bigcap_{{\mathcal{D}\in M}\atop\text{$\mathcal{D}$ dense in
$P_{I}$}}\bigcup\\{B:B^{M}\in\mathcal{D}\\}.$

Since $M$ is a countable transitive model, the set on the right is Borel. ∎

Exactly as in Lemma 2.6, we have:

######  Lemma 2.9.

$\equiv^{P_{I}}_{M}$ is a countable Borel equivalence relation.∎

######  Lemma 2.10.

Suppose that in $M$, $\mathbb{P}$ is a partial order, $I$ a $\sigma$-ideal of
Borel subsets of $2^{\omega}$, and $i:P_{I}\to\mathbb{P}$ a dense embedding.
Then, $\equiv^{P_{I}}_{M}\;\cong_{B}\;\equiv^{\mathbb{P}}_{M}$.

###### Proof.

As in the proof of Lemma 2.7, the map
$\widehat{i}:\mathrm{Gen}^{\mathbb{P}}_{M}\to\mathcal{G}^{P_{I}}_{M}$ given by
$\widehat{i}(H)=x_{i^{-1}(H)}$, the $M$-generic real corresponding to
$i^{-1}(H)$, is a bijection which maps $\equiv^{\mathbb{P}}_{M}$-equivalent
filters to $\equiv^{P_{I}}_{M}$-equivalent reals, and vice-versa. To see that
$\widehat{i}$ is Borel, given $N_{p}\subseteq\mathrm{Gen}^{\mathbb{P}}_{M}$
with $p\in\mathbb{P}$,

$\displaystyle\widehat{i}(N_{p})=\\{x\in\mathcal{G}^{P_{I}}_{M}:x\in
i(p)^{\mathbf{V}}\\}=\mathcal{G}^{P_{I}}_{M}\cap i(p)^{\mathbf{V}},$

which is Borel by Lemma 2.8. Thus, $\widehat{i}^{-1}$ is Borel, and so
$\widehat{i}$ is as well. ∎

In sum, when analyzing the complexity of $\equiv^{\mathbb{P}}_{M}$ we will be
able to use various equivalent presentations of $\mathbb{P}$.

###  2.2. Automorphisms and homogeneity

Given a partial order $\mathbb{P}$ in $M$, let $\mathrm{Aut}^{M}(\mathbb{P})$
be the automorphism group of $\mathbb{P}$ in $M$. By absoluteness,

$\mathrm{Aut}^{M}(\mathbb{P})=\mathrm{Aut}(\mathbb{P})\cap M.$

There is a natural action
$\mathrm{Aut}^{M}(\mathbb{P})\curvearrowright\mathrm{Gen}^{\mathbb{P}}_{M}$
given by

$(e,G)\mapsto e^{\prime\prime}G=\\{e(p):p\in G\\},$

for $e\in\mathrm{Aut}^{M}(\mathbb{P})$ and
$G\in\mathrm{Gen}^{\mathbb{P}}_{M}$. This action is well-defined and
$\equiv^{\mathbb{P}}_{M}$-invariant, in the sense that
$M[e^{\prime\prime}G]=M[G]$ (Corollary VII.7.6 in [16]). Treating
$\mathrm{Aut}^{M}(\mathbb{P})$ as a discrete group, this action is continuous.

A partial order $\mathbb{P}$ is _weakly homogeneous_ (in $M$) if for all
$p,q\in\mathbb{P}$, there is an automorphism $e$ of $\mathbb{P}$ (in $M$) such
that $e(p)$ is compatible with $q$.

A continuous action of a group $\Gamma$ (or equivalence relation $E$,
respectively) on a Polish space $X$ is _generically ergodic_ if every
$\Gamma$-invariant ($E$-invariant, respectively) Borel set is either meager or
comeager. Equivalently, the action of $\Gamma$ is generically ergodic if and
only if for all non-empty open $U,V\subseteq X$, there is a $\gamma\in\Gamma$
such that $\gamma(U)\cap V\neq\emptyset$ (cf. Proposition 6.1.9 in [6])

######  Lemma 2.11.

Let $\mathbb{P}$ be a partial order in $M$. The action of
$\mathrm{Aut}^{M}(\mathbb{P})$ on $\mathrm{Gen}^{\mathbb{P}}_{M}$ is
generically ergodic if and only if $\mathbb{P}$ is weakly homogeneous in $M$.

###### Proof.

($\Leftarrow$) Suppose that $\mathbb{P}$ is weakly homogeneous. Let
$U,V\subseteq\mathrm{Gen}^{\mathbb{P}}_{M}$ be non-empty open sets. By Lemma
2.3, we may assume that $U=N_{p}$ and $V=N_{q}$, for some $p,q\in\mathbb{P}$.
By weak homogeneity, there is an $e\in\mathrm{Aut}^{M}(\mathbb{P})$ such that
$e(p)$ is compatible with $q$, say with common lower bound $r$. Let $G$ be an
$M$-generic filter for $\mathbb{P}$ which contains $e^{-1}(r)$. Since
$e^{-1}(r)\leq p$, $G\in N_{p}$. Likewise, since $r\in e^{\prime\prime}G$ and
$r\leq q$, $e^{\prime\prime}G\in N_{q}$, proving $e(U)\cap V\neq\emptyset$.

($\Rightarrow$) Suppose that the action is generically ergodic. Pick
$p,q\in\mathbb{P}$. By generic ergodicity, there is an
$e\in\mathrm{Aut}^{M}(\mathbb{P})$ such that $e(N_{p})\cap
N_{q}\neq\emptyset$. Say $e^{\prime\prime}G\in e(N_{p})\cap N_{q}$. But then,
$e(p),q\in e^{\prime\prime}G$, and $e^{\prime\prime}G$ is a filter, so $e(p)$
and $q$ are compatible. ∎

######  Theorem 2.12.

Let $\mathbb{P}$ be an atomless partial order in $M$. If $\mathbb{P}$ is
weakly homogeneous in $M$, then $\equiv^{\mathbb{P}}_{M}$ is not smooth.

###### Proof.

Since $\mathbb{P}$ is atomless, countable sets are meager in
$\mathrm{Gen}^{\mathbb{P}}_{M}$ by Lemma 2.4. The action of
$\mathrm{Aut}^{M}(\mathbb{P})$ of $\mathrm{Gen}^{\mathbb{P}}_{M}$ is
generically ergodic by Lemma 2.11, and has meager orbits, so it is not smooth
(Proposition 6.1.10 in [6]). The induced orbit equivalence relation is a
subequivalence relation of $\equiv^{\mathbb{P}}_{M}$, and thus these
properties are inherited by $\equiv^{\mathbb{P}}_{M}$. ∎

We caution that weak homogeneity is not preserved by forcing equivalence; for
every partial order, there is a _rigid_ (i.e., having trivial automorphism
group) partial order with the same Boolean completion [8]. However, weak
homogeneity of the Boolean completion is preserved by forcing equivalence (cf.
Theorem 8 in [9]). Moreover, the apparently weaker condition of _cone
homogeneity_ , that for every $p,q\in\mathbb{P}$, there are $p^{\prime}\leq p$
and $q^{\prime}\leq q$ such that $\mathbb{P}\upharpoonright
p^{\prime}\cong\mathbb{P}\upharpoonright q^{\prime}$, implies weak homogeneity
of the Boolean completion provided $\mathbb{P}$ is atomless (Fact 1 in [3]).
In practice, this latter property is often easier to verify.

The following are examples of atomless partial orders $\mathbb{P}$ satisfying
one of the aforementioned homogeneity conditions, and thus, by Theorem 2.12,
yield a non-smooth $\equiv^{\mathbb{P}}_{M}$.

######  Example 2.13.

_Cohen forcing_ : If we take our presentation of Cohen forcing $\mathbb{C}$ to
be the infinite binary tree $2^{<\omega}$, ordered by extension, then given
any $p,q\in 2^{<\omega}$, say with $|p|\leq|q|$, we can extend $p$ to
$p^{\prime}$ with $|p^{\prime}|=|q|$, and use that the automorphism group of
$2^{<\omega}$ acts transitively on each level to get an automorphism $e$ such
that $e(p)\leq e(p^{\prime})=q$. As mentioned in the introduction, the non-
smoothness of $\equiv^{\mathbb{C}}_{M}$ was previously observed in [2].

######  Example 2.14.

_Random forcing_ : Let $\mathbb{B}$ be all non-null Borel subsets of
$2^{\omega}$ in $M$, ordered by an inclusion. This is the idealized forcing
corresponding the null ideal. The weak homogeneity of $\mathbb{B}$ boils down
to the following fact: Whenever $A$ and $B$ are positive measure Borel sets,
there is an $s\in 2^{<\omega}$ such that the translate of $A$ by $s$, adding
modulo $2$ in each coordinate, has positive measure intersection with $B$.
This is a consequence of the Lebesgue Density Theorem (cf. Chapter 7 of [23]):
Take basic open sets determined by finite binary strings of the same length
and having a sufficiently large proportion of their mass intersecting each of
$A$ and $B$, respectively. Then, the $s\in 2^{<\omega}$ which translates one
string to the other will be as desired.

######  Example 2.15.

_Sacks forcing_ , _Miller forcing_ , _Mathias forcing_ , _Laver forcing_ and
many other classical forcing notions are easily seen to be cone homogeneous
for the following reason: the cone below any condition is isomorphic to the
whole partial order. For descriptions of these examples, see [13].

Being a countable Borel equivalence relation, $\equiv^{\mathbb{P}}_{M}$ is
induced by some Borel action of a countable group. When the partial order is a
complete Boolean algebra $\mathbb{A}$ in $M$, this group can be taken to be
$\mathrm{Aut}^{M}(\mathbb{A})$, and the action the canonical one on generics
described above:

######  Theorem 2.16 (Vopěnka–Hájek [31]; Theorem 3.5.1 in [7]).

Let $\mathbb{A}$ be a complete Boolean algebra in $M$. If $G$ and $H$ are
$M$-generic filters for $\mathbb{A}$ and $M[G]=M[H]$, then there is involutive
automorphism $e$ of $\mathbb{A}$ in $M$ such that $H=e^{\prime\prime}G$.

######  Example 2.17.

As an immediate consequence of Theorem 2.16, if $\mathbb{A}$ is a rigid
complete Boolean algebra in $M$, then $\equiv^{\mathbb{A}}_{M}$ is smooth. An
example of a non-trivial Boolean algebra with this property appears in [19].
Another example, which shares properties (e.g., fusion and adding reals of
minimal degree) with Sacks and Miller forcing, is given in [14].

##  3\. Cohen reals

To further analyze the complexity of $\equiv^{\mathbb{C}}_{M}$ for Cohen
forcing $\mathbb{C}$, we will find it useful to consider its idealized
presentation; let $\mathbb{C}$ be all non-meager Borel subsets of
$2^{\omega}$, ordered by containment, as computed in $M$. Since $\mathbb{C}$
satisfies the countable chain condition, we can identify the Boolean
completion $\overline{\mathbb{C}}$ of $\mathbb{C}$, in $M$, with the quotient
of all Borel subsets modulo the meager ideal (cf. Lemma II.2.6.3 in [25]). Let
$\mathcal{C}$ be the set of $M$-generic Cohen reals in $2^{\omega}$, that is,
$\mathcal{C}=\mathcal{G}^{\mathbb{C}}_{M}$ in the notation of §2. The main
result of this section is the following:

######  Theorem 3.1.

$\equiv^{\mathbb{C}}_{M}$ is an increasing union of countably many hyperfinite
Borel equivalence relations. In particular, $\equiv^{\mathbb{C}}_{M}$ is
amenable.

We will need the following results from the literature:

######  Theorem 3.2 (Hjorth–Kechris [10], Sullivan–Weiss–Wright [26], Woodin;
Theorem 12.1 of [15]).

If $E$ is a countable Borel equivalence relation on a Polish space $X$, then
there is a comeager Borel set $C\subseteq X$ such that $E\upharpoonright C$ is
hyperfinite.

######  Theorem 3.3 (Maharam–Stone [17]).

Every automorphism of the Boolean algebra of Borel sets modulo meager sets, in
a complete metric space $X$, is induced by a meager-class preserving Borel
bijection $f:X\to X$.

Here, a bijection $f:X\to X$ on a Polish space is said to be _meager-class
preserving_ if both $f$ and $f^{-1}$ preserve meager sets.

A property of a Borel set $B$ coded in $M$ is _absolute_ if it has the same
truth value for $B^{M}$ in $M$ as for $B$ in $\mathbf{V}$. We can show that a
property of Borel sets is absolute by expressing it as a $\Pi^{1}_{1}$
predicate in their codes; absoluteness then follows by Mostowski’s
Absoluteness Theorem (Theorem 25.4 in [13]). A property of $B$ is _upwards
absolute_ if its truth for $B^{M}$ in $M$ implies its truth for $B$ in
$\mathbf{V}$.

Coding a Borel set, (non-)membership in a Borel set, and containment of Borel
sets, are all expressible as $\Pi^{1}_{1}$ predicates in the codes (Theorem
II.1.2 and Corollary II.1.2 in [25]), and thus absolute. These will be used
implicitly in what follows. We will need the absoluteness of several
additional properties:

######  Lemma 3.4.

The following notions are absolute for Borel sets $A$, $B$, and injective
Borel functions $f$, coded in $M$:

  1. (i)

$f$ is an injective function.

  2. (ii)

$A=f^{\prime\prime}B$.

###### Proof.

(i) The statements that “$f$ is a function” and that “$f$ is injective” are
universal in predicates for membership and non-membership in the graph of $f$,
and thus can be expressed as $\Pi^{1}_{1}$ predicates in a code for $f$.

(ii) It suffices to show that “$x\in f^{\prime\prime}B$” is $\Pi^{1}_{1}$ in
the codes for $f$ and $B$. This is analogous to the classical fact that
injective Borel images of Borel sets are Borel and can be derived from its
effective version (4D.7 in [20]).∎

######  Lemma 3.5.

The following notions are absolute for a Borel equivalence relation $E$ coded
in $M$:

  1. (i)

$E$ is an equivalence relation.

  2. (ii)

$E$ has finite classes.

  3. (iii)

For a countable group $\Gamma$ in $M$ with a Borel action on $2^{\omega}$
coded in $M$, $E$ is the induced orbit equivalence relation.

###### Proof.

(i) The statement that “$E$ is an equivalence relation” is universal in
predicates for membership and non-membership in $E$, and thus can be expressed
as a $\Pi^{1}_{1}$ predicate in a code for $E$.

(ii) Being an equivalence class of a Borel equivalence relation can be
expressed as a $\Pi^{1}_{1}$ predicate using predicates for membership and
non-membership in the equivalence relation. Since the property of being finite
can be expressed using a $\Pi^{1}_{1}$ predicate (cf. Lemma II.1.6.7 in [25]),
having all classes finite is expressible as a $\Pi^{1}_{1}$ predicate as well.

(iii) Both the statement that a Borel function $f:\Gamma\times 2^{\omega}\to
2^{\omega}$ is an action of $\Gamma$, and the fact that $E$ is the resulting
orbit equivalence relation, are easily expressible as $\Pi^{1}_{1}$ predicates
in the appropriate codes; we leave the verification to the reader. ∎

######  Lemma 3.6.

Being a hyperfinite Borel equivalence relation is upwards absolute222Being
hyperfinite is a $\Sigma^{1}_{2}$ property in the codes, but whether it is
$\Sigma^{1}_{2}$-complete, and thus not absolute for countable models, appears
to be unknown. for a Borel equivalence relation coded in $M$.

###### Proof.

Suppose $E$ is a Borel equivalence relation coded in $M$, and that in $M$,
$E^{M}=\bigcup_{n\in\omega}E_{n}^{M}$, where each $E_{n}^{M}$ is a Borel
equivalence relation with finite classes. Since containment and countable
unions are absolute for Borel codes (Lemma II.1.6.1 in [25]),
$E=\bigcup_{n\in\omega}E_{n}$ in $\mathbf{V}$, and by Lemma 3.5, is
hyperfinite. ∎

If $g$ is a meager-class preserving Borel bijection coded in $M$, then by the
absoluteness of meagerness (Lemma II.1.6.6 in [25]) and Lemma 3.4 above,
$g^{M}$ is a meager-class preserving Borel bijection in $M$, and induces an
automorphism of $\mathbb{C}$ (and $\overline{\mathbb{C}}$) given by:

$B\mapsto(g^{M})^{\prime\prime}(B).$

This in turn induces an action on $M$-generic filters for $\mathbb{C}$,

$H\mapsto g^{M}\cdot H=\\{(g^{M})^{\prime\prime}B:B\in H\\}.$

Passing to the generic reals, this action coincides with $g$’s action on
$2^{\omega}$:

######  Lemma 3.7.

Let $g:2^{\omega}\to 2^{\omega}$ be a meager-class preserving Borel bijection
coded in $M$, $x\in\mathcal{C}$, and $H_{x}$ the corresponding $M$-generic
filter for $\mathbb{C}$. Then,

$(g^{M})\cdot H_{x}=H_{g(x)}.$

###### Proof.

Given the correspondence between $M$-generic Cohen reals and $M$-generic
filters for $\mathbb{C}$, it suffices to prove that

$\bigcap\\{A:A^{M}\in g^{M}\cdot H_{x}\\}=\\{g(x)\\}.$

Let $B^{M}\in H_{x}$. Then, $x\in B$, so $g(x)\in g^{\prime\prime}B$. Let
$A^{M}=(g^{M})^{\prime\prime}B$. By Lemma 3.4(ii), $A=g^{\prime\prime}B$, and
thus $g(x)\in A$. This shows that

$g(x)\in\bigcap\\{A:A^{M}\in g^{M}\cdot H_{x}\\}.$

This intersection is a singleton by the genericity of $g^{M}\cdot H_{x}$. ∎

###### Proof of Theorem 3.1.

In $\mathbf{V}$, enumerate $\mathrm{Aut}^{M}(\overline{\mathbb{C}})$ as
$\\{\gamma_{n}:n\in\omega\\}$.

For each $n$, apply Theorem 3.3 in $M$ to find a meager-class preserving Borel
bijection $f_{n}^{M}$ of $(2^{\omega})^{M}$ which induces the automorphism
$\gamma_{n}$ on $\overline{\mathbb{C}}$. Let $\Gamma_{n}$ be an abstract group
in $M$ which is isomorphic to that generated by
$\\{f_{0}^{M},\ldots,f_{n-1}^{M}\\}$. We use $\Gamma_{n}$, rather than the
group generated by $\\{f_{0}^{M},\ldots,f_{n-1}^{M}\\}$, to simplify matters
when passing to $\mathbf{V}$. This induces a Borel action of $\Gamma_{n}$ on
$(2^{\omega})^{M}$; let $E_{n}^{M}$ be the induced orbit equivalence relation.
Note that while each $f_{n}^{M}$ and $\Gamma_{n}$ is in $M$, their enumeration
is not.

For each $n$, apply Theorem 3.2 in $M$ to obtain a comeager Borel set
$C_{n}^{M}$ on which $E_{n}^{M}$ is hyperfinite.

In $\mathbf{V}$, let $C=\bigcap_{n\in\omega}C_{n}$, which is comeager by the
absoluteness of meagerness (Lemma II.1.6.6 in [25]), and let
$E=\bigcup_{n\in\omega}(E_{n}\upharpoonright C)$. By Lemma 3.6, $E$ is an
increasing union of hyperfinite Borel equivalence relations. Since a real is
in $\mathcal{C}$ if and only if it is contained in every comeager Borel set
coded in $M$ (cf. §II.2 of [25]), $\mathcal{C}\subseteq C$.

We claim that $\equiv^{\mathbb{C}}_{M}$ coincides with
$E\upharpoonright\mathcal{C}$. Suppose that $x,y\in\mathcal{C}$ are
$E$-related. Then, there is some $n$ for which $xE_{n}y$. By Lemma 3.5(iii),
$\Gamma_{n}$ induces $E_{n}$, so there is a $g\in\Gamma_{n}$ with $y=g\cdot
x$. $g$’s action on $2^{\omega}$ can be expressed as a word in $f_{0}^{\pm
1},\ldots,f_{n-1}^{\pm 1}$. Let $g^{M}$ be the corresponding word in
$(f_{0}^{M})^{\pm 1},\ldots,(f_{n-1}^{M})^{\pm 1}$. In $M$, $g^{M}$ is a
meager-class preserving Borel bijection $(2^{\omega})^{M}\to(2^{\omega})^{M}$,
and thus, induces an automorphism of $\mathbb{C}$ (in $M$) mapping the
$M$-generic filter corresponding to $x$ to that corresponding to $y$, by Lemma
3.7. Hence, $M[x]=M[y]$.

Conversely, suppose $x,y\in\mathcal{C}$ are $\equiv^{\mathbb{C}}_{M}$-related.
Since $\overline{\mathbb{C}}$ is a complete Boolean algebra in $M$, we can
apply Theorem 2.16 to obtain a
$\gamma_{k}\in\mathrm{Aut}^{M}(\overline{\mathbb{C}})$ such that $\gamma_{k}$
maps the $M$-generic filter corresponding to $x$ to that corresponding $y$. By
Lemma 3.7, $f_{k}(x)=y$, and so $xE_{k+1}y$.

The amenability of $\equiv^{\mathbb{C}}_{M}$ follows from the fact that
hyperfinite equivalence relations are amenable, and increasing unions of
countably many amenable equivalence relations are amenable (Propositions 2.15
in [12]). ∎

##  4\. Random reals

As in §3, we will view _random forcing_ in its idealized form, as the set
$\mathbb{B}$ of all non-null Borel subsets of $2^{\omega}$, ordered by
containment, as computed in $M$. Since $\mathbb{B}$ also satisfies the
countable chain condition, we can identify its completion
$\overline{\mathbb{B}}$ in $M$ with the quotient of all Borel sets modulo the
null ideal. Let $\mathcal{R}$ be the set of $M$-generic random reals in
$2^{\omega}$.

As in §3, if $g$ is a measure-preserving Borel bijection of $2^{\omega}$ coded
in $M$, then by the absoluteness of Lebesgue measure (Lemma II.1.6.4 in [25]),
$g^{M}$ induces an automorphism of $\mathbb{B}$ (and $\overline{\mathbb{B}}$)
by $B\mapsto(g^{M})^{\prime\prime}B$. This induces an action on $M$-generic
filters for $\mathbb{B}$ by $H\mapsto g^{M}\cdot
H=\\{(g^{M})^{\prime\prime}B:B\in H\\}$. The following is the analogue of
Lemma 3.7 for $\mathbb{B}$ and its proof is identical.

######  Lemma 4.1.

Let $g:2^{\omega}\to 2^{\omega}$ be a measure-preserving Borel bijection coded
in $M$, $x\in\mathcal{R}$, and $H_{x}$ the corresponding $M$-generic filter
for $\mathbb{B}$. Then,

$(g^{M})\cdot H_{x}=H_{g(x)}.$

∎

######  Lemma 4.2.

The following notions are absolute for a countably infinite group $\Gamma$ in
$M$:

  1. (i)

The Bernoulli shift action of $\Gamma$.

  2. (ii)

The free part of the Bernoulli shift action of $\Gamma$.

###### Proof.

(i) Let $s^{M}:\Gamma\times(2^{\Gamma})^{M}\to(2^{\Gamma})^{M}$ be the
Bernoulli shift of $\Gamma$, as computed in $M$. Then, $s^{M}(\gamma,x)=y$ if
and only if $y(\delta)=(\gamma^{-1}\delta)$ for all $\delta\in\Gamma$, which
is arithmetic in the multiplication table of $\Gamma$. Thus, we can express
that $s$ is the Bernoulli shift of $\Gamma$ as a $\Pi^{1}_{1}$ predicate in a
code for $s$, using a real which codes $\Gamma$ and its multiplication
operation.

(ii) Likewise, the definition of the free part of the Bernoulli shift is also
arithmetic in the multiplication table of $\Gamma$. ∎

######  Theorem 4.3.

Suppose that $\Gamma$ is a countably infinite group in $M$. Identifying
$2^{\omega}$ with $2^{\Gamma}$, $\mathcal{R}$ is a $\Gamma$-invariant conull
Borel subset of the free part of the Bernoulli shift action of $\Gamma$ and
$F(\Gamma,2)\upharpoonright\mathcal{R}\;\subseteq\;\equiv^{\mathbb{B}}_{M}$.

###### Proof.

We identify (in $M$ and $\mathbf{V}$) $2^{\Gamma}$ with $2^{\omega}$ via some
fixed bijection $\Gamma\to\omega$ in $M$, and thus $\mathbb{B}$ becomes the
set of all Borel subsets of $2^{\Gamma}$ having positive measure in $M$, and
$\mathcal{R}$ a Borel subset of $2^{\Gamma}$ in $\mathbf{V}$.

By Lemma 4.2(i), the shift action of each $\gamma\in\Gamma$ is a measure-
preserving Borel bijection of $2^{\Gamma}$ coded in $M$.

We claim that $\mathcal{R}$ is $\Gamma$-invariant, that is, for every $x\in
2^{\Gamma}$ and $\gamma\in\Gamma$, if $x$ is random over $M$, then so is
$\gamma\cdot x$. To this end, suppose that $x\in\mathcal{R}$ and let
$\gamma\in\Gamma$. Let $H_{x}$ be the corresponding $M$-generic filter for
$\mathbb{B}$. By Lemma 4.1, $(\gamma^{M})\cdot H_{x}=H_{\gamma\cdot x}$, and
so $\gamma\cdot x$ is the random real corresponding to the $M$-generic filter
$\gamma^{M}\cdot H_{x}$.

Observe that if $x\in\mathcal{R}$ and $\gamma\in\Gamma$, then Lemma 4.1 also
shows that $M[x]=M[\gamma\cdot x]$. Thus, the restriction of
$E(\Gamma,2)\upharpoonright\mathcal{R}$ is contained in
$\equiv^{\mathbb{B}}_{M}$.

Lastly, we claim that $\mathcal{R}$ is contained in the free part the
Bernoulli shift action, $B=(2)^{\Gamma}$. By Lemma 4.2(ii), $B$ is coded
correctly in $M$, and so $B^{M}$ is conull in $M$ by the absoluteness of
Lebesgue measure (Lemma II.1.6.4 in [25]). As a real is in $\mathcal{R}$
exactly when it is contained in every conull Borel set coded in $M$ (Theorem
II.2.6 in [25]), we have that $\mathcal{R}\subseteq B=(2)^{\Gamma}$. Note that
$\mathcal{R}$ itself is conull, again by the absoluteness of Lebesgue measure.
∎

######  Theorem 4.4.

$\equiv^{\mathbb{B}}_{M}$ is not amenable. In particular,
$\equiv^{\mathbb{B}}_{M}$ is not hyperfinite.

###### Proof.

Take $\Gamma=F_{2}$, which is clearly in $M$. By Theorem 4.3, $\Gamma$ acts in
a free, measure preserving way on the conull set $\mathcal{R}\subseteq
2^{\Gamma}$ of $M$-generic random reals. Since $\Gamma$ is a non-amenable
group, any free, measure-preserving Borel action of $\Gamma$ on a standard
probability space yields a non-amenable orbit equivalence relation
(Proposition 2.14 in [12]). Hence, $F(\Gamma,2)\upharpoonright\mathcal{R}$ is
not amenable. Since amenability is inherited by subequivalence relations
(Proposition 2.15 in [12]), $\equiv^{\mathbb{B}}_{M}$ is not amenable, and
thus not hyperfinite, either. ∎

Amenability is inherited downwards via Borel reductions (Proposition 2.15 in
[12]), so Theorems 3.1 and 4.4 imply:

######  Corollary 4.5.

$\equiv^{\mathbb{B}}_{M}\;\not\leq_{B}\;\equiv^{\mathbb{C}}_{M}$.∎

Next, we will make use of results for actions of Kazdahn groups. We will not
define the Kazdahn property here (see [33]), as for our applications, only one
such group is needed, namely $\mathrm{SL}_{3}(\mathbb{Z})$.

A Borel homomorphism $f$ from equivalence relations $E$ to $F$, where $E$
lives on a standard measure space $(X,\mu)$, is _$\mu$ -trivial_ if there is a
$\mu$-conull Borel set $C\subseteq X$ which $f$ maps to a single $F$-class. If
no such set exists, it is _$\mu$ -nontrivial_. The following theorem is a
consequence of results in [1]:

######  Theorem 4.6 (Hjorth–Kechris, Theorem 10.5 in [10]).

Let $\Gamma$ be a countable Kazhdan group which acts in an ergodic measure-
preserving Borel way on a standard probability space $(X,\mu)$. If $F$ is a
treeable countable Borel equivalence relation, then every Borel homomorphism
from $E$ to $F$ is $\mu$-trivial.

######  Theorem 4.7.

$\equiv^{\mathbb{B}}_{M}$ is not treeable.

###### Proof.

Let $\Gamma=\mathrm{SL}_{3}(\mathbb{Z})$, which is clearly in $M$. Theorem 4.6
implies that $F(\Gamma,2)\upharpoonright\mathcal{R}$ is not treeable, where
$\mathcal{R}$ is the conull set of $M$-generic random reals in $2^{\Gamma}$.
By Theorem 4.3,
$F(\Gamma,2)\upharpoonright\mathcal{R}\subseteq\;\equiv^{\mathbb{B}}_{M}$, and
since treeability is inherited by subequivalence relations (Proposition 3.3 in
[12]), $\equiv^{\mathbb{B}}_{M}$ is not treeable either. ∎

The next theorem we need is an application of results from [21]:

######  Theorem 4.8 (Thomas, Theorem 3.6 in [28]).

Let $\Delta=\mathrm{SL}_{3}(\mathbb{Z})\times S$, where $S$ is any countable
group. Suppose that $\Gamma$ is a countable group that acts in a free Borel
way on a standard Borel space, with orbit equivalence relation $E$. If there
exists a $\mu$-nontrivial Borel homomorphism from $E(\Delta,2)$ to $E$, then
there exists a group homorphism $\pi:\Delta\to\Gamma$ with finite kernel.

The proof of the following is modeled on that of Theorem 3.9 in [28].

######  Theorem 4.9.

$\equiv^{\mathbb{B}}_{M}$ is not Borel reducible to the orbit equivalence
relation induced by a free action of any countable group $\Gamma$ in $M$.

###### Proof.

Let $\Gamma$ be a countably infinite group in $M$. Suppose, towards a
contradiction, that $\equiv^{\mathbb{B}}_{M}$ is Borel reducible to the orbit
equivalence relation $E$ of a free Borel action of $\Gamma$ on some standard
Borel space. We remark that $E$ need not be coded in $M$.

Working in $M$, as there are uncountably many finitely generated groups, there
exists a finitely generated group $L$ which does not embed into $\Gamma$. Let
$S$ be the free product $L\ast\mathbb{Z}$ and let
$\Delta=\mathrm{SL}_{3}(\mathbb{Z})\times S$. Then, $\Delta$ has no nontrivial
finite normal subgroups and does not embed into $\Gamma$. The non-existence of
such an embedding is absolute and thus applies in $\mathbf{V}$.

By Theorem 4.3,
$F(\Delta,2)\upharpoonright\mathcal{R}\subseteq\;\equiv^{\mathbb{B}}_{M}$,
where $\mathcal{R}$ is the conull set of $M$-generic random reals in
$2^{\Delta}$. This induces a $\mu$-nontrivial homomorphism from $F(\Delta,2)$
to $E$, and thus, by Theorem 4.8, an embedding of $\Delta$ into $\Gamma$, a
contradiction. ∎

We note that Theorem 4.9 implies Theorem 4.7, since $F(F_{2},2)$ is universal
for all treeable Borel equivalence relations (Theorem 3.17 in [12]).

Lastly, we turn to the question of whether $\equiv^{\mathbb{B}}_{M}$ is a
universal countable Borel equivalence relation. We will employ two results
about universality that are conditional on the following conjecture of Andrew
Marks:

######  Marks’s uniformity conjecture (Conjecture 1.4 in [18]).

A countable Borel equivalence relation is universal if and only if it is
uniformly universal with respect to every way it can be generated.

See [18] for the relevant definitions and details. We remark that this
conjecture is closely related to Martin’s conjecture on Turing invariant Borel
maps; for instance, Theorem 4.10(2) below is also a consequence of Martin’s
conjecture (Theorem 5.4 in [27]).

######  Theorem 4.10 (Marks, cf. Theorem 1.5 in [18]).

Assume Marks’s uniformity conjecture.

  1. (1)

An increasing union of countably many non-universal countable Borel
equivalence relations is not universal.

  2. (2)

If $E$ is a countable Borel equivalence relation on a standard probability
space $(X,\mu)$, then there is a $\mu$-conull Borel set $Z\subseteq X$ for
which $E\upharpoonright Z$ is not universal.

A model $M$ of $\mathsf{ZFC}$ is _$\mathbf{\Sigma}^{1}_{2}$ -correct_ if
$\Sigma^{1}_{2}$ formulas with parameters in $M$ are absolute. While a
countable transitive model of $\mathsf{ZFC}$ may failto be
$\mathbf{\Sigma}^{1}_{2}$-correct, $\mathbf{\Sigma}^{1}_{2}$-correct countable
models are plentiful under mild assumptions, e.g., take the transitive
collapse of a countable elementary submodel of $\mathbf{V}_{\kappa}$, when
$\kappa$ is inaccessible.333We would like to thank Gabriel Goldberg for
pointing this out. 444As per footnote 1, we may allow $\omega_{1}\subseteq M$,
provided $|\mathcal{P}(\mathbb{B})\cap M|=|\mathcal{P}(\mathbb{R})\cap M|$ is
still countable in $\mathbf{V}$. In this case, $M$ will be
$\mathbf{\Sigma}^{1}_{2}$-correct by Shoenfield’s Absoluteness Theorem
(Theorem 25.20 in [13]), without any additional hypotheses.

######  Theorem 4.11.

Assume Mark’s uniformity conjecture. If $M$ is
$\mathbf{\Sigma}^{1}_{2}$-correct, then $\equiv^{\mathbb{B}}_{M}$ is not
universal.

To prove this result, we first observe the following lemma, a consequence of
the universality of $E(F_{2},2)$ and quantifier counting.

######  Lemma 4.12.

The statement that a countable Borel equivalence relation $E$ is universal is
$\Sigma^{1}_{2}$ in a code for $E$.∎

We will also need the measure-theoretic analogue of Theorem 3.3:

######  Theorem 4.13 (von Neumann [30]; Theorem 15.21 in [22]).

Every automorphism of the Boolean algebra of Borel sets modulo null sets, in a
standard probability space $(X,\mu)$, is induced by a measure-preserving Borel
bijection $f:X\to X$.

###### Proof of Theorem 4.11.

This argument is very similar to that in the proof of Theorem 3.1, so we will
omit some of the details. Enumerate (in $\mathbf{V}$)
$\mathrm{Aut}^{M}(\overline{\mathbb{B}})$ as $\\{\gamma_{n}:n\in\omega\\}$.
For each $n$, in $M$ we use Theorem 4.13 to find a measure-preserving Borel
bijection $f_{n}^{M}$ of $(2^{\omega})^{M}$ which induces the automorphism
$\gamma_{n}$. Let $\Gamma_{n}$ be an abstract group in $M$ which is isomorphic
to that generated by $\\{f_{0}^{M},\ldots,f_{n-1}^{M}\\}$, and let $E_{n}^{M}$
be the induced orbit equivalence relation on $(2^{\omega})^{M}$.

For each $n$, apply Theorem 4.10(2) in $M$ to obtain a conull Borel set
$C_{n}^{M}$ on which $E_{n}^{M}$ is not universal (in $M$).

In $\mathbf{V}$, let $C=\bigcap_{n\in\omega}C_{n}$, and let
$E=\bigcup_{n\in\omega}(E_{n}\upharpoonright C)$. Since $M$ is
$\mathbf{\Sigma}^{1}_{2}$-correct, each $E_{n}$ is not universal in
$\mathbf{V}$ by Lemma 4.12. Thus, by Theorem 4.10(1), $E$ is not universal.
Since $M$-generic random reals are contained in every conull Borel set coded
in $M$, $\mathcal{R}\subseteq C$.

It remains to argue that $\equiv^{\mathbb{B}}_{M}$ coincides with
$E\upharpoonright\mathcal{R}$. This is done in exactly the same way as for
$\equiv^{\mathbb{C}}_{M}$ in the proof of Theorem 3.1, using the completeness
(in $M$) of the Boolean algebra of Borel sets modulo null sets, Theorem 2.16,
and Lemmas 3.5 and 4.1. ∎

##  5\. Further questions

Much of this paper has focused on Cohen and random forcing. This is due to the
intimate connections these examples have with Baire category and measure,
respectively. A natural next step is to consider those partial orders
mentioned in Example 2.15:

######  Question 5.1.

What can we say about the complexity of $\equiv^{\mathbb{P}}_{M}$ when
$\mathbb{P}$ is, e.g., Sacks, Miller, Mathias, or Laver forcing, or any of the
other classical forcing notions? In particular, is $\equiv^{\mathbb{P}}_{M}$
hyperfinite in any of these cases?

The increasing unions problem for hyperfinite equivalence relations [4] asks
whether an increasing union of countably many hyperfinite Borel equivalence
relations is hyperfinite. By Theorem 3.1, a positive resolution to this
problem would imply that $\equiv^{\mathbb{C}}_{M}$ is hyperfinite, when
$\mathbb{C}$ is Cohen forcing. This provides an interesting special case of
this long-standing open problem:

######  Question 5.2.

Is $\equiv^{\mathbb{C}}_{M}$ hyperfinite?

Given a positive answer to Question 5.2, the Glimm-Effros dichotomy for
countable Borel equivalence relations (Theorem 1.5 in [11]) would allow us to
improve Corollary 4.5 to
$\equiv^{\mathbb{C}}_{M}\;<_{B}\;\equiv^{\mathbb{B}}_{M}$.

In Theorem 4.9, we left open the question of whether
$\equiv^{\mathbb{B}}_{M}$, for $\mathbb{B}$ random forcing, is _essentially
free_ , that is, reducible to the orbit equivalence relation of a free Borel
action of some countable group. Note that it is easy to check that the
associated action of $\mathrm{Aut}^{M}(\mathbb{B})$ on the random reals is not
free.

######  Question 5.3.

Is $\equiv^{\mathbb{B}}_{M}$ essentially free?

Since there is no countable collection of groups such that an equivalence
relation is essentially free if and only if it is reducible to an orbit
equivalence relation coming from a free action of a group in that collection
(cf. Corollary 3.10 in [28]), Theorem 4.9 cannot be used directly to resolve
Question 5.3.

Can we obtain the result in Theorem 4.11 without the extra hypotheses of
Marks’s uniformity conjecture and the $\mathbf{\Sigma}^{1}_{2}$-correctness of
$M$?

######  Question 5.4.

Is $\equiv^{\mathbb{B}}_{M}$ non-universal (for any $M$)?

More generally, to what extent does the model $M$ affect the complexity of
$\equiv^{\mathbb{P}}_{M}$? In asking this question, we have to avoid certain
trivialities; for instance, by collapsing $|\mathbb{P}|^{M}$ to $\aleph_{0}$,
we can go from a model $M$ for which $\equiv^{\mathbb{P}}_{M}$ is smooth
(Example 2.17), to a model $M^{\prime}$ in which $\mathbb{P}$ is equivalent to
Cohen forcing and thus $\equiv^{\mathbb{P}}_{M^{\prime}}$ is not smooth. So,
we focus on the case of idealized forcings which are $\mathsf{ZFC}$-correct,
in the sense of [32], and thus have a natural interpretation in any model.

######  Question 5.5.

Is there a $\mathsf{ZFC}$-correct $\sigma$-ideal $I$ on $2^{\omega}$ and
countable transitive models $M$ and $N$ such that $\equiv^{(P_{I})^{M}}_{M}$
and $\equiv^{(P_{I})^{N}}_{N}$ are not Borel bireducible?

## References

  * [1] S. R. Adams and R. J. Spatzier.  Kazhdan groups, cocycles and trees.  Amer. J. Math., 112(2):271–287, 1990.
  * [2] J. Clemons, S. Coskey, and S. Dworetzky.  The classification of countable models of set theory.  Preprint, 2017.
  * [3] N. Dobrinen and S.-D. Friedman.  Homogeneous iteration and measure one covering relative to HOD.  Arch. Math. Logic, 47(7-8):711–718, 2008.
  * [4] R. Dougherty, S. Jackson, and A. S. Kechris.  The structure of hyperfinite Borel equivalence relations.  Trans. Amer. Math. Soc., 341(1):193–225, 1994.
  * [5] J. Feldman and C. C. Moore.  Ergodic equivalence relations, cohomology, and von Neumann algebras. I.  Trans. Amer. Math. Soc., 234(2):289–324, 1977.
  * [6] S. Gao.  Invariant descriptive set theory, volume 293 of Pure and Applied Mathematics.  CRC Press, Boca Raton, FL, 2009.
  * [7] S. Grigorieff.  Intermediate submodels and generic extensions in set theory.  Ann. Math. (2), 101:447–490, 1975.
  * [8] J. D. Hamkins.  On ${V}$-decisive and weakly homogeneous forcings.  MathOverflow.  URL:https://mathoverflow.net/q/184806 (version: 2017-04-13).
  * [9] Y. Hayut and A. Karagila.  Restrictions on forcings that change cofinalities.  Arch. Math. Logic, 55(3-4):373–384, 2016.
  * [10] G. Hjorth and A. S. Kechris.  Borel equivalence relations and classifications of countable models.  Ann. Pure Appl. Logic, 82(3):221–272, 1996.
  * [11] M. Hrušák.  Selectivity of almost disjoint families.  Acta Univ. Carolin. Math. Phys., 41(2):13–21, 2000.
  * [12] S. Jackson, A. S. Kechris, and A. Louveau.  Countable Borel equivalence relations.  J. Math. Log., 2(1):1–80, 2002.
  * [13] T. Jech.  Set theory.  Springer Monographs in Mathematics. Springer-Verlag, Berlin, 2003.  The third millennium edition, revised and expanded.
  * [14] T. Jech and S. Shelah.  A complete Boolean algebra that has no proper atomless complete subalgebra.  J. Algebra, 182(3):748–755, 1996.
  * [15] A. S. Kechris and B. D. Miller.  Topics in orbit equivalence, volume 1852 of Lecture Notes in Mathematics.  Springer-Verlag, Berlin, 2004.
  * [16] K. Kunen.  Set theory, volume 102 of Studies in Logic and the Foundations of Mathematics.  North-Holland, Amsterdam, 1980.
  * [17] D. Maharam and A. H. Stone.  Realizing isomorphisms of category algebras.  Bull. Austral. Math. Soc., 19(1):5–10, 1978.
  * [18] A. S. Marks.  Uniformity, universality, and computability theory.  J. Math. Log., 17(1):1750003, 50, 2017.
  * [19] K. McAloon.  Consistency results about ordinal definability.  Ann. Math. Logic, 2(4):449–467, 1970/71.
  * [20] Y. N. Moschovakis.  Descriptive set theory, volume 155 of Mathematical Surveys and Monographs.  American Mathematical Society, Providence, RI, second edition, 2009.
  * [21] S. Popa.  Cocycle and orbit equivalence superrigidity for malleable actions of $w$-rigid groups.  Invent. Math., 170(2):243–295, 2007.
  * [22] H. L. Royden.  Real analysis.  Macmillan Publishing Company, New York, third edition, 1988.
  * [23] W. Rudin.  Real and complex analysis.  McGraw-Hill Book Co., New York, third edition, 1987.
  * [24] T. A. Slaman and J. R. Steel.  Definable functions on degrees.  In Cabal Seminar 81–85, volume 1333 of Lecture Notes in Math., pages 37–55. Springer, Berlin, 1988.
  * [25] R. M. Solovay.  A model of set-theory in which every set of reals is Lebesgue measurable.  Ann. of Math. (2), 92:1–56, 1970.
  * [26] D. Sullivan, B. Weiss, and J. D. M. Wright.  Generic dynamics and monotone complete $C^{\ast}$-algebras.  Trans. Amer. Math. Soc., 295(2):795–809, 1986.
  * [27] S. Thomas.  Martin’s conjecture and strong ergodicity.  Arch. Math. Logic, 48(8):749–759, 2009.
  * [28] S. Thomas.  Popa superrigidity and countable Borel equivalence relations.  Ann. Pure Appl. Logic, 158(3):175–189, 2009.
  * [29] S. Thomas and S. Schneider.  Countable borel equivalence relations.  In J. Cummings and E. Schimmerling, editors, Appalachian Set Theory 2006-2012, volume 406 of Lecture Notes Series, pages 25–62. London Mathematical Society, 2012.
  * [30] J. von Neumann.  Einige Sätze über messbare Abbildungen.  Ann. of Math. (2), 33(3):574–586, 1932.
  * [31] P. Vopěnka and P. Hájek.  The theory of semisets.  Academia (Publishing House of the Czechoslovak Academy of Sciences), Prague, 1972.
  * [32] J. Zapletal.  Forcing idealized, volume 174 of Cambridge Tracts in Mathematics.  Cambridge University Press, Cambridge, 2008.
  * [33] R. J. Zimmer.  Ergodic theory and semisimple groups, volume 81 of Monographs in Mathematics.  Birkhäuser Verlag, Basel, 1984.