ON LARGE EXTERNALLY DEFINABLE SETS IN NIP

Abstract

We study cofinal systems of finite subsets of $\omega _1$. We show that while such systems can be NIP, they cannot be defined in an NIP structure. We deduce a positive answer to a question of Chernikov and Simon from 2013: In an NIP theory, any uncountable externally definable set contains an infinite definable subset. A similar result holds for larger cardinals.

1 Introduction

Suppose that M is a structure and x a tuple of variables. Recall that a set $X \subseteq M^x$ is M -definable if there is some formula $\phi (x)$ over M such that $\phi (M)=X$ . The set X is externally definable if there is some elementary extension $N \succ M$ and a formula $\psi (x)$ over N such that .

When ${\operatorname {Th}}(M)$ is stable, all externally definable subsets are in fact M-definable (this is a characterization of stability: all types over any model are definable).

Let T be a theory. We consider the following natural question:

Question 1.1. Is there some (infinite) cardinal $\lambda $ such that for any $M \vDash T$ and any externally definable set $X \subseteq M^k$ , if $|X| \geq \lambda $ , then X contains an infinite M-definable subset?

We cannot hope to say much about externally definable sets in arbitrary theories. In particular, supposing that T has a strong form of the independence property (IP), the answer to Question 1.1 is negative (see Remark 5.5). On the other hand:

Fact 1.2. [CS13, Corollary 1.12]

Suppose T is not IP (NIP). Then the answer to Question 1.1 is positive: One can take $\lambda = \beth _\omega $ .

For a complete theory T, let $\text {ext}(T)$ be the minimal $\lambda $ as in Question 1.1 if such exists, and $\text {ext}(T) = \infty $ otherwise. If T is NIP, Fact 1.2 shows that $\text {ext}(T) \leq \beth _\omega $ . We first observe that we cannot hope to improve this to $\text {ext}(T) = \aleph _0$ .

Example 1.3. [CS13, just above Question 1.13] Let M be the linear order $(\omega + \mathbb {Z}, <)$ , whose theory is NIP (and even dp-minimal; see [Sim15, Proposition A.2]). Then, $\omega $ is externally definable (as is any cut), but no infinite subset of $\omega $ is M-definable since ${\operatorname {Th}}(M)$ has quantifier elimination after adding the successor and predecessor functions. Thus, $\text {ext}({\operatorname {Th}}(M))\geq \aleph _1$ .

In their paper [CS13, Question 1.13], Chernikov and Simon posed the following question:

Is it true that $\text {ext}(T) \leq \aleph _1$ whenever T is NIP?

In this paper, we positively answer this question (see Main Theorem 1.1). We use the existence of honest definitions (see Definition 2.3 and Fact 2.4). Let $X = \phi (M,c)$ be externally definable and uncountable, and let $\psi (x,z)$ be an honest definition for $\operatorname {tp}_{\phi ^{\operatorname {opp}}}(c/M)$ . This means that for every finite set $X_0 \subseteq X$ , there is some $d\in M^z$ such that

(*) $$ \begin{align} X_0 = \phi(X_0,c) \subseteq \psi(M,d) \subseteq \phi(M,c) = X. \end{align} $$

If one of these sets $Y_d: = \psi (M,d)$ is infinite we are done, so assume for all d as in Equation (*), $Y_d$ is finite. We get a family of finite subsets of X which is cofinal as a subset of the partial order $\mathcal {P}^{<\omega }(X)$ of finite subsets of X. This raises the question:

Question 1.4. Suppose $\mathcal F$ is a cofinal family of finite subsets of $\aleph _1$ . Can $\mathcal F$ have finite VC-dimension?

In other words, can the relation $\mathord {\in } |_{(\aleph _1 \times \mathcal F)}$ be NIP?

In Theorem 3.8, we give a positive answer to Question 1.4. This means that the fact that the honest definition is NIP is not in itself a guarantee that X has an infinite M-definable subset (see Remark 5.2).

On the other hand, we prove that if $\mathcal F$ is a cofinal family of finite subsets of $\aleph _1$ , then the two-sorted structure $(\aleph _1, \mathcal F;\mathord {\in })$ has IP. We conclude (in Theorem 5.1):

Main Theorem 1.1. For T NIP, $\text {ext}(T) \leq \aleph _1$ .

1.1 A generalisation to arbitrary cardinals

We also consider the following generalisation of Question 1.1.

Question 1.5. Let T be a theory and $\kappa $ an infinite cardinal. Is there some cardinal $\lambda $ such that for any $M \vDash T$ and any externally definable set $X \subseteq M^k$ , if $|X| \geq \lambda $ , then X contains an M-definable subset of size $\geq \kappa $ ?

For a complete theory T, let $\text {ext}(T,\kappa )$ be the minimal $\lambda $ as in Question 1.5 (if it does not exist, let $\text {ext}(T,\kappa ) = \infty $ ). So $\text {ext}(T) = \text {ext}(T,\aleph _0)$ . The proof of [CS13, Corollary 1.12] can easily be adapted to show that if T is NIP, then $\text {ext}(T,\kappa ) \leq \beth _\omega (\kappa )$ .

The following slight adaptation of Example 1.3 gives us an NIP theory T (namely DLO) with $\text {ext}(T,\kappa ) \geq \kappa ^+$ for $\kappa \geq \aleph _1$ . Let I be an extension of the linear order $(\kappa ,<)$ where between any two ordinals we put a copy of $\mathbb {Q}$ . Let $M = \mathbb {Q} + I + \mathbb {Q}$ . Then $\mathcal {M}$ is a dense linear order and thus ${\operatorname {Th}}(\mathcal {M})$ has quantifier elimination. The set I is externally definable but contains no M-definable subset of size $\kappa $ .

In fact, we prove the main theorem, Theorem 5.1, in this generality: If T is NIP, then $\text {ext}(T,\kappa )\leq \kappa ^+$ .

1.2 Structure of the paper

In Section 2, we give the necessary preliminaries on NIP and honest definitions. In Section 3, we discuss Question 1.4. In Section 4, we prove the technical lemmas needed to prove Theorem 5.1, which is proven in Section 5 and supplemented by some open questions.

