# Isomorphism of locally compact Polish metric structures

Maciej Malicki  Institute of Mathematics, Polish Academy of Sciences, ul.
Sniadeckich 8, Warsaw, Poland<EMAIL_ADDRESS>
###### Abstract.

We study the isomorphism relation on Borel classes of locally compact Polish
metric structures. We prove that isomorphism on such classes is always
classifiable by countable structures (equivalently: Borel reducible to graph
isomorphism), which implies, in particular, that isometry of locally compact
Polish metric spaces is Borel reducible to graph isomorphism. We show that
potentially $\bm{\Pi}^{0}_{\alpha+1}$ isomorphism relations are Borel
reducible to equality on hereditarily countable sets of rank $\alpha$,
$\alpha\geq 2$. We also study approximations of the Hjorth-isomorphism game,
and formulate a condition ruling out classifiability by countable structures.

###### Key words and phrases:

equivalence relations, infinitary continuous logic, locally compact
structures.

###### 2020 Mathematics Subject Classification:

Primary 03E15; Secondary 03C66, 03C75

##  1\. Introduction

An equivalence relation $E$ on a Polish space $X$ is Borel reducible to an
equivalence relation $F$ on a Polish space $Y$ if there is a Borel mapping
$f:X\rightarrow Y$ such that

$x_{1}Ex_{2}\mbox{ iff }f(x_{1})Ff(x_{2}).$

The notion of Borel reducibility can be thought of as a general framework for
measuring complexity of various notions of isomorphism. For instance,
Ornstein’s celebrated theorem says that isomorphism of Bernoulli shifts can be
characterized by their entropy, i.e., by real numbers. This translates into
the language of Borel reducibility as the statement that the isomorphism
equivalence relation on the space of Bernoulli shifts is Borel reducible to
the equality relation on $\mathbb{R}$ (via an appropriate coding of Bernoulli
shifts as elements of a Polish space, and a Borel mapping assigning to shifts
their entropy). In other words, this relation is _smooth_ : it admits
invariants that are elements of a Polish space. However, there are many
interesting classification results that do not yield as concrete invariants.
Halmos and von Neumann proved that isomorphism of measure preserving
transformations with discrete spectrum is reducible to equality on countable
subsets of the unit circle (via a mapping assigning to such transformations
their spectrum). And Kechris showed that orbit equivalence relations induced
by actions of locally compact Polish groups are Borel reducible to relations
with countable classes, i.e., they are _essentially countable_.

As a matter of fact, all these results have a common feature: they say that
the involved equivalence relations are _classifiable by countable structures_
, i.e., they are Borel reducible to the isomorphism relation on a Borel class
of countable structures in the sense of model theory. It should not be
surprising that in this setting tools coming from logic play a vital role. It
has been known for a long time that there are deep connections between model
theory of the infinitary logic $\mathcal{L}_{\omega_{1}\omega}$ and
descriptive set theory – e.g., Scott analysis or the Lopez-Escobar theorem.
And Hjorth’s theory of turbulence, inspired by Scott analysis, is a prominent
example of this phenomenon in the theory of Borel reducibility. Another
important result, due to Hjorth and Kechris, characterizes in model-
theoretical terms essential countability of isomorphism on Borel classes of
countable structures: it is essentially countable iff there is a countable
fragment $F$ of $\mathcal{L}_{\omega_{1}\omega}$ such that for every structure
$M$ in the class there is a tuple $\bar{a}$ such that
${\rm{Th}}_{F}(M,\bar{a})$ is $\aleph_{0}$-categorical.

Very recently, successful attempts have been made at extending this approach
to continuous logic. In this setting, Polish (i.e., separable and complete)
metric structures play the role of countable structures. A continuous
$\mathcal{L}_{\omega_{1}\omega}$ logic was first studiedb by Ben Yaacov and
Iovino in [3], and a continuous version of Scott analysis was developed in
[2], laying the foundations for descriptive set theoretic applications. And in
[6], Hjorth and Kechris’ characterization of essential countability has been
generalized to locally compact Polish metric structures, leading to a model-
theoretic proof of Kechris’ theorem on orbit equivalence relations induced by
actions of locally compact Polish groups.

In the present paper, we continue this line of research. We show in Theorem
4.5 that isomorphism classes of locally compact Polish metric structures can
be characterized by hereditarily countable sets built out of closed subsets of
appropriate type spaces, and this implies that isomorphism on Borel classes of
locally compact Polish metric structures is always classifiable by countable
structures (Theorem 4.6). In particular, we confirm a conjecture of Gao and
Kechris from [4], where they asked whether isometry of locally compact Polish
metric spaces is Borel reducible to graph isomorphism (Theorem 4.7). Next, we
perform a fine-grained analysis of Borel isomorphism relations along the lines
of [8]. Generalizing in Theorem 4.12 results from [9], we prove that
potentially $\bm{\Pi}^{0}_{\alpha+2}$ isomorphism on a Borel class of locally
compact Polish metric structures is Borel reducible to equality on
hereditarily countable sets of rank $\alpha+1$, $\alpha\geq 1$.

In the last part of the paper, we turn to equivalence relations that are _not_
classifiable by countable structures. Lupini and Panagiotopolous [11] recently
developed a game-theoretic approach that (with an aid of Hjorth’s theory of
turbulence) gives an interesting sufficient condition for not being
classifiable in this way. We introduce and study a hierarchy of games that are
finer and finer approximations of the Hjorth-isomorphism game considered in
[11]. We show that in the case of isomorphism of countable structures, these
games capture information contained in families $Th^{\alpha}(M)$ (where
$Th^{0}(M)$ is the theory of $M$, $Th^{1}(M)$ is the family of theories of
structures $(M,\bar{a})$, etc). We also provide in Theorem 5.8 a sufficient
condition ruling out classifiability by countable structures, and, in Theorem
5.7, by countable structures with isomorphism of a given Borel complexity.

##  2\. Notation and basic facts

In this section, we briefly discuss basics of infinitary continuous logic
$\mathcal{L}_{\omega_{1}\omega}$. For a more detailed treatment, the reader is
referred to [2] and [6]. A _modulus of continuity_ is a continuous function
$\Delta\colon[0,\infty)\to[0,\infty)$ satisfying for all $r,s\in[0,\infty)$:

  * •

$\Delta(0)=0$,

  * •

$\Delta(r)\leq\Delta(r+s)\leq\Delta(r)+\Delta(s)$.

Suppose that $\Delta$ is a modulus of continuity and that $(X,d_{X})$ and
$(Y,d_{Y})$ are metric spaces. We say that a map $f:X\to Y$ _respects_
$\Delta$ if

$d_{Y}(f(x_{1}),f(x_{2}))\leq\Delta(d_{X}(x_{1},x_{2}))\quad\text{ for all
}x_{1},x_{2}\in X.$

A _signature_ $L$ is a collection of predicate and function symbols and as is
customary, we treat constants as $0$-ary functions. Throughout the paper, we
assume that $L$ is countable. To each symbol $P$ are associated its _arity_
$n_{P}$ and its _modulus of continuity_ $\Delta_{P}$, and, if $P$ is a
predicate, its _bound_ , i.e., a compact interval $I_{P}\subseteq\mathbb{R}$.
In a metric structure $M$ with _complete_ metric $d$, extended to finite or
infinite tuples by putting, for $m,n\leq\omega$, $\bar{a}\in M^{m}$,
$\bar{b}\in M^{n}$,

$d(\bar{a},\bar{b})=\max\\{d(a_{i},b_{i}):i<\min(m,n)\\},$

predicate symbols are interpreted as real-valued functions of the appropriate
arity respecting the modulus of continuity and the bound; similarly for
function symbols.

Terms and atomic formulas in infinitary continuous logic
$\mathcal{L}_{\omega_{1}\omega}(L)$ in signature $L$ are defined in the usual
way. Other formulas are built using:

  * •

Finitary connectives: if $\phi$ and $\psi$ are formulas and $r\in\mathbb{Q}$,
then $\phi+\psi$, $r\phi$, and $\phi\vee\psi$ are formulas. Here
$\phi\vee\psi$ is interpreted as $\max(\phi,\psi)$, we also define
$\phi\wedge\psi\coloneqq-(-\phi\vee-\psi)=\min(\phi,\psi)$,
$\phi\dotdiv\psi=\max(\phi-\psi,0)$. The constant $1$ is a formula.

  * •

Quantifiers: if $\phi(x,\bar{y})$ is a formula, then $\sup_{x}\phi$ and
$\inf_{x}\phi$ are formulas.

  * •

Infinitary connectives: if $\\{\phi_{n}(\bar{x}):n\in\mathbb{N}\\}$ are
formulas with the same finite set of free variables $\bar{x}$ that _respect a
common continuity modulus and bound_ , then $\bigvee_{n}\phi_{n}$ and
$\bigwedge_{n}\phi_{n}$ are formulas. The symbol $\bigvee$ is interpreted as a
countable supremum and $\bigwedge$ is interpreted as a countable infimum. The
condition that we impose ensures that the interpretations of these formulas
are still bounded, uniformly continuous functions.

The interpretations of formulas in a metric structure $M$ are defined in the
usual way. It is important to keep in mind that to any formula are associated
its modulus of continuity and bound that can be calculated from its
constituents. If $\phi$ is a formula, we will denote by $\phi^{M}$ the
interpretation of $\phi$ in $M$. A _sentence_ is a formula with no free
variables, and a _theory_ is a collection of conditions of the form $\phi=c$,
where $\phi$ is a sentence and $c\in\mathbb{R}$; throughout the paper, we will
consider only countable theories. A condition $\phi=c$ is _satisfied_ in a
structure $M$ if $\phi^{M}=c$. A structure $M$ is a _model_ of the theory $T$,
denoted by $M\models T$, if all conditions in $T$ are satisfied in $M$.

Fix a signature $L$. A _fragment_ of $\mathcal{L}_{\omega_{1}\omega}(L)$ is a
countable collection $F\subseteq\mathcal{L}_{\omega_{1}\omega}(L)$ that
contains all atomic formulas and is closed under finitary connectives,
quantifiers, taking subformulas, and substitution of terms for variables. The
smallest fragment is _the finitary fragment_ $\mathcal{L}_{\omega\omega}(L)$
that contains no infinitary formulas. If $F$ is a fragment and $T$ is a
theory, we will say that $T$ is an $F$-theory if all sentences that appear in
$T$ are in $F$.

Fix a fragment $F$. For an $F$-theory $T$, $M\models T$, and $\bar{a}\in
M^{n}$, the _type of $\bar{a}$_ (or $F$-type if $F$ is not clear from the
context)), denoted by $\rm{tp}(\bar{a})$ (or $\rm{tp}_{F}(\bar{a})$), is
defined as a collection of all conditions of the form
$\phi(x_{1},\ldots,x_{n})=c$ such that $\phi\in F$, and $\phi^{M}(\bar{a})=c$
(we write $\phi(\rm{tp}(\bar{a}))=c$). An _$n$ -type_ of $T$ is the type of an
$n$-tuple $\bar{a}$ in $M$ such that $M\models T$ (note that this definition
agrees with the definition of a realizable type from Section 2.2 in [6]). The
set $S_{n}(T)$ is the set of all $n$-types of $T$, i.e.,

$S_{n}(T)=\\{\rm{tp}(\bar{a}):M\models T,\bar{a}\in M^{n}\\}.$

For $\phi\in F$ and $r\in\mathbb{Q}$, put

$[\phi<r]=\\{p\in S_{n}(T):\phi(p)=c\in p\mbox{ for some }c<r\\},$

and define $[\phi\leq r]$, $[\phi=r]$ analogously. Observe that every set
$[\phi\leq r]$ can be written as some $[\psi=0]$, and every $[\phi<r]$ can be
written as a countable union of some $[\psi=0]$. The _logic topology_
$\tau_{n}$ on $S_{n}(T)$ is given by pointwise convergence on formulas, i.e.,
basic open sets are of the form $[\phi<r]$. By [6, Proposition 3.7], this
topology is Polish.

An important feature of type spaces in continuous logic is that, in addition
to the logic topology, they are also equipped with a metric, which, in
general, induces a finer topology. By [6, Proposition 2.6], it can be defined
by

