MAXIMAL STABLE QUOTIENTS OF INVARIANT TYPES IN NIP THEORIES

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 [2] 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 [3].

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 [2]; some questions from [2] were answered in [6]. 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 {\mathrm {{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

$$ \begin{align*}\operatorname{\mathrm{{tp}}}(a_i,b_j/A) = \operatorname{\mathrm{{tp}}}(a_j,b_i/A)\end{align*} $$

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 [2, 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 [2] 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 [6], we gave several characterizations of stability for hyperdefinable sets both with and without assuming that the theory T has NIP (see [6, Section 2]). We also proved that in distal theories all stable hyperdefinable sets are bounded, i.e., of bounded size [6, Corollary 3.5]. In Proposition 2.2, we will deduce another characterization of stability under NIP, via the so-called weak stability, generalizing [7, 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 [2] hold outside of the context of type-definable groups. However, the naive counterpart of [2, 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 [2, Remark 1.4] (as both $X/E$ and $X/\!\!\equiv _a$ are stable).

Let ${\mathfrak C}\prec {\mathfrak C}'$ be two monster models of a NIP theory T such that ${\mathfrak C}$ is small in ${\mathfrak C}'$ . 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}')$ relatively type-definable over a small (relative to ${\mathfrak C}$ ) set of parameters of ${\mathfrak C}$ and with stable quotient $p({\mathfrak C}')/E^{st}$ .

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

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}')$ 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}'$ be models of T such that ${\mathfrak C}$ is $\kappa $ -saturated with a strong limit cardinal $\kappa>\lvert T\rvert $ , and ${\mathfrak C}'$ is $\kappa '$ -saturated and strongly $\kappa '$ -homogeneous with a strong limit cardinal $\kappa '>\lvert {\mathfrak C}\rvert $ . We say that $\kappa $ is the degree of saturation of ${\mathfrak C}$ and $\kappa '$ is the degree of saturation of ${\mathfrak C}'$ . We say that a set is ${\mathfrak C}$ -small if its cardinality is smaller than $\kappa $ and ${\mathfrak C}'$ -small if its cardinality is smaller than $\kappa '$ . 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}'$ , 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}')$ . 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}')$ 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}')$ (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 [7, 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

$$ \begin{align*}\operatorname{\mathrm{{tp}}}(a_i,b_j,c/A) = \operatorname{\mathrm{{tp}}}(a_j,b_i,c/A)\end{align*} $$

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

We obtain a hyperdefinable counterpart of [7, 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 [6, 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

$$ \begin{align*}\operatorname{\mathrm{{tp}}}(a_{j},a_{{j+1}}/A)\neq \operatorname{\mathrm{{tp}}}(a_{{j+1}},a_{j}/A),\end{align*} $$

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 {\mathrm {{tp}}}(b_i,b_j/A)\neq \operatorname {\mathrm {{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 [4, 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}$

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

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'(x)\in S(B)$ which is a strong heir over A of q (see [4, 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'(x)\in S(\mathfrak {C})$ is a strong heir extension over A of $q(x)$ . Then $q'(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'(x)$ with $a \underset {A}\equiv b$ and $\neg \varphi (x,b)\in q'(x)$ . Then, there exist $a',b'\in \mathcal {M}$ such that $a'\underset {A}{\equiv } a$ and $b' \underset {A}{\equiv } b$ for which $\varphi (x,a') \in q(x)$ while $\neg \varphi (x,b')\in q(x)$ . Then $a' \underset {A}{\equiv } b'$ , 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}',{\mathfrak C}')\cap X({\mathfrak C}')^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}',{\mathfrak C}')\cap X({\mathfrak C}')^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}')$ 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}')$ . Then, $\pi $ relatively defines an equivalence relation on $p(\mathfrak {C}')$ with stable quotient if and only if it relatively defines an equivalence relation on $p\!\upharpoonright _{\mathcal {M}}(\mathfrak {C}')$ with stable quotient.

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

Assume first that $p({\mathfrak C}')/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}')$ for all $i<\omega $ and for all $i\neq j$

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

and so $p\!\upharpoonright _{\mathcal {M}}\!\!(\mathfrak {C}')/E'$ is unstable.

Assume now that $p\!\upharpoonright _{\mathcal {M}}\!\!(\mathfrak {C}')/E'$ 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}')$ for all $i<\omega $ and for all $i\neq j$

Consider and let $q'\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'$ . Then,

1. (1) $(c_i^{\prime },b_i^{\prime })_{i<\omega }$ is ${\mathfrak C}$ -indiscernible;

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

3. (3) for all $i \ne 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'$ is a strong heir extension over A of q, we can find $d'\subseteq \mathcal {M}$ such that

$$ \begin{align*}\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')\in q,\end{align*} $$

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

$(2)$ follows from the fact that $\operatorname {\mathrm {{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 \ne j$ . As E is the restriction to $p({\mathfrak C})$ of the equivalence relation $E'$ , we see that implies . So , and hence because $q \subseteq q'$ and $\pi (x,y)$ is over $\mathcal {M}$ . This is a contradiction.

By (1)–(3), $p({\mathfrak C}')/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}')$ 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}')$ , for some $B \subseteq {\mathfrak C}$ . Then, $E=\bigcap _{i\in I}E_i \cap p({\mathfrak C}')^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}')$ . Thus, E is the restriction to $p({\mathfrak C}')$ of a $B'$ -type-definable equivalence relation F on $p\!\upharpoonright _{B'}\!\!({\mathfrak C}')$ for some $B'\subseteq {\mathfrak C}$ with $\lvert B'\rvert \leq |B| +|x| + |T|$ .

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

Proof Fix a partial type $\pi (x,y)$ relatively defining E on $p({\mathfrak C}')$ . 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

$$ \begin{align*}p(x)\wedge p(y)\wedge p(z)\wedge \pi(x,y)\wedge \pi(y,z)\end{align*} $$

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

$$ \begin{align*}\psi_1(x)\wedge\psi_1(y)\wedge \psi_1(z) \wedge \varphi_1(x,y)\wedge \varphi_1(y,z)\end{align*} $$

implies $\varphi _0(x,z) \wedge \varphi _0(z,x).$ Proceeding by induction, we construct a partial type

$$ \begin{align*}\{\varphi_i(x,y): i<\omega\}\end{align*} $$

relatively defining an equivalence relation on $\bigcap _{i<\omega }\psi _i({\mathfrak C}')$ . 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}')$ . 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}')$ .

The following result is a criterion for when an equivalence relation on $p({\mathfrak C}')$ 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}')$ 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}')$ with stable quotient if and only if it relatively defines the finest $\mathcal {M}'$ -type-definable equivalence relation on $p\!\upharpoonright _{\mathcal {M}'}\!\!(\mathfrak {C}')$ with stable quotient for every $\mathcal {M}'\prec {\mathfrak C}'$ with $\lvert \mathcal {M}'\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}')$ and $E'$ be the equivalence relation relatively defined by $\pi $ on $p\!\upharpoonright _{\mathcal {M}}\!\!(\mathfrak {C}')$ .