In a previous version of this paper there was a mistake in the proof of Theorem 3.8 (pointed out to us by George Peterzil). The old proof involved the construction of well orders of order type $\omega $ on countable ordinals which agree up to finite sets. Since this result may be of independent interest, we put it in Appendix A.

2 Preliminaries

2.1 Notations

Our notation is standard. We use $\mathcal L$ to denote a first order language and $\phi (x,y)$ to denote a formula $\phi $ with a partition of (perhaps a superset of) its free variables. Let ${\phi ^{\operatorname {opp}}}$ be the partitioned formula $\phi (y,x)$ (it is the same formula with the partition reversed).

T will denote a complete theory in $\mathcal L$ , and $\mathcal {U} \vDash T$ will be a monster model (a sufficiently large saturated model).

When x is a tuple of variables and A is a set contained in some structure (perhaps in a collection of sorts), we write $A^{x}$ to denote the tuples of the sort of x (and of length $|x|$ ) of elements from A; alternatively, one may think of $A^{x}$ as the set of assignments of the variables x to A. If M is a structure and $A \subseteq M^x$ , $b\in M^y$ , then .

When $B \subseteq \mathcal {U}$ , $\mathcal L(B)$ is the language $\mathcal L$ augmented with constants for elements from B so that a set is B-definable if it is definable in $\mathcal L(B)$ .

For an $\mathcal L$ -formula $\phi (x,y)$ , an instance of $\phi $ over $B \subseteq \mathcal {U}$ is a formula $\phi (x,b)$ where $b \in B^y$ , and a (complete) $\phi $ -type over B is a maximal partial type consisting of instances and negations of instances of $\phi $ over B. We write $S_{\phi }(B)$ for the space of $\phi $ -types over B in x (in this notation, we keep in mind the partition $(x,y)$ , and x is the first tuple there). We also use the notation $\phi ^1=\phi $ and $\phi ^0 = \neg \phi $ . For $a \in \mathcal {U}^x$ , we write $\operatorname {tp}_\phi (a/B) \in S_\phi (B)$ for its $\phi $ -type over B.

2.2 VC-dimension and NIP

Definition 2.1 (VC-dimension)

Let X be a set and $\mathcal F\subseteq \mathcal {P}(X)$ . The pair $(X,\mathcal F)$ is called a set system. We say that $A\subseteq X$ is shattered by $\mathcal F$ if for every $S\subseteq A$ there is $F\in \mathcal F$ such that $F\cap A=S$ . A family $\mathcal F$ is said to be a VC-class on X if there is some $n<\omega $ such that no subset of X of size n is shattered by $\mathcal F$ . In this case, the VC-dimension of $\mathcal F$ , denoted by $\operatorname {VC}(\mathcal F)$ , is the smallest integer n such that no subset of X of size $n+1$ is shattered by $\mathcal F$ .

If no such n exists, we write $\operatorname {VC}(\mathcal F)=\infty $ .

Definition 2.2. Suppose T is an $\mathcal L$ -theory and $\phi (x,y)$ is a formula. Say $\phi (x,y)$ is NIP if for some/every $M\vDash T$ , the family is a VC-class. Otherwise, $\phi $ is IP.

The theory T is NIP if all formulas are NIP. A structure M is NIP if ${\operatorname {Th}}(M)$ is NIP.

Definition 2.3. [Sim15, Definition 3.16 and Remark 3.14] Suppose T is an $\mathcal L$ -theory and $M \vDash T$ . Suppose that $\phi (x,y)$ is a formula, $A\subseteq M^{x}$ is some set and $b \in \mathcal {U}^y$ . Say that an $\mathcal L$ -formula $\psi (x,z)$ (with z a tuple of variables each of the same sort as x) is an honest definition of $\operatorname {tp}_{\phi ^{\operatorname {opp}}}(b/A)$ if for every finite $A_0\subseteq A$ there is some $c\in A^{z}$ such

$$\begin{align*}\phi(A_0,b) \subseteq \psi(A,c) \subseteq \phi(A,b).\end{align*}$$

In other words, for all $a\in A$ , if $\psi (a,c)$ holds, then so does $\phi (a,b)$ and for all $a\in A_0$ the other direction holds: If $\phi (a,b)$ holds, then $\psi (a,c)$ holds.

The existence of honest definitions for NIP theories was first proved in [CS13]. This was improved in [CS15] to get uniformity of the honest definitions assuming that T is NIP. This was subsequently improved to:

Fact 2.4. [BKS21, Corollary 5.23]

If $\phi (x,y)$ is NIP, then there is a formula $\psi (x,z)$ that serves as an honest definition for any ${\phi ^{\operatorname {opp}}}$ -type over any set A of size $\geq 2$ .

We also recall the Shelah expansion.

Definition 2.5. For a structure M, the Shelah expansion $M^{\text {Sh}}$ of M is given by: For any formula $\phi (x,y)$ and any $b \in \mathcal {U}^y$ , add a new relation $R_{\phi (x,b)}(x)$ interpreted as $\phi (M,b)$ .

Fact 2.6. [She09]

If T is NIP, then for any $M\vDash T$ , $M^{\text {Sh}}$ is NIP.

3 The VC-dimension of cofinal families of finite subsets of an uncountable set

The goal of this section is to answer Question 1.4.

Definition 3.1. We say that a set $\mathcal F$ of subsets of a set X is $\omega $ -cofinal if every finite subset of X is contained in some element of $\mathcal F$ . (In the case that $\mathcal F$ consists of finite subsets of X, we omit ‘ $\omega $ -’.)

We start with an easy observation.

Remark 3.2. If $\mathcal F$ is an $\omega $ -cofinal family of subsets of an infinite set X such that if $s \in \mathcal F$ then $|s|<|X|$ , then $\in |_{(X \times \mathcal F)}$ is unstable: There exist $(x_i,s_i){i \in \omega }$ such that $x_i \in s_j$ iff $i\leq j$ . Indeed, inductively choose $x_i \in X$ and $s_i \in \mathcal F$ such that $x_i \notin \bigcup _{j<i}s_j$ and $s_i$ contains .

