# Maximal stable quotients of invariant types in NIP theories

Krzysztof Krupiński  and  Adrián Portillo  Instytut Matematyczny Uniwersytetu
Wrocławskiego, pl. Grunwaldzki 2, 50-384 Wrocław, Poland  Krzysztof Krupiński
https://orcid.org/0000-0002-2243-4411<EMAIL_ADDRESS>Adrián Portillo https://orcid.org/0000-0001-9354-8574 Adrian.Portillo-
<EMAIL_ADDRESS>
###### Abstract.

For a NIP theory $T$, a sufficiently saturated model ${\mathfrak{C}}$ of $T$,
and an invariant (over some small subset of ${\mathfrak{C}}$) global type $p$,
we prove that there exists a finest relatively type-definable over a small set
of parameters from ${\mathfrak{C}}$ equivalence relation on the set of
realizations of $p$ which has stable quotient. This is a counterpart for
equivalence relations of the main result of [HP18] on the existence of maximal
stable quotients of type-definable groups in NIP theories. Our proof adapts
the ideas of the proof of this result, working with relatively type-definable
subsets of the group of automorphisms of the monster model as defined in
[HKP21].

###### Key words and phrases:

Stable quotient, hyperimaginary, invariant type.

###### 2020 Mathematics Subject Classification:

03C45

Both authors are supported by the Narodowe Centrum Nauki grant no.
2016/22/E/ST1/00450. The first author is also supported by the Narodowe
Centrum Nauki grant no. 2018/31/B/ST1/00357.

##  1\. Introduction

Stability theory, developed in the 1970s and 1980s, is a core part of model
theory. One of the main goals of modern model theory is to extend various
ideas and results of stability theory to appropriate unstable contexts; it is
particularly important to distinguish interesting contexts extending
stability. Two of the approaches are to either impose some general global
assumptions on the theory (e.g., NIP, simplicity, $\textrm{NSOP}_{1}$) or some
local ones (such as working with a stable definable set or generically stable
type) in order to prove some structural results. Another ubiquitous strategy
is to look at hyperdefinable sets (i.e. quotients by type-definable
equivalence relations) and assume (or prove) their good properties (e.g.,
boundedness) to obtain further results.

Bounded quotients have been studied thoroughly and played an important role in
model theory and its applications for many years (e.g., to approximate
subgroups). However, stable quotients have not been studied so deeply. The
project originates with a talk by Anand Pillay in Lyon in 2009 on finest
stable hyperdefinable quotients in NIP theories. The case of type-definable
groups was worked out in [HP18]; some questions from [HP18] were answered in
[KP22]. The general case of first order theories will be studied in this
paper. One should mention that it is well known that hyperimaginaries can be
treated as imaginaries in continuous logic, and stability of hyperdefinable
sets is equivalent to stability (of imaginary sorts) in the sense of
continuous logic. But we will not be using this approach in the present paper.

Let $T$ be a complete theory, ${\mathfrak{C}}\models T$ a monster model (i.e.,
$\kappa$-saturated and strongly $\kappa$-homogeneous for a strong limit
cardinal $\kappa>|T|$) in which we are working, and $A\subseteq{\mathfrak{C}}$
a small set of parameters (i.e., $|A|<\kappa$); a cardinal $\gamma$ is bounded
if $\gamma<\kappa$. Let $X/E$ be a hyperdefinable set over $A$, i.e. $X$ is an
$A$-type-definable set and $E$ an $A$-type-definable equivalence relation on
$X$. The complete type over $A$ of an element of $X/E$ can be defined as the
$\operatorname{{Aut}}({\mathfrak{C}}/A)$-orbit of that element, or the
preimage of this orbit under the quotient map, or the partial type defining
this preimage.

######  Definition 1.1.

A hyperdefinable over $A$ set $X/E$ is _stable_ if for every $A$-indiscernible
sequence $(a_{i},b_{i})_{i<\omega}$ with $a_{i}\in X/E$ for all (equivalently,
some) $i<\omega$, we have

$\operatorname{{tp}}(a_{i},b_{j}/A)=\operatorname{{tp}}(a_{j},b_{i}/A)$

for all (some) $i\neq j<\omega$.

Let $G$ be a $\emptyset$-$\bigwedge$-definable group. Since stability of
hyperdefinable sets is invariant under type-definable bijections and closed
under taking products and type-definable subsets (see [HP18, Remark 1.4]), it
is clear that there always exists a smallest $A$-type-definable subgroup
$G^{st}_{A}$ such that the quotient $G/G^{st}_{A}$ is stable. The main result
of [HP18] says that under NIP, $G^{st}_{A}$ does not depend on $A$, and so it
is the smallest type-definable (over parameters) subgroup with stable quotient
$G/G^{st}$. Moreover, it is $\emptyset$-type-definable and normal.

In [KP22], we gave several characterizations of stability for hyperdefinable
sets both with and without assuming that the theory $T$ has NIP (see [KP22,
Section 2]). We also proved that in distal theories all stable hyperdefinable
sets are bounded, i.e. of bounded size ([KP22, Corollary 3.5]). In Proposition
2.2, we will deduce another characterization of stability under NIP, via the
so-called weak stability, generalizing [OP07, Proposition 4.2] from the
definable to the hyperdefinable context.

When we lack the group structure, a natural counterpart of taking the quotient
by a subgroup is to take the quotient by an equivalence relation. Thus, it is
natural to ask if similar results to the ones appearing in [HP18] hold outside
of the context of type-definable groups. However, the naive counterpart of
[HP18, Theorem 1.1] is easily seen to be false. Namely, in general, for any
non-stable type-definable set $X$ (e.g. the home sort of a non-stable theory),
a finest type-definable (over an arbitrary small set of parameters)
equivalence relation on $X$ with stable quotient does not exist. The reason is
that given any type-definable equivalence relation $E$ on $X$ with stable
quotient, $E$ is not the relation of equality, so we can find an $E$-class
which contains at least two distinct elements $a$ and $b$. Then, the
equivalence relation on $X$ being the intersection of $E$ and the relation
$\equiv_{a}$ of having the same type over $a$ is strictly finer that $E$ and
has stable quotient by [HP18, Remark 1.4] (as both $X/E$ and
$X/\\!\\!\equiv_{a}$ are stable).

Let ${\mathfrak{C}}\prec{\mathfrak{C}}^{\prime}$ be two monster models of a
NIP theory $T$ such that ${\mathfrak{C}}$ is small in
${\mathfrak{C}}^{\prime}$. Recall that a relatively type-definable over a
(small) set of parameters $B$ subset of a set $Y$ is the intersection of $Y$
with a set which is type-definable over $B$. The main result of this paper is
the following theorem which will be proved in Section 3.

######  Theorem.

Assume NIP. Let $p(x)\in S(\mathfrak{C})$ be an $A$-invariant type. Assume
that ${\mathfrak{C}}$ is at least $\beth_{(\beth_{2}(\lvert x\rvert+\lvert
T\rvert+\lvert A\rvert))^{+}}$-saturated. Then, there exists a finest
equivalence relation $E^{st}$ on $p({\mathfrak{C}}^{\prime})$ relatively type-
definable over a small (relative to ${\mathfrak{C}}$) set of parameters of
${\mathfrak{C}}$ and with stable quotient $p({\mathfrak{C}}^{\prime})/E^{st}$.

Our proof is via a non-trivial adaptation of the ideas from the proof of the
main theorem of [HP18], using relatively type-definable subsets of the group
of automorphisms of the monster model (as defined in [HKP21]).

We do not know whether $E^{st}$ is relatively type-definable over $A$. At the
end of Section 3, we will observe that if it was true, then the specific
(large) saturation degree assumption in the above theorem could be removed.
Another question is whether one could drop the invariance of $p$ hypothesis
from the above theorem. If such a strengthening is true, a proof would
probably require some new tricks.

In Section 2, we prove several basic results concerning the existence of
finest relatively type-definable equivalence relations with stable quotients
some of which are used in Section 3, and we discuss the transfer of the
existence of finest relatively type-definable equivalence relations with
stable quotients between models.

In Section 3, we prove the main theorem of this paper stated above.

In the last section, we compute $E^{st}$ in two concrete examples which are
expansions of local orders. In fact, in these examples, we give full
classifications of all relatively type-definable over a small subset of
${\mathfrak{C}}$ equivalence relations on $p({\mathfrak{C}}^{\prime})$ for a
suitable invariant type $p\in S({\mathfrak{C}})$.

We finish the introduction presenting the framework of this paper. Let $T$ be
a complete first-order theory of infinite models in a language $L$. Let
${\mathfrak{C}}\prec{\mathfrak{C}}^{\prime}$ be models of $T$ such that
${\mathfrak{C}}$ is $\kappa$-saturated with a strong limit cardinal
$\kappa>\lvert T\rvert$, and ${\mathfrak{C}}^{\prime}$ is
$\kappa^{\prime}$-saturated and strongly $\kappa^{\prime}$-homogeneous with a
strong limit cardinal $\kappa^{\prime}>\lvert{\mathfrak{C}}\rvert$. We say
that $\kappa$ is the degree of saturation of ${\mathfrak{C}}$ and
$\kappa^{\prime}$ is the degree of saturation of ${\mathfrak{C}}^{\prime}$. We
say that a set is ${\mathfrak{C}}$-small if its cardinality is smaller than
$\kappa$ and ${\mathfrak{C}}^{\prime}$-small if its cardinality is smaller
than $\kappa^{\prime}$. Note that $|T|$ is the cardinality of the set of all
formulas in $L$. Unless stated otherwise, $p(x)$ will always be a type in
$S_{x}({\mathfrak{C}})$ invariant over some ${\mathfrak{C}}$-small
$A\subseteq{\mathfrak{C}}$, where $x$ is a ${\mathfrak{C}}$-small tuple of
variables. (In fact, instead of assuming that $\kappa$ is a strong limit
cardinal, in Section 2 it is enough to assume that $\kappa>2^{|T|+|A|}$ and in
Section 3 that $\kappa\geq\beth_{(2^{2^{|T|+|A|}+\lvert x\rvert})^{+}}$.)
Whenever $B\subseteq{\mathfrak{C}}^{\prime}$, by $p\\!\upharpoonright_{B}$ we
mean the restriction to $B$ of the unique extension of $p$ to an $A$-invariant
type in $S({\mathfrak{C}}^{\prime})$. If $E$ is a type-definable equivalence
relation and $a$ is an element of its domain, $[a]_{E}$ denotes the $E$-class
of $a$.

##  2\. Basic results and transfers between models

The goal of this section is to present a useful criterion that allows us to
check whether a relatively type-definable over a ${\mathfrak{C}}$-small
$B\subseteq{\mathfrak{C}}$ equivalence relation $E$ on
$p({\mathfrak{C}}^{\prime})$ with stable quotient is, in fact, the finest one
(see Lemma 2.8). As a corollary, we get the transfer to elementary extensions
of ${\mathfrak{C}}$ of the property of being the finest relatively type-
definable equivalence relation on $p({\mathfrak{C}}^{\prime})$ (see Corollary
2.9). We also take the opportunity to prove a new characterization of
stability of hyperdefinable sets in NIP theories (see Proposition 2.2).

Let $E$ be a type-definable equivalence relation on a type-definable subset
$X$ of ${\mathfrak{C}}^{\lambda}$, where $\lambda<\kappa$. The following
definition is the hyperimaginary analogous of [OP07, Definition 1.2].

######  Definition 2.1.

A hyperdefinable (over $A$) set $X/E$ is _weakly stable_ if for every
$A$-indiscernible sequence $(a_{i},b_{i},c)_{i<\omega}$ with $a_{i},b_{i}\in
X/E$ for all (equivalently, some) $i<\omega$, we have

$\operatorname{{tp}}(a_{i},b_{j},c/A)=\operatorname{{tp}}(a_{j},b_{i},c/A)$

for all (some) $i\neq j<\omega$.

We obtain a hyperdefinable counterpart of [OP07, Proposition 4.2].

######  Proposition 2.2.

A hyperdefinable set $X/E$ which has NIP is weakly stable if and only if it is
stable.

###### Proof.

Without loss of generality, assume that both $X$ and $E$ are type-definable
over the empty set.

It is clear that stable sets are weakly stable, even without the $NIP$
assumption. By [KP22, Theorem 2.10], under the $NIP$ assumption, the stability
of $X/E$ is equivalent to the fact that every indiscernible sequence of
elements of $X/E$ is totally indiscernible. Hence, it is enough to show that
weak stability of $X/E$ also implies this property.

Suppose that the sequence $(a_{i})_{i<\omega}$ in $X/E$ is indiscernible but
not totally indiscernible. Let us, without loss of generality, replace
$\omega$ by $\mathbb{Q}$. Then, there exist a natural number $n$ and $j<n-1$
such that

$\operatorname{{tp}}(a_{j},a_{{j+1}}/A)\neq\operatorname{{tp}}(a_{{j+1}},a_{j}/A),$

where $A$ is the set of all $a_{k}$ for $k<n$ distinct from $j$ and $j+1$.
Choose any rationals $l_{0}<l_{1}<\dots$ in the interval $(j,{j+1})$. Let
$b_{i}:=a_{l_{i}}$ for $i<\omega$. Then, the sequence $(b_{i})_{i<\omega}$ is
$A$-indiscernible and
$\operatorname{{tp}}(b_{i},b_{j}/A)\neq\operatorname{{tp}}(b_{j},b_{i}/A)$ for
all $i<j<\omega$. Let $a$ be an enumeration of $A$. We conclude that the
sequence $(b_{i},b_{i},a)_{i<\omega}$ contradicts the weak stability of $X/E$.
∎

Next, we present a definition that we use throughout the whole section. This
definition first appeared in [KNS19, Definition 3.2].

######  Definition 2.3.

Let $A\subseteq\mathcal{M}\subseteq B$ and $q(x)\in S(B)$. We say that $q(x)$
is a _strong heir extension over A_ of $q\\!\upharpoonright_{\mathcal{M}}(x)$
if for all finite $m\subseteq\mathcal{M}$

$(\forall\varphi(x,y)\in L)(\forall b\subseteq B)[\varphi(x,b)\in
q(x)\implies(\exists b^{\prime}\subseteq\mathcal{M})(\varphi(x,b^{\prime})\in
q(x)\wedge b\underset{Am}{\equiv}b^{\prime})].$

Note that if $q\in S({\mathfrak{C}})$ is a strong heir extension over $A$ of
$q\\!\upharpoonright_{\mathcal{M}}(x)$, then $\mathcal{M}$ is an
$\aleph_{0}$-saturated model in the language $L_{A}$ (i.e., $L$ expanded by
constants from $A$). Conversely, if $\mathcal{M}$ is an $\aleph_{0}$-saturated
model in $L_{A}$ and $q(x)\in S(\mathcal{M})$, there always exists
$q^{\prime}(x)\in S(B)$ which is a strong heir over $A$ of $q$ (see [KNS19,
Lemma 3.3]).

######  Lemma 2.4.

Assume that $q(x)\in S(\mathcal{M})$ is $A$-invariant (for some
$A\subseteq\mathcal{M}$) and $q^{\prime}(x)\in S(\mathfrak{C})$ is a strong
heir extension over $A$ of $q(x)$. Then $q^{\prime}(x)$ is the unique global
$A$-invariant extension of $q(x)$.

###### Proof.

To show $A$-invariance, suppose for a contradiction that there are $a,b$ and
$\varphi(x,a)\in q^{\prime}(x)$ with $a\underset{A}{\equiv}b$ and
$\neg\varphi(x,b)\in q^{\prime}(x)$. Then, there exist
$a^{\prime},b^{\prime}\in\mathcal{M}$ such that
$a^{\prime}\underset{A}{\equiv}a$ and $b^{\prime}\underset{A}{\equiv}b$ for
which $\varphi(x,a^{\prime})\in q(x)$ while $\neg\varphi(x,b^{\prime})\in
q(x)$. Then $a^{\prime}\underset{A}{\equiv}b^{\prime}$, which contradicts the
$A$-invariance of $q(x)$.

Uniqueness follows from the fact that $\mathcal{M}$ is $\aleph_{0}$-saturated
in $L_{A}$. ∎

Given a partial type (possibly with parameters) $\pi(x,y)$, we say that
$\pi(x,y)$ _relatively defines an equivalence relation_ on a type-definable
set $X$ if $\pi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime})\cap
X({\mathfrak{C}}^{\prime})^{2}$ is an equivalence relation. Given a type-
definable equivalence relation $E$ on a type-definable set $X$, a _partial
type relatively defining_ $E$ is any partial type $\pi(x,y)$ such that
$\pi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime})\cap
X({\mathfrak{C}}^{\prime})^{2}=E$. We say that a type-definable equivalence
relation $E$ on a type-definable set $X$ is _countably relatively defined_ if
some partial type $\pi(x,y)$ relatively defining it consists of countably many
formulas, and we say that $E$ is relatively type-definable over $B$ (or
$B$-relatively type-definable) if it is relatively defined by a partial type
over $B$.

Lemma 2.5 gives us a useful stability criterion when an equivalence relation
on $p({\mathfrak{C}}^{\prime})$ is relatively type-definable over a
sufficiently saturated model.

######  Lemma 2.5.

