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 [Reference Krupiński and Portillo6, 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$ .

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

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.

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.

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.

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.

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.

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

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 [Reference Hrushovski, Krupiński and Pillay3, 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 $ .

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.

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 [Reference Ben-Yaacov1, 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.

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

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 [Reference Haskel and Pillay2, 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.

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

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.

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*} $$

Proof By [Reference Krupiński and Portillo6, 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}$ .

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.

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

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}$ .

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 [Reference Krupiński and Portillo6, 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 [Reference Krupiński and Portillo6, 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.

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.