The proof of [CS13, Corollary 1.12(2)] can be adapted to say that if $|X| \geq \beth _\omega $ and $\mathcal F$ is a cofinal family of finite subsets of X, then $\mathcal F$ is not a VC-class (i.e., it has IP). In fact, one can also make a connection between the VC-dimension of $\mathcal F$ and the cardinality of X (via the alternation rank of the appropriate relation). The next proposition replaces $\beth _\omega $ with $\aleph _\omega $ , and gives a precise lower bound on the VC-dimension in terms of the cardinality of X.

Proposition 3.3. If $|X| \geq \aleph _n$ , then any cofinal system $\mathcal F$ of finite subsets of X has VC-dimension $> n$ . So any cofinal set system of finite sets on a set of size $\geq \aleph _\omega $ has IP.

Proof. We may assume $X = \aleph _n$ .

For finite subsets $A,B \subseteq X$ , write $A \vdash B$ to mean that if $D \in \mathcal F$ contains A then $D \cap B \neq \emptyset $ , and write $A \not \vdash B$ for the negation of this.

Observation 3.4. We have $A \not \vdash \emptyset $ for any A since $\mathcal F$ is cofinal.

Observation 3.5. If $A \not \vdash B$ , then there are only finitely many $c \in X$ such that $A \vdash B\cup \{c\}$ . (Indeed, if $D \in \mathcal F$ witnesses $A \not \vdash B$ , then we must have $c \in D$ .)

Observation 3.6. If $A' \subseteq A$ and $A \not \vdash B$ , then $A' \not \vdash B$ .

We find $c_i \in \aleph _i$ for $0\leq i \leq n$ by downwards induction such that for $k = n,...,0,-1$ :

$$\begin{align*}{(+)_k} \begin{cases} \text{for any partition }c_{>k} = A \cup B,\text{ where }A,B\text{ are disjoint and any }b_i \in \aleph_i\text{ for }i \leq k,\\ \qquad\qquad\qquad b_{\leq k} \cup A \not \vdash B. \end{cases} \end{align*}$$

(+) $_n$ holds by Observation 3.4.

(+) $_{-1}$ means that is shattered, from which we conclude.

Suppose (+) $_k$ holds, we choose $c_k \in \aleph _k$ such that (+) $_{k-1}$ holds.

Such a $c_k$ exists because for each of the $\aleph _{k-1}$ choices for $b_{<k}$ and A, there are only finitely many choices to rule out. More explicitly, for every choice of $b_{<k}$ as above, and any $A \subseteq c_{>k}$ such that , let . By Observation 3.5, $s_{b_{<k},A}$ is finite for each such $b_{<k},A$ , and let .

(+) $_{k-1}$ holds: If $c_k \in A$ , then we are done by induction, and otherwise $c_k \in B$ and this follows from Observation 3.6 and the choice of $c_k$ .

Remark 3.7. With the same proof mutatis mutandis, one can see that if $\mathcal F$ is an $\omega $ -cofinal family of subsets of X, each of size $<\aleph _\alpha $ , and if $|X| \geq \aleph _{\alpha +n}$ , then $\mathcal F$ has VC-dimension $>n$ .

Theorem 3.8. There is a cofinal family $\mathcal F$ of finite subsets of $\aleph _1$ of VC-dimension 2.

Proof. Let $\delta \leq \omega _1$ . Suppose that $\mathcal {C} = (\mathord {<^\alpha }){\alpha <\delta }$ is a sequence of linear orders, where $<^\alpha $ is a linear order on $\alpha $ . We define the following relation on triples $\alpha ,\beta ,\gamma <\delta $ : $\alpha , \beta \vdash _{\mathcal {C}} \gamma $ iff $\beta ,\gamma <\alpha $ and $\gamma <^\alpha \beta $ . Say $B \subseteq \delta $ is $\vdash _{\mathcal {C}}$ -closed if for any $\alpha ,\beta \in B$ , if $\alpha ,\beta \vdash _{\mathcal {C}} \gamma $ , then $\gamma \in B$ .

We inductively define well-orders $<^\alpha $ on $\alpha < \omega _1$ such that

$(*)_\alpha $ any finite subset $A \subseteq \alpha $ extends to a finite subset $A \subseteq B \subseteq \alpha $ such that $B\cup \{\alpha \}$ is $\vdash _{\mathcal {C}_\alpha }$ -closed for $\mathcal {C}_{\alpha }:=(<^\beta ){\beta \leq \alpha }$ .

$(*)_0$ holds with $<^0$ the empty order.

Suppose $(*)_\alpha $ holds. Let $<^{\alpha +1}$ be the order obtained from $<^\alpha $ by putting $\alpha $ at the start: . Let $A \subseteq \alpha +1$ . By $(*)_\alpha $ , let $B \subseteq \alpha $ be a finite set containing such that $B' := B \cup \{\alpha \}$ is $\vdash _{\mathcal {C}_{\alpha }}$ -closed. Then it follows from the definition of $<^{\alpha +1}$ that also $B' \cup \{\alpha +1\}$ is $\vdash _{\mathcal {C}_{\alpha +1}}$ -closed. Since $B'$ is finite and contains A, we conclude that $(*)_{\alpha +1}$ holds.

Suppose that $\eta < \omega _1$ is a limit ordinal and $(*)_\alpha $ holds for all $\alpha < \eta $ . Note that for $\alpha <\beta <\eta $ and any $B\subseteq \alpha $ , B is $\vdash _{\mathcal {C}_\alpha }$ -closed iff B is $\vdash _{\mathcal {C}_\beta }$ -closed.