Let $\mathcal{M}\prec\mathfrak{C}$ be $\aleph_{0}$-saturated in $L_{A}$, and
$\pi(x,y)$ a partial type over $\mathcal{M}$ relatively defining an
equivalence relation on
$p\\!\upharpoonright_{\mathcal{M}}(\mathfrak{C}^{\prime})$. Then, $\pi$
relatively defines an equivalence relation on $p(\mathfrak{C}^{\prime})$ with
stable quotient if and only if it relatively defines an equivalence relation
on $p\\!\upharpoonright_{\mathcal{M}}(\mathfrak{C}^{\prime})$ with stable
quotient.

###### Proof.

Firstly, note that since $\pi$ relatively defines an equivalence relation on
the set $p\\!\upharpoonright_{\mathcal{M}}\\!\\!({\mathfrak{C}}^{\prime})$, it
relatively defines an equivalence relation on $p({\mathfrak{C}}^{\prime})$.
Let $E$ be the equivalence relation relatively defined by $\pi(x,y)$ on
$p({\mathfrak{C}}^{\prime})$ and let $E^{\prime}$ be the equivalence relation
relatively defined by $\pi(x,y)$ on
$p\\!\upharpoonright_{\mathcal{M}}\\!\\!({\mathfrak{C}}^{\prime})$.

Assume first that $p({\mathfrak{C}}^{\prime})/E$ is unstable. Then, there
exists a ${\mathfrak{C}}$-indiscernible sequence $(c_{i},b_{i})_{i<\omega}$
such that $c_{i}\in p({\mathfrak{C}}^{\prime})$ for all $i<\omega$ and for all
$i\neq j$

$\operatorname{{tp}}\left({\raisebox{1.99997pt}{$[c_{i}]_{E},b_{j}$}\left/\raisebox{-1.99997pt}{${\mathfrak{C}}$}\right.}\right)\neq\operatorname{{tp}}\left({\raisebox{1.99997pt}{$[c_{j}]_{E},b_{i}$}\left/\raisebox{-1.99997pt}{${\mathfrak{C}}$}\right.}\right).$

This implies that for all $i\neq j$ we have

$\operatorname{{tp}}\left({\raisebox{1.99997pt}{$[c_{i}]_{E^{\prime}},b_{j}$}\left/\raisebox{-1.99997pt}{${\mathfrak{C}}$}\right.}\right)\neq\operatorname{{tp}}\left({\raisebox{1.99997pt}{$[c_{j}]_{E^{\prime}},b_{i}$}\left/\raisebox{-1.99997pt}{${\mathfrak{C}}$}\right.}\right),$

and so
$p\\!\upharpoonright_{\mathcal{M}}\\!\\!(\mathfrak{C}^{\prime})/E^{\prime}$ is
unstable.

Assume now that
$p\\!\upharpoonright_{\mathcal{M}}\\!\\!(\mathfrak{C}^{\prime})/E^{\prime}$ is
unstable. This is witnessed by an $\mathcal{M}$-indiscernible sequence
$(c_{i},b_{i})_{i<\omega}$ such that $c_{i}\in
p\\!\upharpoonright_{\mathcal{M}}\\!\\!({\mathfrak{C}}^{\prime})$ for all
$i<\omega$ and for all $i\neq j$

$\operatorname{{tp}}\left({\raisebox{1.99997pt}{$[c_{i}]_{E^{\prime}},b_{j}$}\left/\raisebox{-1.99997pt}{$\mathcal{M}$}\right.}\right)\neq\operatorname{{tp}}\left({\raisebox{1.99997pt}{$[c_{j}]_{E^{\prime}},b_{i}$}\left/\raisebox{-1.99997pt}{$\mathcal{M}$}\right.}\right).$

Consider
$q:=\operatorname{{tp}}\left({\raisebox{1.99997pt}{$(c_{i},b_{i})_{i<\omega}$}\left/\raisebox{-1.99997pt}{$\mathcal{M}$}\right.}\right)$
and let $q^{\prime}\in S({\mathfrak{C}})$ be a strong heir extension over $A$
of $q$. Let $(c_{i}^{\prime},b_{i}^{\prime})_{i<\omega}$ be a realization of
$q^{\prime}$. Then,

  1. (1)

$(c_{i}^{\prime},b_{i}^{\prime})_{i<\omega}$ is
${\mathfrak{C}}$-indiscernible;

  2. (2)

$\operatorname{{tp}}(c_{i}^{\prime}/{\mathfrak{C}})=p(x)$ for all $i<\omega$;

  3. (3)

$\operatorname{{tp}}\left({\raisebox{1.99997pt}{$[c^{\prime}_{i}]_{E},b^{\prime}_{j}$}\left/\raisebox{-1.99997pt}{${\mathfrak{C}}$}\right.}\right)\neq\operatorname{{tp}}\left({\raisebox{1.99997pt}{$[c_{j}^{\prime}]_{E},b^{\prime}_{i}$}\left/\raisebox{-1.99997pt}{${\mathfrak{C}}$}\right.}\right)$
for all $i\neq j$.

$(1)$ Suppose for a contradiction that $(1)$ does not hold. Then, it is
witnessed by a formula (with parameters $d$ from ${\mathfrak{C}}$) of the form
$\varphi(x_{i_{1}},y_{i_{1}},\dots,x_{i_{n}},y_{i_{n}},d)\wedge\neg\varphi(x_{j_{1}},y_{j_{1}},\dots,x_{j_{n}},y_{j_{n}},d)$,
for some $i_{1}<\dots<i_{n}$ and $j_{1}<\dots<j_{n}$. Now, using that
$q^{\prime}$ is a strong heir extension over $A$ of $q$, we can find
$d^{\prime}\subseteq\mathcal{M}$ such that

$\varphi(x_{i_{1}},y_{i_{1}},\dots,x_{i_{n}},y_{i_{n}},d^{\prime})\wedge\neg\varphi(x_{j_{1}},y_{j_{1}},\dots,x_{j_{n}},y_{j_{n}},d^{\prime})\in
q,$

contradicting the $\mathcal{M}$-indiscernibility of
$(c_{i},b_{i})_{i<\omega}$.

$(2)$ follows from the fact that
$\operatorname{{tp}}(c_{i}^{\prime}/{\mathfrak{C}})$ is a strong heir
extension over $A$ of $p\\!\upharpoonright_{\mathcal{M}}\\!\\!(x)$, which has
to be $p(x)$ by Lemma 2.4.

$(3)$ Suppose $(3)$ fails for some $i\neq j$. As $E$ is the restriction to
$p({\mathfrak{C}})$ of the equivalence relation $E^{\prime}$, we see that
$\operatorname{{tp}}\left({\raisebox{1.99997pt}{$[c^{\prime}_{i}]_{E},b^{\prime}_{j}$}\left/\raisebox{-1.99997pt}{${\mathfrak{C}}$}\right.}\right)=\operatorname{{tp}}\left({\raisebox{1.99997pt}{$[c_{j}^{\prime}]_{E},b^{\prime}_{i}$}\left/\raisebox{-1.99997pt}{${\mathfrak{C}}$}\right.}\right)$
implies
$\operatorname{{tp}}\left({\raisebox{1.99997pt}{$[c^{\prime}_{i}]_{E^{\prime}},b^{\prime}_{j}$}\left/\raisebox{-1.99997pt}{${\mathfrak{C}}$}\right.}\right)=\operatorname{{tp}}\left({\raisebox{1.99997pt}{$[c_{j}^{\prime}]_{E^{\prime}},b^{\prime}_{i}$}\left/\raisebox{-1.99997pt}{${\mathfrak{C}}$}\right.}\right)$.
So
$\operatorname{{tp}}\left({\raisebox{1.99997pt}{$[c^{\prime}_{i}]_{E^{\prime}},b^{\prime}_{j}$}\left/\raisebox{-1.99997pt}{$\mathcal{M}$}\right.}\right)=\operatorname{{tp}}\left({\raisebox{1.99997pt}{$[c_{j}^{\prime}]_{E^{\prime}},b^{\prime}_{i}$}\left/\raisebox{-1.99997pt}{$\mathcal{M}$}\right.}\right)$,
and hence
$\operatorname{{tp}}\left({\raisebox{1.99997pt}{$[c_{i}]_{E^{\prime}},b_{j}$}\left/\raisebox{-1.99997pt}{$\mathcal{M}$}\right.}\right)=\operatorname{{tp}}\left({\raisebox{1.99997pt}{$[c_{j}]_{E^{\prime}},b_{i}$}\left/\raisebox{-1.99997pt}{$\mathcal{M}$}\right.}\right)$
because $q\subseteq q^{\prime}$ and $\pi(x,y)$ is over $\mathcal{M}$. This is
a contradiction.

By (1), (2), and (3), $p({\mathfrak{C}}^{\prime})/E$ is unstable. ∎

Even though at first glance the requirement that $\pi(x,y)$ relatively defines
an equivalence relation on
$p\\!\upharpoonright_{\mathcal{M}}\\!\\!(\mathfrak{C}^{\prime})$ might not
seem very natural, the following result shows that this can always be assumed.

######  Proposition 2.6.

Let $E$ be a $B$-relatively type-definable equivalence relation on
$p({\mathfrak{C}}^{\prime})$, for some $B\subseteq{\mathfrak{C}}$. Then,
$E=\bigcap_{i\in I}E_{i}\cap p({\mathfrak{C}}^{\prime})^{2}$, where
$|I|\leq|B|+|x|+|T|$, and for each $i\in I$ there is a countable
$B_{i}\subseteq{\mathfrak{C}}$ such that $E_{i}$ is a countably
$B_{i}$-relatively defined equivalence relation on
$p\\!\upharpoonright_{B_{i}}\\!\\!({\mathfrak{C}}^{\prime})$. Thus, $E$ is the
restriction to $p({\mathfrak{C}}^{\prime})$ of a $B^{\prime}$-type-definable
equivalence relation $F$ on
$p\\!\upharpoonright_{B^{\prime}}\\!\\!({\mathfrak{C}}^{\prime})$ for some
$B^{\prime}\subseteq{\mathfrak{C}}$ with $\lvert
B^{\prime}\rvert\leq|B|+|x|+|T|$.

Moreover, if we start from a given partial type $\pi(x,y)$ over $B$ relatively
defining $E$, then $B^{\prime}$ and $F$ in the previous sentence can be taken
so that $|B^{\prime}|\leq|\pi|$ and $F$ is $B^{\prime}$-type-definable on
$p\\!\upharpoonright_{B^{\prime}}\\!\\!({\mathfrak{C}}^{\prime})$ by
$\pi(x,y)$.

###### Proof.

Fix a partial type $\pi(x,y)$ relatively defining $E$ on
$p({\mathfrak{C}}^{\prime})$. It clearly consists of reflexive formulas and
without loss of generality it is closed under conjunction. Let $\psi_{0}(x)$
be any formula in $p(x)$ and $\varphi_{0}(x,y)$ any formula in $\pi(x,y)$.
Then the partial type

$p(x)\wedge p(y)\wedge p(z)\wedge\pi(x,y)\wedge\pi(y,z)$

implies $\varphi_{0}(x,z)\wedge\varphi_{0}(z,x)$. By compactness, there are
$\varphi_{1}(x,y)$ in $\pi(x,y)$ and $\psi_{1}(x)$ in $p(x)$ such that the
formula

$\psi_{1}(x)\wedge\psi_{1}(y)\wedge\psi_{1}(z)\wedge\varphi_{1}(x,y)\wedge\varphi_{1}(y,z)$

implies $\varphi_{0}(x,z)\wedge\varphi_{0}(z,x).$ Proceeding by induction, we
construct a partial type

$\\{\varphi_{i}(x,y):i<\omega\\}$

relatively defining an equivalence relation on
$\bigcap_{i<\omega}\psi_{i}({\mathfrak{C}}^{\prime})$. Let
$B_{\varphi_{0},\psi_{0}}$ be a countable set containing the parameters of all
the constructed formulas $\varphi_{i}(x,y)$ and $\psi_{i}(x)$, $i<\omega$.
Then, the partial type $\\{\varphi_{i}(x,y):i<\omega\\}$ clearly relatively
defines over $B_{\varphi_{0},\psi_{0}}$ an equivalence relation on
$p\\!\upharpoonright_{B_{\varphi_{0},\psi_{0}}}\\!\\!({\mathfrak{C}}^{\prime})$.
Applying this process separately to every $\varphi(x,y)\in\pi(x,y)$ yields the
desired family of equivalence relations. ∎

######  Corollary 2.7.

Let $E$ and $\pi(x,y)$ be as in Proposition 2.6, where $B$ is
${\mathfrak{C}}$-small. Then there is $\mathcal{M}\prec{\mathfrak{C}}$
containing $B$ with $\lvert\mathcal{M}\rvert\leq 2^{\lvert T\rvert+\lvert
A\rvert}+\lvert B\rvert+\lvert\pi\rvert$ which is $\aleph_{0}$-saturated in
$L_{A}$ and such that $\pi(x,y)$ relatively defines an equivalence relation on
$p\\!\upharpoonright_{\mathcal{M}}\\!\\!({\mathfrak{C}}^{\prime})$.

The following result is a criterion for when an equivalence relation on
$p({\mathfrak{C}}^{\prime})$ relatively type-definable over a sufficiently
saturated ${\mathfrak{C}}$-small model is the finest relatively type-definable
equivalence relation over a ${\mathfrak{C}}$-small $B\subseteq{\mathfrak{C}}$
on $p({\mathfrak{C}}^{\prime})$ with stable quotient.

######  Lemma 2.8.

Let $\mathcal{M}$ and $\pi(x,y)$ be as in Lemma 2.5, and assume that
$\mathcal{M}$ is $\mathfrak{C}$-small. Then $\pi$ relatively defines the
finest relatively type-definable over a ${\mathfrak{C}}$-small subset of
${\mathfrak{C}}$ equivalence relation on $p({\mathfrak{C}}^{\prime})$ with
stable quotient if and only if it relatively defines the finest
$\mathcal{M}^{\prime}$-type-definable equivalence relation on
$p\\!\upharpoonright_{\mathcal{M}^{\prime}}\\!\\!(\mathfrak{C}^{\prime})$ with
stable quotient for every $\mathcal{M}^{\prime}\prec{\mathfrak{C}}^{\prime}$
with $\lvert\mathcal{M}^{\prime}\rvert\leq 2^{\lvert T\rvert+\lvert
A\rvert}+\lvert\mathcal{M}\rvert$ that is $\aleph_{0}$-saturated in $L_{A}$
and contains $\mathcal{M}$.

###### Proof.

Let $E$ be the equivalence relation relatively defined by $\pi$ on
$p({\mathfrak{C}}^{\prime})$ and $E^{\prime}$ be the equivalence relation
relatively defined by $\pi$ on
$p\\!\upharpoonright_{\mathcal{M}}\\!\\!(\mathfrak{C}^{\prime})$.

($\Leftarrow$) By Lemma 2.5, the right hand side implies that $E$ has stable
quotient. Assume that there exists $E_{B}$, a relatively type-definable
equivalence relation on $p({\mathfrak{C}}^{\prime})$ over some
${\mathfrak{C}}$-small set of parameters $B\subseteq{\mathfrak{C}}$ such that
the quotient $p({\mathfrak{C}}^{\prime})/E_{B}$ is stable and $E_{B}\subsetneq
E$. Take a presentation of $E_{B}$ as $\bigcap_{i\in I}E_{i}\cap
p({\mathfrak{C}}^{\prime})^{2}$ satisfying the conclusion of Proposition 2.6.
Abusing notation, write $E_{i}$ for $E_{i}\cap
p({\mathfrak{C}}^{\prime})^{2}$. As $E_{B}\subsetneq E$, there exists some
$i\in I$ such that

$E\cap E_{i}\subsetneq E.$

Since $p({\mathfrak{C}}^{\prime})/E_{B}$ is stable and $E_{B}\subseteq E\cap
E_{i}$, we have that $p({\mathfrak{C}}^{\prime})/E\cap E_{i}$ is stable. Pick
$B_{i}$ as in Proposition 2.6 and choose any
$\mathcal{M}^{\prime}\supseteq\mathcal{M}\cup B_{i}$ $\aleph_{0}$-saturated in
$L_{A}$, contained in ${\mathfrak{C}}$ and of size at most $2^{|T|+\lvert
A\rvert}+\lvert\mathcal{M}\rvert$. By the choice of $B_{i}$ and $E_{i}$, there
is a partial type $\delta(x,y)$ over $\mathcal{M}^{\prime}$ relatively
defining $E_{i}$ which also relatively defines an equivalence relation on
$p\\!\upharpoonright_{\mathcal{M}^{\prime}}\\!\\!({\mathfrak{C}}^{\prime})$.
Let $\rho(x,y)$ be $\pi(x,y)\wedge\delta(x,y)$. Then $\rho(x,y)$ relatively
defines an equivalence relation on
$p\\!\upharpoonright_{\mathcal{M}^{\prime}}\\!\\!({\mathfrak{C}}^{\prime})$
and
${\raisebox{1.99997pt}{$p({\mathfrak{C}}^{\prime})$}\left/\raisebox{-1.99997pt}{$\rho({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime})\cap
p({\mathfrak{C}}^{\prime})^{2}$}\right.}$ is stable. Hence, applying Lemma
2.5, we obtain that the quotient