$\partial(p,q)=\sup_{\phi\in F_{1}}|\phi(p)-\phi(q)|,$

where $F_{1}$ is the collection of all $1$-Lipschitz formulas in $F$.

A type $p\in S_{n}(T)$ is _isolated_ if $\tau$\- and $\partial$\- topologies
coincide on some neighborhood of $p$. A model $M$ of a theory $T$ is _atomic_
if all the types realized in $M$ are isolated. And it is _$\aleph_{0}$
-categorical_ if it is a unique Polish metric structure modeling
${\rm{Th}}_{F}(M)$.

The space $\rm{Mod}(L)$ of all Polish metric structures in signature $L$ is
defined as in [2]. Because functions can be easily coded as predicates (see
Section 4 in [2]), we can assume that $L$ is a relational signature. Enumerate
all predicates in $L$ as $P_{0}=d,P_{1},\ldots$, and let $n_{0},n_{1},\ldots$
be their respective arities. Let $\rm{Mod}(L)$ be the set of all
$\xi\in\prod_{i}\mathbb{R}^{\mathbb{N}^{n_{i}}}$ such that there exists a
metric structure $M_{\xi}$ and a tail-dense sequence $(a_{i})$ of elements of
$M$ such that

$\xi(i)(j_{0},\ldots,j_{n_{i}-1})=P^{M}_{i}(a_{j_{0}},\ldots,a_{j_{n_{i}-1}})$

for all $i\in\mathbb{N}$, $(j_{0},\ldots,j_{n_{i}-1})\in\mathbb{N}^{n_{i}}$.
Observe that $M_{\xi}$ can be obtained from $\xi$ by completing the
pseudometric $P_{0}$ on $\mathbb{N}$ (coded by
$\xi(0)\in\mathbb{R}^{\mathbb{N}^{2}}$), extending predicates $P_{i}$ (coded
by $\xi(i)$, $i>0$) to the completion, and taking the quotient with respect to
the pseudometric. In other words, we can think of elements $\xi\in\rm{Mod}(L)$
as of Polish metric structures with a distinguished tail-dense sequence
$(a_{i})$. In particular, tuples in $M_{\xi}$ consisting of elements from this
sequence can be unequivocally referred to as tuples from
$\mathbb{N}^{<\mathbb{N}}$. Slightly abusing notation, we will often identify
$\xi$ and $M_{\xi}$.

Beside the standard product topology on $\rm{Mod}(L)$, one can consider finer
topologies generated by fragments, analogously to topologies generated by
fragments in the setting of classical countable models (see Section 11 in [5]
for details). For a fragment $F$, a basis for the topology $t_{F}$ is given by
sets of the form

$[\phi(\bar{a})<r]=\\{M\in\rm{Mod}(L):\phi^{M}(\bar{a})<r\\},$

where $\phi\in F$, $\bar{a}\in\mathbb{N}^{<\mathbb{N}}$, and $r\in\mathbb{Q}$.
Note that the standard topology can be regarded as the topology generated by
sets $[\phi(\bar{a})<r]$, where $\phi$ is finitary and quantifier-free.

For a theory $T$, the space $\rm{Mod}(T)\subseteq\rm{Mod}(L)$ is the space of
all Polish metric structures modeling $T$. By [6, Lemma 3.5], topologies
$t_{F}$ are Polish on $\rm{Mod}(T)$, provided that $F$ contains all sentences
in $T$. The symbol $\cong_{T}$ denotes the isomorphism relation on
$\rm{Mod}(T)$, and $[M]$ is the isomorphism class of $M\in\rm{Mod}(T)$. We say
that $\cong_{T}$ is potentially $\bm{\Pi}^{0}_{\alpha}$ (where
$\bm{\Pi}^{0}_{\alpha}$ refers to Borel sets of multiplicative rank $\alpha$)
if there is a Polish topology $t$ on $\rm{Mod}(T)$, consisting of Borel sets
in the standard product topology on $\rm{Mod}(L)$, such that
$\cong_{T}\in\bm{\Pi}^{0}_{\alpha}(t\times t)$.

For a metric space $(X,d)$, denote balls in $X$ by

$B^{X}_{r}(a)=\\{b\in X:d(a,b)<r\\},\,B^{X}_{\leq r}(a)=\\{b\in X:d(a,b)\leq
r\\};$

if $X$ is clear from the context, we will write $B_{r}(a)$ and $B_{\leq
r}(a)$. We will also consider balls in $X^{\mathbb{N}}$ and $X^{<\omega}$
around finite tuples, using the extension of $d$ defined above; in particular
$B^{X^{\mathbb{N}}}_{r}(\emptyset)=X^{\mathbb{N}}$ and
$B^{X^{<\omega}}_{r}(\emptyset)=X^{<\omega}$.

For a Polish metric structure $M\in\rm{Mod}(L)$, let

$D(M)=\\{(y_{i})\in M^{\mathbb{N}}:\\{y_{i}\\}\mbox{ is tail-dense in }M\\}.$

$D(M)$ is clearly a $G_{\delta}$ set in $M^{\mathbb{N}}$, and therefore a
Polish space. Denote by $\pi\colon D(M)\to[M]$ the map given by

(1) $P_{i}^{\pi(y)}(\bar{a})=P_{i}^{M}(y(a_{0}),\ldots,y(a_{n_{i}-1}))$

for $y\in D(M)$, $\bar{a}\in\mathbb{N}^{n_{i}}$. It is surjective, and
continuous with respect to topologies generated by fragments. More
importantly, $\pi$ plays the role of the logic action in the context of
countable structures. For $A\subseteq\rm{Mod}(L)$,
$\bar{a}\in\mathbb{N}^{<\mathbb{N}}$, and $u\in\mathbb{Q}^{+}$, define
$A^{*\bar{a},u}$ by

$M\in A^{*\bar{a},u}\Leftrightarrow\forall^{*}y\in
B^{D(M)}_{u}(\bar{a})(\pi(y)\in A),$

and $A^{*}=A^{*\emptyset,0}$; $A^{\Delta\bar{a},u}$ and $A^{\Delta}$ are
defined similarly. The operations $A^{*\bar{a},u}$ are analogs of Vaught
transforms. By [2, Theorem 6.3], which is a continuous counterpart of the
Lopez-Escobar theorem, $[M]$ is Borel for $M\in\rm{Mod}(L)$, and every
isomorphism-invariant Borel $A\subseteq\rm{Mod}(L)$ is of the form
$\rm{Mod}(T)$ for some theory $T$.

##  3\. AE families

Using Vaught transforms, one can characterize isomorphism classes of countable
structures in terms of satisfiability of appropriately chosen formulas. For
example, if $[M]$ is $\bm{\Pi}^{0}_{2}$, there are formulas $\phi_{k,l}$,
$k,l\in\mathbb{N}$, such that $N\in[M]$ iff

$\forall\bar{b}\forall k\exists\bar{c}\supseteq\bar{b}\exists
l(N\models\phi_{k,l}(\bar{c}))$

(see the proof of [5, Theorem 11.5.7] for details). It turns out that this
approach can be generalized to higher Borel complexity, and to the continuous
setting. As it will turn out in the next section, it allows for taking
advantage of type spaces in defining nicely behaving invariants of isomorphism
for classes of locally compact structures.

For a fixed (countable) fragment $F$ in signature $L$, $\alpha<\omega_{1}$,
and a tuple $\bar{x}$ of free variables, an _$\alpha$ -AE family_ $P(\bar{x})$
is defined as follows. An $(-1)$-family $P(\bar{x})$ is a formula
$\phi(\bar{x})$ in $F$. Provided that $\gamma$-AE families have been defined
for $\gamma<\beta$, where $\beta=0$ or $\beta$ is a limit ordinal, a
$\beta$-AE family $P(\bar{x})$ is a collection of $\gamma$-AE families
$p_{k}(\bar{x})$, $k\in\mathbb{N}$, $\gamma<\beta$, a $(\beta+1)$-AE family
$P(\bar{x})$ is a collection of $\gamma$-AE families $p_{k,l}(\bar{x}_{k,l})$,
$\gamma<\beta$, $k,l\in\mathbb{N}$, $\bar{x}\subseteq\bar{x}_{k,l}$, and a
$(\beta+n)$-AE family $P(\bar{x})$, $2\leq n<\omega$, is a collection of
$(\beta+n-2)$-AE families $p_{k,l}(\bar{x}_{k,l})$, $k,l\in\mathbb{N}$,
$\bar{x}\subseteq\bar{x}_{k,l}$. Moreover, every $\alpha$-AE family
$P(\bar{x})=\\{p_{k,l}(\bar{x}_{k,l})\\}$, $\alpha\geq 1$, comes equipped with
a fixed $u_{P}\geq 0$ such that $u_{P}\geq u_{p_{k,l}}$, $k,l\in\mathbb{N}$.

We say that a tuple $\bar{a}$ in $M\in\rm{Mod}(L)$ realizes a $(-1)$-AE family
$P(\bar{x})=\phi(\bar{a})$ if $\phi^{M}(\bar{a})=0$, and $\bar{a}$ realizes a
$\beta$-AE family $P(\bar{x})$, where $\beta=0$ or $\beta$ is a limit ordinal,
if it realizes every $p(\bar{x})\in P(\bar{x})$. Finally, $\bar{a}$ realizes a
$(\beta+n)$-AE family $P(\bar{x})=\\{p_{k,l}(\bar{x}_{k,l})\\}$, $1\leq
n<\omega$, if it holds in $M$ that

$\forall\bar{b}\in B^{M^{<\omega}}_{u_{P}}(\bar{a})\forall v>0\forall
k\exists\bar{c}\in B^{M^{<\omega}}_{v}(\bar{b})\exists l\,(\bar{c}\mbox{
realizes }p_{k,l}(\bar{x}_{k,l})\mbox{ in }M).$

If $\emptyset$ in $M$ realizes $P(\emptyset)$, we say that $M$ models $P$.

######  Remark 3.1.

Note that in order to verify that $\bar{a}$ realizes $P(\bar{x})$, it suffices
to check that the above condition holds for
$\bar{b},\bar{c}\in\mathbb{N}^{<\mathbb{N}}$ with $|\bar{b}|\geq|\bar{a}|$,
$|\bar{c}|\geq|\bar{b}|$, and for all sufficiently small $v>0$.

######  Theorem 3.2.

Let $F$ be fragment in signature $L$, and let $1\leq\alpha<\omega_{1}$.
Suppose that $A\in\bm{\Pi}^{0}_{1+\alpha}(t_{F})$ for some
$A\subseteq\rm{Mod}(L)$. For every $\bar{a}\in\mathbb{N}^{<\mathbb{N}}$, and
$u\in\mathbb{Q}^{+}$, there exists an $\alpha$-AE family $P(\bar{x})$ such
that

$A^{*\bar{a},u}=\\{N\in\rm{Mod}(L):\bar{a}\mbox{ realizes }P(\bar{x})\mbox{ in
}N\\}.$

###### Proof.

We prove the theorem by induction on $\alpha$. Let us consider the base cases
$\alpha=1$, and $\alpha=2$. Fix $A\subseteq\rm{Mod}(L)$ such that
$A\in\bm{\Pi}^{0}_{2}(t_{F})$, $\bar{a}\in\mathbb{N}^{<\mathbb{N}}$,
$u\in\mathbb{Q}^{+}$, and closed sets $A_{k,l}$, $k,l\in\mathbb{N}$, in
$t_{F}$ of the form $[\phi=0]$ such that

$A=\bigcap_{k}\bigcup_{l}A_{k,l}.$

Then

$N\in A^{*\bar{a},u}\Leftrightarrow\forall^{*}y\in
B^{D(N)}_{u}(\bar{a})\forall k\exists l\,(\pi(y)\in A_{k,l})\Leftrightarrow$
$\forall\bar{b}\in B^{N^{<\omega}}_{u}(\bar{a})\forall v>0\forall
k\exists^{*}y\in B^{D(N)}_{v}(\bar{b})\exists l\,(\pi(y)\in
A_{k,l})\Leftrightarrow$ $\forall\bar{b}\in
B^{N^{<\omega}}_{u}(\bar{a})\forall v>0\forall k\exists\bar{c}\in
B^{N^{<\omega}}_{v}(\bar{b})\exists l\exists w>0\forall^{*}y\in
B^{D(N)}_{w}(\bar{c})\,(\pi(\bar{y})\in A_{k,l})\Leftrightarrow$
$\forall\bar{b}\in B^{N^{<\omega}}_{u}(\bar{a})\forall v>0\forall
k\exists\bar{c}\in B^{N^{<\omega}}_{v}(\bar{b})\exists l\exists w>0\,(N\in
A^{*\bar{c},w}_{k,l}).$