Since $\eta $ is countable, it follows that $\eta = \bigcup _{n \in \omega } S_n$ , where for each $n<\omega $ , $S_n$ is finite, $S_n \subseteq S_{n+1}$ and $S_n$ is $\vdash _{\mathcal {C}_\alpha }$ -closed for any (some) $\alpha <\eta $ such that $S_n \subseteq \alpha $ . (In the construction, given $S_n$ , let $S_n' = S_n \cup \{\beta _n\}$ , where $(\beta _n){n<\omega }$ enumerates $\eta $ and let $S_{n+1}$ be finite and $\vdash _{\mathcal {C}_{\alpha }}$ -closed containing $S_n'$ for $\alpha <\eta $ such that $S_n'\subseteq \alpha $ .) We define $<^\eta $ to be of order type $\omega $ in such a way that each $S_n$ is an initial segment. Then $(*)_\eta $ holds: If A is a finite subset of $\eta $ , then A is contained in some $S_n$ which is finite and $\vdash _{\mathcal {C}_\alpha }$ -closed for any $\alpha $ large enough, and since $S_n$ is an initial segment of $<^\eta $ , $S_n\cup \{\eta \}$ is $\vdash _{\mathcal {C}_\eta }$ -closed.

Finally, let $\mathcal {C} = ({\mathord {<^\alpha }}){\alpha <\omega _1}$ and $\mathord {\vdash } = \mathord {\vdash }_{\mathcal {C}}$ . Let $\mathcal F$ be the family of finite subsets of $\omega _1$ which are $\vdash $ -closed. By the above construction, $\mathcal F$ is cofinal. As for any triple $\alpha _0,\alpha _1,\alpha _2<\omega _1$ of distinct ordinals, there is some permutation $\sigma $ of 3 such that $\alpha _{\sigma (0)},\alpha _{\sigma (1)}\vdash \alpha _{\sigma (2)}$ , $\mathcal F$ does not shatter any set of size 3.

Corollary 3.9. The following statement is independent of the Zermelo-Frankel axioms of set theory and Choice (ZFC): there is an NIP cofinal family of finite subsets of $2^{\aleph _0}$ .

Proof. On the one hand, the Continuum Hypothesis (CH) is consistent with ZFC (by Gödel’s theorem; see e.g., [Jec03, Theorem 13.20]), and on the other hand it is consistent with ZFC that $\aleph _\omega < 2^{\aleph _0}$ (using Cohen forcing; see, e.g., [Jec03, Chapter 15, “Cohen Reals”]). Thus, the statement follows from Proposition 3.3 and Theorem 3.8.

Question 3.10. Is there a cofinal family of finite subsets of $\aleph _2$ of VC-dimension 3? More generally: Is the bound in Proposition 3.3 tight, or can we improve $\aleph _\omega $ to a smaller cardinal?

4 NIP and cofinal families of finite subsets of an uncountable set

This section is devoted to proving the following theorem.

Theorem 4.1. Suppose that $\kappa $ is an infinite cardinal, $|X| \geq \kappa ^+$ , and $\mathcal F$ is an $\omega $ -cofinal family of subsets of X, each of size $<\kappa $ . Then $(X,\mathcal F;\mathord {\in })$ has IP (as a two-sorted structure whose only relation is $\mathord {\in } \subseteq X \times \mathcal F$ ).

The proof relies upon the following lemma.

Lemma 4.2. Let $\kappa $ be any infinite cardinal. Assume that:

1. 1. $|X|\geq \kappa ^+$ .

2. 2. $R \subseteq X^n$ and $1\leq n$ .

3. 3. For every $a_1,\dots ,a_{n-1}\in X$ , .

4. 4. For every set $A \subseteq X$ of size $|A|=n$ , for some $a\in A$ and some tuple , $R(a,\bar {a})$ holds.

Then, there is some partition of $\{1,\dots ,n-1\}$ into nonempty disjoint sets $u,v$ such that, letting $x: = ({x_i}){i\in u\cup \{0\}}$ and $y := ({x_i}){i\in v}$ , the partitioned formula $\phi (x,y):= R(x_{0},x_1, \dots , x_{n-1})$ has IP.

Remark 4.3. Lemma 4.2 does not hold if we replace $\kappa ^+$ by $\kappa $ in (1). Indeed, let $X = \omega $ and let $R(x,y) = (x<y)$ . Then (2)–(4) hold for $\kappa = \aleph _0$ and $n=2$ but R is NIP (by, e.g., [Sim15, Proposition A.2]).

Remark 4.4. Note that conditions (1)–(4) imply that $n>2$ . If $n=1$ then by (3), R defines a set of size $<\kappa $ , but by (4), R contains X, contradicting (1). Suppose that $n=2$ and for $a \in X$ let . Let $X_0, X_1 \subseteq X$ be such that $X_0 \cap X_1 =\emptyset $ , $|X_0|=\kappa $ and $|X_1|=\kappa ^+$ . Let . As $|S|\leq \kappa $ , there must be some . As $|s_b|<\kappa $ , there must be some . Then $a \notin s_b$ and $b \notin s_a$ , contradicting (4).

The following example shows that the conditions of Lemma 4.2 can hold when $n=3$ .

Example 4.5. Suppose that for each $\alpha <\omega _1$ , $<^\alpha $ is a well order on $\alpha $ of order type $\omega $ . For $\alpha ,\beta ,\gamma <\omega _1$ , let $R(\gamma , \beta , \alpha )$ hold iff $\gamma ,\beta <\alpha $ and $\gamma <^\alpha \beta $ . Then R satisfies the conditions of Lemma 4.2 with $\kappa = \aleph _0$ .

Remark 4.6. In essence, the proof of Lemma 4.2 is an induction on n, with Remark 4.4 as the base case. However, we need to keep track of sets witnessing IP ( $D^{k,j,\bar {c}}_{\bar A}$ in the proof below), which substantially complicates the proof.

Proof of Lemma 4.2

Assume not, that is, that

1. (5) for any partition of $\{1,\dots ,n-1\}$ into nonempty disjoint sets $u,v$ , letting $x: = ({x_i}){i\in u\cup \{0\}}$ and $y := ({x_i}){i\in v}$ the partitioned formula $\phi (x,y):= R(x_{0},x_1, \dots , x_{n-1})$ is NIP.

Define $R' \subseteq X^n$ by $R'(a_0,\dots ,a_{n-1})$ iff for some tuple $\bar {a} \in \{a_1,\dots ,a_{n-1}\}^{n-1}$ , $R(a_0,\bar {a})$ holds. Note that $R'$ satisfies (2)–(5) above (it satisfies (5) as a finite disjunction of NIP relations; in fact (5) can now be simplified by saying that $R'(x_{0},\dots ,x_{k-1};x_{k},\dots ,x_{n-1})$ is NIP for any $1<k<n$ ). Thus, we can replace R with $R'$ and assume in addition that