${\raisebox{1.99997pt}{$p\\!\upharpoonright_{\mathcal{M}^{\prime}}\\!\\!({\mathfrak{C}}^{\prime})$}\left/\raisebox{-1.99997pt}{$\rho({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime})\cap
p\\!\upharpoonright_{\mathcal{M}^{\prime}}\\!\\!({\mathfrak{C}}^{\prime})^{2}$}\right.}.$

is stable. Moreover,

$\rho({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime})\cap
p\\!\upharpoonright_{\mathcal{M}^{\prime}}\\!\\!({\mathfrak{C}}^{\prime})^{2}\subsetneq\pi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime})\cap
p\\!\upharpoonright_{\mathcal{M}^{\prime}}\\!\\!({\mathfrak{C}}^{\prime})^{2}.$

Thus, we have proved that the right hand side of the lemma fails.

($\Rightarrow$) By Lemma 2.5, the left hand side implies that $E^{\prime}$ is
stable. Assume that the right hand side does not hold, witnessed by a model
$\mathcal{M}^{\prime}$ of size at most $2^{\lvert T\rvert+\lvert
A\rvert}+\lvert\mathcal{M}\rvert$ that is $\aleph_{0}$-saturated in $L_{A}$
and contains $\mathcal{M}$ and a partial type $\rho(x,y)$ over
$\mathcal{M}^{\prime}$. By saturation of ${\mathfrak{C}}$, we can assume that
$\mathcal{M}^{\prime}\subseteq{\mathfrak{C}}$. Hence, by Lemma 2.5, the fact
that the quotient
${\raisebox{1.99997pt}{$p\\!\upharpoonright_{\mathcal{M}^{\prime}}\\!\\!(\mathfrak{C}^{\prime})$}\left/\raisebox{-1.99997pt}{$\rho(\mathfrak{C}^{\prime},\mathfrak{C}^{\prime})\cap
p\\!\upharpoonright_{\mathcal{M}^{\prime}}\\!\\!(\mathfrak{C}^{\prime})^{2}$}\right.}$
is stable implies that the quotient
${\raisebox{1.99997pt}{$p(\mathfrak{C}^{\prime})$}\left/\raisebox{-1.99997pt}{$\rho(\mathfrak{C}^{\prime},\mathfrak{C}^{\prime})\cap
p(\mathfrak{C}^{\prime})^{2}$}\right.}$ is stable. Let $b_{1},b_{2}\in
p\\!\upharpoonright_{\mathcal{M}^{\prime}}\\!\\!({\mathfrak{C}}^{\prime})$ be
elements witnessing

$\rho(\mathfrak{C}^{\prime},\mathfrak{C}^{\prime})\cap
p\\!\upharpoonright_{\mathcal{M}^{\prime}}\\!\\!(\mathfrak{C}^{\prime})^{2}\subsetneq\pi(\mathfrak{C}^{\prime},\mathfrak{C}^{\prime})\cap
p\\!\upharpoonright_{\mathcal{M}^{\prime}}\\!\\!(\mathfrak{C}^{\prime})^{2},$

that is,
$(b_{1},b_{2})\in\pi(\mathfrak{C}^{\prime},\mathfrak{C}^{\prime})\setminus\rho(\mathfrak{C}^{\prime},\mathfrak{C}^{\prime})$.
Let
$q:=\operatorname{{tp}}\left({\raisebox{1.99997pt}{$b_{1},b_{2}$}\left/\raisebox{-1.99997pt}{$\mathcal{M}^{\prime}$}\right.}\right)$
and let $q^{\prime}\in S({\mathfrak{C}})$ be a strong heir extension over $A$
of $q$. By Lemma 2.4, any realization $(b_{1}^{\prime},b_{2}^{\prime})\in
q^{\prime}({\mathfrak{C}}^{\prime})$ satisfies
$b_{1}^{\prime},b_{2}^{\prime}\in p({\mathfrak{C}}^{\prime})$,
$(b_{1}^{\prime},b_{2}^{\prime})\in\pi(\mathfrak{C}^{\prime},\mathfrak{C}^{\prime})$,
and
$(b_{1}^{\prime},b_{2}^{\prime})\not\in\rho(\mathfrak{C}^{\prime},\mathfrak{C}^{\prime})$.
Therefore,

$\rho(\mathfrak{C}^{\prime},\mathfrak{C}^{\prime})\cap
p(\mathfrak{C}^{\prime})^{2}\subsetneq\pi(\mathfrak{C}^{\prime},\mathfrak{C}^{\prime})\cap
p(\mathfrak{C}^{\prime})^{2},$

which contradicts the minimality of $E$. ∎

Let ${\mathfrak{C}}\prec{\mathfrak{C}}_{1}\prec{\mathfrak{C}}^{\prime}$ be
such that ${\mathfrak{C}}_{1}$ is ${\mathfrak{C}}^{\prime}$-small and
$\kappa_{1}$-saturated with $\kappa_{1}\geq\kappa$. A set is
${\mathfrak{C}}_{1}$-small if its cardinality is smaller than $\kappa_{1}$.
Let $p_{1}(x)\in S({\mathfrak{C}}_{1})$ be the unique $A$-invariant extension
of $p(x)$.

######  Corollary 2.9.

Assume that $E$ is the finest relatively type-definable over a
${\mathfrak{C}}$-small subset of ${\mathfrak{C}}$ equivalence relation on
$p({\mathfrak{C}}^{\prime})$ with stable quotient. Then $E\cap
p_{1}({\mathfrak{C}}^{\prime})^{2}$ is the finest relatively type-definable
over a ${\mathfrak{C}}_{1}$-small subset of ${\mathfrak{C}}_{1}$ equivalence
relation on $p_{1}({\mathfrak{C}}^{\prime})$ with stable quotient.

###### Proof.

Using Corollary 2.7, we can find a $\mathfrak{C}$-small
$\mathcal{M}\prec{\mathfrak{C}}$ which is $\aleph_{0}$-saturated in $L_{A}$
and a partial type $\pi(x,y)$ over $\mathcal{M}$ relatively defining $E$ and
relatively defining an equivalence relation on
$p\\!\upharpoonright_{\mathcal{M}}\\!\\!({\mathfrak{C}}^{\prime})$. By Lemma
2.8, the right hand side of the equivalence in Lemma 2.8 holds. But this right
hand side does not depend on the choice of ${\mathfrak{C}}$, and so, again by
Lemma 2.8, $E\cap p_{1}({\mathfrak{C}}^{\prime})^{2}$ is the finest relatively
type-definable over a ${\mathfrak{C}}_{1}$-small subset of
${\mathfrak{C}}_{1}$ equivalence relation on $p_{1}({\mathfrak{C}}^{\prime})$
with stable quotient. ∎

However, there is no obvious transfer going in the opposite direction (i.e.,
from ${\mathfrak{C}}_{1}$ to ${\mathfrak{C}}$), as an application of Corollary
2.7 for $p_{1}$ may produce a model $\mathcal{M}\prec{\mathfrak{C}}_{1}$ whose
cardinality is bigger than the degree of saturation of ${\mathfrak{C}}$, and
then we cannot embed it into ${\mathfrak{C}}$ via an automorphism. We have
only the following corollary.

######  Corollary 2.10.

Assume that $E$ is the finest relatively type-definable over a
${\mathfrak{C}}_{1}$-small subset of ${\mathfrak{C}}_{1}$ equivalence relation
on $p_{1}({\mathfrak{C}}^{\prime})$ with stable quotient, and suppose that $E$
is relatively defined by a type $\pi(x,y,B)$ over a ${\mathfrak{C}}$-small set
$B$. Let $\sigma\in\operatorname{{Aut}}({\mathfrak{C}}_{1}/A)$ be such that
$\sigma[B]\subseteq\mathfrak{C}$. Then
$\pi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime},\sigma[B])\cap
p({\mathfrak{C}}^{\prime})^{2}$ is the finest relatively type-definable over a
${\mathfrak{C}}$-small subset of ${\mathfrak{C}}$ equivalence relation on
$p({\mathfrak{C}}^{\prime})$ with stable quotient.

###### Proof.

By Corollary 2.7 applied to ${\mathfrak{C}}_{1}$ and $p_{1}$ in place of
${\mathfrak{C}}$ and $p$, there is $\mathcal{M}\prec{\mathfrak{C}}_{1}$
containing $B$ with $\lvert\mathcal{M}\rvert\leq 2^{\lvert T\rvert+\lvert
A\rvert}+\lvert B\rvert+\lvert x\rvert$ which is $\aleph_{0}$-saturated in
$L_{A}$ and such that $\pi(x,y,B)$ relatively defines an equivalence relation
on $p_{1}\\!\upharpoonright_{\mathcal{M}}\\!\\!({\mathfrak{C}}^{\prime})$.
Since $\kappa>2^{\lvert T\rvert+\lvert A\rvert}+\lvert B\rvert+\lvert
x\rvert$, we can modify $\sigma$ outside $A\cup B$ so that
$\sigma[\mathcal{M}]\subseteq{\mathfrak{C}}$.

By assumption and Lemma 2.8, the right hand side of that lemma holds for
$p_{1}$ in place of $p$. Since $\sigma(p_{1})=p_{1}$, it still holds for
$p_{1}$ and $\sigma[\mathcal{M}]$ in place of $\mathcal{M}$. Since this right
hand side does not depend on ${\mathfrak{C}}_{1}$ and we have
$\sigma[\mathcal{M}]\subseteq{\mathfrak{C}}$, it holds for $p$ and
$\sigma[\mathcal{M}]$, so by Lemma 2.8, we get that
$\pi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime},\sigma[B])\cap
p({\mathfrak{C}}^{\prime})^{2}$ is the finest relatively type-definable over a
${\mathfrak{C}}$-small subset of ${\mathfrak{C}}$ equivalence relation on
$p({\mathfrak{C}}^{\prime})$ with stable quotient. ∎

The following proposition and its proof was proposed by the referee.

######  Proposition 2.11.

The finest relatively type-definable over a ${\mathfrak{C}}$-small subset of
${\mathfrak{C}}$ equivalence relation on $p({\mathfrak{C}}^{\prime})$ with
stable quotient exists if and only if the finest ${\mathfrak{C}}$-type-
definable equivalence relation on $p({\mathfrak{C}}^{\prime})$ with stable
quotient is relatively type-definable over a ${\mathfrak{C}}$-small subset of
${\mathfrak{C}}$, and, in that case, both equivalence relations coincide.

###### Proof.

Let $F$ be the finest ${\mathfrak{C}}$-type-definable equivalence relation on
$p({\mathfrak{C}}^{\prime})$ with stable quotient. Every relatively type-
definable over a ${\mathfrak{C}}$-small subset of ${\mathfrak{C}}$ equivalence
relation on $p({\mathfrak{C}}^{\prime})$ with stable quotient is coarser than
$F$. Thus, if $F$ is is relatively type-definable over a
${\mathfrak{C}}$-small subset of ${\mathfrak{C}}$, then it is the finest one
with stable quotient. Conversely, suppose that the finest relatively type-
definable over a ${\mathfrak{C}}$-small subset of ${\mathfrak{C}}$ equivalence
relation on $p({\mathfrak{C}}^{\prime})$ with stable quotient exists and
denote it by $E$. As we have already pointed out, we have $F\subseteq E$. On
the other hand, let $\pi(x,y)$ be a partial type over a ${\mathfrak{C}}$-small
subset of ${\mathfrak{C}}$ relatively defining $E$ and $\rho(x,y)$ a partial
type over ${\mathfrak{C}}$ defining $F$. Pick
${\mathfrak{C}}\prec{\mathfrak{C}}_{1}\prec{\mathfrak{C}}^{\prime}$ such that
${\mathfrak{C}}_{1}$ is $\kappa_{1}$-saturated with
$\kappa_{1}>\lvert{\mathfrak{C}}\rvert$. By Corollary 2.9, $\pi(x,y)$
relatively defines the finest relatively type-definable over a
${\mathfrak{C}}_{1}$-small subset of ${\mathfrak{C}}_{1}$ equivalence relation
on $p_{1}({\mathfrak{C}}^{\prime})$ with stable quotient. Since
$p_{1}({\mathfrak{C}}^{\prime})\subseteq p({\mathfrak{C}}^{\prime})$ and
$\kappa_{1}>\lvert{\mathfrak{C}}\rvert$, we have that $\rho(x,y)$ relatively
defines, over a ${\mathfrak{C}}_{1}$-small subset of ${\mathfrak{C}}_{1}$, an
equivalence relation on $p_{1}({\mathfrak{C}}^{\prime})$ with stable quotient.
Hence, $\pi(x,y)\cup p_{1}(x)\cup p_{1}(y)\models\rho(x,y)$. Consider any
formula $\phi(x,y,c_{0})$ implied by $\rho(x,y)$, where
$c_{0}\in{\mathfrak{C}}$. By compactness, there is a formula $\psi(x,c_{1})\in
p_{1}(x)$ and a formula $\Delta(x,y,c_{2})$ implied $\pi(x,y)$ with
$c_{2}\in{\mathfrak{C}}$ and such that

$\Delta(x,y,c_{2})\wedge\psi(x,c_{1})\wedge\psi(y,c_{1})\models\varphi(x,y,c_{0}).$

Now, take $c\in{\mathfrak{C}}$ such that
$\operatorname{{tp}}(c,c_{0},c_{2}/A)=\operatorname{{tp}}(c_{1},c_{0},c_{2}/A)$.
Then,
$\Delta(x,y,c_{2})\wedge\psi(x,c)\wedge\psi(y,c)\models\varphi(x,y,c_{0}).$ On
the other hand, by $A$-invariance of $p_{1}(x)$, we get $\psi(x,c)\in
p(x)=p_{1}\\!\upharpoonright_{{\mathfrak{C}}}\\!\\!(x)$. Therefore,
$\pi(x,y)\cup p(x)\cup p(y)\models\varphi(x,y,c_{0})$. As $\varphi$ was
arbitrary, we get $\pi(x,y)\cup p(x)\cup p(y)\models\rho(x,y)$, so $E\subseteq
F$, concluding $E=F$. ∎

##  3\. The main theorem

The goal of this section is to prove the theorem stated in the introduction
(see Theorem 3.7).

We use results on relatively type-definable subsets of the group of
automorphisms of ${\mathfrak{C}}^{\prime}$ extracted from [HKP21]. The
following is Definition 2.14 of [HKP21], which extends the notion of
relatively definable subset of the automorphism group of the monster model
from [KPR18, Appendix A].

######  Definition 3.1.

By a relatively type-definable subset of
$\operatorname{Aut}({\mathfrak{C}}^{\prime})$, we mean a subset of the form
$\\{\sigma\in\operatorname{{Aut}}({\mathfrak{C}}^{\prime}):{\mathfrak{C}}^{\prime}\models\pi(\sigma(a),b))\\}$
for some partial type $\pi(x,y)$ without parameters, where $x$ and $y$ are
${\mathfrak{C}}^{\prime}$-small tuples of variables, and $a$, $b$ are
corresponding tuples from ${\mathfrak{C}}^{\prime}$.

In particular, given a partial type $\pi(x,y,z)$ over the empty set, a
(${\mathfrak{C}}^{\prime}$-small) set of parameters $A$ and
(${\mathfrak{C}}^{\prime}$-small) tuples $a,b,c$ in ${\mathfrak{C}}^{\prime}$
corresponding to $x,y,z$, respectively, we have a relatively type-definable
subset of $\operatorname{Aut}({\mathfrak{C}}^{\prime})$ of the form

$A_{\pi(x;y,z);a;b,c}({\mathfrak{C}}^{\prime}/A):=\\{\sigma\in\operatorname{Aut}({\mathfrak{C}}^{\prime}/A):{\mathfrak{C}}^{\prime}\models\pi(\sigma(a);b,c)\\}.$

In this section, if $A=\emptyset$, we will omit $({\mathfrak{C}}^{\prime}/A)$,
and when it is clear how the variables are arranged, we will denote sets of
the form $A_{\pi(x;y,z);a;a,c}({\mathfrak{C}}^{\prime}/A)$ as
$A_{\pi;a;c}({\mathfrak{C}}^{\prime}/A)$.

We use relatively type-definable sets of the group
$\operatorname{Aut}({\mathfrak{C}}^{\prime})$ to prove the following:

######  Lemma 3.2.

Let $a\in\mathfrak{C}^{\prime}$ and a sequence
$(a_{i})_{i<\omega}\subseteq\mathfrak{C}^{\prime}$ (of
${\mathfrak{C}}^{\prime}$-small tuples $a_{i}$) be such that
$a_{0}\underset{a}{\equiv}a_{i}$ for all $i<\omega$ and $a\models
p\\!\upharpoonright_{a_{<\omega}}$. Let $\pi(x,y,z)$ be a partial type over
the empty set such that for every $i<\omega$ the partial type $\pi(x,y,a_{i})$
relatively defines an equivalence relation on
$p\\!\upharpoonright_{a_{i}}\\!\\!(\mathfrak{C^{\prime}})$. Assume that there
is a formula $\varphi(x,y,z)$ implied by $\pi(x,y,z)$ such that for every
$i<\omega$

$\bigcap_{j\neq
i}\pi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime},a_{j})\cap(p\\!\upharpoonright_{a_{<\omega}}\\!\\!({\mathfrak{C}}^{\prime}))^{2}\not\subseteq\varphi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime},a_{i}).$

Then $T$ has IP.

To prove this result, we need the following three observations on relatively
type-definable subsets of $\operatorname{Aut}({\mathfrak{C}}^{\prime})$ of
special kind.