( $\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}')$ over some ${\mathfrak C}$ -small set of parameters $B\subseteq {\mathfrak C}$ such that the quotient $p({\mathfrak C}')/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}')^2$ satisfying the conclusion of Proposition 2.6. Abusing notation, write $E_i$ for $E_i \cap p({\mathfrak C}')^2$ . As $E_B\subsetneq E$ , there exists some $i\in I$ such that

$$ \begin{align*}E\cap E_i\subsetneq E. \end{align*} $$

Since $p({\mathfrak C}')/E_B$ is stable and $E_B\subseteq E\cap E_i$ , we have that $p({\mathfrak C}')/E\cap E_i$ is stable. Pick $B_i$ as in Proposition 2.6 and choose any $\mathcal {M}'\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}'$ relatively defining $E_i$ which also relatively defines an equivalence relation on $p \!\upharpoonright _{\mathcal {M}'}\!\!({\mathfrak C}')$ . 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}'}\!\!({\mathfrak C}')$ and is stable. Hence, applying Lemma 2.5, we obtain that the quotient

is stable. Moreover,

$$ \begin{align*}\rho({\mathfrak C}',{\mathfrak C}')\cap p\!\upharpoonright_{\mathcal{M}'}\!\!({\mathfrak C}')^2\subsetneq\pi({\mathfrak C}',{\mathfrak C}')\cap p\!\upharpoonright_{\mathcal{M}'}\!\!({\mathfrak C}')^2.\end{align*} $$

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'$ is stable. Assume that the right-hand side does not hold, witnessed by a model $\mathcal {M}'$ 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}'$ . By saturation of ${\mathfrak C}$ , we can assume that $\mathcal {M}'\subseteq {\mathfrak C}$ . Hence, by Lemma 2.5, the fact that the quotient is stable implies that the quotient is stable. Let $b_1,b_2\in p\!\upharpoonright _{\mathcal {M}'}\!\!({\mathfrak C}')$ be elements witnessing

$$ \begin{align*}\rho(\mathfrak{C}',\mathfrak{C}')\cap p\!\upharpoonright_{\mathcal{M}'}\!\!(\mathfrak{C}')^2 \subsetneq \pi(\mathfrak{C}',\mathfrak{C}')\cap p\!\upharpoonright_{\mathcal{M}'}\!\!(\mathfrak{C}')^2,\end{align*} $$

that is, $(b_1,b_2) \in \pi (\mathfrak {C}',\mathfrak {C}') \setminus \rho (\mathfrak {C}',\mathfrak {C}')$ . Let and let $q'\in S({\mathfrak C})$ be a strong heir extension over A of q. By Lemma 2.4, any realization $(b_1',b_2')\in q'({\mathfrak C}')$ satisfies $b_1',b_2'\in p({\mathfrak C}')$ , $(b_1',b_2')\in \pi (\mathfrak {C}',\mathfrak {C}')$ , and $(b_1',b_2')\not \in \rho (\mathfrak {C}',\mathfrak {C}')$ . Therefore,

$$ \begin{align*}\rho(\mathfrak{C}',\mathfrak{C}')\cap p(\mathfrak{C}')^2 \subsetneq \pi(\mathfrak{C}',\mathfrak{C}')\cap p(\mathfrak{C}')^2,\end{align*} $$

which contradicts the minimality of E.