Since $A_{k,l}$ are closed, we have that

$N\in A^{*\bar{c},w}_{k,l}\Leftrightarrow\neg\exists^{*}y\in
B^{D(N)}_{w}(\bar{c})\,(\pi(y)\not\in A_{k,l})\Leftrightarrow$ $\neg\exists
y\in B^{D(N)}_{w}(\bar{c})\,(\pi(y)\not\in
A_{k,l})\Leftrightarrow\neg\exists\bar{d}\,(d^{N}(\bar{c},\bar{d})<w\mbox{ and
}\bar{d}\not\in A_{k,l}).$

Moreover, $A_{k,l}$ are of the form $[\phi=0]$, so there are formulas
$\phi_{k,l}(\bar{x}_{k,l})$ in $F$ such that

$N\in A^{*\bar{a},u}\Leftrightarrow\forall\bar{b}\in
B^{N^{<\omega}}_{u}(\bar{a})\forall v>0\forall k\exists\bar{c}\in
B^{N^{<\omega}}_{v}(\bar{b})\exists l\,(\phi^{N}_{k,l}(\bar{c})=0)$

Put $P(\bar{x})=\\{\phi_{k,l}(\bar{x}_{k,l})\\}$, and $u_{P}=u$. It is a
$1$-AE family, and

$N\in A^{*\bar{a},u}\Leftrightarrow\bar{a}\mbox{ realizes }P(\bar{x})\mbox{ in
}N.$

For $\alpha=2$, fix $A\in\bm{\Pi}^{0}_{3}(t_{F})$, a tuple $\bar{a}$, and
closed in $t_{F}$ sets $A_{k,l,m}$ of the form $[\phi=0]$ such that

$A=\bigcap_{k}\bigcup_{l}\bigcap_{m}A_{k,l,m}.$

Then

$N\in A^{*\bar{a},u}\Leftrightarrow\forall^{*}y\in
B^{D(N)}_{u}(\bar{a})g\forall k\exists l\forall m\,(\pi(y)\in
A_{k,l,m})\Leftrightarrow$ $\forall\bar{b}\in
B^{N^{<\omega}}_{u}(\bar{a})\forall v>0\forall k\exists^{*}y\in
B^{D(N)}_{v}(\bar{b})\exists l\forall m\,(\pi(y)\in A_{k,l,m})\Leftrightarrow$
$\forall\bar{b}\in B^{N^{<\omega}}_{u}(\bar{a})\forall v>0\forall
k\exists\bar{c}\in B^{N^{<\omega}}_{v}(\bar{b})\exists w>0\exists
l\forall^{*}y\in B^{D(N)}_{w}(\bar{c})\forall m\,(\pi(y)\in A_{k,l,m}).$

Since $A_{k,l,m}$ are closed, the condition $\forall^{*}y\in
B^{D(N)}_{w}(\bar{c})\forall m\,(\pi(y)\in A_{k,l,m})$ is also closed for
every $w$, $\bar{c}$, $k$, and $l$. Therefore there are formulas
$\phi_{k,l,m}(\bar{x}_{k,l,m})$ in $F$ such that the above is equivalent to

$\forall\bar{b}\in B^{N^{<\omega}}_{u}(\bar{a})\forall v>0\forall
k\exists\bar{c}\in B^{N^{<\omega}}_{v}(\bar{b})\exists l\forall
m\,(\phi^{N}_{k,l,m}(\bar{c})=0).$

In other words, for
$p_{k,l}(\bar{x}_{k,l})=\\{\phi_{k,l,m}(\bar{x}_{k,l}):m\in\mathbb{N}\\}$, and
the $2$-AE family $P(\bar{x})=\\{p_{k,l}(\bar{x}_{k,l})\\}$, $u_{P}=u$, we
have that

$N\in A^{*\bar{a},u}\Leftrightarrow\bar{a}\mbox{ realizes }P(\bar{x})\mbox{ in
}N.$

Suppose $\alpha>2$, and write $\alpha=\beta+n$, where $\beta$ is $0$ or a
limit ordinal, and $n<\omega$. For $n=0$, this is straightforward. For $n=1$
or $n>2$, exactly the same argument as for $\alpha=1$ works, only we use the
inductive assumption to deal with $A^{*\bar{c},w}_{k,l}$. And for $n=2$, we
repeat the argument for $\alpha=2$, again using the inductive assumption. ∎

In particular, since $[M]=[M]^{*}$, we get

######  Corollary 3.3.

Let $F$ be fragment in signature $L$, and let $1\leq\alpha<\omega_{1}$.
Suppose that $[M]\in\bm{\Pi}^{0}_{1+\alpha}(t_{F})$ for some
$M\in\rm{Mod}(L)$. There exists an $\alpha$-AE family $P_{M}$ such that

$[M]=\\{N\in\rm{Mod}(L):N\mbox{ models }P_{M}\\}.$

##  4\. Locally compact structures

AE families are hereditarily countable objects that characterize isomorphism
classes of Polish metric structures. Unfortunately (although unsurprisingly),
it is not always possible to assign them to structures in a definable (i.e.,
Borel) and isomorphism-invariant manner. However, the case of locally compact
structures is simpler. Let us start with basic facts about type spaces of
theories with locally compact models.

For a fragment $F$, $F$-theory $T$, locally compact $M\in\rm{Mod}(T)$,
$n\in\mathbb{N}$, and $n$-tuple $\bar{a}$ in $M$, let

$\Theta_{n}(M)=\\{\rm{tp}_{F}(\bar{b}):\bar{b}\in M^{n}\\},$
$\rho_{M}(\bar{a})=\sup\\{r\in\mathbb{R}:\overline{B^{M^{n}}_{r}(\bar{a})}\text{
is compact}\\},$

or simply $\rho(\bar{a})$, when $M$ is clear from the context.

######  Lemma 4.1 (Lemma 6.2 in [6]).

Let $\Phi\colon(M^{n},d)\to(S_{n}(T),\partial)$ be defined by
$\Phi(\bar{a})=\rm{tp}(\bar{a})$. Then the following hold:

  1. (1)

$\Phi$ is a contraction for the metrics $d$ on $M^{n}$ and $\partial$ on
$S_{n}(T)$.

  2. (2)

If $r<\rho(\bar{a})$, then $\Phi(B_{\leq r}(\bar{a}))=B_{\leq r}(\Phi(a))$. In
particular,
$B_{\leq r}(\rm{tp}(\bar{a}))\subseteq\Theta_{n}(M)$, $B_{\leq
r}(\rm{tp}(\bar{a}))$ is $\partial$-compact, and $\tau_{n}$\- and
$\partial$-topology coincide on $B_{\leq r}(\rm{tp}(\bar{a}))$.

  3. (3)

If $r\leq\rho(\bar{a})$, then $\Phi(B_{r}(\bar{a}))=B_{r}(\Phi(\bar{a}))$. In
particular, $\Phi$ is an open mapping.

  4. (4)

The set $\Theta_{n}(M)$ is open in $(S_{n}(T),\partial)$ and the space
$(\Theta_{n}(M),\partial)$ is locally compact and separable.

For each topology $\tau_{n}$ fix a countable basis
$\mathcal{U}_{n}=\\{U_{l,n}\\}$ containing $\emptyset$ and the whole space,
and put $\mathcal{U}=\bigcup_{n}\mathcal{U}_{n}$. For $U\in\mathcal{U}_{n}$,
$\epsilon>0$, and $n$-tuple $\bar{a}$ in $M$, we say that $(U,\epsilon)$ is
_$\bar{a}$ -good_ in $M$ if

  * •

$\rm{tp}(\bar{a})\in U$,

  * •

$2\epsilon<\rho(\bar{a})$,

  * •

there is $\delta>0$ such that $U\cap B_{2\epsilon}(\rm{tp}(\bar{a}))\subseteq
B_{\epsilon-\delta}(\rm{tp}(\bar{a}))$.

######  Remark 4.2.

The following observations easily follow from the fact that $\partial$\- and
$\tau$\- topologies coincide on compact subsets of $(S_{n}(T),\partial)$.

  1. (1)

For every $\delta>0$ there exist $U\in\mathcal{U}$ and $0<\epsilon<\delta$
such that $(U,\epsilon)$ is $\bar{a}$-good,

  2. (2)

if $(U,\epsilon)$ is $\bar{a}$-good, then

$\overline{B_{\epsilon}(\rm{tp}(\bar{a}))\cap
U}^{\tau}\subseteq\Theta_{|\bar{a}|}(M),$

  3. (3)

if $(U,\epsilon)$ is $\bar{a}$-good, there is $\delta>0$ such that
$d(\bar{a},\bar{a}^{\prime})<\delta$ implies that $(U,\epsilon)$ is
$\bar{a}^{\prime}$-good, and

$U\cap B_{\epsilon}(\rm{tp}(\bar{a}))=U\cap
B_{\epsilon}(\rm{tp}(\bar{a}^{\prime})).$

Now, for $\bar{a}\in\mathbb{N}^{<\mathbb{N}}$, $U\in\mathcal{U}_{n}$, and
$\epsilon\in\mathbb{Q}^{+}$, define

$T^{0}_{U,\epsilon}(\bar{a})=\overline{B_{\epsilon}(\rm{tp}(\bar{a}))\cap
U}^{\tau},$

if $(U,\epsilon)$ is $\bar{a}$-good,

$T^{0}_{U,\epsilon}(\bar{a})=\emptyset,$

otherwise, and

(2)
$T^{\alpha}_{U,\epsilon}(\bar{a})=\\{T^{\beta}_{U^{\prime},\epsilon^{\prime}}(\bar{a}^{\prime}):\beta<\alpha,|\bar{a}^{\prime}|\geq|\bar{a}|,U^{\prime}\in\mathcal{U}_{|\bar{a}^{\prime}|},U^{\prime}\upharpoonright|\bar{a}|\subseteq
U,\epsilon^{\prime}\leq\epsilon\\}$

for $\alpha>0$. Also, for $u>0$, put

(3)
$T^{\alpha}_{u}(\bar{a})=\\{T^{\beta}_{U,v}(\bar{b}):\beta<\alpha,\bar{b}\in
B^{M^{<\omega}}_{u}(\bar{a}),|\bar{b}|\geq|\bar{a}|,U\in\mathcal{U}_{|\bar{b}|},v>0\\},$

$T^{\alpha}(M)=T^{\alpha}_{1}(\emptyset).$

As tuples in the definition of $T^{\alpha}_{U,\epsilon}(\bar{a})$ range over
$\mathbb{N}^{<\mathbb{N}}$, $U$ range over a countable family, and
$\epsilon\in\mathbb{Q}^{+}$, $T^{1}(M)$ is a countable family of $\tau$-closed
sets, $T^{2}(M)$ is a countable family of countable families of $\tau$-closed
sets, etc. Moreover, using Remark 4.2(3), it is straightforward to observe
that

######  Remark 4.3.

$M\cong N$ implies that $T^{\alpha}(M)=T^{\alpha}(N)$ for all $\alpha\geq 1$.

######  Proposition 4.4.

Let $F$ be a fragment, and let $T$ be an $F$-theory. Suppose that $M,N\in
Mod(T)$ are locally compact, and
$T^{\alpha}_{u}(\bar{a})=T^{\alpha}_{u^{\prime}}(\bar{a}^{\prime})$ for some
tuples $\bar{a}$, $\bar{a}^{\prime}$ in $M$, $N$, respectively. Then every
$\alpha$-AE family $P(\bar{x})$ with $u_{P}\leq u$ realized by
$\bar{a}^{\prime}$, is also realized by $\bar{a}$.

###### Proof.