######  Claim 3.3.

Let $a$, $(a_{i})_{i<\omega}$, and $\pi(x,y,z)$ be as in Lemma 3.2, and let
$E_{a_{i}}$ be the equivalence relation on
$p\\!\upharpoonright_{a_{i}}\\!\\!({\mathfrak{C}}^{\prime})$ relatively
defined by $\pi(x,y,a_{i})$. Then, for all $i<\omega$,
$A_{\pi;a;a_{i}}({\mathfrak{C}}^{\prime}/a_{i})$ is the stabilizer of the
class $[a]_{E_{a_{i}}}$ under the action of
$\operatorname{Aut}({\mathfrak{C}}^{\prime}/a_{i})$, and
$A_{\pi;a;a_{i}}({\mathfrak{C}}^{\prime}/a_{<\omega})$ is the stabilizer of
the class $[a]_{E_{a_{i}}}$ under the action of
$\operatorname{Aut}({\mathfrak{C}}^{\prime}/a_{<\omega})$.

###### Proof.

It is clear that $\operatorname{Aut}({\mathfrak{C}}^{\prime}/a_{i})$ preserves
both $p\\!\upharpoonright_{a_{i}}\\!\\!({\mathfrak{C}}^{\prime})$ and
$E_{a_{i}}$.

Let $\sigma\in A_{\pi;a;a_{i}}({\mathfrak{C}}^{\prime}/a_{i})$. By the
definition of $A_{\pi;a;a_{i}}$, we have $\models\pi(\sigma(a),a,a_{i})$.
Hence, $\sigma(a)\in[a]_{E_{a_{i}}}$, and so
$\sigma([a]_{E_{a_{i}}})=[a]_{E_{a_{i}}}$. Thus, we have proved that

$A_{\pi;a;a_{i}}({\mathfrak{C}}^{\prime}/a_{i})\subseteq\operatorname{Stab}_{\operatorname{Aut}({\mathfrak{C}}^{\prime}/a_{i})}([a]_{E_{a_{i}}}).$

Conversely, let
$\sigma\in\operatorname{Stab}_{\operatorname{Aut}({\mathfrak{C}}^{\prime}/a_{i})}([a]_{E_{a_{i}}})$.
This implies $\sigma(a)E_{a_{i}}a$. Hence, $\models\pi(\sigma(a),a,a_{i})$,
and so $\sigma\in A_{\pi;a;a_{i}}({\mathfrak{C}}^{\prime}/a_{i})$. Thus,

$\operatorname{Stab}_{\operatorname{Aut}({\mathfrak{C}}^{\prime}/a_{i})}([a]_{E_{a_{i}}})\subseteq
A_{\pi;a;a_{i}}({\mathfrak{C}}^{\prime}/a_{i}).$

The same proof works for
$\operatorname{Stab}_{\operatorname{Aut}({\mathfrak{C}}^{\prime}/a_{<\omega})}([a]_{E_{a_{i}}})$.
∎

######  Claim 3.4.

Let $a$, $a_{0}$, and $\pi(x,y,z)$ be as in Lemma 3.2. Then, for each formula
$\varphi(x,y,z)$ implied by $\pi(x,y,z)$ there is a formula $\theta(x,y,z)$
implied by $\pi(x,y,z)$ such that

$A_{\pi;a;a_{0}}({\mathfrak{C}}^{\prime}/a_{0})\cdot
A_{\theta;a;a_{0}}({\mathfrak{C}}^{\prime}/a_{0})\cdot
A_{\pi;a;a_{0}}({\mathfrak{C}}^{\prime}/a_{0})\subseteq
A_{\varphi;a;a_{0}}({\mathfrak{C}}^{\prime}/a_{0}).$

###### Proof.

Let us consider the type
$\pi^{\prime}(x_{1},x_{2};y,z):=\pi(x_{1},y,z)\cup\\{x_{2}=z\\}$. Then,

$A_{\pi;a;a_{0}}({\mathfrak{C}}^{\prime}/a_{0})=A_{\pi^{\prime}(x_{1},x_{2};y,z);aa_{0};a,a_{0}}.$

Hence, by the previous claim,
$A_{\pi^{\prime}(x_{1},x_{2};y,z);aa_{0};a,a_{0}}$ is a group, so it satisfies

$A_{\pi^{\prime}(x_{1},x_{2};y,z);aa_{0};a,a_{0}}^{3}=A_{\pi^{\prime}(x_{1},x_{2};y,z);aa_{0};a,a_{0}}.$

For any formula $\varphi(x,y,z)$ implied by $\pi(x,y,z)$ we have

$A_{\pi^{\prime}(x_{1},x_{2};y,z);aa_{0};a,a_{0}}^{3}\subseteq
A_{\varphi(x;y,z);a;a,a_{0}}.$

Applying compactness ([HKP21, Corollary 4.8]), for each $\varphi(x,y,z)$
implied by $\pi(x,y,z)$ there is some $\theta(x,y,z)$ implied by $\pi(x,y,z)$
such that

$A_{\pi^{\prime}(x_{1},x_{2};y,z);aa_{0};a,a_{0}}\cdot
A_{\\{x_{2}=z\\}\wedge\theta(x_{1};y,z);aa_{0};a,a_{0}}\cdot
A_{\pi^{\prime}(x_{1},x_{2};y,z);aa_{0};a,a_{0}}\subseteq
A_{\varphi(x;y,z);a;a,a_{0}}.$

Finally, since every automorphism on the left hand side belongs to
$\operatorname{Aut}({\mathfrak{C}}^{\prime}/a_{0})$, we conclude that

$A_{\pi;a;a_{0}}({\mathfrak{C}}^{\prime}/a_{0})\cdot
A_{\theta;a;a_{0}}({\mathfrak{C}}^{\prime}/a_{0})\cdot
A_{\pi;a;a_{0}}({\mathfrak{C}}^{\prime}/a_{0})\subseteq
A_{\varphi;a;a_{0}}({\mathfrak{C}}^{\prime}/a_{0}).$

∎

######  Claim 3.5.

Let $a$, $(a_{i})_{i<\omega}$, and $\pi(x,y,z)$ be as in Lemma 3.2. Then, for
any formulas $\varphi(x,y,z)$ and $\theta(x,y,z)$ implied by $\pi(x,y,z)$, for
every $i<\omega$:

$A_{\pi;a;a_{0}}({\mathfrak{C}}^{\prime}/a_{0})\cdot
A_{\theta;a;a_{0}}({\mathfrak{C}}^{\prime}/a_{0})\cdot
A_{\pi;a;a_{0}}({\mathfrak{C}}^{\prime}/a_{0})\subseteq
A_{\varphi;a;a_{0}}({\mathfrak{C}}^{\prime}/a_{0}).$

if and only if

$A_{\pi;a;a_{i}}({\mathfrak{C}}^{\prime}/a_{i})\cdot
A_{\theta;a;a_{i}}({\mathfrak{C}}^{\prime}/a_{i})\cdot
A_{\pi;a;a_{i}}({\mathfrak{C}}^{\prime}/a_{i})\subseteq
A_{\varphi;a;a_{i}}({\mathfrak{C}}^{\prime}/a_{i}).$

###### Proof.

Let $\tau\in\operatorname{Aut}({\mathfrak{C}}^{\prime}/a)$ be such that
$\tau(a_{0})=a_{i}$. The conjugation by $\tau$

$\displaystyle\operatorname{Aut}({\mathfrak{C}}^{\prime}/a_{0})$
$\displaystyle\to\operatorname{Aut}({\mathfrak{C}}^{\prime}/a_{i})$
$\displaystyle\sigma\hskip 20.0pt$ $\displaystyle\mapsto\hskip
10.0pt\tau\sigma\tau^{-1}$

is a bijection whose inverse is the conjugation by $\tau^{-1}$. Moreover,

$\models\pi(\tau\sigma\tau^{-1}(a),a,a_{i})\iff\models\pi(\sigma\tau^{-1}(a),a,a_{0})\iff\models\pi(\sigma(a),a,a_{0}).$

Analogous equivalences also hold for $\varphi$ and for $\theta$ in place of
$\pi$. Hence, the desired equivalence follows by applying the conjugation by
$\tau$. ∎

We are now ready to prove Lemma 3.2.

###### Proof of Lemma 3.2.

Note that for all $i<\omega$, using automorphisms of ${\mathfrak{C}}^{\prime}$
fixing $(a_{i})_{i<\omega}$, we can reduce the condition

$\bigcap_{j\neq
i}\pi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime},a_{j})\cap(p\\!\upharpoonright_{a_{<\omega}}\\!\\!({\mathfrak{C}}^{\prime}))^{2}\not\subseteq\varphi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime},a_{i})$

to

$\bigcap_{j\neq i}\pi({\mathfrak{C}}^{\prime},a,a_{j})\cap
p\\!\upharpoonright_{a_{<\omega}}\\!\\!({\mathfrak{C}}^{\prime})\not\subseteq\varphi({\mathfrak{C}}^{\prime},a,a_{i}),$

because, given a pair $(c,d)$ witnessing the former condition, there exists
some
$\sigma\in\operatorname{Aut}({\mathfrak{C}}^{\prime}/a_{<\omega})$ such that
$\sigma(d)=a$, and then the pair $(\sigma(c),a)$ witnesses the latter
condition. Moreover, using the same approach, one can see that the latter
condition can be expressed using relatively type-definable subsets of
$\operatorname{Aut}({\mathfrak{C}}^{\prime})$ as

$A_{\bigwedge_{j\neq i}\pi(x;y,z_{j});a;a,(a_{j})_{j\neq
i}}({\mathfrak{C}}^{\prime}/a_{<\omega})\not\subseteq
A_{\varphi(x;y,z_{i});a;a,a_{i}}.$

For every $i<\omega$, choose some

$\sigma_{i}\in A_{\bigwedge_{j\neq i}\pi(x;y,z_{j});a;a,(a_{j})_{j\neq
i}}({\mathfrak{C}}^{\prime}/a_{<\omega})\setminus
A_{\varphi(x;y,z_{i}),a,a,a_{i}},$

and let $\sigma_{I}$ denote the composition $\prod_{i\in I}\sigma_{i}$, for
any finite $I\subseteq\omega$.

By Claims 3.4 and 3.5, there is a formula $\theta(x,y,z)$ implied by
$\pi(x,y,z)$ such that for all $i<\omega$

$A_{\pi;a;a_{i}}({\mathfrak{C}}^{\prime}/a_{i})\cdot
A_{\theta;a;a_{i}}({\mathfrak{C}}^{\prime}/a_{i})\cdot
A_{\pi;a;a_{i}}({\mathfrak{C}}^{\prime}/a_{i})\subseteq
A_{\varphi;a;a_{i}}({\mathfrak{C}}^{\prime}/a_{i}).$

######  Claim.

For any finite $I\subseteq\omega$

$\models\theta(\sigma_{I}(a),a,a_{i})\iff i\notin I.$

###### Proof of claim.

Firstly, take $i\not\in I$. Then, for every $j\in I$, $\sigma_{j}$ belongs to
the set $A_{\pi;a;a_{i}}({\mathfrak{C}}^{\prime}/a_{<\omega})$. By Claim 3.3,
the set $A_{\pi;a;a_{i}}({\mathfrak{C}}^{\prime}/a_{<\omega})$ is a group, and
so we get $\sigma_{I}\in
A_{\pi;a;a_{i}}({\mathfrak{C}}^{\prime}/a_{<\omega})$. Hence,
$\theta(\sigma_{I}(a),a,a_{i})$ holds.

Now take $i\in I$ and write $I:=I_{0}\sqcup\\{i\\}\sqcup I_{1}$, where
$I_{0}=\\{j\in I:j<i\\}$ and $I_{1}=\\{j\in I:j>i\\}$. For each $j\in
I_{0}\cup I_{1}$ we have $\sigma_{j}\in\
A_{\pi;a;a_{i}}({\mathfrak{C}}^{\prime}/a_{<\omega})$. Then,
$\theta(\sigma_{I}(a),a,a_{i})$ does not hold. Otherwise,

$\sigma_{I}=\sigma_{I_{0}}\sigma_{i}\sigma_{I_{1}}\in
A_{\theta;a;a_{i}}({\mathfrak{C}}^{\prime}/a_{<\omega}),$

which, by Claim 3.3 and the choice of $\theta$, implies

$\sigma_{i}\in A_{\varphi;a;a_{i}}({\mathfrak{C}}^{\prime}/a_{<\omega}),$

a contradiction with our choice of $\sigma_{i}$. ∎

The formula $\theta$ witnesses that $T$ has IP. ∎

When we write (NIP) in the statement of a result, it means that we assume that
the theory $T$ has NIP.

######  Lemma 3.6 (NIP).

Let $\pi(x,y,z)$ be a partial type over the empty set (with a
${\mathfrak{C}}^{\prime}$-small $z$), and let
$a_{0}\subseteq\mathfrak{C}^{\prime}$ be such that $\pi(x,y,a_{0})$ relatively
defines an equivalence relation on
$p\\!\upharpoonright_{a_{0}}\\!\\!(\mathfrak{C}^{\prime})$. Then, for any
$(a_{i})_{i<\lambda}$, where $\lambda\geq\beth_{(2^{(\lvert a_{0}\rvert+\lvert
x\rvert+\lvert T\rvert+\lvert A\rvert)})^{+}}$ and
$a_{i}\underset{A}{\equiv}a_{0}$ for all $i<\lambda$, there exists $i<\lambda$
such that

$\bigcap_{j\neq
i}\pi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime},a_{j})\cap(p\\!\upharpoonright_{a_{<\lambda}}\\!\\!({\mathfrak{C}}^{\prime}))^{2}\subseteq\pi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime},a_{i}).$

###### Proof.

Assume the conclusion does not hold. Then, for every $i<\lambda$

$\bigcap_{j\neq
i}\pi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime},a_{j})\cap(p\upharpoonright_{a_{<\lambda}}\\!\\!({\mathfrak{C}}^{\prime}))^{2}\not\subseteq\pi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime},a_{i}).$

Take pairs $(b_{i},c_{i})_{i<\lambda}$ witnessing it. Let
$(a_{i}^{\prime},b_{i}^{\prime},c_{i}^{\prime})_{i<\omega}\subseteq{\mathfrak{C}}^{\prime}$
be an $A$-indiscernible sequence obtained by extracting indiscernibles from
the sequence $(a_{i},b_{i},c_{i})_{i<\lambda}$ (e.g. see [BY03, Lemma 1.2]).
Then, since $p$ is $A$-invariant, for all $i<\omega$ the elements
$(a_{i}^{\prime},b_{i}^{\prime},c_{i}^{\prime})$ satisfy:

$\displaystyle(b_{i}^{\prime},c_{i}^{\prime})$ $\displaystyle\in\bigcap_{j\neq
k}\pi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime},a_{j}^{\prime})\cap(p\\!\upharpoonright_{a^{\prime}_{<\omega}}\\!\\!({\mathfrak{C}}^{\prime}))^{2};$
$\displaystyle(b_{i}^{\prime},c_{i}^{\prime})$
$\displaystyle\not\in\pi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime},a_{i}^{\prime});$
$\displaystyle a_{i}^{\prime}$
$\displaystyle\equiv_{A}a_{0}^{\prime}\equiv_{A}a_{0}.$

(Note that the $A$-invariance of $p$, together with the property of being an
extracted sequence, is used to ensure that $(b_{i}^{\prime},c_{i}^{\prime})$
belongs to
$p\\!\upharpoonright_{a^{\prime}_{<n}}\\!\\!({\mathfrak{C}}^{\prime})^{2}$ for
each $n\in\omega$.) By the indiscernibility of the sequence
$(a_{i}^{\prime},b_{i}^{\prime},c_{i}^{\prime})_{i<\omega}$, there exists a
formula $\varphi(x,y,z)$ implied by $\pi(x,y,z)$ such that for all $i<\omega$

$(b_{i}^{\prime},c_{i}^{\prime})\not\in\varphi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime},a_{i}^{\prime}).$

Take any $a\models p\\!\upharpoonright_{a^{\prime}_{<\omega}}$. Since $p$ is
$A$-invariant, $a_{i}^{\prime}\equiv_{A}a_{j}^{\prime}$ implies
$a_{i}^{\prime}\equiv_{a}a_{j}^{\prime}$. Moreover, since
$a_{i}^{\prime}\equiv_{A}a_{0}^{\prime}\equiv_{A}a_{0}$, $\pi(x,y,a_{0})$
relatively defines an equivalence relation on
$p\\!\upharpoonright_{a_{0}}\\!\\!(\mathfrak{C}^{\prime})$, and $p$ is
$A$-invariant, we get that $\pi(x,y,a_{i}^{\prime})$ relatively defines an
equivalence relation on
$p\\!\upharpoonright_{a_{i}^{\prime}}\\!\\!(\mathfrak{C}^{\prime})$ for all
$i<\omega$.

Hence, the sequence $(a_{i}^{\prime})_{i<\omega}$ together with $a$,
$\pi(x,y,z)$, and $\varphi(x,y,z)$ satisfies the assumptions of Lemma 3.2, and
so we get IP, which is a contradiction. ∎

The next theorem is the main result of this paper.

######  Theorem 3.7 (NIP).