Let ${\mathfrak C}\prec {\mathfrak C}_1\prec {\mathfrak C}'$ be such that ${\mathfrak C}_1$ is ${\mathfrak C}'$ -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}')$ with stable quotient. Then $E\cap p_1({\mathfrak C}')^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}')$ 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}')$ . 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}')^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}')$ 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}')$ 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 {\mathrm {{Aut}}}({\mathfrak C}_1/A)$ be such that $\sigma [B] \subseteq \mathfrak {C}$ . Then $\pi ({\mathfrak C}',{\mathfrak C}',\sigma [B]) \cap p({\mathfrak C}')^2$ is the finest relatively type-definable over a ${\mathfrak C}$ -small subset of ${\mathfrak C}$ equivalence relation on $p({\mathfrak C}')$ 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}')$ . 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}',{\mathfrak C}',\sigma [B]) \cap p({\mathfrak C}')^2$ is the finest relatively type-definable over a ${\mathfrak C}$ -small subset of ${\mathfrak C}$ equivalence relation on $p({\mathfrak C}')$ 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}')$ with stable quotient exists if and only if the finest ${\mathfrak C}$ -type-definable equivalence relation on $p({\mathfrak C}')$ 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}')$ with stable quotient. Every relatively type-definable over a ${\mathfrak C}$ -small subset of ${\mathfrak C}$ equivalence relation on $p({\mathfrak C}')$ 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}')$ 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}'$ 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}')$ with stable quotient. Since $p_1({\mathfrak C}')\subseteq p({\mathfrak C}')$ 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}')$ 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

$$ \begin{align*}\Delta(x,y,c_2)\wedge \psi(x,c_1)\wedge\psi(y,c_1)\models \varphi(x,y,c_0).\end{align*} $$