1. (6) For any tuple $\bar {a} \in X^{n-1}$ and for any permutation $\bar {a}'$ of $\bar {a}$ , $R(X,\bar {a})=R(X,\bar {a}')$ .

For any nonempty set $t \subseteq X$ of size $\leq n-1$ , let $s_t = R(X,\bar {a})$ , where $\bar {a}$ is any enumeration of t of length $n-1$ ; this is well-defined by (6). We can then restate (4) as:

$\boxtimes $ For every t of size n, for some $a\in t$ , .

We may assume that $|X|=\kappa ^+$ and even that $X = \kappa ^+$ . When we say that a subset of X is ‘cofinal’ or ‘contains an end segment of some cofinal set’, we mean with respect to the canonical order on $\kappa ^+$ . For a cofinal set $D \subseteq X$ and some property $P \subseteq X$ , write $\forall ^* x\in D \ P(x)$ to mean that P contains an end segment of D. By downwards induction on $k \in [2,n]$ (note that by Remark 4.4, $n>2$ , so this range for k makes sense), we will find:

1. (A) $m_k < \omega $ , and

2. (B) a cofinal set $D^{k,j,\bar {c}}_{\bar A} \subseteq X$ for every $j \in [k,n)$ and $\bar {c}\in X^{j-k}$ and ${\bar A} \in \prod _{i\in [k,j]}{\mathcal {P}(m_i)}$

such that $\boxplus _k$ and $\boxtimes _k$ below hold. To state these conditions, we first introduce some additional notation:

• • For $l,j$ with $k \leq l \leq j \leq n$ , let $M_l^j := \prod _{i \in [l,j]}{\mathcal {P}(m_i)}$ . We denote elements of $M_l^j$ by $(j+1-l)$ -tuples ${\bar A}$ . For $j<l$ , set $M_l^j := \{\emptyset \}$ .

• • For $j \in [k,n]$ , $t\subseteq X$ of size $k-1$ , $\bar {c}\in X^{j-k}$ , and ${\bar A} \in M_k^{j-1}$ , define sets $s^{k,j,\bar {c},{\bar A}}_t$ as follows. We set $s^{k,n,\bar {c},{\bar A}}_t =s_{t \cup \bar {c}}$ , and then define recursively for $j \in [k,n)$ :

  

• • For $t\subseteq X$ of size $k-1$ , let $s^k_t = s^{k,k,\emptyset ,\emptyset }_t$ .

Now, we can state the conditions to be satisfied by our inductive construction:

• $\boxplus _k$ For every $j \in (k,n)$ and every $c\bar {c}\in X^{j-k}$ and $A{\bar A} \in M_k^j$ , $D^{k,j,c\bar {c}}_{A{\bar A}} \subseteq D^{k+1,j,\bar {c}}_{{\bar A}}$ (for $k\geq n-1$ , this condition holds trivially).

• $\boxtimes _k$ For all $t\subseteq X$ of size $|t|=k$ , for some $a \in t$ , .

Note that each $|s^{k,j,\bar {c},{\bar A}}_t|<\kappa $ by downwards induction on j: For $j=n$ this is clear, and suppose that $|s^{k,j+1,\bar {c}c,{\bar A} A }_t|<\kappa $ for all $c \in X$ and $A\subseteq m_j$ . Towards a contradiction, assume that $s^{k,j,\bar {c},{\bar A}}_t$ contains a set F of size $\kappa $ . We may assume that for some $A \subseteq m_j$ and all $a \in F$ , $\forall ^* c\in D^{k,j,\bar {c}}_{{\bar A} A} \ a\in s^{k,j+1,\bar {c}c,{\bar A} A}_t$ . For any $a \in F$ , there is an end segment $F_a$ of $D^{k,j,\bar {c}}_{{\bar A} A}$ such that for any $c \in F_a$ , $a\in s^{k,j+1,\bar {c}c,{\bar A} A}_t$ . Since $D^{k,j,\bar {c}}_{{\bar A} A}$ is cofinal in $\kappa ^+$ (which is a regular cardinal), $\bigcap _{a\in F}F_a$ contains an end segment of $D^{k,j,\bar {c}}_{{\bar A} A}$ , and in particular is nonempty. Let $c \in \bigcap _{a\in F}F_a$ . Then $F \subseteq s^{k,j+1,\bar {c}c,{\bar A} A}_t$ , contradicting the induction hypothesis.

Note also that for $t \subseteq X$ of size $n-1$ , $s_t = s^{n}_t$ .

We now proceed with the inductive construction of the $m_k$ and $D^{k,j,\bar {c}}_{\bar A}$ .

For $k=n$ , let $m_n=0$ . Then $\boxplus _n$ holds trivially and $\boxtimes _n$ holds by $\boxtimes $ above.

Assume that $2\leq k<n$ , and we found $m_{k'}$ and cofinal sets $D^{k',j,\bar {c}}_{\bar A}$ such that $\boxplus _{k'}$ and $\boxtimes _{k'}$ hold for all $k'>k$ . We want to find $m_k$ and sets $D^{k,j,\bar {c}}_{\bar A}$ such that $\boxplus _k$ and $\boxtimes _k$ hold.

For $m<\omega $ , we let $\otimes _m$ be the following statement: There are

• • cofinal sets $D^{k,j,\bar {c}}_{\bar A}$ for $j \in [k,n)$ and $\bar {c}\in X^{j-k}$ and ${\bar A} \in (\mathcal {P}(m) \times M_{k+1}^j)$ , and

• • subsets $t_i \subseteq X$ of size k for $i < m$

such that:

1. (I) $\boxplus _k$ holds with m playing the role of $m_k$ ;