Let $p(x)\in S_{x}(\mathfrak{C})$ be an $A$-invariant type with a
${\mathfrak{C}}$-small $x$. Assume that the degree of saturation of
${\mathfrak{C}}$ is at least $\beth_{(\beth_{2}(\lvert x\rvert+\lvert
T\rvert+\lvert A\rvert))^{+}}$. Then, there exists a finest equivalence
relation $E^{st}$ on $p({\mathfrak{C}}^{\prime})$ relatively type-definable
over a ${\mathfrak{C}}$-small set of parameters from ${\mathfrak{C}}$ and with
stable quotient $p({\mathfrak{C}}^{\prime})/E^{st}$.

###### Proof.

Let $\nu:=\beth_{(\beth_{2}(\lvert x\rvert+\lvert T\rvert+\lvert
A\rvert))^{+}}$.

######  Claim.

If for every countable partial type $\pi(x,y,z)$ over the empty set and
countable tuple $a_{0}$ from $\mathfrak{C}$ such that $\pi(x,y,a_{0})$
relatively defines an equivalence relation $E_{a_{0}}$ on
$p(\mathfrak{C}^{\prime})$ with stable quotient there is no sequence
$(a_{i})_{i<\nu}$ of (countable) tuples $a_{i}$ in ${\mathfrak{C}}$ such that
for all $i<\nu$ we have $a_{i}\underset{A}{\equiv}a_{0}$ and
$\bigcap_{j<i}E_{a_{j}}\not\subseteq E_{a_{i}}$, then the theorem holds.

###### Proof of claim.

Consider an arbitrary collection $(E_{i})_{i\in I}$ of of equivalence
relations on $p({\mathfrak{C}}^{\prime})$ relatively type-definable over a
${\mathfrak{C}}$-small subset of ${\mathfrak{C}}$ and with stable quotients.
Our goal is to prove that the intersection $\bigcap_{i\in I}E_{i}$ is a
relatively type-definable over a ${\mathfrak{C}}$-small subset of
${\mathfrak{C}}$ equivalence relation on $p({\mathfrak{C}}^{\prime})$ with
stable quotient.

Using Proposition 2.6, we can write each $E_{j}$ as $\bigcap_{i\in
I_{j}}F^{i}_{j}$, where each $F^{i}_{j}$ is a type-definable equivalence
relation on $p({\mathfrak{C}}^{\prime})$ countably relatively definable over a
countable subset of ${\mathfrak{C}}$. Since the $F^{i}_{j}$’s are coarser than
the corresponding $E_{j}$, each $F^{i}_{j}$ also has stable quotient. We can
now write

$\bigcap_{j\in I}E_{j}=\bigcap_{j\in I}\bigcap_{i\in I_{j}}F^{i}_{j}.$

Note that the number of possible countable types over $\emptyset$ whose
instances relatively define the $F^{i}_{j}$’s is bounded by $2^{\lvert
x\rvert+\lvert T\rvert}$, and the set of types over $A$ of the countable
tuples of parameters used in the relative definitions of the $F^{i}_{j}$’s is
bounded by $2^{\lvert T\rvert+\lvert A\rvert}$. Hence, by the assumptions of
the claim, the intersection $\bigcap_{j\in I}E_{j}$ coincides with an
intersection $\bigcap_{k\in K}F^{i_{k}}_{j_{k}}$, where $\lvert K\rvert\leq
2^{\lvert T\rvert+\lvert A\rvert}\times 2^{\lvert T\rvert+\lvert
x\rvert}\times\nu=\nu$. In fact, since $2^{\lvert T\rvert+|A|+\lvert x\rvert}$
is strictly smaller than the cofinality of $\nu$, we can even get $|K|<\nu$.
Finally, by [HP18, Remark 1.4], $\bigcap_{k\in K}F^{i_{k}}_{j_{k}}$ is a
relatively type-definable over a ${\mathfrak{C}}$-small subset of
${\mathfrak{C}}$ (as ${\mathfrak{C}}$ is $\nu$-saturated) equivalence relation
on $p({\mathfrak{C}}^{\prime})$ with stable quotient. ∎

Suppose the theorem fails. By the claim, there exists a countable type
$\pi(x,y,z)$ over $\emptyset$ and a countable tuple $a_{0}$ in
${\mathfrak{C}}$ such that $\pi(x,y,a_{0})$ relatively defines an equivalence
relation on $p({\mathfrak{C}}^{\prime})$ with
${\raisebox{1.99997pt}{$p({\mathfrak{C}}^{\prime})$}\left/\raisebox{-1.99997pt}{$\pi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime},a_{0})\cap
p({\mathfrak{C}}^{\prime})^{2}$}\right.}$ stable and there is
$(a_{i})_{i<\nu}\subseteq{\mathfrak{C}}$ such that for all $i<\nu$,
$a_{i}\equiv_{A}a_{0}$ and
$\bigcap_{j<i}\pi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime},a_{j})\cap
p({\mathfrak{C}}^{\prime})^{2}\not\subseteq\pi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime},a_{i})$.
By Corollary 2.7, enlarging $a_{0}$, we can assume that $a_{0}$ enumerates an
$\aleph_{0}$-saturated model in $L_{A}$ of size at most $2^{|T|+|A|}$ and
$\pi(x,y,a_{0})$ relatively defines an equivalence relation on
$p\\!\upharpoonright_{a_{0}}\\!\\!({\mathfrak{C}}^{\prime})$; by Lemma 2.5,
this relation also yields a stable quotient on
$p\\!\upharpoonright_{a_{0}}\\!\\!({\mathfrak{C}}^{\prime})$.

Let $(b_{i},c_{i})_{i<\nu}$ be a sequence witnessing that
$\bigcap_{j<i}\pi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime},a_{j})\cap
p({\mathfrak{C}}^{\prime})^{2}\not\subseteq\pi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime},a_{i})$.
Let
$(a_{i}^{\prime},b_{i}^{\prime},c_{i}^{\prime})_{i<\nu}\subseteq{\mathfrak{C}}^{\prime}$
be an $A$-indiscernible sequence extracted from $(a_{i},b_{i},c_{i})_{i<\nu}$.
Then, since $p$ is $A$-invariant, we get that for all $i<\nu$

$(b_{i}^{\prime},c_{i}^{\prime})\in\left(\bigcap_{j<i}\pi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime},a^{\prime}_{j})\cap(p\\!\upharpoonright_{a^{\prime}_{<\nu}}\\!\\!({\mathfrak{C}}^{\prime}))^{2}\right)\setminus\pi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime},a^{\prime}_{i}).$

Moreover, since $a_{0}^{\prime}\equiv_{A}a_{0}$ and $p$ is $A$-invariant, we
get that $\pi(x,y,a_{0}^{\prime})$ relatively defines an equivalence relation
on $p\\!\upharpoonright_{a_{0}^{\prime}}({\mathfrak{C}}^{\prime})$, and we
also have $a_{i}^{\prime}\equiv_{A}a_{0}^{\prime}$ for all $i<\nu$. Therefore,
by Lemma 3.6, there exists some $\beta<\nu$ such that

$(*)\;\;\;\;\;\;\bigcap_{\alpha\neq\beta}\pi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime},a_{\alpha}^{\prime})\cap(p\\!\upharpoonright_{a_{<\nu}^{\prime}}\\!\\!({\mathfrak{C}}^{\prime}))^{2}\subseteq\pi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime},a_{\beta}^{\prime}).$

In the sequence $(a_{i}^{\prime},b_{i}^{\prime},c_{i}^{\prime})_{i<\nu}$, let
us insert a sequence
$(d^{\prime}_{i},e^{\prime}_{i},f^{\prime}_{i})_{i<\omega}$ from
${\mathfrak{C}}^{\prime}$ in place of the element
$(a_{\beta}^{\prime},b_{\beta}^{\prime},c_{\beta}^{\prime})$ so that the
resulting sequence is still $A$-indiscernible. Then, since $p$ is
$A$-invariant, for all $i<\omega$

$(**)\;\;\;\;\;\;(e_{i}^{\prime},f_{i}^{\prime})\in\left(\bigcap_{j<i}\pi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime},d_{j}^{\prime})\cap(p\\!\upharpoonright_{a^{\prime}_{\begin{subarray}{c}\alpha<\nu\\\
\alpha\neq\beta\end{subarray}},d^{\prime}_{<\omega}}\\!\\!({\mathfrak{C}}^{\prime}))^{2}\right)\setminus\pi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime},d_{i}^{\prime}).$

Hence, due to the $A$-indiscernibility of the sequence
$(d_{i}^{\prime},e_{i}^{\prime},f_{i}^{\prime})_{i<\omega}$, there exists some
formula $\varphi$ implied by $\pi$ such that for all $i<\omega$ we have
$(e_{i}^{\prime},f_{i}^{\prime})\not\in\varphi({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime},d_{i}^{\prime})$.

Moreover, since $d_{i}^{\prime}\equiv_{A}a_{0}^{\prime}$ and using the
$A$-invariance of $p$, we get that $\pi(x,y,d_{i}^{\prime})$ relatively
defines an equivalence relation on
$p\\!\upharpoonright_{d_{i}^{\prime}}\\!\\!({\mathfrak{C}}^{\prime})$.

Let us consider the set

$X:=p\\!\upharpoonright_{a^{\prime}_{\begin{subarray}{c}\alpha<\nu\\\
\alpha\neq\beta\end{subarray}}}\\!\\!({\mathfrak{C}}^{\prime}).$

By the above choices and $A$-invariance of $p$, the type
$\bigcup_{\begin{subarray}{c}\alpha<\nu\\\
\alpha\neq\beta\end{subarray}}\pi(x,y,a^{\prime}_{\alpha})$ relatively defines
an equivalence relation $E$ on $X$ with stable quotient, and the sequence
$(d_{i}^{\prime},[e_{i}^{\prime}]_{E},[f_{i}^{\prime}]_{E})$ is indiscernible
over

$B:=A\cup\\{a^{\prime}_{\alpha}:\alpha<\nu;\alpha\neq\beta\\}.$

Hence,

$\operatorname{{tp}}\left({\raisebox{1.99997pt}{$(d_{j}^{\prime},[e_{i}^{\prime}]_{E},[f_{i}^{\prime}]_{E})$}\left/\raisebox{-1.99997pt}{$B$}\right.}\right)=\operatorname{{tp}}\left({\raisebox{1.99997pt}{$(d_{i}^{\prime},[e_{j}^{\prime}]_{E},[f_{j}^{\prime}]_{E})$}\left/\raisebox{-1.99997pt}{$B$}\right.}\right)$

for all $j<i$.

Let $E_{i}$ be the equivalence relation relatively defined by the partial type
$\pi(x,y,d_{i}^{\prime})$ on
$p\\!\upharpoonright_{a^{\prime}_{\begin{subarray}{c}\alpha<\nu\\\
\alpha\neq\beta\end{subarray}},d_{i}^{\prime}}\\!\\!({\mathfrak{C}}^{\prime})$.
By $(**)$, $e_{i}^{\prime}E_{j}f_{i}^{\prime}$ for all $j<i$. Using this and
the previous paragraph, we will deduce that
$e_{j}^{\prime}E_{i}f_{j}^{\prime}$ for all $j<i$.

Indeed, take any $j<i$. Since
$\operatorname{{tp}}\left({\raisebox{1.99997pt}{$(d_{j}^{\prime},[e_{i}^{\prime}]_{E},[f_{i}^{\prime}]_{E})$}\left/\raisebox{-1.99997pt}{$B$}\right.}\right)=\operatorname{{tp}}\left({\raisebox{1.99997pt}{$(d_{i}^{\prime},[e_{j}^{\prime}]_{E},[f_{j}^{\prime}]_{E})$}\left/\raisebox{-1.99997pt}{$B$}\right.}\right)$,
there is $\sigma\in\operatorname{{Aut}}({\mathfrak{C}}^{\prime}/B)$ such that
$\sigma(d_{j}^{\prime},[e_{i}^{\prime}]_{E},[f_{i}^{\prime}]_{E})=(d_{i}^{\prime},[e_{j}^{\prime}]_{E},[f_{j}^{\prime}]_{E})$.
Then, by the $A$-invariance of $p$, $\sigma[E_{j}]=E_{i}$. Thus, since
$e_{i}^{\prime}E_{j}f_{i}^{\prime}$, we conclude that
$\sigma(e_{i}^{\prime})E_{i}\sigma(f_{i}^{\prime})$. On the other hand, by
$(*)$ and $A$-invariance of $p$, we have
$E\upharpoonright_{\operatorname{dom}(E_{i})}\subseteq E_{i}$, which together
with the fact that $e_{j}^{\prime}E\sigma(e_{i}^{\prime})$,
$f_{j}^{\prime}E\sigma(f_{i}^{\prime})$, and
$e_{j}^{\prime},f_{j}^{\prime},\sigma(e_{i}^{\prime}),\sigma(f_{i}^{\prime})\in\operatorname{dom}(E_{i})$
gives us $e_{j}^{\prime}E_{i}\sigma(e_{i}^{\prime})$ and
$f_{j}^{\prime}E_{i}\sigma(f_{i}^{\prime})$. Therefore,
$e_{j}^{\prime}E_{i}f_{j}^{\prime}$, as required.

We have shown that the sequence
$(d_{i}^{\prime},e_{i}^{\prime},f_{i}^{\prime})$ satisfies:

$\displaystyle\pi(e_{j}^{\prime},f_{j}^{\prime},d_{i}^{\prime})$
$\displaystyle\text{ for all }i\neq j;\hskip 3.0pti,j<\omega;$
$\displaystyle\neg\varphi(e_{i}^{\prime},f_{i}^{\prime},d_{i}^{\prime})$
$\displaystyle\text{ for all }i<\omega.$

Take any $a\models p\\!\upharpoonright_{d^{\prime}_{<\omega}}$. Since
$d_{i}^{\prime}\equiv_{A}d_{0}^{\prime}$ for all $i<\omega$ and $p$ is
$A$-invariant, we get that $d_{i}^{\prime}\equiv_{a}d_{0}^{\prime}$ for all
$i<\omega$. Thus, the sequence $(d_{i}^{\prime})_{i<\omega}$ satisfies the
assumption of Lemma 3.2, and so we get IP, a contradiction. ∎

We end this section with some comments on whether the large saturation
condition in Theorem 3.7 is necessary or could be eliminated.

Note that in the above proof, in order to extract indiscernibles from the
sequence $(a_{i},b_{i},c_{i})_{i<\lambda}$, we need to know that $\nu$ is at
least $\beth_{(2^{2^{|T|+|A|}+\lvert
x\rvert+|T|+|A|})^{+}}=\beth_{(2^{2^{|T|+|A|}+\lvert x\rvert})^{+}}$. On the
other hand, the proof of the claim requires that any number smaller than $\nu$
is bounded in ${\mathfrak{C}}$. That is why the whole proof requires that
${\mathfrak{C}}$ is at least $\beth_{(2^{2^{|T|+|A|}+\lvert
x\rvert})^{+}}$-saturated. In the statement of the theorem, it is enough to
assume that ${\mathfrak{C}}$ is $\beth_{(2^{2^{|T|+|A|}+\lvert
x\rvert})^{+}}$-saturated; we used a bigger degree of saturation, which is
notationally more concise.

Although our proof uses essentially the assumption on the degree of
saturation, one could still try to transfer the existence of the finest
relatively type-definable equivalence relation from big models to their
elementary substructures.

Let ${\mathfrak{C}}\prec{\mathfrak{C}}_{1}\prec{\mathfrak{C}}^{\prime}$ be
such that ${\mathfrak{C}}_{1}$ is ${\mathfrak{C}}^{\prime}$-small and at least
as saturated as ${\mathfrak{C}}$, and let $p_{1}(x)\in S({\mathfrak{C}}_{1})$
be the unique $A$-invariant extension of $p(x)$.

While Corollary 2.9 allows us to transfer the existence of the finest
relatively type-definable over a ${\mathfrak{C}}$-small subset of
${\mathfrak{C}}$ equivalence relation on $p({\mathfrak{C}}^{\prime})$ with
stable quotient to the finest relatively type-definable over a
${\mathfrak{C}}_{1}$-small subset of ${\mathfrak{C}}_{1}$ equivalence relation
on $p_{1}({\mathfrak{C}}^{\prime})$, in order to eliminate the specific
saturation assumption in Theorem 3.7, we would need to have a transfer going
in the other direction. In Corollary 2.10, we proved such a transfer but only
under the additional assumption that the finest relatively type-definable over
a ${\mathfrak{C}}_{1}$-small subset of ${\mathfrak{C}}_{1}$ equivalence
relation $E$ on $p_{1}({\mathfrak{C}}^{\prime})$ is relatively type-definable
over a ${\mathfrak{C}}$-small subset. Therefore, the specific saturation
assumption could be eliminated if we could answer positively the following
question.

######  Question 3.8.

In the context of Theorem 3.7, is $E^{st}$ always relatively type-definable
over $A$?

In the examples studied in the next section, this turns out to be true. Also,
in the context of type-definable groups studied in [HP18], $G^{st}$ is type-
definable over the parameters over which $G$ is type-definable.

##  4\. Examples

We present two examples where $E^{st}$ is computed explicitly, the second
example is based on [KP22, Setcion 4]. In fact, in both examples, we give full
classifications of all relatively type-definable over ${\mathfrak{C}}$-small
subsets of ${\mathfrak{C}}$ equivalence relations on
$p({\mathfrak{C}}^{\prime})$, for suitably chosen $p\in S({\mathfrak{C}})$.