Suppose that $T^{1}_{u}(\bar{a})=T^{1}_{u^{\prime}}(\bar{a}^{\prime})$, and
fix a $1$-AE family $P(\bar{x})=\\{p_{k,l}(x_{k,l})\\}$ realized by
$\bar{a}^{\prime}$, and with $u_{P}\leq u$. Fix $\bar{b}\in
B^{M^{<\omega}}_{u_{P}}(\bar{a})$, $v>0$, and $k\in\mathbb{N}$. By Remarks 3.1
and 4.2(1), we can assume that $v<\rho(\bar{b})$, and there is
$U\in\mathcal{U}$ such that $(U,v/2)$ is $\bar{b}$-good. Find
$\bar{b}^{\prime}\in B^{N^{<\omega}}_{u_{P}}(\bar{a}^{\prime})$,
$U^{\prime}\in\mathcal{U}$, and $v^{\prime}>0$ such that
$T^{0}_{U,v/2}(\bar{b})=T^{0}_{U^{\prime},v^{\prime}}(\bar{b}^{\prime})$. As
$\bar{a}^{\prime}$ realizes $P(\bar{x})$, there is $\bar{c}^{\prime}\in
B^{N^{<\omega}}_{v/2}(\bar{b}^{\prime})$, and $l$ such that
$p_{k,l}^{N}(\bar{c}^{\prime})=0$. But then

$\inf_{\bar{x}}[(d(\bar{b},\bar{x})\dotdiv v/2)\vee
p_{k,l}(\bar{x})]\in\rm{tp}(\bar{b}^{\prime}),$

and, by Remark 4.2(2), there is $\bar{d}\in B^{N}_{v/2}(\bar{b})$ with
$\rm{tp}(\bar{d})=\rm{tp}(\bar{b}^{\prime})$. By the compactness of
$B^{M}_{v/2}(\bar{d})$, there is $\bar{c}\in B^{M}_{v/2}(\bar{d})$ such that
$p_{k,l}^{M}(\bar{c})=0$. Clearly, $\bar{c}\in B^{M^{<\omega}}_{v}(\bar{b})$.
As $\bar{b}$, $v$ and $k$ were arbitrary, this shows that $\bar{a}$ realizes
$P(\bar{x})$.

Suppose now that $T^{2}_{u}(\bar{a})=T^{2}_{u^{\prime}}(\bar{a}^{\prime})$,
and let $P(\bar{x})$ be a $2$-AE family realized by $\bar{a}^{\prime}$, and
with $u_{P}\leq u$. Fix $\bar{b}\in B^{M^{<\omega}}_{u_{P}}(\bar{a})$, $v>0$,
$k\in\mathbb{N}$, and $U\in\mathcal{U}$ such that $(U,v/2)$ is $\bar{b}$-good.
Fix $\bar{b}^{\prime}\in B^{N^{<\omega}}_{u_{P}}(\bar{a}^{\prime})$,
$U^{\prime}\in\mathcal{U}$ and $v^{\prime}>0$ such that
$T^{1}_{U,v/2}(\bar{b})=T^{1}_{U^{\prime},v^{\prime}}(\bar{b}^{\prime})$. As
$\bar{a}^{\prime}$ realizes $P(\bar{x})$, there is $l$, and
$\bar{c}^{\prime}\in B^{N^{<\omega}}_{v/2}(\bar{b}^{\prime})$ such that
$\rm{tp}(\bar{c}^{\prime})\upharpoonright|\bar{b}^{\prime}|\in U^{\prime}$,
and $\bar{c}^{\prime}$ realizes $p_{k,l}(\bar{x}_{k,l})$. Fix
$V,V^{\prime}\in\mathcal{U}$, $0<w,w^{\prime}\leq v/2$, and $\bar{d}\in
B^{M^{<\omega}}_{v/2}(\bar{b})$ such that $(V^{\prime},w^{\prime})$ is
$\bar{c}^{\prime}$-good, and
$T^{0}_{V,w}(\bar{d})=T^{0}_{V^{\prime},w^{\prime}}(\bar{c}^{\prime})$. Then
there is $\bar{c}\in B^{M^{<\omega}}_{w}(\bar{d})$ with
$\rm{tp}(\bar{c})=\rm{tp}(\bar{c^{\prime}})$, i.e., $\bar{c}\in
B^{M^{<\omega}}_{v}(\bar{b})$, and $\bar{c}$ realizes
$p_{k,l}(\bar{x}_{k,l})$.

For $\alpha>1$, this is an easy induction. ∎

Proposition 4.4 combined with Corollary 3.3 immediately gives:

######  Theorem 4.5.

Let $F$ be a fragment, and let $T$ be an $F$-theory all of whose models are
locally compact. Suppose that $[M]\in\Pi^{0}_{1+\alpha}(t_{F})$, $\alpha\geq
1$, for some $M\in\rm{Mod}(T)$. Then

$[M]=\\{N\in\rm{Mod}(T):T^{\alpha}(N)=T^{\alpha}(M)\\}.$

######  Theorem 4.6.

Let $F$ be a fragment, and let $T$ be an $F$-theory all of whose models are
locally compact. Then $\cong_{T}$ is classifiable by countable structures.

###### Proof.

First, for a given $M\in\rm{Mod}(T)$, we construct a countable structure
$C_{M}$, essentially, as in the proof of [7][Lemma 6.30]. Its universe
consists of elements $x$ of the form

$x=(\overline{B_{\epsilon}(\rm{tp}(\bar{a}))\cap
U}^{\tau},|\bar{a}|,U,\epsilon),$

where $\bar{a}\in\mathbb{N}^{<\mathbb{N}}$, $U\in\mathcal{U}_{|\bar{a}|}$,
$\epsilon\in\mathbb{Q}^{+}$, and $(U,\epsilon)$ is $\bar{a}$-good. The
relevant information carried by these objects is recorded with an aid of the
relations $O_{l}$, $R_{k,l,\delta}$, $k,l\in\mathbb{N}$,
$\delta\in\mathbb{Q}^{+}$, and $E$, defined, for
$x=(\overline{B_{\epsilon}(\rm{tp}(\bar{a}))\cap
U}^{\tau},|\bar{a}|,U,\epsilon)$,
$x^{\prime}=(\overline{B_{\epsilon^{\prime}}(\rm{tp}(\bar{a}^{\prime}))\cap
U^{\prime}}^{\tau},|\bar{a}^{\prime}|,U^{\prime},\epsilon^{\prime})$, as
follows:

  * •

$O_{l}(x)$ iff
$U_{l,|\bar{a}|}\cap\overline{B_{\epsilon}(\rm{tp}(\bar{a}))\cap
U}^{\tau}=\emptyset$,

  * •

$R_{k,l,\delta}(x)$ iff $k=|\bar{a}|$, $U=U_{l,k}$, $\delta=\epsilon$,

  * •

$xEx^{\prime}$ iff $|\bar{a}^{\prime}|\geq|\bar{a}|$,
$U^{\prime}\upharpoonright|\bar{a}|\subseteq U$,
$\epsilon^{\prime}\leq\epsilon$.

By Remark 4.2(3), $M\cong N$ implies that $C_{M}=C_{N}$. On the other hand, as
the relations $O_{l}$ record complements of sets
$\overline{B_{\epsilon}(\rm{tp}(\bar{a}))\cap U}^{\tau}$ in
$S_{|\bar{a}|}(T)$, we have that

$\pi((\overline{B_{\epsilon}(\rm{tp}(\bar{a}))\cap
U}^{\tau},|\bar{a}|,U,\epsilon))=(\overline{B_{\epsilon}(\rm{tp}(\bar{a}))\cap
U}^{\tau},|\bar{a}|,U,\epsilon)$

for any isomorphim $\pi:C_{M}\rightarrow C_{N}$. It obviously follows that
$T^{0}_{U,\epsilon}(\bar{a})=T^{0}_{U,\epsilon}(\bar{a^{\prime}})$, if
$\pi(x)=x^{\prime}$. And $E$ warranties that
$T^{\alpha}_{U,\epsilon}(\bar{a})=T^{\alpha}_{U,\epsilon}(\bar{a^{\prime}})$
for $\alpha>0$. In particular, $T^{\alpha}(M)=T^{\alpha}(N)$ for
$\alpha<\omega_{1}$.

It is not hard to construct a Borel mapping $\rm{Mod}(T)\rightarrow
2^{\mathbb{N}}$, $M\mapsto D_{M}$, so that $D_{M}$ codes a countable model
isomorphic to $C_{M}$. First, by [6, Lemma 6.4], the mappings

$\rm{Mod}(T)\times\mathbb{N}^{n}\rightarrow\mathbb{R},\
(M,\bar{a})\mapsto\rho_{M}(\bar{a}),$
$\rm{Mod}(T)\times\mathbb{N}^{n}\times\mathbb{Q}^{+}\rightarrow\mathcal{K}(S_{n}(T)),(M,\bar{a},r)\mapsto
B_{\leq r}(\rm{tp}(\bar{a})),$

where $\mathcal{K}(X)$ is the standard Borel space of closed subsets of $X$,
are Borel. Therefore the relation “$(U,\epsilon)$ is $\bar{a}$-good in $M$”,
regarded as a subset of
$\rm{Mod}(T)\times\mathbb{N}^{<\mathbb{N}}\times\mathcal{U}\times\mathbb{Q}^{+}$,
is also Borel. This gives rise to a Borel enumeration
$e:\mathbb{N}\rightarrow(\bigsqcup_{n}\mathcal{K}(S_{n}(T)))\times\mathcal{U}\times\mathbb{Q}^{+}$
of the universe of $C_{M}$. Using this $e$, we can easily construct the
required Borel mapping $M\mapsto D_{M}$.

By [2, Corollary 5.6], for every $M\in\rm{Mod}(T)$, the isomorphism class
$[M]$ is Borel, i.e., $[M]\in\bm{\Pi}^{0}_{\alpha}(t_{F})$ for some
$\alpha<\omega_{1}$. Hence, Theorem 4.5 implies that $M\cong N$ iff
$D_{M}\cong D_{N}$. ∎

The next result confirms a conjecture stated by Gao and Kechris in [4]
(Hjorth, see [4], announced a positive answer for its weaker form, with a
$\Delta^{1}_{2}$-reduction).

######  Theorem 4.7.

Isometry of locally compact Polish metric spaces is Borel reducible to graph
isomorphism.

###### Proof.

Every locally compact Polish metric space $K$ can be coded as
$M_{K}\in\rm{Mod}(L)$ with the trivial signature $L$, and metric bounded by
$1$. Simply, pick a countable tail-dense subset of $K$, and replace the
original metric $d$ with the metric $1/(1+d)$ which does not change the
isometry relation. Actually, for
$\mathcal{LC}\subseteq\mathcal{K}(\mathbb{U})$ denoting the standard Borel
space of all locally compact Polish metric spaces, regarded as subsets of the
Urysohn space $\mathbb{U}$, the coding $\mathcal{LC}\rightarrow\rm{Mod}(L)$,
$K\mapsto M_{K}$, can be defined in a Borel way: the Kuratowski–Ryll-
Nardzewski theorem yields a Borel function
$f:\mathcal{K}(\mathbb{U})\rightarrow\mathbb{U}^{\mathbb{N}}$ such that
$f(K)=(k_{n})$ is a tail-dense subset of $K$. As the signature $L$ is trivial,
the isomorphism relation $\cong$ is just the isometry relation. Moreover, the
property of being locally compact can be expressed as a sentence in
$\mathcal{L}_{\omega_{1}\omega}(L)$, so the set of all possible codes of
locally compact Polish metric spaces is of the form $\rm{Mod}(T)$. By Theorem
4.6 and [5, Theorem 13.1.2], the isometry relation is Borel reducible to graph
isomorphism. ∎

### Borel isomorphism relations