2. (II) if $B \neq A$ are subsets of m, and , then for some enumeration $\bar {a}$ of $t_i$ , the following hold:

   • $\oplus $ for all $c_k \in D^{k,k,\emptyset }_{(B)}$ , for some $A_{k+1} \subseteq m_{k+1}$ and all $c_{k+1} \in D^{k,k+1,(c_k)}_{(B,A_{k+1})}$ , …, for some $A_{n-1} \subseteq m_{n-1}$ and all $c_{n-1}$ in $D^{k,n-1,(c_k,\dots ,c_{n-2})}_{(B,\dots ,A_{n-1})}$ ,

     $$ \begin{align*}R(\bar{a},c_k,\dots,c_{n-1}) ;\end{align*} $$

   • $\ominus $ for all $c_k \in D^{k,k,\emptyset }_{(A)}$ , for all $A_{k+1} \subseteq m_{k+1}$ and all $c_{k+1} \in D_{(A,A_{k+1})}^{k,k+1,(c_k)}$ , …, for all $A_{n-1} \subseteq m_{n-1}$ and all $c_{n-1}$ in $D_{(A,\dots ,A_{n-1})}^{k,n-1,(c_k,\dots ,c_{n-2})}$ ,

     $$ \begin{align*}\neg R(\bar{a},c_k,\dots,c_{n-1}) .\end{align*} $$

If $\otimes _m$ holds for all $m<\omega $ , we get IP as we now explain. Consider the formula

$$ \begin{align*}\phi(\bar{x},\bar{y}) = \bigvee_{{\bar A} \in M_{k+1}^{n-1}}R(x_0,\dots,x_{k-1};y_k,y_{k+1}^{\bar A},y_{k+2}^{\bar A},\dots,y_{n-1}^{\bar A}).\end{align*} $$

Fix some $m<\omega $ . For $A\subseteq m$ , we define a $\bar {y}$ -tuple $\bar {c}^A$ as follows. Let $c^A_k \in D^{k,k,\emptyset }_{(A)}$ and for $j \in [k+1,n)$ and $(A_{k+1},...,A_{n-1}) \in M_{k+1}^{n-1}$ , inductively let $c^{A,{\bar A}}_j \in D^{k,j,(c^A_k,c^{A,{\bar A}}_{k+1},\dots ,c^{A,{\bar A}}_{j-1})}_{(A,A_{k+1},...,A_j)}$ . Then, by (II) we get that if $B \neq A$ and , then for some tuple $\bar {a}$ enumerating $t_i$ , $\phi (\bar {a},\bar {c}^B)$ holds, while $\phi (\bar {a},\bar {c}^A)$ does not. Let E be the set of all $\bar {x}$ -tuples $\bar {a}$ enumerating $t_i$ for all $i<m$ . We get that the number of $\phi $ -types in $\bar {y}$ over E is exponential in m (at least $2^m$ ). However, $|E|\leq m k!$ . By Sauer–Shelah ([Sim15, Lemma 6.4]), we get that $\phi (\bar {x},\bar {y})$ has IP. As NIP formulas are closed under Boolean combinations, we get that $R(x_0,\dots ,x_{k-1};y_k,\dots ,y_{n-1})$ has IP, contradicting (5).

We first show that $\otimes _0$ holds. Let $D_{(\emptyset )} ^{k,k,\emptyset }=X$ and for $j>k$ , ${\bar A} \in M_{k+1}^j$ , $\bar {c} \in X^{j-(k+1)}$ and $c\in X$ , let $D_{\emptyset {\bar A}} ^{k,j,c\bar {c}} = D_{\bar A} ^{k+1,j,\bar {c}}$ . Then (I) is immediate, and (II) is trivially satisfied.

Let $m_k$ be maximal such that $\otimes _{m_k}$ holds, witnessed by $D^{k,j,\bar {c}}_{\bar A}$ and $t_i$ . We claim that this $m_k$ and $D^{k,j,\bar {c}}_{\bar A}$ satisfy $\boxplus _k$ and $\boxtimes _k$ . $\boxplus _k$ is satisfied by (I), so we are left to check $\boxtimes _k$ .

Assume that $\boxtimes _k$ does not hold. Then there is some $t \subseteq X$ of size k witnessing this: For all $a\in t$ , . We will show that, letting $t_{m_k}:=t$ , we can find new $D^{k,j,\bar {c}}_{\bar A}$ for ${\bar A} \in \mathcal {P}(m_k+1) \times M_{k+1}^j$ and $\bar {c}\in X^{j-k}$ witnessing $\otimes _{m_k+1}$ . We will construct two sequences of cofinal sets, $E_{\bar A}^{k,j,\bar {c}}$ and ${F_{\bar A}^{k,j,\bar {c}}}$ , that will then be used to find suitable D’s.

Let $A_k \subseteq m_k$ . Let . Since $s^{k+1}_t$ has size $<\kappa $ , $E_{(A_k)}^{k,k,\emptyset }$ is still cofinal. Let $c_k \in E_{(A_k)}^{k,k,\emptyset }$ . By $\boxtimes _{k+1}$ applied to $t \cup \{c_k\}$ , and as $c_k \notin s^{k+1}_t$ , for some $a_{c_k,A_k} \in t$ , we have . As t is finite, by reducing $E_{(A_k)}^{k,k,\emptyset }$ , we may assume that there is some $a_{A_k} \in t$ such that for any $c_k \in E_{(A_k)}^{k,k,\emptyset }$ .

Let $j \in (k,n)$ , ${\bar A} \in M_k^j$ , and $\bar {c}\in X^{j-k}$ . Write $\bar {c}=c_k\bar {c}'$ and ${\bar A} = A_k{\bar A}'$ , so ${\bar A}' \in M_{k+1}^j$ . We define cofinal sets $E_{{\bar A}}^{k,j,\bar {c}}$ as follows

• • If , then let $S\subseteq D_{{\bar A}'}^{k+1,j,\bar {c}'}$ be an end segment witnessing this, and set $E_{{\bar A}}^{k,j,\bar {c}}= S \cap D_{{\bar A}}^{k,j,\bar {c}}$ . Note that $E_{{\bar A}}^{k,j,\bar {c}}$ is cofinal as $D_{{\bar A}}^{k,j,\bar {c}} \subseteq D_{{\bar A}'}^{k+1,j,\bar {c}'}$ by $\boxplus _k$ .

• • Otherwise, let $E_{{\bar A}}^{k,j,\bar {c}} = D_{{\bar A}}^{k,j,\bar {c}}$ .

By (upwards) induction on $j \in [k,n)$ , one proves that:

• († _j ) For any $A_k\subseteq m_k$ and any $c_k \in E_{(A_k)}^{k,k,\emptyset }$ there is some $A_{k+1} \subseteq m_{k+1}$ such that for any $c_{k+1} \in E_{(A_k,A_{k+1})}^{k,k+1,(c_k)}$ there is some $A_{k+2} \subseteq m_{k+2}$ such that …for any $c_j \in E_{(A_k,\dots ,A_j)}^{k,j,(c_k,\dots ,c_{j-1})}$ , .

Now, for $A_k \subseteq m_k$ , let $F_{(A_k)}^{k,k,\emptyset } \subseteq D_{(A_k)}^{k,k,\emptyset }$ be a cofinal set such that for any $c \in F_{(A_k)}^{k,k,\emptyset }$ ; such a set exists since .

Then for any $j \in (k,n)$ , any $\bar {c} \in X^{j-k}$ and any ${\bar A} = (A_k,...,A_j) \in M_k^j$ , we similarly define cofinal sets $F_{{\bar A}}^{k,j,\bar {c}}$ as follows.

• • If , let $F_{\bar A}^{k,j,\bar {c}}=D_{\bar A}^{k,j,\bar {c}}$ , and

• • if , let $F_{\bar A}^{k,j,\bar {c}}\subseteq D_{\bar A}^{k,j,\bar {c}}$ be cofinal such that for any $c \in F_{\bar A}^{k,j,\bar {c}}$ .

Recall that by choice of t, for all $a\in t$ . By (upwards) induction on $j \in [k,n]$ one proves that:

• ($ _j ) If $(A_k,...,A_{j-1}) \in M_k^{j-1}$ and $(c_k,\dots ,c_{j-1}) \in X^{j-k}$ are such that $c_i \in F_{(A_k,\dots ,A_i)}^{k,i,(c_k,\dots ,c_{i-1})}$ for every $i \in [k,j)$ , then for every $i \in [k,j]$ ,

  

Now, for any $A{\bar A}\in \mathcal {P}(m_k+1)\times M_{k+1}^j$ , let $G_{A{\bar A}}^{k,j,\bar {c}} := F_{A{\bar A}}^{k,j,\bar {c}}$ if $m_k \notin A$ , else let $G_{A{\bar A}}^{k,j,\bar {c}} := E_{(A \cap m_k){\bar A}}^{k,j,\bar {c}}$ . Now, we show that $({t_i}){i\leq m_k}$ and these $G_{A{\bar A}}^{k,j,\bar {c}}$ witness $\otimes _{m_k+1}$ . Note that $G_{A{\bar A}}^{k,j,\bar {c}}$ is a cofinal subset of $D_{(A\cap m_k){\bar A}}^{k,j,\bar {c}}$ . Hence, $\boxplus _k$ still holds, establishing (I). For (II), let $B \neq A$ be subsets of $m_k+1$ . If and $i < m_k$ , then and so $\oplus $ and $\ominus $ still hold (using $G_{A{\bar A}}^{k,j,\bar {c}} \subseteq D_{(A\cap m_k){\bar A}}^{k,j,\bar {c}}$ ). If not, then $B = A\cup \{m_k\}$ . Let $\bar {a}$ be an enumeration of $t_{m_k}$ starting with $a_{A}$ . Then $\oplus $ follows from $(\dagger _{n-1})$ and $\ominus $ follows from $(\$_n)$ , as required.

This completes the construction of $m_k$ and $D_{\bar A}^{k,j,\bar {c}}$ as in (A), (B) above for all $k \in [2,n]$ .

Finally, $\boxtimes _2$ yields a contradiction by the argument of Remark 4.4. Indeed, by $\boxtimes _2$ we get that for any distinct $a,b \in X$ , either $a \in s^2_{\{b\}}$ or $b \in s^2_{\{a\}}$ . Let $X_0, X_1 \subseteq X$ be such that $X_0 \cap X_1 =\emptyset $ , $|X_0|=\kappa $ and $|X_1|=\kappa ^+$ . Let . As $|S|\leq \kappa $ , there must be some . As $|s^2_{\{b\}}|<\kappa $ , there must be some . But then $a \notin s^2_{\{b\}}$ and $b \notin s^2_{\{a\}}$ – contradiction.

Proof of Theorem 4.1

Suppose that $|X| \geq \kappa ^+$ and that $\mathcal F$ is a cofinal family of subsets of X, each of size $<\kappa $ . Suppose that $\operatorname {VC}(\mathcal F) = n$ .

For any $0\leq k \leq n$ and any $m \leq k$ , let $R_{m,k}(x_0,\dots , x_k)$ be the relation defined by

$$\begin{align*}[\exists t\in \mathcal F\; \bigwedge_{1\leq i \leq k} (x_i \in t)^{(i \leq m)}] \land [\forall t \in \mathcal F\; ((\bigwedge_{1\leq i \leq k} (x_i \in t)^{(i \leq m)})\to x_0 \in t)].\end{align*}$$

(If $k=0$ the conjunction is empty and thus holds trivially, meaning that $R_{0,0}(x_0) = \forall t\in \mathcal F\; x_0\in t$ .)

Let $R(x_0,x_1,\dots ,x_n) = \bigvee _{m \leq k\leq n} R_{m,k}(x_0,\dots ,x_k)$ . We claim that R satisfies the conditions of Lemma 4.2 on X. Conditions (1) and (2) are trivial; condition (3) follows from the fact that it is true for each $m,k$ separately and that each $t \in \mathcal F$ has size $<\kappa $ (using the existential clause of the definition of $R_{m,k}$ ).

We show condition (4). Suppose that $A \subseteq X$ has size $n+1$ . Since $\operatorname {VC}(\mathcal F) = n$ , $\mathcal F$ does not shatter A. Let $B \subseteq A$ be of minimal size such that $\mathcal F$ does not shatter B. Note that B is nonempty, and let $k = |B|-1$ . Since B is not shattered, there is some $B_0 \subseteq B$ such that for no $t \in \mathcal F$ , $t\cap B = B_0$ . Note that $B_0 \neq B$ since $\mathcal F$ is $\omega $ -cofinal (and B is finite). Let $m = |B_0|$ . Let , and let $a_1,\dots ,a_k$ enumerate such that $a_i \in B_0$ iff $i \leq m$ . It follows that $R_{m,k}(a_0,a_1,\dots ,a_k)$ holds: the first clause holds by the minimality of B (any proper subset is shattered), and the second clause follows by the choice of $B_0$ .