Now, take $c\in {\mathfrak C}$ such that $\operatorname {\mathrm {{tp}}}(c,c_0,c_2/A)=\operatorname {\mathrm {{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}'$ extracted from [3]. The following is Definition 2.14 of [3], which extends the notion of relatively definable subset of the automorphism group of the monster model from [5, Appendix A].

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

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

$$ \begin{align*}A_{\pi(x;y,z);a;b,c}({\mathfrak C}'/A):=\{\sigma\in \operatorname{\mathrm{Aut}}({\mathfrak C}'/A): {\mathfrak C}'\models \pi(\sigma(a);b,c)\}.\end{align*} $$

In this section, if $A=\emptyset $ , we will omit $({\mathfrak C}'/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}'/A)$ as $A_{\pi ;a;c}({\mathfrak C}'/A)$ .

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

Lemma 3.2. Let $a\in \mathfrak {C}'$ and a sequence $(a_i)_{i<\omega } \subseteq \mathfrak {C}'$ (of ${\mathfrak C}'$ -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'})$ . Assume that there is a formula $\varphi (x,y,z)$ implied by $\pi (x,y,z)$ such that for every $i<\omega $

$$ \begin{align*}\bigcap_{j\neq i}\pi({\mathfrak C}',{\mathfrak C}',a_j)\cap (p\!\upharpoonright_{a_{<\omega}}\!\!({\mathfrak C}'))^2 \not\subseteq \varphi({\mathfrak C}',{\mathfrak C}',a_i).\end{align*} $$

Then T has IP.

To prove this result, we need the following three observations on relatively type-definable subsets of $\operatorname {\mathrm {Aut}}({\mathfrak C}')$ 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}')$ relatively defined by $\pi (x,y,a_i)$ . Then, for all $i<\omega $ , $ A_{\pi ;a;a_i}({\mathfrak C}'/a_{i})$ is the stabilizer of the class $[a]_{E_{a_i}}$ under the action of $\operatorname {\mathrm {Aut}}({\mathfrak C}'/a_{i})$ , and $ A_{\pi ;a;a_i}({\mathfrak C}'/a_{<\omega })$ is the stabilizer of the class $[a]_{E_{a_i}}$ under the action of $\operatorname {\mathrm {Aut}}({\mathfrak C}'/a_{<\omega })$ .

Proof It is clear that $\operatorname {\mathrm {Aut}}({\mathfrak C}'/a_i)$ preserves both $p\!\upharpoonright _{a_i}\!\!({\mathfrak C}')$ and $E_{a_i}$ .

Let $\sigma \in A_{\pi ;a;a_i}({\mathfrak C}'/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

$$ \begin{align*}A_{\pi;a;a_i}({\mathfrak C}'/a_{i})\subseteq \operatorname{\mathrm{Stab}}_{\operatorname{\mathrm{Aut}}({\mathfrak C}'/a_{i})}([a]_{E_{a_i}}).\end{align*} $$

Conversely, let $\sigma \in \operatorname {\mathrm {Stab}}_{\operatorname {\mathrm {Aut}}({\mathfrak C}'/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}'/a_i)$ . Thus,

$$ \begin{align*}\operatorname{\mathrm{Stab}}_{\operatorname{\mathrm{Aut}}({\mathfrak C}'/a_{i})}([a]_{E_{a_i}}) \subseteq A_{\pi;a;a_i}({\mathfrak C}'/a_{i}).\end{align*} $$

The same proof works for $\operatorname {\mathrm {Stab}}_{\operatorname {\mathrm {Aut}}({\mathfrak C}'/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

$$ \begin{align*}A_{\pi;a;a_0}({\mathfrak C}'/a_0)\cdot A_{\theta;a;a_0}({\mathfrak C}'/a_0)\cdot A_{\pi;a;a_0}({\mathfrak C}'/a_0) \subseteq A_{\varphi;a;a_0}({\mathfrak C}'/a_0).\end{align*} $$

Proof Let us consider the type $\pi '(x_1,x_2;y,z):=\pi (x_1,y,z)\cup \{x_2=z\}$ . Then,

$$ \begin{align*}A_{\pi;a;a_0}({\mathfrak C}'/a_0)=A_{\pi'(x_1,x_2;y,z); aa_0;a,a_0} .\end{align*} $$

Hence, by the previous claim, $A_{\pi '(x_1,x_2;y,z); aa_0;a,a_0}$ is a group, so it satisfies

$$ \begin{align*}A_{\pi'(x_1,x_2;y,z); aa_0;a,a_0}^3=A_{\pi'(x_1,x_2;y,z); aa_0;a,a_0}.\end{align*} $$

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

$$ \begin{align*}A_{\pi'(x_1,x_2;y,z); aa_0;a,a_0}^3\subseteq A_{\varphi(x;y,z); a;a,a_0}.\end{align*} $$

Applying compactness [3, 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

$$ \begin{align*}A_{\pi'(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'(x_1,x_2;y,z); aa_0;a,a_0} \subseteq A_{\varphi(x;y,z); a;a,a_0}.\end{align*} $$

Finally, since every automorphism on the left-hand side belongs to $\operatorname {\mathrm {Aut}}({\mathfrak C}'/a_0)$ , we conclude that

$$ \begin{align*}A_{\pi;a;a_0}({\mathfrak C}'/a_0)\cdot A_{\theta;a;a_0}({\mathfrak C}'/a_0)\cdot A_{\pi;a;a_0}({\mathfrak C}'/a_0) \subseteq A_{\varphi;a;a_0}({\mathfrak C}'/a_0).\\[-34pt] \end{align*} $$

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 $ ,

$$ \begin{align*}A_{\pi;a;a_0}({\mathfrak C}'/a_0)\cdot A_{\theta;a;a_0}({\mathfrak C}'/a_0)\cdot A_{\pi;a;a_0}({\mathfrak C}'/a_0) \subseteq A_{\varphi;a;a_0}({\mathfrak C}'/a_0),\end{align*} $$

if and only if

$$ \begin{align*}A_{\pi;a;a_i}({\mathfrak C}'/a_i)\cdot A_{\theta;a;a_i}({\mathfrak C}'/a_i)\cdot A_{\pi;a;a_i}({\mathfrak C}'/a_i) \subseteq A_{\varphi;a;a_i}({\mathfrak C}'/a_i).\end{align*} $$

Proof Let $\tau \in \operatorname {\mathrm {Aut}}({\mathfrak C}'/a)$ be such that $\tau (a_0)=a_i$ . The conjugation by $\tau $

$$ \begin{align*} \operatorname{\mathrm{Aut}}({\mathfrak C}'/a_0)&\to \operatorname{\mathrm{Aut}}({\mathfrak C}'/a_i)\\ \sigma\hspace{20pt} &\mapsto \hspace{10pt} \tau\sigma\tau^{-1} \end{align*} $$

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

$$ \begin{align*}\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).\end{align*} $$

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}'$ fixing $(a_i)_{i<\omega }$ , we can reduce the condition

$$ \begin{align*}\bigcap_{j\neq i}\pi({\mathfrak C}',{\mathfrak C}',a_j)\cap (p\!\upharpoonright_{a_{<\omega}}\!\!({\mathfrak C}'))^2\not\subseteq \varphi({\mathfrak C}',{\mathfrak C}',a_i)\end{align*} $$

to

$$ \begin{align*}\bigcap_{j\neq i}\pi({\mathfrak C}',a,a_j)\cap p\!\upharpoonright_{a_{<\omega}}\!\!({\mathfrak C}')\not\subseteq \varphi({\mathfrak C}',a,a_i),\end{align*} $$

because, given a pair $(c,d)$ witnessing the former condition, there exists some $\sigma \in \operatorname {\mathrm {Aut}}({\mathfrak C}'/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 {\mathrm {Aut}}({\mathfrak C}')$ as

$$ \begin{align*}A_{\bigwedge_{j\neq i}\pi(x;y,z_j);a;a,(a_j)_{j\neq i}}({\mathfrak C}'/a_{<\omega}) \not\subseteq A_{\varphi(x;y,z_i);a;a,a_i}.\end{align*} $$

For every $i<\omega $ , choose some

$$ \begin{align*}\sigma_i\in A_{\bigwedge_{j\neq i}\pi(x;y,z_j);a;a,(a_j)_{j\neq i}}({\mathfrak C}'/a_{<\omega}) \setminus A_{\varphi(x;y,z_i),a,a,a_i},\end{align*} $$

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 $

$$ \begin{align*}A_{\pi;a;a_i}({\mathfrak C}'/a_i)\cdot A_{\theta;a;a_i}({\mathfrak C}'/a_i)\cdot A_{\pi;a;a_i}({\mathfrak C}'/a_i) \subseteq A_{\varphi;a;a_i}({\mathfrak C}'/a_i).\end{align*} $$

Claim. For any finite $I\subseteq \omega $

$$ \begin{align*}\models \theta(\sigma_I(a),a,a_i)\iff i\notin I.\end{align*} $$

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}'/a_{<\omega })$ . By Claim 3.3, the set $ A_{\pi ;a;a_i}({\mathfrak C}'/a_{<\omega })$ is a group, and so we get $\sigma _{I}\in A_{\pi ;a;a_i}({\mathfrak C}'/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}'/a_{<\omega })$ . Then, $\theta (\sigma _{I}(a),a,a_i)$ does not hold. Otherwise,

$$ \begin{align*}\sigma_I = \sigma_{I_0} \sigma_i \sigma_{I_1}\in A_{\theta;a;a_i}({\mathfrak C}'/a_{<\omega}),\end{align*} $$

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

$$ \begin{align*}\sigma_i\in A_{\varphi;a;a_i}({\mathfrak C}'/a_{<\omega}),\end{align*} $$

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}'$ -small z), and let $a_0\subseteq \mathfrak {C}'$ be such that $\pi (x,y,a_0)$ relatively defines an equivalence relation on $p\!\upharpoonright _{a_0}\!\!(\mathfrak {C}')$ . 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

$$ \begin{align*}\bigcap_{j\neq i} \pi({\mathfrak C}',{\mathfrak C}',a_j)\cap(p\!\upharpoonright_{a_{<\lambda}}\!\!({\mathfrak C}'))^2\subseteq\pi({\mathfrak C}',{\mathfrak C}',a_i).\end{align*} $$

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

$$ \begin{align*}\bigcap_{j\neq i} \pi({\mathfrak C}',{\mathfrak C}',a_j)\cap(p\upharpoonright_{a_{<\lambda}}\!\!({\mathfrak C}'))^2\not\subseteq\pi({\mathfrak C}',{\mathfrak C}',a_i).\end{align*} $$

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}'$ be an A-indiscernible sequence obtained by extracting indiscernibles from the sequence $(a_i,b_i,c_i)_{i<\lambda }$ (e.g., see [1, 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:

$$ \begin{align*} (b_i^{\prime},c_i^{\prime})&\in\bigcap_{j\neq k}\pi({\mathfrak C}',{\mathfrak C}',a_j^{\prime})\cap (p\!\upharpoonright_{a^{\prime}_{<\omega}}\!\!({\mathfrak C}'))^2;\\ (b_i^{\prime},c_i^{\prime})&\not\in\pi({\mathfrak C}',{\mathfrak C}',a_i^{\prime});\\ a_i^{\prime}&\equiv_{A}a_0' \equiv_A a_0. \end{align*} $$

(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}')^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 $

$$ \begin{align*}(b_i^{\prime},c_i^{\prime})\not\in\varphi({\mathfrak C}',{\mathfrak C}',a_i^{\prime}).\end{align*} $$

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' \equiv _A a_0$ , $\pi (x,y,a_0)$ relatively defines an equivalence relation on $p\!\upharpoonright _{a_0}\!\!(\mathfrak {C}')$ , 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}')$ 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}')$ relatively type-definable over a ${\mathfrak C}$ -small set of parameters from ${\mathfrak C}$ and with stable quotient $p({\mathfrak C}')/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}')$ 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}')$ 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}')$ 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}')$ 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

$$ \begin{align*}\bigcap_{j\in I}E_j=\bigcap_{j\in I}\bigcap_{i\in I_j} F^i_j.\end{align*} $$

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 [2, 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}')$ 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}')$ with 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}',{\mathfrak C}',a_j)\cap p({\mathfrak C}')^2\not \subseteq \pi ({\mathfrak C}',{\mathfrak C}',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}')$ ; by Lemma 2.5, this relation also yields a stable quotient on $p\!\upharpoonright _{a_0}\!\!({\mathfrak C}')$ .

Let $(b_i,c_i)_{i<\nu }$ be a sequence witnessing that $\bigcap _{j<i}\pi ({\mathfrak C}',{\mathfrak C}',a_j)\cap p({\mathfrak C}')^2\not \subseteq \pi ({\mathfrak C}',{\mathfrak C}',a_i)$ . Let $(a_i^{\prime },b_i^{\prime },c_i^{\prime })_{i< \nu } \subseteq {\mathfrak C}'$ 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 $

$$ \begin{align*}(b_i^{\prime},c_i^{\prime}) \in \left(\bigcap_{j<i}\pi({\mathfrak C}',{\mathfrak C}',a^{\prime}_j)\cap (p\!\upharpoonright_{ a^{\prime}_{<\nu}}\!\!({\mathfrak C}'))^2\right)\setminus \pi({\mathfrak C}',{\mathfrak C}',a^{\prime}_i).\end{align*} $$

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

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

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}'$ 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 ,$

$$ \begin{align*} (**)\;\;\;\;\;\; (e_i^{\prime},f_i^{\prime}) \in \left(\bigcap_{j< i}\pi({\mathfrak C}',{\mathfrak C}',d_j^{\prime})\cap (p\!\upharpoonright_{a^{\prime}_{\substack{\alpha<\nu\\ \alpha \neq \beta}}, d^{\prime}_{<\omega}}\!\!({\mathfrak C}'))^2\right) \setminus\pi({\mathfrak C}',{\mathfrak C}',d_i^{\prime}). \end{align*} $$

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}',{\mathfrak C}',d_i^{\prime })$ .

Moreover, since $d_i^{\prime } \equiv _A a_0'$ 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}')$ .

Let us consider the set

$$ \begin{align*}X:=p\! \upharpoonright _{a^{\prime}_{\substack{\alpha<\nu\\\alpha\neq \beta} }}\!\!({\mathfrak C}').\end{align*} $$

By the above choices and A-invariance of p, the type $\bigcup _{\substack {\alpha <\nu \\\alpha \neq \beta } }\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

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

Hence,

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 }_{\substack {\alpha <\nu \\\alpha \neq \beta } },d_i^{\prime }}\!\!({\mathfrak C}')$ . 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\hspace{-1pt}<\hspace{-1pt}i$ . Since , there is $\sigma \in \operatorname {\mathrm {{Aut}}}({\mathfrak C}'/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 {\mathrm {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 {\mathrm {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:

$$ \begin{align*} \pi(e_j^{\prime},f_j^{\prime},d_i^{\prime}) &\text{ for all } i\neq j; \hspace{3pt} i,j<\omega;\\ \neg\varphi(e_i^{\prime},f_i^{\prime},d_i^{\prime}) &\text{ for all } i<\omega. \end{align*} $$

Take any $a \models p\! \upharpoonright _{d^{\prime }_{<\omega }}$ . Since $d_i^{\prime } \equiv _A d_0'$ for all $i<\omega $ and p is A-invariant, we get that $d_i^{\prime }\equiv _a d_0'$ 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}'$ be such that ${\mathfrak C}_1$ is ${\mathfrak C}'$ -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}')$ 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}')$ , 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}')$ 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 [2], $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 [6, Section 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}')$ , 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

$$ \begin{align*}d:{\mathfrak C}'\times{\mathfrak C}'\to \mathbb{R}\sqcup \mathbb{Q}_+\sqcup\mathbb{Q}_-\sqcup \{\infty\}\end{align*} $$

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

$$ \begin{align*} &d(x,y)=q\in\mathbb{Q} \iff y=f_q(x);\\ &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);\\ &d(x,y)=q_+ \in \mathbb{Q}_+ \iff y\ne f_q(x) \text{ is infinitely close to }f_q(x)\text{ on the right;}\\ &d(x,y)=q_- \in \mathbb{Q}_- \iff y \ne f_q(x) \text{ is infinitely close to }f_q(x)\text{ on the left;}\\ &d(x,y)=\infty \iff \neg(R_s(x,y)\lor R_s(y,x)) \text{ for all } s\in \mathbb{Q}^+. \end{align*} $$

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'+q_+:=(q'+q)_+ \text { and }q'+q_-:=(q'+q)_-$ for any $q,q' \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'}(a,b)$ and $\neg R_{q'}(a,c)$ hold for some $q'\in \mathbb {Q}^+$ (for any $r_1<q'<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 \ne \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

$$ \begin{align*} \mathrm{tp}^{\mathrm{qf}} (b_1,\dots,b_n,b_{n+1})=\mathrm{tp}^{\mathrm{qf}}(a_1,\dots,a_n, a_{n+1}). \end{align*} $$

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})\ne d(a_1,a_i)$ for all $1< i \leq n$ . Hence, Lemma 4.1 implies that

$$ \begin{align*} \mathrm{tp}^{\mathrm{qf}}(b_1,\dots,b_n,b_{n+1})=\mathrm{tp}^{\mathrm{qf}}(a_1,\dots,a_n, a_{n+1}).\\[-34pt] \end{align*} $$

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

$$ \begin{align*} \bigwedge_{c\in{\mathfrak C}}\bigwedge_{n\in\omega}\neg R_n(x,c)\wedge \neg R_n(c,x). \end{align*} $$

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

$$ \begin{align*}\bigwedge_{r\in\mathbb{Q}^+}R_r(x,y)\vee R_r(y,x)\end{align*} $$

and by $E\!\upharpoonright _{p}$ the equivalence relation on $p({\mathfrak C}')$ relatively defined by the same partial type.

Lemma 4.3. The hyperdefinable set ${\mathfrak C}'/E({\mathfrak C}',{\mathfrak C}')$ is stable.

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

Clearly, the elements c and $c'$ are in the same E-class if and only if $c=c'$ or $d(c,c')=0_{\pm }$ .

Note that whenever $d(c,a) =d(c',a)\neq \infty $ , then $cEc'$ . Therefore, specifying the distance $d(c,a) \ne \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 {\mathrm {{tp}}}(c/A)$ . Therefore, $|S_{{\mathfrak C}'/E}(A)| \leq \mathfrak {c}\times \mathfrak {c} +1= \mathfrak {c}$ .

Proposition 4.4. The only equivalence relations on $p({\mathfrak C}')$ 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}')$ 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}')$ such that $aFb$ and $\models \bigwedge _{n\in \mathbb {N}}\neg S_n(a,b)$ . For any $c,d\in p({\mathfrak C}')$ we can find $e\in p({\mathfrak C}')$ 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.,

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

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}')$ with $aFb$ there exists $n\in \mathbb {N}$ such that $\models S_n(a,b)$ .

First, we show that $aFb$ implies $aE\!\upharpoonright _pb$ . 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 {\mathrm {Aut}}({\mathfrak C}'/{\mathfrak C})$ satisfying $\sigma (a)=b$ . Let $b_i:=\sigma ^i(a)$ for $i<\omega $ . Clearly,

$$ \begin{align*}(a,b)\equiv_{{\mathfrak C}}(b,b_2)\equiv_{{\mathfrak C}}(b_2,b_3)\equiv_{{\mathfrak C}}\ldots .\end{align*} $$

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'\in p({\mathfrak C}')$ such that $aFb'$ and $\models \neg S_n(a,b')$ 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}')$ such that $aFb$ , and so $aE\!\upharpoonright _pb$ by the last paragraph. Take any distinct $c,d\in p({\mathfrak C}')$ 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}')$ 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}')$ 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 [6, Section 4]. We work in the language $L:=\{+,-,1,R_r(x,y): r\in \mathbb {Q}^+\}$ and our theory T is $\operatorname {\mathrm {{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 [6, Propositions 4.1 and 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}'$ is a reduct of a monster model of $\operatorname {\mathrm {{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

$$ \begin{align*}\{ \neg R_r(x,c)\wedge \neg R_r(c,x) : c\in {\mathfrak C}, r \in \mathbb{Q}^+ \}.\end{align*} $$

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}')$ relatively defined by

$$ \begin{align*}\bigwedge_{r\in\mathbb{Q}^+}S_r(x,y).\end{align*} $$

In other words, this is the relation on $p({\mathfrak C}')$ of lying in the same coset modulo the subgroup of all infinitesimals in ${\mathfrak C}'$ 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}')$ are as follows. Take any $c \in {\mathfrak C}$ . Let $E_c$ be the equivalence relation on $p({\mathfrak C}')$ 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}')$ relatively defined by a type over c. We also have the equivalence relation $E_c^{\mu }$ given by $ x E_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}')$ given as

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

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

$$ \begin{align*}\bigwedge_{a \in A} \bigwedge_{n \in \mathbb{N}^+} R_1(n(x-y),a) \wedge R_1(n(y-x),a).\end{align*} $$

One can also combine the above examples to produce one more class of equivalence relations on $p({\mathfrak C}')$ . 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}'$ defined by

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

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

Theorem 4.7. The only equivalence relations on $p({\mathfrak C}')$ 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 \ne 0$ or $n \ne 0$ .

Proof Let $F(x,y)$ be an arbitrary equivalence relation on $p({\mathfrak C}')$ 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}')$ 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',b'\in p({\mathfrak C}')$ . By compactness and $|{\mathfrak C}|^+$ -saturation of ${\mathfrak C}'$ , we can find $d'\in p({\mathfrak C}')$ such that $\models \bigwedge _{n \in \mathbb {Q}^+} \bigwedge _{c\in {\mathfrak C}}\neg S_n(t(a',d'),c)$ and $\models \bigwedge _{n \in \mathbb {Q}^+} \bigwedge _{c\in {\mathfrak C}}\neg S_n(t(b',d'),c)$ for all non-constant terms $t(x,y)$ . Then, by q.e. and [6, Remark 4.6], $(a',d')\equiv _{{\mathfrak C}}(a,b)\equiv _{{\mathfrak C}}(b',d')$ . Since F is ${\mathfrak C}$ -invariant, we conclude that $a'Fb'$ , hence F is the total equivalence relation.

Case 2: For any $ a$ , $b\in p({\mathfrak C}')$ 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}')$ such that

$$ \begin{align*}(*) \;\;\;\;\;\; aFb \;\;\textrm{and}\;\; \models \bigwedge_{q\in \mathbb{Q}^+ } \neg S_q(a,b) \;\; \textrm{and}\;\; a+b\in p({\mathfrak C}'). \end{align*} $$

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}')$ 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',b') \in F$ and elements $c,c' \in {\mathfrak C}$ such that $c-c' \notin \mu $ and $a+b -c \in \mu $ and $a'+b'-c' \in \mu $ . In this second case, applying an an automorphism of ${\mathfrak C}'$ over ${\mathfrak C}$ mapping $a'$ to a, we may assume that $a'=a$ , and so we get $F(b,b')$ and $b-b' \in c-c' + \mu $ . Then $b+b' \in 2b' +c -c' + \mu $ is not related to any element of ${\mathfrak C}$ (as $2b'$ is not related), so $b+b' \in p({\mathfrak C}')$ . Since we assumed that $(*)$ fails, we conclude that $S_m(b,b') \wedge \neg S_n(b,b')$ 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 {\mathrm {Aut}}({\mathfrak C}'/{\mathfrak C})$ be such that $\sigma (a)=b$ ; set $b_k:=\sigma ^k(a)$ . We produced an infinite sequence.

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}')$ . As we can use arbitrarily large k, by compactness (or rather $|{\mathfrak C}|^+$ -saturation of ${\mathfrak C}'$ ), there exist b such that $(a,b)$ satisfies $(*)$ , a contradiction.

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

$$ \begin{align*}(**)\;\;\;\;\;\; aFb' \;\; \textrm{with}\;\; a+b',a-b'\in p({\mathfrak C}').\end{align*} $$

Namely, either $b':=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 {\mathrm {Aut}}({\mathfrak C}'/{\mathfrak C})$ be such that $\sigma (a)=b$ ; set $b_k:=\sigma ^k(a)$ . We have the following sequence.

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'$ using compactness (or rather $|{\mathfrak C}|^+$ -saturation of ${\mathfrak C}'$ ).

Since we are working in a divisible group, using [6, 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}')$ . Notice that for each $d \in p({\mathfrak C}')$ there exists at most one rational q such that

$$ \begin{align*}S_k(t_q(a,d),c)\end{align*} $$

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

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

$$ \begin{align*}aFb"\;\; \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),\end{align*} $$

contradicting the assumption of Case 2.

Namely, either $d:=b'$ 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'),c)$ . By the choice of a and $b'$ satisfying $(**)$ , we have that $q \notin \{-1,0,1\}$ .