As a matter of fact, a more detailed analysis can be performed in case the
isomorphism relation is Borel. Let $\mathcal{P}^{0}(\mathbb{N})=\mathbb{N}$,
and, for $\alpha<\omega_{1}$, let $\mathcal{P}^{\alpha}(\mathbb{N})=$ all
countable subsets of $\mathcal{P}^{<\alpha}(\mathbb{N})\cup\mathbb{N}$, where
$\mathcal{P}^{<\alpha}(\mathbb{N})=\bigcup_{\beta<\alpha}\mathcal{P}^{\beta}(\mathbb{N})$.
Thus, $\mathcal{P}^{1}(\mathbb{N})$ (the reals) consists of all subsets of
$\mathbb{N}$, $\mathcal{P}^{2}(\mathbb{N})$ of all countable sets of reals,
etc. We denote the equality relation on $\mathcal{P}^{\alpha}(\mathbb{N})$ by
$=_{\alpha}$. In [9], it is explained how elements of
$\mathcal{P}^{\alpha}(\mathbb{N})$ can be coded as countable models so that
$=_{\alpha}$ becomes an isomorphism relation of Borel class
$\bm{\Pi}^{0}_{\alpha+1}$.

For a fragment $F$ in signature $L$, the rank ${\rm{rk}}_{F}(\phi)$ is defined
by ${\rm{rk}}_{F}(\phi)=0$ for $\phi\in F$,
${\rm{rk}}_{F}(\sup_{x}\phi)={\rm{rk}}_{F}(\inf_{x}\phi)={\rm{rk}}_{F}(r\phi)={\rm{rk}}_{F}(\phi)$,
${\rm{rk}}_{F}(\phi_{1}\vee\phi_{2})={\rm{rk}}_{F}(\phi_{1}+\phi_{2})=\max\\{{\rm{rk}}_{F}(\phi_{1}),{\rm{rk}}_{F}(\phi_{2})\\}$,
and $\psi$ ${\rm{rk}}_{F}(\phi)=\sup\\{{\rm{rk}}_{F}(\phi_{i})+1\\}$ if $\phi$
is an infinite supremum $\bigvee_{i}\phi_{i}$ or infinite infimum
$\bigwedge_{i}\phi_{i}$. We also put
${\rm{rk}}_{F}(X)=\sup\\{{\rm{rk}}_{F}(\phi):\phi\in X\\}$ for a collection of
formulas $X$. Note that it is straightforward to code a formula $\phi$ as an
element of $\mathcal{P}^{\alpha}(\mathbb{N})$ if
${\rm{rk}}_{F}(\phi)\leq\alpha$.

######  Theorem 4.8.

Let $L$ be a signature, let $t$ be a Polish topology on $\rm{Mod}(L)$
consisting of Borel subsets of the standard topology, and let
$\alpha<\omega_{1}$. There exists a fragment $F$ such that
$A^{*},A^{*\bar{a},1/k}\in\bm{\Pi}^{0}_{\alpha}(t_{F})$ for every
$A\in\bm{\Pi}^{0}_{\alpha}(t)$, $\bar{a}\in\mathbb{N}^{<\mathbb{N}}$, and
$k>0$.

###### Proof.

We prove by induction on $\alpha$ that if $A\in\bm{\Sigma}^{0}_{\alpha}(t)$,
then there is a fragment $F$ such that $A^{\Delta},A^{\Delta
u,k}\in\bm{\Sigma}^{0}_{\alpha}(t_{F})$. For $\alpha=2$, fix a countable basis
$\mathcal{A}$ for the topology $t$. Without loss of generality, we can assume
that it contains the standard basis on $\rm{Mod}(L)$, and is closed under
finite intersections. It is straightforward to observe that for every
$M\in\rm{Mod}(L)$, $A\subseteq\rm{Mod}(L)$,
$\bar{a}\in\mathbb{N}^{<\mathbb{N}}$, and $k>0$

$\forall^{*}y\in B^{D(M)}_{1/k}(\bar{a})(\pi(y)\in
A)\Leftrightarrow\mbox{inf}^{*}_{y\in D(M)}(\chi_{A}(\pi(y))\vee
kd(y,\bar{a}))=1.$

By [2, Theorem 6.3], there exists a formula $\phi_{A,k}$ such that

$\forall^{*}y\in B^{D(M)}_{1/k}(\bar{a})(\pi(y)\in
A)\Leftrightarrow\phi_{A,k}^{M}(\bar{a})=1.$

Let $F$ be the fragment generated by such formulas for $A\subseteq\rm{Mod}(L)$
whose complement is in $\mathcal{A}$. Fix $A\in\bm{\Sigma}^{0}_{2}(t)$, and
$A_{n,m}$, $n,m\in\mathbb{N}$, whose complement is in $\mathcal{A}$ and

$A=\bigcup_{n}\bigcap_{m}A_{n,m}.$

Then

$M\in A^{\Delta\bar{a},1/k}\Leftrightarrow\exists^{*}y\in
B^{D(M)}_{1/k}(\bar{a})\,\exists n\forall m\,(\pi(y)\in
A_{n,m})\Leftrightarrow$ $\exists n\exists^{*}y\in
B^{D(M)}_{1/k}(\bar{a})\forall m\,(\pi(y)\in A_{n,m})\Leftrightarrow$ $\exists
n\exists\bar{a}^{\prime}\in\mathbb{N}^{<\mathbb{N}}\exists
k^{\prime}\forall^{*}y\in B^{D(M)}_{1/k^{\prime}}(\bar{a}^{\prime})\forall
m\,(d(\bar{a}^{\prime},\bar{a})\leq 1/k\mbox{ and }\pi(y)\in
A_{n,m})\Leftrightarrow$ $\exists
n\exists\bar{a}^{\prime}\in\mathbb{N}^{<\mathbb{N}}\exists k^{\prime}\forall
m\forall^{*}y\in
B^{D(M)}_{1/k^{\prime}}(\bar{a}^{\prime})\,(d(\bar{a}^{\prime},\bar{a})\leq
1/k\mbox{ and }\pi(y)\in A_{n,m}),$

so there exist $B_{\bar{a}^{\prime},k^{\prime},n,m}\in\mathcal{A}$ such that

$A^{\Delta\bar{a},1/k}=\bigcup_{n}\bigcup_{\bar{a}^{\prime}}\bigcup_{k^{\prime}}\bigcap_{m}\bigcap_{\epsilon>0}[\phi_{B_{\bar{a}^{\prime},k^{\prime},n,m},k}(\bar{a})\leq\epsilon],$

i.e., $A\in\bm{\Sigma}^{0}_{2}(t_{F})$. For $A^{\Delta}$, the argument is
analogous.

Suppose now that the lemma holds for all $\beta<\alpha$. Fix
$A\in\bm{\Sigma}^{0}_{\alpha}(t)$,
$A_{n,m}\in\bm{\Sigma}^{0}_{\beta_{n,m}}(t)$, $n,m\in\mathbb{N}$,
$\beta_{n,m}<\alpha$, such that

$A=\bigcup_{n}\bigcap_{m}A_{n,m}.$

Then

$M\in A^{\Delta\bar{a},1/k}\Leftrightarrow\exists^{*}y\in
B^{D(M)}_{1/k}(\bar{a})\,\exists n\forall m\,(\pi(y)\in
A_{n,m})\Leftrightarrow$ $\exists n\exists^{*}y\in
B^{D(M)}_{1/k}(\bar{a})\forall m\,(\pi(y)\in A_{n,m})\Leftrightarrow$ $\exists
n\exists\bar{a}^{\prime}\in\mathbb{N}^{<\mathbb{N}}\exists
k^{\prime}\forall^{*}y\in B^{D(M)}_{1/k^{\prime}}(\bar{a}^{\prime})\forall
m\,(\pi(y)\in A_{n,m})\Leftrightarrow$ $\exists
n\exists\bar{a}^{\prime}\in\mathbb{N}^{<\mathbb{N}}\exists k^{\prime}\forall
m\forall^{*}y\in B^{D(M)}_{1/k^{\prime}}(\bar{a}^{\prime})\,(\pi(y)\in
A_{n,m})\Leftrightarrow$ $\exists
n\exists\bar{a}^{\prime}\in\mathbb{N}^{<\mathbb{N}}\exists k^{\prime}\forall
m\forall\bar{a}^{\prime\prime}\in\mathbb{N}^{<\mathbb{N}}\forall
k^{\prime\prime}\exists^{*}y\in
B^{D(M)}_{1/k^{\prime\prime}}(\bar{a}^{\prime\prime})\big{(}d(\bar{a},\bar{a}^{\prime})<1/k\mbox{
and }$ $(d(\bar{a}^{\prime},\bar{a}^{\prime\prime})\geq 1/k\mbox{ or
}\pi(y)\in A_{n,m})\big{)}\Leftrightarrow$ $\exists
n\exists\bar{a}^{\prime}\in\mathbb{N}^{<\mathbb{N}}\exists k^{\prime}\forall
m\forall\bar{a}^{\prime\prime}\in\mathbb{N}^{<\mathbb{N}}\forall
k^{\prime\prime}(M\in
B^{\Delta\bar{a}^{\prime},k^{\prime}}_{\bar{a},\bar{a}^{\prime},k^{\prime},n,m}),$

where
$B_{\bar{a},\bar{a}^{\prime},k^{\prime},n,m}\in\bm{\Sigma}^{0}_{\beta_{n,m}}(t)$.
By the inductive hypothesis, there are fragments
$F_{\bar{a}^{\prime},k^{\prime}}$ such that
$B^{\Delta\bar{a}^{\prime},k^{\prime}}_{\bar{a},\bar{a}^{\prime},k^{\prime},n,m}\in\bm{\Sigma}^{0}_{\alpha}(t_{F_{\bar{a}^{\prime},k^{\prime}}})$.
Therefore $A^{\Delta u,k}\in\bm{\Sigma}^{0}_{\alpha}(t_{F})$, where $F$ is the
fragment generated by all $F_{\bar{a}^{\prime},k^{\prime}}$.

∎

Since $A^{*}=A$, if $A=[M]$, the above gives the following:

######  Corollary 4.9.

Let $L$ be a signature, and let $T$ be a theory such that $\cong_{T}$ is
potentially $\bm{\Pi}^{0}_{\alpha}$. There exists a fragment $F$ such that
$[M]\in\bm{\Pi}^{0}_{\alpha}(t_{F})$ for every $M\in\rm{Mod}(T)$.

The following fact is due to Todor Tsankov.

######  Proposition 4.10.

Let $L$ be a signature. For every fragment $F$, there exists a fragment
$F^{\prime}\supseteq F$ such that ${\rm{Th}}_{F^{\prime}}(M)$ is
$\aleph_{0}$-categorical for every $F$-atomic model $M\in\rm{Mod}(L)$.

###### Proof.

By the uniqueness of atomic models, it suffices to find an
$\mathcal{L}_{\omega_{1}\omega}(L)$ sentence that expresses that the model is
$F$-atomic. We claim that the following works:

(4) $\bigvee_{n}\sup_{z=(z_{1},\ldots,z_{n})}\bigwedge_{\psi\in
F_{1}}\sup_{x}\big{(}(1\dotdiv\psi(x))\wedge\bigvee_{\phi\in
F_{1}}|\phi(x)-\phi(z)|\big{)}=0.$

We will check that (4) holds in a structure $M$ iff for every $n$ and every
$\bar{c}\in M^{n}$, $\rm{tp}(\bar{c})$ is isolated, i.e., by [2, Lemma 7.4],
that for every $\delta>0$, there exists $\psi\in F$ such that
$[\psi<1]\subseteq B_{\delta}(\rm{tp}(\bar{c}))$ (calculated in
$S_{n}({\rm{Th}}_{F}(M))$). Put $T={\rm{Th}}_{F}(M)$. The “if” direction is
clear; we check the converse.

Suppose (4) holds in $M$, and fix $n\in\mathbb{N}$, $\bar{c}\in M^{n}$ and
$\delta<1/2$. Let $\psi$ be such that the value of the remaining formula is
less than $\delta$. We will show that $[\psi<1/2]\subseteq
B_{\delta}(\rm{tp}(\bar{c}))$, i.e., for all $q\in S_{n}(T)$

(5) $\psi(q)<1/2\mbox{ implies }\partial(q,\rm{tp}(\bar{c}))\leq\delta.$

As the set of $q\in S_{n}(T)$ that satisfy (5) is $\tau$-closed and the set of
types realized in $M$ is $\tau$-dense, it suffices to check (5) for all
$q\in\Theta_{n}(M)$. Let $\bar{a}\in M^{n}$, $q=\rm{tp}(\bar{a})$ and suppose
that $\psi^{M}(\bar{a})<1/2$. Then