### Example 1

Let our language be
$L:=\\{R_{r}(x,y),f_{s}(x):r\in\mathbb{Q}^{+},s\in\mathbb{Q}\\}$ and $T$ be
the theory of $(\mathbb{R},R_{r},f_{s})_{r\in\mathbb{Q}^{+},s\in\mathbb{Q}}$,
where $f_{s}(x):=x+s$ and $R_{r}(x,y)$ holds if and only if $0\leq y-x\leq r$.

We define the directed distance between two points as a function

$d:{\mathfrak{C}}^{\prime}\times{\mathfrak{C}}^{\prime}\to\mathbb{R}\sqcup\mathbb{Q}_{+}\sqcup\mathbb{Q}_{-}\sqcup\\{\infty\\}$

(where $\mathbb{Q}_{+}$ and $\mathbb{Q}_{-}$ are disjoint copies of
$\mathbb{Q}$ which are disjoint from $\mathbb{R}\sqcup\\{\infty\\}$)
satisfying:

$\displaystyle d(x,y)=q\in\mathbb{Q}\iff y=f_{q}(x);$ $\displaystyle
d(x,y)=r\in\mathbb{R}^{+}\setminus\mathbb{Q}\iff\forall
s_{1},s_{2}\in\mathbb{Q}^{+}\text{ such that }s_{1}<r<s_{2},\neg
R_{s_{1}}(x,y)\wedge R_{s_{2}}(x,y);$ $\displaystyle
d(x,y)=q_{+}\in\mathbb{Q}_{+}\iff y\neq f_{q}(x)\text{ is infinitely close to
}f_{q}(x)\text{ on the right;}$ $\displaystyle
d(x,y)=q_{-}\in\mathbb{Q}_{-}\iff y\neq f_{q}(x)\text{ is infinitely close to
}f_{q}(x)\text{ on the left;}$ $\displaystyle
d(x,y)=\infty\iff\neg(R_{s}(x,y)\lor R_{s}(y,x))\text{ for all
}s\in\mathbb{Q}^{+}.$

We complete the definition of $d$ extending it symmetrically in the negative
irrational case, i.e $d(y,x):=-d(x,y)$ whenever
$d(x,y)\in\mathbb{R}^{+}\setminus\mathbb{Q}$. This clearly gives us a well
defined function $d$. Addition on $\mathbb{R}$ is extended to
$\mathbb{R}\sqcup\mathbb{Q}_{+}\sqcup\mathbb{Q}_{-}\sqcup\\{\infty\\}$ in the
natural way, in particular:

  * •

$q^{\prime}+q_{+}:=(q^{\prime}+q)_{+}\text{ and
}q^{\prime}+q_{-}:=(q^{\prime}+q)_{-}$ for any $q,q^{\prime}\in\mathbb{Q}$;

  * •

$r+\infty:=\infty\text{ for any
}r\in\mathbb{R}\cup\mathbb{Q}_{+}\cup\mathbb{Q}_{-}\cup\\{\infty\\}.$

######  Lemma 4.1.

Properties of the distance:

  1. (1)

$d(a,f_{q}(b))=q+d(a,b)$ and $d(f_{q}(a),b)=-q+d(a,b)$;

  2. (2)

For any distinct real numbers $r_{1},r_{2}$, if $d(a,b)=r_{1}$ and
$d(a,c)=r_{2}$, then $d(b,c)=r_{2}-r_{1}$;

  3. (3)

For any irrational $r$, if $d(a,b)=r$ and $d(b,c)=0_{\pm}$, then $d(a,c)=r$;

  4. (4)

For any irrational $r$, if $d(a,b)=r=d(a,c)$, then $d(b,c)=0_{\pm}$.

###### Proof.

$(1)$ follows from the definition of the distance.

$(2)$ Since the rational case is covered in $(1)$, we can assume that
$r_{1},r_{2}$ are irrationals. Consider the case $0<r_{1}<r_{2}$; other cases
are similar. Let $q$ be any rational bigger than $r_{2}-r_{1}$. We can write
$q$ as $q_{2}-q_{1}$, where $q_{1},q_{2}$ are rationals such that
$q_{1}<r_{1}<r_{2}<q_{2}$. Since $R_{q^{\prime}}(a,b)$ and $\neg
R_{q^{\prime}}(a,c)$ hold for some $q^{\prime}\in\mathbb{Q}^{+}$ (for any
$r_{1}<q^{\prime}<r_{2}$) and $R_{q_{1}}(a,b)$ does not hold,
$R_{q_{2}-q_{1}}(b,c)$ has to hold; otherwise $R_{q_{2}}(a,c)$ would not hold,
contradicting $d(a,c)=r_{2}$. Hence, $d(b,c)\leq q$

Let now $q$ be any positive rational smaller than $r_{2}-r_{1}$. We can write
$q$ as $q_{2}-q_{1}$, where $q_{1},q_{2}$ are rationals such that
$r_{1}<q_{1}<q_{2}<r_{2}$. Since $R_{q_{1}}(a,b)$ holds,
$R_{q_{2}-q_{1}}(b,c)$ cannot hold; otherwise, $R_{q_{2}}(a,c)$ would hold,
contradicting $d(a,c)=r_{2}$. Hence, $d(b,c)\geq q$.

$(3)$ Consider the case $r>0$ and $d(b,c)=0_{+}$; the other cases are
analogous. Let $q$ be any rational bigger than $r$. We can write $q$ as
$q_{1}+q_{2}$, where $q_{1},q_{2}$ are rationals, $q_{1}>r$, and $q_{2}>0$.
Then, $R_{q_{1}}(a,b)$ and $R_{q_{2}}(b,c)$ hold, hence so does
$R_{q_{1}+q_{2}}(a,c)$. This implies that $d(a,c)\leq q$. Let now $q$ be any
positive rational smaller than $r$. Then, $R_{q}(a,c)$ cannot hold; otherwise
it would imply $R_{q}(a,b)$, a contradiction.

$(4)$ Consider the case $r>0$; the other case is similar. Consider any
rationals $q_{1}$, $q_{2}$ satisfying $0<q_{1}<r<q_{2}$. Then,
$R_{q_{2}-q_{1}}(f_{q_{1}}(a),b)\wedge R_{q_{2}-q_{1}}(f_{q_{1}}(a),c)$ holds,
which imply $R_{q_{2}-q_{1}}(b,c)\vee R_{q_{2}-q_{1}}(c,b)$. Since $q_{2}$ and
$q_{1}$ were arbitrary, this means that $b$ and $c$ are infinitesimally close.
∎

It is clear that the distance determines the quantifier-free type of a pair
$(a,b)$. Since our language only contains unary and binary symbols, the
collection of distances between the elements of a given $n$-tuple determines
its quantifier-free type.

######  Proposition 4.2.

The theory $T$ has NIP and quantifier elimination.

###### Proof.

$T$ has NIP, because it is a reduct of an o-minimal theory.

We prove quantifier elimination using a back and forth argument. Let
$\mathcal{M}$ and $\mathcal{N}$ be two $\aleph_{0}$-saturated models of $T$
and let $(a_{1},\dots,a_{n})$ and $(b_{1},\dots,b_{n})$ be tuples of elements
of $\mathcal{M}$ and $\mathcal{N}$, respectively, satisfying the same
quantifier free type. Choose a new element $a_{n+1}\in\mathcal{M}$. There are
three cases:

  1. (1)

$a_{n+1}$ is infinitely far from $a_{1},\dots,a_{n}$;

  2. (2)

$a_{n+1}=f_{q}(a_{i})$ for some $q\in\mathbb{Q}$ and $i=1,\dots,n$;

  3. (3)

$a_{n+1}$ is related (i.e., at finite distance) to some of the $a_{i}$’s but
is not equal to $f_{q}(a_{i})$ for any $q\in\mathbb{Q}$ and $i=1,\dots,n$.

In the first two cases, by $\aleph_{0}$-saturation, we can clearly choose
$b_{n+1}\in\mathcal{N}$ such that $(a_{1},\dots,a_{n+1})$ and
$(b_{1},\dots,b_{n+1})$ have the same quantifier-free type. Now, let us tackle
the third case.

In the third case, by removing the elements of the sequence
$(a_{1},\dots,a_{n})$ which are at infinite distance from $a_{n+1}$ as well as
the corresponding elements of the sequence $(b_{1},\dots,b_{n})$, we may
assume that no $a_{i}$ is infinitely far from $a_{n+1}$. Note also that for
each $i<n$ there is at most one $q_{i}\in\mathbb{Q}$ such that
$f_{q_{i}}(a_{i})$ is infinitesimally close to $a_{n+1}$. Let $A$ be the set
of all such $f_{q_{i}}(a_{i})$’s.

First, consider the case when $A\neq\emptyset$. Then $A$ is a finite set
totally ordered by the relation $R_{1}(x,y)$ and all elements in $A$ are
infinitesimally close to each other and to $a_{n+1}$. Let
$B:=\\{f_{q_{i}}(b_{i}):f_{q_{i}}(a_{i})\in A\\}$. Note that all the elements
in $B$ are infinitesimally close to each other and that the map sending
$f_{q_{i}}(a_{i})$ to $f_{q_{i}}(b_{i})$ is an $R_{1}$-order isomorphism.
Then, by density, there exists $b_{n+1}$ with the same $R_{1}$-relative
position to the elements in $B$ as $a_{n+1}$ to the corresponding elements in
$A$. Hence, $d(b_{n+1},f_{q_{i}}(b_{i}))=d(a_{n+1},f_{q_{i}}(a_{i}))$ for each
$f_{q_{i}}(a_{i})\in A$, and, by Lemma 4.1, this implies

$\operatorname{{tp^{qf}}}(b_{1},\dots,b_{n},b_{n+1})=\operatorname{{tp^{qf}}}(a_{1},\dots,a_{n},a_{n+1}).$

In the case when $A=\emptyset$, $d(a_{i},a_{n+1})$ is irrational for every
$i\leq n$. Pick $b_{n+1}$ so that $d(b_{1},b_{n+1})=d(a_{1},a_{n+1})$. Since
$A=\emptyset$, by Lemma 4.1(4), we get that $d(a_{1},a_{n+1})\neq
d(a_{1},a_{i})$ for all $1<i\leq n$. Hence, Lemma 4.1 implies that
$\operatorname{{tp^{qf}}}(b_{1},\dots,b_{n},b_{n+1})=\operatorname{{tp^{qf}}}(a_{1},\dots,a_{n},a_{n+1}).$
∎

Let $p\in S_{x}({\mathfrak{C}})$ be the $0$-invariant complete global type
determined by

$\bigwedge_{c\in{\mathfrak{C}}}\bigwedge_{n\in\omega}\neg R_{n}(x,c)\wedge\neg
R_{n}(c,x).$

We denote by $E(x,y)$ the equivalence relation on ${\mathfrak{C}}^{\prime}$
defined by

$\bigwedge_{r\in\mathbb{Q}^{+}}R_{r}(x,y)\vee R_{r}(y,x)$

and by $E\\!\upharpoonright_{p}$ the equivalence relation on
$p({\mathfrak{C}}^{\prime})$ relatively defined by the same partial type.

######  Lemma 4.3.

The hyperdefinable set
${\mathfrak{C}}^{\prime}/E({\mathfrak{C}}^{\prime},{\mathfrak{C}}^{\prime})$
is stable.

###### Proof.

By [KP22, Theorem 2.10], it is enough to prove that for any
$A\subseteq{\mathfrak{C}}^{\prime}$ with $|A|\leq\mathfrak{c}$ we have
$|S_{{\mathfrak{C}}^{\prime}/E}(A)|\leq\mathfrak{c}$.

Clearly, the elements $c$ and $c^{\prime}$ are in the same $E$-class if and
only if $c=c^{\prime}$ or $d(c,c^{\prime})=0_{\pm}$. Note that whenever
$d(c,a)=d(c^{\prime},a)\neq\infty$, then $cEc^{\prime}$. Therefore, specifying
the distance $d(c,a)\neq\infty$ from $c$ to a given element $a\in A$
determines the class $[c]_{E}$. On the other hand, by q.e., the condition
saying that $d(c,a)=\infty$ for all $a\in A$ determines
$\operatorname{{tp}}(c/A)$. Therefore,
$|S_{{\mathfrak{C}}^{\prime}/E}(A)|\leq\mathfrak{c}\times\mathfrak{c}+1=\mathfrak{c}$.
∎

######  Proposition 4.4.

The only equivalence relations on $p({\mathfrak{C}}^{\prime})$ relatively
type-definable over a ${\mathfrak{C}}$-small subset of ${\mathfrak{C}}$ are
equality, $E\\!\upharpoonright_{p}$, and the total equivalence relation.

###### Proof.

Let $F(x,y)$ be any equivalence relation on $p({\mathfrak{C}}^{\prime})$
relatively type-definable over a ${\mathfrak{C}}$-small subset of
${\mathfrak{C}}$. Let $S_{n}(x,y):=R_{n}(x,y)\vee R_{n}(y,x)$. There are two
cases.

Case 1: There are $a,b\in p({\mathfrak{C}}^{\prime})$ such that $aFb$ and
$\models\bigwedge_{n\in\mathbb{N}}\neg S_{n}(a,b)$. For any $c,d\in
p({\mathfrak{C}}^{\prime})$ we can find $e\in p({\mathfrak{C}}^{\prime})$ such
that $\models\bigwedge_{n\in\mathbb{N}}\neg
S_{n}(c,e)\wedge\bigwedge_{n\in\mathbb{N}}\neg S_{n}(d,e)$. Hence, by q.e.,

$(d,e)\equiv_{{\mathfrak{C}}}(a,b)\equiv_{{\mathfrak{C}}}(c,e).$

As $F$ is ${\mathfrak{C}}$-invariant, we conclude that $cFd$. This implies
that $F$ is the total relation.

Case 2: For any $a,b\in p({\mathfrak{C}}^{\prime})$ with $aFb$ there exists
$n\in\mathbb{N}$ such that $\models S_{n}(a,b)$.

First, we show that $aFb$ implies $aE\\!\upharpoonright_{p}b$. Assume that it
is not the case. Then there exists $m\in\mathbb{Q}^{+}$ such that $aFb$ and
$\neg S_{m}(a,b)$. On the other hand, $S_{n}(a,b)$ for some $n\in\mathbb{N}$.
Since $a\equiv_{\mathfrak{C}}b$, there is
$\sigma\in\operatorname{Aut}({\mathfrak{C}}^{\prime}/{\mathfrak{C}})$
satisfying $\sigma(a)=b$. Let $b_{i}:=\sigma^{i}(a)$ for $i<\omega$. Clearly,

$(a,b)\equiv_{{\mathfrak{C}}}(b,b_{2})\equiv_{{\mathfrak{C}}}(b_{2},b_{3})\equiv_{{\mathfrak{C}}}\cdots.$

We deduce that for all $k\in\mathbb{N}$, $aFb_{k}$ and $\models\neg
S_{km}(a,b_{k})$. Hence, by compactness, there exists $b^{\prime}\in
p({\mathfrak{C}}^{\prime})$ such that $aFb^{\prime}$ and $\models\neg
S_{n}(a,b^{\prime})$ for all $n\in\mathbb{N}$, contradicting the hypothesis of
the second case.

Finally, if $F$ is not equality, there exist elements $a\neq b\in
p({\mathfrak{C}}^{\prime})$ such that $aFb$, and so
$aE\\!\upharpoonright_{p}b$ by the last paragraph. Take any distinct $c,d\in
p({\mathfrak{C}}^{\prime})$ satisfying $cE\\!\upharpoonright_{p}d$. Then, by
q.e., either $(a,b)\equiv_{{\mathfrak{C}}}(c,d)$ or
$(a,b)\equiv_{{\mathfrak{C}}}(d,c)$. Both cases imply $cFd$, which means that
$F$ and $E\\!\upharpoonright_{p}$ are the same equivalence relation. ∎

Since $p({\mathfrak{C}}^{\prime})$ is not stable, we obtain the following:

######  Corollary 4.5.

The equivalence relation $E\\!\upharpoonright_{p}$ is the finest equivalence
relation on $p({\mathfrak{C}}^{\prime})$ relatively type-definable over a
${\mathfrak{C}}$-small set of parameters from ${\mathfrak{C}}$ and with stable
quotient, that is $E^{st}=E\\!\upharpoonright_{p}$.

### Example 2

This example is based on [KP22, Section 4]. We work in the language
$L:=\\{+,-,1,R_{r}(x,y):r\in\mathbb{Q}^{+}\\}$ and our theory $T$ is
$\operatorname{{Th}}((\mathbb{R},+,-,1,R_{r}(x,y))_{r\in\mathbb{Q}^{+}})$,
where $\mathbb{R}\models R_{r}(x,y)$ if and only if $0\leq y-x\leq r$.

The next result was proven in [KP22, Proposition 4.1, Proposition 4.8].

######  Fact 4.6.

The theory $T$ has $NIP$ and quantifier elimination.

Without loss of generality, for convenience we can assume that
${\mathfrak{C}}^{\prime}$ is a reduct of a monster model of
$\operatorname{{Th}}(\mathbb{R},+,-,1,\leq)$. So it makes sense to use $\leq$.
Let $p\in S_{x}({\mathfrak{C}})$ be the complete $0$-invariant global type
determined by