Again, let $\sigma \in \operatorname {\mathrm {Aut}}({\mathfrak C}'/{\mathfrak C})$ be such that $\sigma (a)=b'$ ; set $b^{\prime }_k:=\sigma ^k(a)$ . We havethe following sequence.

Then $aFb_k'$ 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')$ is related to some element of ${\mathfrak C}$ . Hence, by an observation above, we get that for all rationals $r \ne q^k$ , $t_r(a,b_k')$ 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"$ 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 {\mathrm {dcl}}$ -closed subset of ${\mathfrak C}$ over which F is relatively defined on $p({\mathfrak C}')$ . Extending the notation from before the statement of Theorem 4.7, for any $B' \subseteq B$ put

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

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

$$ \begin{align*}F \subseteq \bigcap \{E_{B'}: B' \subseteq B \;\; \textrm{such that}\;\; F \subseteq E_{B'}\} = E_A,\end{align*} $$

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}')$ such that $\alpha F\beta $ . Then

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

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

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

determines a complete type over $\operatorname {\mathrm {dcl}}(A,\alpha )$ . By o-minimality of $(\mathbb {R},+,-,1,\leq )$ , this boils down to showing that there is no $b \in \operatorname {\mathrm {dcl}}^{*}(A,\alpha )$ with $\bigwedge _{a \in A^+} \alpha <b\leq \alpha +a$ , where $\operatorname {\mathrm {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 \ne 1$ , we get that $\alpha $ is related to an element of A which contradicts the fact that $\alpha \in p({\mathfrak C}')$ .

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 {\mathrm {Aut}}({\mathfrak C}'/{\mathfrak C})$ be such that $\sigma (x)=y$ ; set $y_k:=\sigma ^{k}(x)$ . We have the following sequence.

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}'$ ), there exist $x',y' \in p({\mathfrak C}')$ such that $F(x',y')$ and:

1. (1) $\bigwedge _{a \in A^+} 0<y'-x'<a$ ;

2. (2) $\bigwedge _{b \in B^+\setminus A^+} b<y'-x'$ .

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

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

determines a complete type over $\operatorname {\mathrm {dcl}}(B,x')$ . By o-minimality of $(\mathbb {R},+,-,1,\leq )$ , this boils down to showing that there is no $c \in \operatorname {\mathrm {dcl}}^{*}(B,x')$ realizing $\pi (t/x')$ , where $\operatorname {\mathrm {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'$ for some $\beta \in B$ and $q \in \mathbb {Q}$ , so

$$ \begin{align*}\bigwedge_{a\in A^+} \bigwedge_{b \in B^+\setminus A^+} b<\beta +(q-1)x'<a.\end{align*} $$

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 \ne 1$ , as $1\in A$ , we get that $x'$ is related to an element of B, which contradicts the fact that $x' \in p({\mathfrak C}')$ .

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 {\mathrm {Aut}}({\mathfrak C}'/{\mathfrak C})$ mapping $y'$ to $\alpha $ , we obtain $\gamma :=\sigma (x')$ 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'y' \equiv _B \gamma \beta $ . As $(x',y') \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}')$ . Since $F \ne \;=$ , there exists $b \ne 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' \ne a$ also satisfies $aFb'$ , then $b,b' \in -a+c_0 + \mu $ , so $b-b' \in \mu $ , hence $b=b'$ because $bFb'$ . This unique b belongs to $\operatorname {\mathrm {dcl}}({\mathfrak C}, a)$ , so $g:=a+b-c_0 \in \operatorname {\mathrm {dcl}}({\mathfrak C},a) \cap \mu $ . Since a is not related to any element of ${\mathfrak C}$ and $\operatorname {\mathrm {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}')$ . Since $E\cap F \ne F$ and $F \subseteq E_{c_0}^{\mu }$ , there exists $b\in p({\mathfrak C}')$ 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 {\mathrm {Aut}}({\mathfrak C}'/{\mathfrak C} a)$ .

Since $\sigma (g)-g \in \mu _A$ for every $\sigma \in \operatorname {\mathrm {Aut}}({\mathfrak C}'/{\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 {\mathrm {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 {\mathrm {dcl}}^{*}$ is the definable closure computed in the language $\{+,-,1,\leq \}$ (which coincides with $\operatorname {\mathrm {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 {\mathrm {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}')$ 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' \in [a]_F$ . Since $(a,b) \in F \setminus E$ and $F \subseteq E_{c_0}^{\mu }$ , we have that $b' \in a + \mu $ or $b' \in b + \mu $ . As $E \cap F=E_A$ , we conclude that $b' \in a + \mu _A$ (and so $b'E_{A,c}a$ ) or $b' \in b+ \mu _A$ (and so $b'E_{A,c}b$ which together with $aE_{A,c}b$ implies $b'E_{A,c}a$ ).

Corollary 4.8. The equivalence relation E is the finest equivalence relation on $p({\mathfrak C}')$ 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}')/E$ is stable by [6, 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}')$ 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}')/F=p({\mathfrak C}')$ is clearly unstable.)

Pick any $\alpha \in A$ . It is easy to check that for every $a,d,e\in {\mathfrak C}'$ and infinitesimal $c\in {\mathfrak C}'$ 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}')$ and infinitesimal $c\in {\mathfrak C}'$ 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

$$ \begin{align*}\operatorname{\mathrm{{tp}}}([a^{\prime}_i]_F,[a^{\prime}_{i+1}]_F/ {\mathfrak C})\neq\operatorname{\mathrm{{tp}}}([a^{\prime}_{i+1}]_F, [a^{\prime}_i]_F/ {\mathfrak C}).\end{align*} $$

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