$\partial(\rm{tp}(\bar{a}),\rm{tp}(\bar{c}))=\sup_{\phi\in
F_{1}}|\phi(\bar{a})-\phi(\bar{c})|\leq\delta,$

which finishes the proof. ∎

######  Lemma 4.11.

Let $F$ be a fragment, and let $T$ be an $F$-theory all of whose models are
locally compact. Suppose that $M\in\bm{\Pi}^{0}_{\alpha+2}(t_{F})$ for some
$M\in\rm{Mod}(T)$, $\alpha\geq 1$. There is a fragment $F_{M}\supseteq F$ such
that $[M]\in\bm{\Pi}^{0}_{2}(t_{F_{M}})$, and ${\rm{rk}}_{F}(F_{M})=\alpha$.

###### Proof.

Assume that $\alpha<\omega$.

Case 1: $\alpha$ is even. Let $P_{M}$ be the $(\alpha-1)$-AE family as in
Corollary 3.3. We will find a fragment $F_{0}$ with ${\rm{rk}}_{F}(F_{1})=2$,
and an $(\alpha-3)$-AE family $P_{0}$ in $F_{0}$ such that $N\in\rm{Mod}(T)$
models $P_{0}$ iff $N$ models $P_{M}$.

Fix a tuple $\bar{a}\in\mathbb{N}^{<\mathbb{N}}$ in $M$, and
$u\in\mathbb{Q}^{+}$. For $\bar{b}\in B_{u}(\bar{a})$,
$\bar{b}\in\mathbb{N}^{<\mathbb{N}}$, $\epsilon\in\mathbb{Q}^{+}$, fix
$q_{\bar{b},\epsilon}(\bar{y})\in B_{\epsilon}(\rm{tp}(\bar{b}))$, let
$L_{\bar{b},\epsilon}$ be the set of all $1$-Lipschitz formulas $\phi$ in $F$
such that $\phi(q_{\bar{b},\epsilon})=0$, and let

$\phi_{\bar{b},\epsilon}=\bigvee L_{\bar{b},\epsilon}.$

As $\phi\in L_{\bar{b},\epsilon}$ are $1$-Lipschitz, each
$\phi_{\bar{b},\epsilon}$ is a $1$-Lipschitz formula in
$\mathcal{L}_{\omega_{1}\omega}$, and a tuple $\bar{b}^{\prime}$ in
$N\in\rm{Mod}(T)$ realizes $q_{\bar{b},\epsilon}(\bar{y})$ iff
$\phi_{\bar{b},\epsilon}^{N}(\bar{b}^{\prime})=0$. Define $1$-Lipschitz
formulas

$\psi^{1}_{\bar{a},u}(\bar{x})=\sup_{\bar{y}}[(u\dotdiv
d(\bar{x},\bar{y}))\wedge\bigwedge_{\bar{b},\epsilon}(\phi_{\bar{b},\epsilon}(\bar{y})+\epsilon)],$
$\psi^{2}_{\bar{a},u}(\bar{x})=\bigvee_{\bar{b},\epsilon}\inf_{\bar{y}}[(d(\bar{x},\bar{y})\dotdiv
u)\vee(\phi_{\bar{b},\epsilon}(\bar{y})+\epsilon)],$
$\psi_{\bar{a},u}=\psi^{1}_{\bar{a},u}\vee\psi^{2}_{\bar{a},u}.$

Fix $N\in\rm{Mod}(T)$, and tuple $\bar{a}^{\prime}$ in $N$. Clearly, if
$T^{1}_{u}(\bar{a})=T^{1}_{u}(\bar{a}^{\prime})$, then
$\psi^{N}_{\bar{a},u}(\bar{a}^{\prime})=0$. On the other hand, if
$(\psi^{1}_{\bar{a},u})^{N}(\bar{a}^{\prime})=0$, then for every
$\bar{b}^{\prime}\in B_{u}(\bar{a}^{\prime})$, and $\epsilon>0$, there is
$\bar{b}$ such that $\phi_{\bar{b},\epsilon}^{N}(\bar{b}^{\prime})<\epsilon$.
And if $(\psi^{2}_{\bar{a},u})^{N}(\bar{a}^{\prime})=0$, then for every
$\bar{b}$, and $\epsilon>0$, there is $\bar{b}^{\prime}\in
B_{u}(\bar{a}^{\prime})$ such that
$\phi_{\bar{b},\epsilon}^{N}(\bar{b}^{\prime})<\epsilon$. Moreover,

$\partial(\rm{tp}^{N}(\bar{b}^{\prime}),q_{\bar{b},\epsilon})<\epsilon,$

hence

$\partial(\rm{tp}^{N}(\bar{b}^{\prime}),\rm{tp}^{M}(\bar{b}))<2\epsilon.$

By local compactness of $N$, it follows that
$T^{1}_{u}(\bar{a})=T^{1}_{u}(\bar{a}^{\prime})$. Thus,

$T^{1}_{u}(\bar{a})=T^{1}_{u}(\bar{a}^{\prime})\mbox{ iff
}\psi^{N}_{\bar{a},u}(\bar{a}^{\prime})=0$

for every tuple $\bar{a}^{\prime}$ in $N\in\rm{Mod}(T)$.

Let $F_{0}$ be the fragment generated by $F$ and $\psi_{\bar{a},u}(\bar{x})$,
$\bar{a}\in\mathbb{N}^{<\mathbb{N}}$, $u\in\mathbb{Q}^{+}$. Fix a bijection
$\langle\cdot,\cdot\rangle:\mathbb{N}\times\mathbb{Q}^{+}\rightarrow\mathbb{N}$.
We construct an $(\alpha-3)$-family $P_{0}(\bar{x})$, by replacing every
$3$-AE family $Q(\bar{x})=\\{q_{k,l}(\bar{x}_{k,l})\\}$ appearing in
$P_{M}(\bar{x})$ with a $1$-AE family
$Q^{\prime}(\bar{x})=\\{q^{\prime}_{\langle k,v\rangle,l}(\bar{x}_{\langle
k,v\rangle,l})\\}$, where, for any fixed $k$, and $v\in\mathbb{Q}^{+}$,
$\\{q^{\prime}_{\langle k,v\rangle,l}\\}$ enumerates all $\psi_{\bar{c},v}$
that come from $\bar{c}$ in $M$ and $v>0$ witnessing realizations of
$Q(\bar{x})$. Obviously, $M$ models $P_{0}$. And if $N\in\rm{Mod}(T)$ models
$P_{M}$, it is isomorphic with $M$, hence models $P_{0}$. On the other hand,
if $\bar{c}^{\prime}$ realizes some $q^{\prime}_{\langle
k,v\rangle,l}(\bar{x}_{\langle k,v\rangle,l})$, there is $\bar{c}$ in $M$
witnessing a realization of $Q(\bar{x})$, and such that
$T^{1}_{v}(\bar{c})=T^{1}_{v}(\bar{c}^{\prime})$. By Proposition 4.4,
$\bar{c}^{\prime}$ realizes some $q_{k,l^{\prime}}(\bar{x})$. And
$[M]\in\bm{\Pi}^{0}_{\alpha-2}(t_{F_{0}})$, since $[M]$ is characterized by an
$(\alpha-3)$-family. Finally, in order to get the required $F_{M}$, we iterate
the above construction sufficiently many times.

Case 2: $\alpha$ is odd. Consider $F_{1}$ generated by $F$ and formulas
$\phi_{\bar{c},\epsilon}$ as above for $\bar{c}\in\mathbb{N}^{<\mathbb{N}}$,
$\epsilon\in\mathbb{Q}^{+}$. Clearly, ${\rm{rk}}_{F}(F_{1})=1$. We construct
an $(\alpha-2)$-AE family $P_{1}(\bar{x}$) in $F_{1}$ by replacing every
$2$-AE family $Q(\bar{x})=\\{q_{k,l}(\bar{x}_{k,l})\\}$ appearing in
$P(\bar{x})$ with $Q^{\prime}(\bar{x})=\\{q^{\prime}_{\langle
k,v\rangle,l}(\bar{x}_{\langle k,v\rangle,l})\\}$, where for any fixed $k$,
and $v\in\mathbb{Q}^{+}$, $\\{q^{\prime}_{\langle k,v\rangle,l}\\}$ enumerates
all $\phi_{\bar{c},v}$ that come from $\bar{c}$ in $M$ and $v>0$ witnessing
realizations of $Q(\bar{x})$. As before, $N\in\rm{Mod}(T)$ models $P_{1}$ iff
$N$ models $P_{M}$, and $[M]\in\bm{\Pi}^{0}_{\alpha-1}(t_{F_{0}})$. In this
way, Case 2 can be reduced to Case 1.

Finally, an easy induction using the above arguments reduces the case
$\alpha\geq\omega$ to the case $\alpha<\omega$. ∎

######  Theorem 4.12.

Let $F$ be a fragment, and let $T$ be an $F$-theory all of whose models are
locally compact. Suppose that $\cong_{T}$ is potentially
$\bm{\Pi}^{0}_{\alpha+2}$, where $\alpha\geq 1$. Then $\cong_{T}$ is Borel
reducible to $=_{\alpha+1}$.

###### Proof.

Observe that for $M\in\rm{Mod}(T)$, the fragment $F_{M}$ given by Lemma 4.11
can be coded as an element of $\mathcal{P}^{\alpha}(\mathbb{N})$. First, it is
not hard to see that, with an aid of the Kuratowski–Ryll-Nardzewski theorem,
selecting the types $q_{\bar{b},u}$ in the proof of the lemma can be arranged
in a Borel and isomorphism invariant way. Moreover, the fragments $F_{0}$ and
$F_{1}$ are also constructively specified, given $q_{\bar{b},u}$’s, so it is
somewhat tedious but completely standard to verify that the assignment
$M\mapsto F_{M}$ can be done in a Borel and isomorphism invariant manner.

Now, by [6, Theorem 4.3], each $M$ is an $F_{M}$-atomic model of
${\rm{Th}}_{F_{M}}(M)$, so it is $\aleph_{0}$-categorical in the theory
${\rm{Th}}_{F^{\prime}_{M}}(M)$, where $F^{\prime}_{M}$ is the fragment given
by Proposition 4.10. As ${\rm{Th}}_{F^{\prime}_{M}}(M)$ can be regarded as an
element of $\mathcal{P}^{\alpha+1}(\mathbb{N})$, the assignment
$M\mapsto(F^{\prime}_{M},{\rm{Th}}_{F^{\prime}_{M}}(M))$ can be coded as a
Borel mapping $f:\rm{Mod}(T)\rightarrow\mathcal{P}^{\alpha+1}(\mathbb{N})$
reducing $\cong_{T}$ to $=_{\alpha+1}$. ∎

##  5\. Countable structures and approximations of the Hjorth-isomorphism game

### Countable structures

Classical countable structures can be recovered in the setting of Polish
metric structures by imposing the requirement that $d(x,y)=1$ for $x\neq y$,
which can be axiomatized by the condition

$\sup_{x,y}(d(x,y)\wedge(d(x,y)\dotdiv 1)\wedge(1\dotdiv d(x,y)))=0;$

in the same way one can make sure that predicates take only values $0$ or $1$.
For such metric $d$, quantifiers $\sup_{x}$ and $\inf_{y}$ behave as $\forall
x$ and $\exists x$, so $\mathcal{L}_{\omega\omega}$,
$\mathcal{L}_{\omega_{1}\omega}$, and topologies defined by fragments are as
in the classical setting. In particular, $\rm{Mod}(L)$ is the space of all
structures in signature $L$ and with universe $\mathbb{N}$, and, for $u<1$,
$d(\bar{a},\bar{b})<u$ iff $\bar{a}\subseteq\bar{b}$ or
$\bar{b}\subseteq\bar{a}$, so it suffices to consider only AE families
$P(\bar{x})$ with $u_{P}=1$. Observe that then a tuple $\bar{a}$ in $M$
realizes a $(\beta+n)$-AE family $P(\bar{x})=\\{p_{k,l}(\bar{x}_{k,l})\\}$,
$1\leq n<\omega$, iff