$\\{\neg R_{r}(x,c)\wedge\neg
R_{r}(c,x):c\in{\mathfrak{C}},r\in\mathbb{Q}^{+}\\}.$

As in the previous example, let $S_{r}(x,y):=R_{r}(x,y)\vee R_{r}(y,x)$. We
say that $x,y$ are related if $S_{r}(x,y)$ holds for some
$r\in\mathbb{Q}^{+}$. We denote by $E(x,y)$ the equivalence relation on
$p({\mathfrak{C}}^{\prime})$ relatively defined by

$\bigwedge_{r\in\mathbb{Q}^{+}}S_{r}(x,y).$

In other words, this is the relation on $p({\mathfrak{C}}^{\prime})$ of lying
in the same coset modulo the subgroup of all infinitesimals in
${\mathfrak{C}}^{\prime}$ which will be denoted by $\mu$.

Other possible relatively type-definable over a ${\mathfrak{C}}$-small subset
of ${\mathfrak{C}}$ equivalence relations on $p({\mathfrak{C}}^{\prime})$ are
as follows. Take any $c\in{\mathfrak{C}}$. Let $E_{c}$ be the equivalence
relation on $p({\mathfrak{C}}^{\prime})$ given by $xE_{c}y$ if and only if
$x=y$ or $x+y=c$. It is clear that this is an equivalence relation on
$p({\mathfrak{C}}^{\prime})$ relatively defined by a type over $c$. We also
have the equivalence relation $E_{c}^{\mu}$ given by $xE_{c}^{\mu}y$ if and
only if $xEy$ or $(x+y)Ec$, which is also relatively defined by a type over
$c$.

For any non-empty ${\mathfrak{C}}$-small set $A$ of positive infinitesimals in
${\mathfrak{C}}$ we will consider the equivalence relation $E_{A}$ on
$p({\mathfrak{C}}^{\prime})$ given as

$\bigwedge_{a\in A}\bigwedge_{n\in\mathbb{N}^{+}}|x-y|\leq\frac{1}{n}a.$

Note that this relation is relatively type-definable over $A$ on
$p({\mathfrak{C}}^{\prime})$ in the original language $L$ by the following
condition

$\bigwedge_{a\in A}\bigwedge_{n\in\mathbb{N}^{+}}R_{1}(n(x-y),a)\wedge
R_{1}(n(y-x),a).$

One can also combine the above examples to produce one more class of
equivalence relations on $p({\mathfrak{C}}^{\prime})$. Take any
$c\in{\mathfrak{C}}$ and any non-empty ${\mathfrak{C}}$-small set $A$ of
positive infinitesimals in ${\mathfrak{C}}$. Let $\mu_{A}$ be the
infinitesimals in ${\mathfrak{C}}^{\prime}$ defined by

$\bigwedge_{a\in A}\bigwedge_{n\in\mathbb{N}^{+}}|x|\leq\frac{1}{n}a.$

Then we have the equivalence relation $E_{A,c}$ on
$p({\mathfrak{C}}^{\prime})$ given by $xE_{A,c}y$ if and only if $xE_{A}y$ or
$(x+y)E_{A}c$, which is clearly relatively defined on
$p({\mathfrak{C}}^{\prime})$ by a type over $Ac$.

######  Theorem 4.7.

The only equivalence relations on $p({\mathfrak{C}}^{\prime})$ relatively
type-definable over a ${\mathfrak{C}}$-small subset of ${\mathfrak{C}}$ are:
the total equivalence relation, equality, $E$, the relations of the form
$E_{c}$ or $E_{c}^{\mu}$ (where $c\in{\mathfrak{C}}$), and the relations of
the form $E_{A}$ or $E_{A,c}$ for any non-empty ${\mathfrak{C}}$-small set $A$
of positive infinitesimals in ${\mathfrak{C}}$ and any $c\in{\mathfrak{C}}$.

In the proof below, by a non-constant term $t(x,y)$ (in the language $L$) we
mean an expression $nx+my+k$, where $m,n,k\in\mathbb{Z}$ and $m\neq 0$ or
$n\neq 0$.

###### Proof.

Let $F(x,y)$ be an arbitrary equivalence relation on
$p({\mathfrak{C}}^{\prime})$ relatively type-definable over a
${\mathfrak{C}}$-small subset of ${\mathfrak{C}}$.

######  Claim.

Either $F$ is the total equivalence relation, or $F$ is finer than
$E_{c}^{\mu}$ (i.e., $F\subseteq E_{c}^{\mu}$) for some $c\in{\mathfrak{C}}$ .

###### Proof of Claim.

We consider two cases.

Case 1: There are $a$, $b\in p({\mathfrak{C}}^{\prime})$ such that $aFb$ and
$\models\bigwedge_{n\in\mathbb{Q}^{+}}\bigwedge_{c\in{\mathfrak{C}}}\neg
S_{n}(t(a,b),c)$ for all non-constant terms $t(x,y)$. Take any
$a^{\prime},b^{\prime}\in p({\mathfrak{C}}^{\prime})$. By compactness and
$|{\mathfrak{C}}|^{+}$-saturation of ${\mathfrak{C}}^{\prime}$, we can find
$d^{\prime}\in p({\mathfrak{C}}^{\prime})$ such that
$\models\bigwedge_{n\in\mathbb{Q}^{+}}\bigwedge_{c\in{\mathfrak{C}}}\neg
S_{n}(t(a^{\prime},d^{\prime}),c)$ and
$\models\bigwedge_{n\in\mathbb{Q}^{+}}\bigwedge_{c\in{\mathfrak{C}}}\neg
S_{n}(t(b^{\prime},d^{\prime}),c)$ for all non-constant terms $t(x,y)$. Then,
by q.e. and [KP22, Remark 4.6],
$(a^{\prime},d^{\prime})\equiv_{{\mathfrak{C}}}(a,b)\equiv_{{\mathfrak{C}}}(b^{\prime},d^{\prime})$.
Since $F$ is ${\mathfrak{C}}$-invariant, we conclude that
$a^{\prime}Fb^{\prime}$, hence $F$ is the total equivalence relation.

Case 2: For any $a$, $b\in p({\mathfrak{C}}^{\prime})$ with $aFb$ there are
$n\in\mathbb{Q}^{+}$, $c\in{\mathfrak{C}}$, and a non-constant term $t(x,y)$
such that $\models S_{n}(t(a,b),c)$. Suppose that for every
$c\in{\mathfrak{C}}$, $F$ is not finer than $E_{c}^{\mu}$. We will reach a
contradiction, but this will require quite a bit of work.

First, we claim that there are $a,b\in p({\mathfrak{C}}^{\prime})$ such that

$(*)\;\;\;\;\;\;aFb\;\;\textrm{and}\;\;\models\bigwedge_{q\in\mathbb{Q}^{+}}\neg
S_{q}(a,b)\;\;\textrm{and}\;\;a+b\in p({\mathfrak{C}}^{\prime}).$

Firstly, note that by (topological) compactness of the intervals $[-r,r]$,
$r\in\mathbb{Q}^{+}$, we easily get that $a\not\in p({\mathfrak{C}}^{\prime})$
if and only if $a\in c+\mu$ for some $c\in{\mathfrak{C}}$. Assume that $(*)$
does not hold, that is, for any $aFb$ we have $aE_{c}^{\mu}b$ for some
$c\in{\mathfrak{C}}$ or $S_{n}(a,b)\wedge\neg S_{m}(a,b)$ for some
$m,n\in\mathbb{Q}^{+}$. Since $F$ is not contained in any $E_{c}^{\mu}$,
either we get a pair $(a,b)\in F$ such that $S_{m}(a,b)\wedge\neg S_{n}(a,b)$
for some $m,n\in\mathbb{Q}^{+}$, or we get two pairs
$(a,b),(a^{\prime},b^{\prime})\in F$ and elements
$c,c^{\prime}\in{\mathfrak{C}}$ such that $c-c^{\prime}\notin\mu$ and
$a+b-c\in\mu$ and $a^{\prime}+b^{\prime}-c^{\prime}\in\mu$. In this second
case, applying an an automorphism of ${\mathfrak{C}}^{\prime}$ over
${\mathfrak{C}}$ mapping $a^{\prime}$ to $a$, we may assume that
$a^{\prime}=a$, and so we get $F(b,b^{\prime})$ and $b-b^{\prime}\in
c-c^{\prime}+\mu$. Then $b+b^{\prime}\in 2b^{\prime}+c-c^{\prime}+\mu$ is not
related to any element of ${\mathfrak{C}}$ (as $2b^{\prime}$ is not related),
so $b+b^{\prime}\in p({\mathfrak{C}}^{\prime})$. Since we assumed that $(*)$
fails, we conclude that $S_{m}(b,b^{\prime})\wedge\neg S_{n}(b,b^{\prime})$
for some $m,n\in\mathbb{Q}^{+}$. In this way, the whole second case reduces to
the first one, i.e. we have a pair $(a,b)\in F$ with $S_{m}(a,b)\wedge\neg
S_{n}(a,b)$ for some $m,n\in\mathbb{Q}^{+}$.

Let $\sigma\in\operatorname{Aut}({\mathfrak{C}}^{\prime}/{\mathfrak{C}})$ be
such that $\sigma(a)=b$; set $b_{k}:=\sigma^{k}(a)$. We produced an infinite
sequence

$a$$b_{1}$$b_{2}$$\cdots$$\sigma$$\sigma$$\sigma$

Then for all $k\in\mathbb{N}^{+}$, $aFb_{k}$ and $\models S_{km}(a,b_{k})$ and
$\models\neg S_{kn}(a,b_{k})$. Since $\models S_{km}(a,b_{k})$ and $b_{k}$ is
not related to anything in ${\mathfrak{C}}$, we get
$\bigwedge_{q\in\mathbb{Q}^{+}}\bigwedge_{c\in{\mathfrak{C}}}\neg
S_{q}(a,-b_{k}+c)$, that is $a+b_{k}\in p({\mathfrak{C}}^{\prime})$. As we can
use arbitrarily large $k$, by compactness (or rather
$|{\mathfrak{C}}|^{+}$-saturation of ${\mathfrak{C}}^{\prime}$), there exist
$b$ such that $(a,b)$ satisfies $(*)$, a contradiction.

We will show now that there is $b^{\prime}\in p({\mathfrak{C}}^{\prime})$ such
that

$(**)\;\;\;\;\;\;aFb^{\prime}\;\;\textrm{with}\;\;a+b^{\prime},a-b^{\prime}\in
p({\mathfrak{C}}^{\prime}).$

Namely, either $b^{\prime}:=b$ already satisfies it, or $a-b$ is related to
some infinite $c\in{\mathfrak{C}}$. In the latter case, $a-b$ is related
precisely to the elements from the set $c+\mathbb{R}+\mu$.

Let $\sigma\in\operatorname{Aut}({\mathfrak{C}}^{\prime}/{\mathfrak{C}})$ be
such that $\sigma(a)=b$; set $b_{k}:=\sigma^{k}(a)$. We have

$a$$b_{1}$$b_{2}$$\cdots$$\sigma$$\sigma$$\sigma$

Then $aFb_{k}$, and one easily checks that $a-b_{k}$ is related precisely to
the elements from the set $kc+\mathbb{R}+\mu$, and so $a+b_{k}$ is not related
to anything in ${\mathfrak{C}}$. Since $c$ is infinite, the sets
$kc+\mathbb{R}+\mu$ are pairwise disjoint for different $k$’s, and so we find
the desired $b^{\prime}$ using compactness (or rather
$|{\mathfrak{C}}|^{+}$-saturation of ${\mathfrak{C}}^{\prime}$).

Since we are working in a divisible group, using [KP22, Remark 4.6], we can
replace the terms $t(x,y)$ in the statement of Case 2 by expressions
$t_{q}(x,y):=nx-my$, where $q=\frac{n}{m}$ is the reduced fraction of $q$
(i.e. $\gcd(m,n)=1$ with $m>0$). In particular, note that no term of the form
$t(x,y)=nx$ or $t(x,y)=my$ can occur in Case 2 hypothesis, since that would
contradict $a,b\in p({\mathfrak{C}}^{\prime})$. Notice that for each $d\in
p({\mathfrak{C}}^{\prime})$ there exists at most one rational $q$ such that

$S_{k}(t_{q}(a,d),c)$

holds for some $c\in{\mathfrak{C}}$ and $k\in\mathbb{Q}^{+}$. For if there
existed $q\neq q^{\prime}\in\mathbb{Q}$ (with reduced fractions $\frac{n}{m}$
and $\frac{n^{\prime}}{m^{\prime}}$, respectively),
$k,k^{\prime}\in\mathbb{Q}^{+}$, and $c,c^{\prime}\in{\mathfrak{C}}$ such that
$S_{k}(t_{q}(a,d),c)$ and $S_{k^{\prime}}(t_{q^{\prime}}(a,d),c^{\prime})$,
this would imply
$S_{n^{\prime}k+nk^{\prime}}((mn^{\prime}-m^{\prime}n)d,nc^{\prime}-n^{\prime}c)$,
contradicting that $d\in p({\mathfrak{C}}^{\prime})$ when
$mn^{\prime}-m^{\prime}n\neq 0$.

We will show now that there exists $b^{\prime\prime}\in
p({\mathfrak{C}}^{\prime})$ such that

$aFb^{\prime\prime}\;\;\textrm{and}\;\;\models\bigwedge_{q\in\mathbb{Q}}\bigwedge_{n\in\mathbb{Q}^{+}}\bigwedge_{c\in{\mathfrak{C}}}\neg
S_{n}(t_{q}(a,d),c),$

contradicting the assumption of Case 2.

Namely, either $d:=b^{\prime}$ does the job, or there are $q\in\mathbb{Q}$,
$n\in\mathbb{Q}^{+}$, and $c\in{\mathfrak{C}}$ such that
$S_{n}(t_{q}(a,b^{\prime}),c)$. By the choice of $a$ and $b^{\prime}$
satisfying $(**)$, we have that $q\notin\\{-1,0,1\\}$.

Again, let
$\sigma\in\operatorname{Aut}({\mathfrak{C}}^{\prime}/{\mathfrak{C}})$ be such
that $\sigma(a)=b^{\prime}$; set $b^{\prime}_{k}:=\sigma^{k}(a)$. We have

$a$$b_{1}^{\prime}$$b_{2}^{\prime}$$\cdots$$\sigma$$\sigma$$\sigma$

Then $aFb_{k}^{\prime}$ for all $k\in\mathbb{N}^{+}$. On the other hand,
applying powers of $\sigma$, we easily conclude that for every
$k\in\mathbb{N}^{+}$, $t_{q^{k}}(a,b_{k}^{\prime})$ is related to some element
of ${\mathfrak{C}}$. Hence, by an observation above, we get that for all
rationals $r\neq q^{k}$, $t_{r}(a,b_{k}^{\prime})$ is not related to anything
in ${\mathfrak{C}}$. Since $q\notin\\{-1,0,1\\}$, we know that $q,q^{2},\dots$
are pairwise distinct. So, by compactness, the desired $b^{\prime\prime}$
exists. ∎

######  Claim.

$F\cap E$ is either equality, or $E$, or $E_{A}$ for some non-empty
${\mathfrak{C}}$-small set $A$ of positive infinitesimals in ${\mathfrak{C}}$.

###### Proof of Claim.

We may assume that $F\subseteq E$, and just work with $F$. Let $B$ be a
${\mathfrak{C}}$-small $\operatorname{dcl}$-closed subset of ${\mathfrak{C}}$
over which $F$ is relatively defined on $p({\mathfrak{C}}^{\prime})$.
Extending the notation from before the statement of Theorem 4.7, for any
$B^{\prime}\subseteq B$ put

$E_{B^{\prime}}:=\\{(x,y)\in p({\mathfrak{C}}^{\prime})^{2}:\bigwedge_{b\in
B^{\prime+}}\bigwedge_{n\in\mathbb{N}^{+}}|y-x|\leq\frac{1}{n}b\\},$

where $B^{\prime+}:=\\{b\in B^{\prime}:0<b\leq 1\\}$. Let
$A:=\bigcup\\{B^{\prime}\subseteq B:F\subseteq E_{B^{\prime}}\\}$. Then

$F\subseteq\bigcap\\{E_{B^{\prime}}:B^{\prime}\subseteq B\;\;\textrm{such
that}\;\;F\subseteq E_{B^{\prime}}\\}=E_{A},$

and, as $F\subseteq E$, we have that $1\in A$.

We will show that either $F$ is equality, or $F=E_{A}$. This will clearly
complete the proof of the claim (note that if $A$ does not contain any
positive infinitesimals, then $E_{A}=E$). Suppose $F$ is not the equality. It
remains to show that $F\supseteq E_{A}$.

Case 1: $A=B$. Pick any distinct $\alpha,\beta\in p({\mathfrak{C}}^{\prime})$
such that $\alpha F\beta$. Then

$\bigwedge_{a\in A^{+}}|\alpha-\beta|\leq a.$