By Lemma 4.2, for some permutation $\sigma $ of $\{1,\dots ,n\}$ and some $1<k<n$ the partitioned formula $R(x_{0},x_{\sigma (1)}, \dots , x_{\sigma (k-1)}; x_{\sigma (k)},\dots ,x_{\sigma (n-1)})$ has IP and we are done.

Question 4.7. Let $R(x, y, z)$ be the relation from Example 4.5. The proof of Lemma 4.2 yields that $R(x,y;z)$ has IP. Could the relation $R(x;y,z)$ be NIP? Note that is a cofinal family of finite subsets of $\omega _1$ (see Theorem 3.8).

Similarly, we do not know whether the formula $\phi (x,z;y) = R(x,y,z)$ has IP.

5 Conclusion and final thoughts

We conclude with the final theorem, that is, the generalisation of Main Theorem 1.1 discussed in Section 1.1.

Theorem 5.1. Let $\kappa $ be an infinite cardinal. If $T = {\operatorname {Th}}(M)$ is NIP and $X \subseteq M^k$ is externally definable of size $\geq \kappa ^+$ , then X contains an M-definable subset of size $\geq \kappa $ . In other words, $\text {ext}(T,\kappa ) \leq \kappa ^+$ .

Proof. Suppose that X is defined by $\phi (x,c)$ for some formula $\phi (x,y)$ . Let $\psi (x,z)$ be an honest definition for $\operatorname {tp}_{\phi ^{\operatorname {opp}}}(c/M)$ . This means that for every finite set $X_0 \subseteq X$ , there is some $d\in M^z$ such that

$$\begin{align*}X_0 = \phi(X_0,c) \subseteq \psi(M,d) \subseteq \phi(M,c) = X.\end{align*}$$

Let . Note that Y is definable in $M^{Sh}$ . If for some $d\in Y$ , $\psi (M,d)$ has size $\geq \kappa $ , we are done, so assume for all $d\in Y$ , $|\psi (M,d)|<\kappa $ . Let . Then $N:=(X,\mathcal F; \in )$ is interpretable in $M^{Sh}$ . By Fact 2.6, it follows that N is NIP, contradicting Theorem 4.1 as required.

Remark 5.2. Note that the above proof implies that in an NIP theory, if $X = \phi (M,c)$ is externally definable of size $\kappa ^+$ , then an instance of the honest definition of $\operatorname {tp}_{\phi ^{\operatorname {opp}}}(c/M)$ has size $\geq \kappa $ . By Fact 2.4, we know that the existence of an honest definition $\psi (x,z)$ only requires $\phi $ to be NIP. We do not know if $\psi $ itself can be chosen to be NIP (this is open even for the finite case; see [EK20, Question 22]). However, even if it were NIP, we cannot get a contradiction as in the proof above due to Theorem 3.8.

Question 5.3. Suppose that M is a structure and $X = \phi (M,c)$ is externally definable of size $\geq \aleph _1$ . Suppose that $\phi $ is NIP. Does it follow that X contains an infinite definable subset?

Note that when T eliminates the quantifier $\exists ^\infty $ , the answer is ‘yes’ (even just assuming that X is infinite), as in [CS13, Corollary 1.12(1)]: by Fact 2.4 (or [Sim15, Theorem 3.13]), $\operatorname {tp}_{{\phi ^{\operatorname {opp}}}}(c/M)$ has an honest definition $\psi $ , and so as above some instance $\psi (M,d) \subseteq X$ contains a finite subset $X_0$ large enough that, by elimination of $\exists ^\infty $ , the instance must be infinite.

Refining Question 5.3, we can define $\text {ext}(T,\phi ,\kappa )$ as the minimal $\lambda $ (if exists) such that whenever $M \vDash T$ and $X \subseteq M^k$ is externally definable by $\phi (x,c)$ for some $c\in \mathcal {U}$ , then X contains an M-definable subset of size $\geq \kappa $ . By Theorem 5.1, if T is NIP, then $\text {ext}(T,\phi ,\kappa ) \leq \kappa ^+$ . If the honest definition of $\phi $ is NIP, then by Remark 3.7, if $\kappa = \aleph _\alpha $ , $\text {ext}(T,\phi ,\kappa )\leq \aleph _{\alpha +\omega }$ . If we assume only that $\phi $ is NIP, it is not even clear that $\text {ext}(T,\phi ,\aleph _0)$ exists.

Question 5.4. What is $\text {ext}(T,\phi ,\kappa )$ when $\phi $ is NIP?

Remark 5.5. Let T be a complete theory. Suppose that there is some infinite $\emptyset $ -definable set Z of x-tuples such that $\phi (x,y)$ is random on Z: For any finite disjoint sets $A,B\subseteq Z$ , there is some y-tuple d such that $A = \phi (A\cup B,d)$ (for the notations, see Section 2.1). This is a strong negation of NIP and happens for example, in the case of the random graph. Then every subset of Z is externally definable by compactness. Let $T^{\operatorname {Sk}}$ be a Skolemization of T. Let $\lambda $ be any infinite cardinal, and let $I = ({a_i}){i< \lambda }$ be an indiscernible sequence (in the sense of $T^{\operatorname {Sk}}$ ) contained in Z (in some model of T), and let $N = \operatorname {Sk}(I)$ (the Skolem hull of I). Then is a subset of N which is externally definable by an instance of $\phi $ but which does not contain an infinite N-definable subset (even in $\mathcal L^{\operatorname {Sk}}$ ). Hence, $\text {ext}(T,\phi ,\aleph _0) = \infty $ , and in particular $\text {ext}(T, \aleph _0) = \infty $ .

Question 5.6. Does $\text {ext}(T,\aleph _0) = \infty $ hold whenever T is IP? That is, does every IP theory have a model containing an uncountable externally definable set which contains no infinite definable set?