$\forall\bar{b}\supseteq\bar{a}\forall k\exists\bar{c}\supseteq\bar{b}\exists
l(\bar{c}\mbox{ realizes }p_{k,l}(\bar{x}_{k,l})\mbox{ in }M).$

As a matter of fact, Theorem 4.5 also takes a more transparent form. Fix a
fragment $F$ in signature $L$. For $M\in\rm{Mod}(L)$, and
$\bar{a}\in\mathbb{N}^{<\mathbb{N}}$, we define
$\rm{tp}^{0}(\bar{a})=\rm{tp}(\bar{a})$, and, for $\alpha>0$,

$\rm{tp}^{\alpha}(\bar{a})=\\{\rm{tp}^{\beta}(\bar{b}):\beta<\alpha,\,\bar{b}\in\mathbb{N}^{<\mathbb{N}},\,\bar{a}\subseteq\bar{b}\\}.$

We also put ${\rm{Th}}^{\alpha}(M)=\rm{tp}^{\alpha}(\emptyset)$. If $M$ or $F$
is not clear from the context, we may explicitly specify it by writing
$\rm{tp}^{\alpha}_{M}(\bar{a})$, $\rm{tp}^{\alpha}_{F}(\bar{a})$ or
${\rm{Th}}^{\alpha}_{F}(M)$. Clearly, ${\rm{Th}}^{0}(M)={\rm{Th}}(M)$,
${\rm{Th}}^{1}(M)$ is the collection of all $F$-types realized in $M$,
${\rm{Th}}^{2}(M)$ is the collection of all $F$-types of structures
$(M,\bar{a})$, $\bar{a}\in\mathbb{N}^{<\mathbb{N}}$, etc.

######  Theorem 5.1.

Let $F$ be a fragment in signature $L$. Suppose that
$[M]\in\bm{\Pi}^{0}_{1+\alpha}(t_{F})$, $\alpha\geq 1$, for some
$M\in\rm{Mod}(L)$. Then

$[M]=\\{N\in\rm{Mod}(L):{\rm{Th}}^{\alpha}_{F}(N)={\rm{Th}}^{\alpha}_{F}(M)\\}.$

###### Proof.

We show that ${\rm{Th}}^{\alpha}_{F}(M)={\rm{Th}}^{\alpha}_{F}(N)$ implies
that $M$ and $N$ model the same $\alpha$-AE families $P(\emptyset)$, and apply
Corollary 3.3. For $\alpha=1$, suppose that $M$ and $N$ realize the same
types, and let $P(\emptyset)=\\{p_{k,l}(\bar{x}_{k,l})\\}$ be a $1$-AE family.
Let $\bar{b}$, $\bar{b}^{\prime}$ be tuples in $M$, $N$, respectively, such
that $\rm{tp}(\bar{b})=\rm{tp}(\bar{b}^{\prime})$. Then, for every $k$ and
$l$, there is $\bar{c}$ such that the formula $p_{k,l}(\bar{b},\bar{c})$ holds
in $M$ iff there is $\bar{c}^{\prime}$ such that
$p_{k,l}(\bar{b}^{\prime},\bar{c}^{\prime})$ holds in $N$. For $\alpha=2$ the
argument is analogous, and for $\alpha>2$ this is an easy induction. ∎

### Approximations of the Hjorth-isomorphism game

A _Polish $G$-space_ $X$ is a continuous action of a Polish group $G$ on a
Polish space $X$, $E_{X}$ denotes the orbit equivalence relation induced by
$X$, and $[x]$ is the equivalence class of $x\in X$. In [11], a game-theoretic
approach to Hjorth’s theory of turbulence has been developed, giving rise to
an interesting sufficient condition for orbit equivalence relations not to be
classifiable by countable structures. In this section, we introduce a
hierarchy of games $\rm{Appr}_{\alpha}(x,y)$, $\alpha<\omega_{1}$, that are
finer and finer approximations of the Hjorth-isomorphism game
${\rm{Iso}}(x,y)$ from [11]. As it turns out, winning strategies in these
games, played for the logic $\mbox{Sym}(\mathbb{N})$-spaces $\rm{Mod}(L)$, are
related to families ${\rm{Th}}^{\alpha}(M)$. Moreover, when put together, they
also can be used to rule out classifiability by countable structures.

For a Polish $G$-space $X$, $x,y\in X$, a collection $\mathcal{V}$ of open
neighborhoods of $1$ in $G$, an open neighborhood $V$ of $1$ in $G$, and open
$U\subseteq X$, we define games $\rm{Appr}_{\alpha}(x,y,\mathcal{V},V,U)$,
$\alpha<\omega_{1}$. Fix $\alpha<\omega_{1}$, set $x_{0}=x$, $y_{0}=y$,
$V^{y}_{0}=V$, $U^{y}_{0}=U$, and let Odd and Eve play as follows.

(1) In the first turn, Odd either sets $V^{x}_{1}=V^{y}_{0}$,
$\alpha_{1}=\alpha$ or plays a new $V^{x}_{1}\in\mathcal{V}$, and
$\alpha_{1}<\alpha$. Then he plays an open neighborhood $U^{x}_{0}$ of
$x_{0}$. Eve replies with $g^{y}_{0}\in G$.

(2) In the second turn, Odd either sets $V^{y}_{1}=V^{x}_{0}$,
$\alpha_{2}=\alpha_{1}$ or plays a new $V^{y}_{1}\in\mathcal{V}$, and
$\alpha_{2}<\alpha_{1}$. Then he plays an open neighborhood $U^{y}_{1}$ of
$y_{1}$. Eve replies with $g^{x}_{0}\in G$.

(2n+1) In the $(2n+1)$-th turn, $n>0$, Odd either sets $V^{x}_{n}=V^{y}_{n}$,
$\alpha_{2n+1}=\alpha_{2n}$ or plays a new $V^{x}_{n}\in\mathcal{V}$, and
$\alpha_{2n+1}<\alpha_{2n}$. Then he plays an open neighborhood $U^{x}_{n}$ of
$x_{n}=g^{x}_{n-1}.x_{n-1}$. Eve replies with $g^{y}_{n}\in G$.

(2n) In the $(2n)$-th turn, $n>1$, Odd either sets $V^{y}_{n}=V^{x}_{n-1}$,
$\alpha_{2n}=\alpha_{2n-1}$ or plays a new $V^{y}_{n}\in\mathcal{V}$, and
$\alpha_{2n}<\alpha_{2n-1}$. Then he plays an open neighborhood $U^{y}_{n}$ of
$y_{n}=g^{y}_{n-1}.y_{n-1}$. Eve replies with $g^{x}_{n-1}\in G$.

The game proceeds in this way, producing elements $V^{x}_{n}$, $V^{y}_{n}$,
$x_{n}$, $y_{n}$, $g^{x}_{n}$, $g^{y}_{n}$, $U^{x}_{n}$ and $U^{y}_{n}$,
$n\in\mathbb{N}$. Eve wins if, for every $n\geq 0$,

  * •

$y_{n+1}\in\overline{U^{x}_{n}}$ and $x_{n}\in\overline{U^{y}_{n}}$,

  * •

$g^{y}_{n}=h_{k}\ldots h_{0}$ for some $k\geq 0$ and $h_{0},\ldots,h_{k}\in
V^{y}_{n}$ such that $h_{i}\ldots h_{0}.y_{n}\in U^{y}_{n}$ for $i\leq k$,

  * •

$g^{x}_{n}=h_{k}\ldots h_{0}$ for some $k\geq 0$ and $h_{0},\ldots,h_{k}\in
V^{x}_{n}$ such that $h_{i}\ldots h_{0}.x_{n}\in U^{x}_{n}$ for $i\leq k$.

We write shortly $\rm{Appr}_{\alpha}(x,y)$ for
$\rm{Appr}_{\alpha}(x,y,\mathcal{U},G,X)$, where $\mathcal{U}$ is the
collection of all open neighborhoods of $1$ in $G$. We write $x\sim_{\alpha}y$
if Eve has a winning strategy in $\rm{Appr}_{\alpha}(x,y)$.

Note that if the conditions regulating the choice of $\alpha$ in
$\rm{Appr}_{\alpha}(x,y)$ are dropped, i.e., Odd can play a new $V^{x}_{n}$
(or $V^{y}_{y}$) without having to select some $\alpha_{2n+1}<\alpha_{2n}$ (or
$\alpha_{2n}<\alpha_{2n-1}$), the resulting game is the Hjorth-isomorphism
game ${\rm{Iso}}(x,y)$ defined in [11]. In other words, the games
$\rm{Appr}_{\alpha}(x,y)$, $\alpha<\omega_{1}$, form a hierarchy of finer and
finer approximations of ${\rm{Iso}}(x,y)$.

As the group $\mbox{Sym}(\mathbb{N})$ of all permutations of natural numbers
has a neighborhood basis at $1$ consisting of subgroups, we have the
following:

######  Remark 5.2.

Suppose that $G\leq\mbox{Sym}(\mathbb{N})$.

  1. (1)

In terms of winning strategies, the requirements for Eve in
$\rm{Appr}_{\alpha}(x,y)$ reduce to

     * •

$y_{n+1}\in\overline{U^{x}_{n}}$ and $x_{n}\in\overline{U^{y}_{n}}$,

     * •

$g^{y}_{n}\in V^{y}_{n}$,

     * •

$g^{x}_{n}\in V^{x}_{n}$.

  2. (2)

If $V\leq G$, $\rm{Appr}_{0}(x,y,\\{V\\},G,X)$ is $\rm{Appr}_{G,V}(x,y)$
defined in [10].

######  Proposition 5.3.

Let $X$ be a $G$-space, and let $\alpha<\omega_{1}$. Then $x\in[y]$ implies
$x\sim_{\alpha}y$ for $x,y\in X$, and $\sim_{\alpha}$ is an equivalence
relation.

###### Proof.

The first statement, and symmetry of $\sim_{\alpha}$, are obvious.

We prove transitivity for $\alpha=1$. Suppose that $x\sim_{1}y$ and
$y\sim_{1}z$. We show that $z\sim_{\alpha}x$, which, by symmetry of
$\sim_{\alpha}$, implies that $x\sim_{\alpha}z$. In the first turn, Odd plays
$U^{z}_{0}\subseteq X$ and $V^{z}_{1}\subseteq G$. Applying her winning
strategy for $\rm{Appr}_{1}(z,y)$, Eve can find $h^{y}_{0}$ such that
$h^{y}_{0}.y\in U^{z}_{0}$. Then, applying her winning strategy for
$\rm{Appr}_{1}(y,x)$, for a neighborhood $W$ of $y$ with $h^{y}_{0}.W\subseteq
U^{z}_{0}$, she can find $h^{x}_{0}$ such that $h^{x}_{0}.x\in W$, i.e.,
$h^{y}_{0}h^{x}_{0}.x\subseteq U^{z}_{0}$. She plays
$g^{x}_{0}=h^{y}_{0}h^{x}_{0}$. In the second turn, Odd plays
$U^{x}_{1}\subseteq X$ and $V^{x}_{1}\subseteq G$. Eve first applies her
winning strategy for $\rm{Appr}_{1}(y,x)$ to find $(h^{y}_{0})^{\prime}$ such
that $(h^{y}_{0})^{\prime}.y\in W$ for a neighborhood $W$ of $h^{x}_{0}.x$
such that $h^{y}_{0}.W\subseteq U^{x}_{1}$. Then she applies her winning
strategy for $\rm{Appr}_{1}(y,z)$ to find $h^{z}_{0}$ such that
$h^{z}_{0}.z\in W^{\prime}$ for a neighborhood $W^{\prime}$ of $h^{y}_{0}.y$
such that $h^{y}_{0}(h^{y}_{0})^{\prime}(h^{y}_{0})^{-1}.W^{\prime}\subseteq
W$. Clearly, $h^{y}_{0}(h^{y}_{0})^{\prime}(h^{y}_{0})^{-1}.z\in U^{x}_{1}$,
so Eve plays $g^{z}_{0}=h^{y}_{0}(h^{y}_{0})^{\prime}(h^{y}_{0})^{-1}$ in
$\rm{Appr}_{1}(z,x)$. Proceeding in this way, we can construct a winning
strategy for Eve for the entire game $\rm{Appr}_{1}(z,x)$, i.e., $z\sim_{1}x$.