Consider any $\alpha^{\prime},\beta^{\prime}\in p({\mathfrak{C}}^{\prime})$
with $\alpha^{\prime}E_{A}\beta^{\prime}$. Then either
$\alpha^{\prime}=\beta^{\prime}$ (and so $\alpha^{\prime}F\beta^{\prime}$), or
$\bigwedge_{a\in A^{+}}0<|\beta^{\prime}-\alpha^{\prime}|\leq a$. In the
latter case, it remains to show that
$\alpha\beta\equiv_{A}\alpha^{\prime}\beta^{\prime}$ or
$\alpha\beta\equiv_{A}\beta^{\prime}\alpha^{\prime}$ (as then
$\alpha^{\prime}F\beta^{\prime}$, since $F$ is relatively type-definable over
$A$). Without loss of generality, $\beta>\alpha$ and
$\beta^{\prime}>\alpha^{\prime}$; equivalently, $R_{1}(\alpha,\beta)$ and
$R_{1}(\alpha^{\prime},\beta^{\prime})$ both hold. Since
$\alpha\equiv_{{\mathfrak{C}}}\alpha^{\prime}$, we can assume that
$\alpha=\alpha^{\prime}$. It suffices to show that

$\\{0<t-\alpha\leq a:a\in A^{+}\\}$

determines a complete type over $\operatorname{dcl}(A,\alpha)$. By
o-minimality of $(\mathbb{R},+,-,1,\leq)$, this boils down to showing that
there is no $b\in\operatorname{dcl}^{*}(A,\alpha)$ with $\bigwedge_{a\in
A^{+}}\alpha<b\leq\alpha+a$, where $\operatorname{dcl}^{*}$ is computed in the
language $\\{+,-,1,\leq\\}$. If there was such a $b$, then, by q.e. for the
theory of divisible ordered abelian groups, it would be of the form
$\gamma+q\alpha$ for some $\gamma\in A$ and $q\in\mathbb{Q}$, and we would
have $\bigwedge_{a\in A^{+}}0<\gamma+(q-1)\alpha\leq a$. If $q=1$, we get
$0<\gamma\leq\frac{1}{2}\gamma<\gamma$, a contradiction. If $q\neq 1$, we get
that $\alpha$ is related to an element of $A$ which contradicts the fact that
$\alpha\in p({\mathfrak{C}}^{\prime})$.

Case 2: $A\subsetneq B$. Take any $b\in B\setminus A$. Then, by maximality of
$A$, $F\nsubseteq E_{A\cup\\{b\\}}$, so there is $(x,y)\in F$ such that
$(x,y)\notin E_{A\cup\\{b\\}}=E_{A}\cap E_{b}$; swapping $x$ and $y$ if
necessary, we may assume that $y>x$. As $F\subseteq E_{A}$, we have that
$(x,y)\notin E_{b}$. In particular, this implies that $b\in B^{+}$ and
$y-x>\frac{1}{n}b$ for some $n\in\mathbb{N}^{+}$. Since $F\subseteq E_{A}$, we
have that $\lvert y-x\rvert<\frac{1}{n}a$ for all $a\in A^{+}$ and
$n\in\mathbb{N}^{+}$, concluding $\bigwedge_{a\in A^{+}}b<a$.

Let $\sigma\in\operatorname{Aut}({\mathfrak{C}}^{\prime}/{\mathfrak{C}})$ be
such that $\sigma(x)=y$; set $y_{k}:=\sigma^{k}(x)$. We have

$a$$y_{1}$$y_{2}$$\cdots$$\sigma$$\sigma$$\sigma$

We easily conclude that $F(x,y_{k})$ and $y_{k}-x>\frac{k}{n}b$ for all $k$;
in particular, $y_{n}-x>b$. By compactness (or rather
$|{\mathfrak{C}}|^{+}$-saturation of ${\mathfrak{C}}^{\prime}$), there exist
$x^{\prime},y^{\prime}\in p({\mathfrak{C}}^{\prime})$ such that
$F(x^{\prime},y^{\prime})$ and:

  1. (1)

$\bigwedge_{a\in A^{+}}0<y^{\prime}-x^{\prime}<a$;

  2. (2)

$\bigwedge_{b\in B^{+}\setminus A^{+}}b<y^{\prime}-x^{\prime}$.

We will check now that whenever $x^{\prime\prime},y^{\prime\prime}\in
p({\mathfrak{C}}^{\prime})$ satisfy (1) and (2), then
$x^{\prime}y^{\prime}\equiv_{B}x^{\prime\prime}y^{\prime\prime}$. For that,
without loss of generality, we can assume that $x^{\prime}=x^{\prime\prime}$.
It remains to show that the partial type

$\pi(t/x^{\prime}):=\\{0<t-x^{\prime}<a:a\in
A^{+}\\}\cup\\{b<t-x^{\prime}:b\in B^{+}\setminus A^{+}\\}$

determines a complete type over $\operatorname{dcl}(B,x^{\prime})$. By
o-minimality of $(\mathbb{R},+,-,1,\leq)$, this boils down to showing that
there is no $c\in\operatorname{dcl}^{*}(B,x^{\prime})$ realizing
$\pi(t/x^{\prime})$, where $\operatorname{dcl}^{*}$ is computed in the
language $\\{+,-,1,\leq\\}$. If there was such a $c$, then, by q.e. for the
theory of divisible ordered abelian groups, it would be of the form
$\beta+qx^{\prime}$ for some $\beta\in B$ and $q\in\mathbb{Q}$, so

$\bigwedge_{a\in A^{+}}\bigwedge_{b\in B^{+}\setminus
A^{+}}b<\beta+(q-1)x^{\prime}<a.$

If $q=1$, we get $\bigwedge_{a\in A^{+}}0<\beta<a$, so $\beta\in
B^{+}\setminus A^{+}$, concluding $\beta<\beta$, a contradiction. If $q\neq
1$, as $1\in A$, we get that $x^{\prime}$ is related to an element of $B$,
which contradicts the fact that $x^{\prime}\in p({\mathfrak{C}}^{\prime})$.

Finally, consider any $(\alpha,\beta)\in E_{A}$, say with $\beta>\alpha$ so
$0<\beta-\alpha<\frac{1}{2}a$ for all $a\in A^{+}$. Applying
$\sigma\in\operatorname{Aut}({\mathfrak{C}}^{\prime}/{\mathfrak{C}})$ mapping
$y^{\prime}$ to $\alpha$, we obtain $\gamma:=\sigma(x^{\prime})$ such that
$\gamma F\alpha$ and $\bigwedge_{b\in B^{+}\setminus A^{+}}b<\alpha-\gamma$.
Since $F\subseteq E_{A}$, we get $b<\alpha-\gamma<\frac{1}{2}a$ for all $b\in
B^{+}\setminus A^{+}$ and $a\in A^{+}$. Therefore, $b<\beta-\gamma<a$ for all
$b\in B^{+}\setminus A^{+}$ and $a\in A^{+}$, So, by the previous paragraph,
$\gamma\alpha\equiv_{B}x^{\prime}y^{\prime}\equiv_{B}\gamma\beta$. As
$(x^{\prime},y^{\prime})\in F$, we conclude that $(\alpha,\beta)\in F$, which
completes the proof of the claim. ∎

By the above two claims, in order to prove the theorem, it remains to consider
the case when $E\cap F\subsetneq F\subseteq E_{c_{0}}^{\mu}$ for some
$c_{0}\in{\mathfrak{C}}$. By the second claim, we have the following two
cases.

Case 1: $E\cap F$ is the equality. We will show that then $F=E_{c}$ for some
$c\in{\mathfrak{C}}$. Consider any $a\in p({\mathfrak{C}}^{\prime})$. Since
$F\neq\;=$, there exists $b\neq a$ such that $aFb$. Since $F\subseteq
E_{c_{0}}^{\mu}$ and $E\cap F$ is the equality, we get that such a $b$ is
unique: if $b^{\prime}\neq a$ also satisfies $aFb^{\prime}$, then
$b,b^{\prime}\in-a+c_{0}+\mu$, so $b-b^{\prime}\in\mu$, hence $b=b^{\prime}$
because $bFb^{\prime}$. This unique $b$ belongs to
$\operatorname{dcl}({\mathfrak{C}},a)$, so
$g:=a+b-c_{0}\in\operatorname{dcl}({\mathfrak{C}},a)\cap\mu$. Since $a$ is not
related to any element of ${\mathfrak{C}}$ and $\operatorname{dcl}$ is given
by “terms” with rational coefficients (which follows from q.e. for $T$), we
get that $g\in{\mathfrak{C}}$. Hence, $c:=a+b=c_{0}+g\in{\mathfrak{C}}$.
Applying automorphisms over ${\mathfrak{C}}$, we get $F=E_{c}$.

Case 2: $E\cap F=E$ or $E\cap F=E_{A}$ for some non-empty
${\mathfrak{C}}$-small set $A$ of positive infinitesimals. Since
$E=E_{\\{1\\}}$ (with the obvious extension of the definition of $E_{A}$), we
can write $E\cap F=E_{A}$, where $A$ is either a non-empty
${\mathfrak{C}}$-small set $A$ of positive infinitesimals or $A=\\{1\\}$. We
will show that then $F=E_{A,c}$ for some $c\in{\mathfrak{C}}$, where
$E_{\\{1\\},c}:=E^{\mu}_{c}$. Extend the definition of $\mu_{A}$ via
$\mu_{\\{1\\}}:=\mu$.

Consider any $a\in p({\mathfrak{C}}^{\prime})$. Since $E\cap F\neq F$ and
$F\subseteq E_{c_{0}}^{\mu}$, there exists $b\in p({\mathfrak{C}}^{\prime})$
such that $(a,b)\in F\setminus E$ and $a+b=c_{0}+g$ for some $g\in\mu$. As
$E\cap F=E_{A}$, we get that $\sigma(g)-g\in\mu_{A}$ for every
$\sigma\in\operatorname{Aut}({\mathfrak{C}}^{\prime}/{\mathfrak{C}}a)$.

Since $\sigma(g)-g\in\mu_{A}$ for every
$\sigma\in\operatorname{Aut}({\mathfrak{C}}^{\prime}/{\mathfrak{C}}a)$, we
conclude by o-minimality of $(\mathbb{R},+,-,1,\leq)$ that, for every
$\alpha\in A$ and $\in\mathbb{N}^{+}$, there are
$c_{\alpha,n},d_{\alpha,n}\in\operatorname{dcl}^{*}({\mathfrak{C}},a)$ such
that $g-\frac{1}{n}\alpha<c_{\alpha,n}\leq g\leq
d_{\alpha,n}<g+\frac{1}{n}\alpha$, where $\operatorname{dcl}^{*}$ is the
definable closure computed in the language $\\{+,-,1,\leq\\}$ (which coincides
with $\operatorname{dcl}$ as both closures are given by “terms” with rational
coefficients). Since $a$ is not related to any element of ${\mathfrak{C}}$ and
for every $\alpha\in A$ and $n\in\mathbb{N}^{+}$ the elements
$c_{\alpha,n},d_{\alpha,n}$ are related to zero, using that
$\operatorname{dcl}^{*}$ is given by “terms” with rationals coefficients, we
conclude that $c_{\alpha,n}$ and $d_{\alpha,n}$ belong to ${\mathfrak{C}}$ for
every $\alpha\in A$ and $n\in\mathbb{N}^{+}$. Since $A$ is
${\mathfrak{C}}$-small, the set of all $c_{\alpha,n}$ and $d_{\alpha,n}$ is
${\mathfrak{C}}$-small, and hence there is $e\in{\mathfrak{C}}$ with
$g-\frac{1}{n}\alpha<e<g+\frac{1}{n}\alpha$ for all $\alpha\in A$ and
$n\in\mathbb{N}^{+}$. Then, $g\in e+\mu_{A}$ with $e\in{\mathfrak{C}}$,
concluding $a+b\in c+\mu_{A}$, where $c=c_{0}+e\in{\mathfrak{C}}$, so
$aE_{A,c}b$.

From the conclusion of the previous paragraph and the fact that $E\cap
F=E_{A}$, we obtain $(a+\mu_{A})\cup(-a+c+\mu_{A})\subseteq[a]_{F}$. By
automorphisms over ${\mathfrak{C}}$, the same is true for any other element of
$p({\mathfrak{C}}^{\prime})$ in place of $a$, so $E_{A,c}\subseteq F$. The
opposite inclusion easily follows using the assumptions $F\subseteq
E_{c_{0}}^{\mu}$ and $E\cap F=E_{A}$. Namely, using automorphisms over
${\mathfrak{C}}$, it is enough to show that $[a]_{F}\subseteq[a]_{E_{A,c}}$.
Consider any $b^{\prime}\in[a]_{F}$. Since $(a,b)\in F\setminus E$ and
$F\subseteq E_{c_{0}}^{\mu}$, we have that $b^{\prime}\in a+\mu$ or
$b^{\prime}\in b+\mu$. As $E\cap F=E_{A}$, we conclude that $b^{\prime}\in
a+\mu_{A}$ (and so $b^{\prime}E_{A,c}a$) or $b^{\prime}\in b+\mu_{A}$ (and so
$b^{\prime}E_{A,c}b$ which together with $aE_{A,c}b$ implies
$b^{\prime}E_{A,c}a$). ∎

######  Corollary 4.8.

The equivalence relation $E$ is the finest equivalence relation on
$p({\mathfrak{C}}^{\prime})$ relatively type-definable over a
${\mathfrak{C}}$-small set of parameters of ${\mathfrak{C}}$ and with stable
quotient, that is $E^{st}=E$

###### Proof.

The quotient $p({\mathfrak{C}}^{\prime})/E$ is stable by [KP22, Proposition
4.9]. Let $F$ be a relatively type-definable over a ${\mathfrak{C}}$-small
subset of ${\mathfrak{C}}$ equivalence relation on
$p({\mathfrak{C}}^{\prime})$ strictly finer than $E$. By Theorem 4.7,
$F=E_{A}$ for some non-empty ${\mathfrak{C}}$-small set $A$ of positive
infinitesimals in ${\mathfrak{C}}$. (There is also the case when $F$ is the
equality, but then $p({\mathfrak{C}}^{\prime})/F=p({\mathfrak{C}}^{\prime})$
is clearly unstable.)

Pick any $\alpha\in A$. It is easy to check that for every
$a,d,e\in{\mathfrak{C}}^{\prime}$ and infinitesimal
$c\in{\mathfrak{C}}^{\prime}$ bigger than all infinitesimals in
${\mathfrak{C}}$ and such that $|d-a|\leq\frac{1}{2}\alpha$ and
$|e-(a+c)|\leq\frac{1}{2}\alpha$, we have $d<e$, and so $\neg R_{1}(e,d)$. And
note that “$|x-y|\leq\frac{1}{2}\alpha$” can be written as an
$L_{\alpha}$-formula.

Take any $a\in p({\mathfrak{C}}^{\prime})$ and infinitesimal
$c\in{\mathfrak{C}}^{\prime}$ bigger than all infinitesimals in
${\mathfrak{C}}$. Using Ramsey’s theorem and compactness, we find a
${\mathfrak{C}}$-indiscernible sequence $(a_{i}^{\prime})_{i<\omega}$ having
the same Erenfeucht-Mostowski type as the sequence $(a+kc)_{k<\omega}$. Then,
the sequence $([a^{\prime}_{i}]_{F})_{i<\omega}$ is
${\mathfrak{C}}$-indiscernible but not totally ${\mathfrak{C}}$-indiscernible,
since the formula $R_{1}(x,y)$ witnesses that

$\operatorname{{tp}}([a^{\prime}_{i}]_{F},[a^{\prime}_{i+1}]_{F}/{\mathfrak{C}})\neq\operatorname{{tp}}([a^{\prime}_{i+1}]_{F},[a^{\prime}_{i}]_{F}/{\mathfrak{C}}).$

Thus, $p({\mathfrak{C}}^{\prime})/F$ is unstable.∎

## Acknowledgments

We would like to thank the anonymous referee for very careful reading and many
suggestions which improved the presentation.

## References

  * [BY03] Itay Ben-Yaacov  “Simplicity in compact abstarct theories”  In _Journal of Mathematical Logic_ 03.02, 2003, pp. 163–191  DOI: 10.1142/S0219061303000297
  * [HKP21] Ehud Hrushovski, Krzysztof Krupiński and Anand Pillay  “On first order amenability”, 2021  arXiv:2004.08306v2 [math.LO]
  * [HP18] Mike Haskel and Anand Pillay  “On maximal stable quotients of definable groups in $NIP$ theories”  In _J. Symb. Log._ 83.1, 2018, pp. 117–122  DOI: 10.1017/jsl.2017.26
  * [KNS19] Krzysztof Krupiński, Ludomir Newelski and Pierre Simon  “Boundedness and absoluteness of some dynamical invariants in model theory”  In _Journal of Mathematical Logic_ 19.02, 2019, pp. 1950012  DOI: 10.1142/S0219061319500120
  * [KP22] Krzysztof Krupiński and Adrián Portillo  “On Stable Quotients”  In _Notre Dame Journal of Formal Logic_ 63.3 Duke University Press, 2022, pp. 373–394  DOI: 10.1215/00294527-2022-0023
  * [KPR18] Krzysztof Krupiński, Anand Pillay and Tomasz Rzepecki  “Topological dynamics and the complexity of strong types”  In _Israel J. Math._ 228, 2018, pp. 863–932  DOI: 10.1007/s11856-018-1780-3
  * [OP07] Alf Onshuus and Ya’acov Peterzil  “A note on stable sets, groups, and theories with NIP”  In _Mathematical Logic Quarterly_ 53.3, 2007, pp. 295–300  DOI: 10.1002/malq.200610046