The inductive step is straightforward: every game $\rm{Appr}_{\alpha}(x,y)$
proceeds initially as $\rm{Appr}_{1}(x,y)$, and then as some
$\rm{Appr}_{\beta}(x,y)$, where $\beta<\alpha$. ∎

For a given signature $L$, the logic $\mbox{Sym}(\mathbb{N})$-space
$\rm{Mod}(L)$ is the logic action of $\mbox{Sym}(\mathbb{N})$ on $\rm{Mod}(L)$
permuting the universe of structures $M\in\rm{Mod}(L)$. Clearly,
$E_{\rm{Mod}(L)}$ is the isomorphism relation on $\rm{Mod}(L)$. As the
relations $\sim_{\alpha}$ depend on the topology on $\rm{Mod}(L)$, for a
fragment $F$, we will write $\sim_{\alpha,F}$ to denote $\sim_{\alpha}$ on
$(\rm{Mod}(T),t_{F})$, and $[M]_{\alpha,F}$ to denote equivalence classes of
$\sim_{\alpha,F}$.

######  Proposition 5.4.

Let $F$ be a fragment in signature $L$, and let $M\in\rm{Mod}(L)$. Then

$[M]_{\alpha,F}=\\{N\in\rm{Mod}(L):{\rm{Th}}^{\alpha}_{F}(N)={\rm{Th}}^{\alpha}_{F}(M)\\}.$

###### Proof.

For $m\in\mathbb{N}$, let $\bar{m}$ denote the tuple $(0,\ldots m-1)$. For
$\alpha=1$, suppose that ${\rm{Th}}^{1}(M)={\rm{Th}}^{1}(N)$ for some
$M,N\in\rm{Mod}(L)$, i.e., $M$ and $N$ realize the same types. Then Eve has a
winning strategy along the following lines. Without loss of generality, we can
assume that in the first turn Odd chooses $[\phi(\bar{m},\bar{a})]$ as
$U^{M}_{0}$, where $\bar{m}$ and $\bar{a}$ are disjoint, and the pointwise
stabilizer $V_{m}$ of $\bar{m}$ as $V^{M}_{1}$. Suppose that
$\rm{tp}_{M}(\bar{m})=\rm{tp}_{N}(\bar{m})$. Eve fixes
$\bar{c}\in\mathbb{N}^{<\mathbb{N}}$ witnessing that
$N\models\exists\bar{x}\phi(\bar{n},\bar{x})$, and chooses $g_{0}^{N}\in
V_{m}$ mapping $\bar{c}$ to $\bar{a}$. Clearly,
$g_{0}.N\in[\phi(\bar{m},\bar{a})]$. Otherwise, since
${\rm{Th}}^{1}(M)={\rm{Th}}^{1}(N)$, there is $\bar{b}$ such that
$\rm{tp}_{M}(\bar{m})=\rm{tp}_{N}(\bar{b})$, so, arguing as before, Eve can
find $g_{0}^{N}\in\mbox{Sym}(\mathbb{N})$ such that
$g_{0}.N\in[\phi(\bar{m},\bar{a})]$. Other turns are analogous. In particular,
for $n>1$, the elements $g_{n}^{M}$ or $g_{n}^{N}$ can be always chosen from
$V_{m}$.

On the other hand, suppose that ${\rm{Th}}^{1}(M)\neq{\rm{Th}}^{1}(N)$, say,
there is $m$ such that no tuple in $N$ realizes $\rm{tp}_{M}(\bar{m})$. Let
Odd choose $V_{m}$ in the first turn, and let $g_{0}^{N}$ be the element
chosen by Eve. Then, for $\bar{b}=(g_{0}^{N})^{-1}(\bar{m})$, there exists
$\phi(\bar{x})\in\rm{tp}_{M}(\bar{m})\bigtriangleup\rm{tp}_{N}(\bar{b})$. It
is not hard to see that without loss of generality, we can assume that
$\phi(\bar{x})$ is of the form $\exists\bar{y}\psi(\bar{x},\bar{y})$ or
$\neg\exists\bar{y}\psi(\bar{x},\bar{y})$. Thus, there exists $\bar{a}$ such
that $\psi(\bar{m},\bar{a})$ holds in one of the structures, while for no
$\bar{c}$, $\psi(\bar{b},\bar{c})$ holds in the other one. In other words,
either $M\in[\psi(\bar{m},\bar{a})]$, while there is no $g\in V_{m}$ such that
$gg_{0}^{N}.N\in[\psi(\bar{m},\bar{a})]$, or $N\in[\psi(\bar{m},\bar{a})]$,
while there is no $g\in V_{m}$ such that $g.M\in[\psi(\bar{m},\bar{a})]$. In
any case, by Remark 5.2, Eve looses the game.

For the inductive step, we assume first that, for every $\beta<\alpha$ and
$m$, $\rm{tp}^{\beta}_{M}(\bar{m})=\rm{tp}^{\beta}_{N}(\bar{m})$ iff Eve has a
winning strategy starting with some $g^{N}_{0}\in V_{m}$. Then we proceed as
above. ∎

######  Corollary 5.5.

Let $F$ be a fragment in signature $L$. Suppose that
$[M]\in\bm{\Pi}^{0}_{1+\alpha}(t_{F})$, $\alpha\geq 1$, for some
$M\in\rm{Mod}(L)$. Then $[M]=[M]_{\alpha,F}$.

For equivalence relations $E$, $F$ on Polish spaces $X$, $Y$, respectively, an
_$(E,F)$ -homomorphism_ is a mapping $f:X\rightarrow Y$ such that

$x_{1}Ex_{2}\mbox{ implies }f(x_{1})Ff(x_{2}).$

Analogously to the Hjorth-isomorphism relation, one can show that Baire-
measurable homomorphisms preserve the relations $\sim_{\alpha}$ on a comeager
set.

######  Proposition 5.6.

Let $X$ be a Polish $G$-space, $Y$ a Polish $H$-space, and let $f$ be a Baire-
measurable $(E_{X},E_{Y})$-homomorphism. For every $\alpha<\omega_{1}$ there
exists a $G$-invariant comeager subset $X_{0}\subseteq X$ such that
$x\sim_{\alpha}y$ implies $f(x)\sim_{\alpha}f(y)$ for $x,y\in X_{0}$.

###### Proof.

As it has been pointed out in Remark 5.2, each $\rm{Appr}_{\alpha}(x,y)$ is
the game ${\rm{Iso}}(x,y)$ with the extra ingredient of selecting (smaller and
smaller) ordinals whenever a new neighborhood of the identity is played by
Odd. Therefore the proof of the proposition is essentially the same as the
proof of Proposition 3.6 in [11], which states the same fact for
${\rm{Iso}}(x,y)$. One only needs to make the following straightforward
observation when constructing a winning strategy for Eve in
$\rm{Appr}_{\alpha}(f(x),f(y))$ based on her winning strategy in
$\rm{Appr}_{\alpha}(x,y)$: as long as no new neighborhood of $1$ has been
played by Odd in $\rm{Appr}_{\alpha}(f(x),f(y))$, no new neighborhood of $1$
is played by Odd in $\rm{Appr}_{\alpha}(x,y)$. ∎

######  Theorem 5.7.

Let $X$ be a Polish $G$-space, and let $\alpha<\omega_{1}$. If for any
$G$-invariant comeager subset $C$ of $X$ there exist $x,y\in C$ such that
$x\sim_{\alpha}y$ but $[x]\neq[y]$, then there is no Borel reduction of a
restriction of $E_{X}$ to a comeager $X_{0}\subseteq X$ to a potentially
$\bm{\Pi}^{0}_{1+\alpha}$ isomorphism relation of the form $\cong_{T}$ for
some fragment $F$ and $F$-theory $T$.

###### Proof.

Suppose that there is an $F$-theory $T$, comeager $X_{0}\subseteq X$, and a
Borel reduction $f$ of the restriction of $E_{X}$ to $X_{0}$, to $\cong_{T}$
such that $\cong_{T}$ is potentially $\bm{\Pi}^{0}_{1+\alpha}$. By Corollary
4.9, we can assume that $M\in\bm{\Pi}^{0}_{1+\alpha}(t_{F})$ for
$M\in\rm{Mod}(T)$. By Proposition 5.6, there is a comeager $C\subseteq X_{0}$
such that $x\sim_{\alpha}y$ implies $f(x)\sim_{\alpha,F}f(y)$ for $x,y\in C$.
Fix $x,y\in C$ such that $x\sim_{\alpha}y$ but $[x]\neq[y]$. But then
$f(x)\sim_{\alpha,F}f(y)$, and, by Corollary 5.5, $f(x)\cong f(y)$, a
contradiction. ∎

######  Theorem 5.8.

Let $X$ be a Polish $G$-space. If for any $\alpha<\omega_{1}$, and any
$G$-invariant comeager subset $C$ of $X$ there exist $x,y\in C$ such that
$x\sim_{\alpha}y$ but $[x]\neq[y]$, then no restriction of $E_{X}$ to a
comeager $X_{0}\subseteq X$ is classifiable by countable structures.

###### Proof.

Suppose that there is a comeager $X_{0}\subseteq X$, and a Borel reduction $f$
of a restriction of $E_{X}$ to $X_{0}$, to $\cong$ on $\rm{Mod}(L)$ for some
signature $L$. By Claim 5.4 in the proof of [1, Theorem 1.3], there is a
comeager $C^{\prime}\subseteq X_{0}$ and $\alpha<\omega_{1}$ such that for
every $x\in C^{\prime}$, $[f(x)]$ is $\bm{\Pi}^{0}_{\alpha}$ in the standard
topology on $\rm{Mod}(L)$, and so also in the topology generated by the
finitary fragment $\mathcal{L}_{\omega\omega}$. By Proposition 5.6, there is a
comeager $C\subseteq C^{\prime}$ such that $x\sim_{\alpha}y$ implies
$f(x)\sim_{\alpha,\mathcal{L}_{\omega\omega}}f(y)$ for $x,y\in C$. Fix $x,y\in
C$ such that $x\sim_{\alpha}y$ but $[x]\neq[y]$. But then
$f(x)\sim_{\alpha,\mathcal{L}_{\omega\omega}}f(y)$, and, by Corollary 5.5,
$f(x)\cong f(y)$, a contradiction. ∎

## References

  * [1] S. Allison, A. Panagiotopoulos, _Dynamical obstructions to classification by (co)homology and other TSI-group invariants_ , Trans. Amer. Math. Soc. 374 (2021), 8793–8811.
  * [2] I. Ben Yaacov, M. Doucha, A. Nies, T. Tsankov, _Metric Scott analysis_ , Adv. Math. 318 (2017), 46–87.
  * [3] I. Ben Yaacov, J. Iovino, _Model theoretic forcing in analysis_ , Ann. Pure Appl. Logic 158 (2009), 163–174.
  * [4] S. Gao, A. Kechris, _On the classification of Polish metric spaces up to isometry_. Memoirs of the American Mathematical Society, 161 (2003).
  * [5] S. Gao, _Invariant Descriptive Set Theory_ , Chapman and Hall 2008.
  * [6] A. Hallbäck, M. Malicki, T. Tsankov, _Continuous logic and Borel equivalence relations_ , J. Symbolic Logic, published online 22.06.2022, DOI:10.1017/jsl.2022.48
  * [7] G. Hjorth, _Classification and orbit equivalence relations_ , Mathematical Surveys and Monographs, vol. 75, American Mathematical Society.
  * [8] G. Hjorth, A. Kechris, _Borel equivalence relations and classifications of countable models_ , Annals Pure Applied Logic 82 (1996), 221–272.
  * [9] G. Hjorth, A. Kechris, A. Louveau, _Borel equivalence relations induced by actions of the symmetric group_ , Annals Pure Applied Logic 92 (1998) 63–112.
  * [10] A. Kechris, M. Malicki, A. Panagiotopoulos, J. Zielinski, On Polish groups admitting non-essentially countable actions. Ergod. Theory Dyn. Syst., 42 (2022), 180–194.
  * [11] M. Lupini, A. Panagiotopoulos, _Games orbits play and obstructions to Borel reducibility_ , Groups Geom. Dyn. 12 (2018), 1461–1483.