FORKING IN VC-MINIMAL THEORIES

SARAH COTTER AND SERGEI STARCHENKO

Abstract. We consider VC-minimal theories admitting unpackable generating families, and show that in such theories, forking of formulae over a model M is equivalent to containment in global types definable over M, generalizing a result of Dolich on o-minimal theories in [4].

1. Introduction

VC-minimality, introduced by Adler in [2], is well situated in the hierarchy of notions of model-theoretic well-behavedness: a generalization of the widely-studied notions of strong minimality, weakly o-minimality and C-minimality, it is still sufficiently strong to imply NIP and dp-minimality. In this paper, we cover the basics of VC-minimality, prove some results on the structure of definable sets, and finally generalize a result of Dolich on o-minimal theories to a VC-minimal context. Section 2 includes the basic definitions and results concerning VC-minimality. In Sections 3 and 4, we consider some decompositions of definable sets in VC-minimal theories, and prove some basic results about those decompositions. Finally, section 5 uses results of [3] in a VC-minimal setting, and proves the main result, characterizing forking of formulae over models in certain VC-minimal theories.

2. Preliminaries

We work throughout in a complete first-order theory T. Tuples such as \overline{x} and \overline{a} will always be of finite length; those denoted by x and a are singletons. We will not generally distinguish between a formula φ(x, \overline{a}) and the set B which it defines, writing B = φ(x, \overline{a}) or B ⊆ φ(x, \overline{a}) where convenient.

Definition 2.1.

(1) A set of formulae Ψ = \{ψ_{i}(x, \overline{y}_{i}) : i ∈ I\} is called a directed family if for any ψ_{0}(x, \overline{y}_{0}), ψ_{1}(x, \overline{y}_{1}) ∈ Ψ and any parameters \overline{a}_{0}, \overline{a}_{1} taken from any model of T, one of the following is true: (i): ψ_{0}(x, \overline{a}_{0}) ⊆ ψ_{1}(x, \overline{a}_{1}); (ii): ψ_{1}(x, \overline{a}_{1}) ⊆ ψ_{0}(x, \overline{a}_{0}); (iii): ψ_{0}(x, \overline{a}_{0}) ∩ ψ_{1}(x, \overline{a}_{1}) = ∅.

(2) A theory T is VC-minimal if there is a directed family Ψ such that for any formula φ(x, \overline{y}) and any parameters \overline{c} taken from any model of T, φ(x, \overline{c}) is equivalent to a finite boolean combination of formulae ψ_{i}(x, \overline{b}_{i}), where each ψ_{i} ∈ Ψ. This Ψ will be called a generating directed family.

2010 Mathematics Subject Classification. Primary 03C45, 03C64.

Both authors were partially supported by the NSF.

Remark 2.2. This differs slightly from Adler’s original definition of “directed VCminimal theories” in [2].

Notation 2.3.

• For notational simplicity, we will generally assume that the formulae x = x and x ≠ x are in any generated directed family Ψ.

• An instance of Ψ is a formula ψ(x, \overline{a}), where ψ(x, \overline{y}) ∈ Ψ and the parameters \overline{a} are taken from some model of T.

The following result can be found in [2]:

Proposition 2.4. Strongly minimal, weakly o-minimal, and C-minimal theories are all VC-minimal.

If T is a VC-minimal theory, with generating directed family Ψ, then each formula in Ψ has VC-codimension no greater than one. As a result, every formula has finite VC-dimension, and thus VC-minimal theories are NIP. (In fact, as discussed in [2] and [5], every VC-minimal theory is dp-minimal, a stronger condition.)

For the remainder of this section, let T be a complete VC-minimal theory, with Ψ its generating directed family. We work in large saturated model 𝕌 of T.

Definition 2.5.

(1) A definable set B ⊆ 𝕌 is a ball if B is defined by an instance of Ψ.

(2) A definable set S ⊆ 𝕌 is a Swiss cheese if S = B \ (B_{0} ∪ ... ∪ B_{n}), where each of B, B_{0}, …, B_{n} is a ball. We will call B an outer ball of S, and each B_{i} is called a hole of S.

It follows from Definition 2.1 that every definable set is the union of some finitely many disjoint Swiss cheeses. Writing a definable set τ(x, \overline{a}) as S_{1} ˙∪... ˙∪S_{n}, where each S_{i} is a Swiss cheese, is called a Swiss cheese decomposition of τ(x, \overline{a}). We say a Swiss cheese decomposition is non-trivial if all the Swiss cheeses are non-empty, all of their holes are non-empty, and for no two Swiss cheeses S_{i} and S_{j} is S_{i} ∪ S_{j} also a Swiss cheese. Every definable set has a non-trivial Swiss cheese decomposition, though in general these are not unique.

The following, which we will use frequently, follows from Compactness:

Theorem 2.6. For every formula τ(x, \overline{y}), there are a finite set Ψ_{0} ⊆ Ψ and natural numbers n_{1} and n_{2} such that for every parameter tuple \overline{a}, τ(x, \overline{a}) can be decomposed as the union of at most n_{1} disjoint Swiss cheeses, each of them having at most n_{2} holes, such that all balls appearing in the decomposition are instances of formulae in Ψ_{0}.

In this paper we deal mostly with VC-minimal theories admitting unpackable generating directed families.

Definition 2.7. We say that the generating directed family Ψ is unpackable if no ball can be properly covered by finitely many other balls: that is, for any instances ψ(x, \overline{b}), ψ_{1}(x, \overline{b}_{1}), ...,ψ_{n}(x, \overline{b}_{n}) of Ψ, if ψ(x, \overline{b}) → ⋁_{i=1}^{n} ψ_{i}(x, \overline{b}_{i}) then there is some i such that ψ(x, \overline{b}) → ψ_{i}(x, \overline{b}_{i}).

It is worth noting that for a fixed theory T, unpackability depends on the choice of Ψ. For example, an o-minimal theory can be thought of as being VC-minimal with packable (i.e. not unpackable) generating directed family Ψ = {y ≤ x, y < x, y = x}; it is also VC-minimal if we take Ψ to be {y ≤ x, y = x}, which is unpackable.

Requiring that the generating directed family be unpackable excludes some noteworthy examples: for instance, the complete theory of the additive group of p-adics together with valuation is VC-minimal; however, its standard generating directed family, {v(x − y_{1}) ≥ v(y_{2})}, is packable. On the other hand, all strongly minimal and weakly o-minimal theories are VC-minimal, and we can choose their generating directed families to be unpackable. The complete theory of an algebraically closed valued field is also VC-minimal, and has an unpackable generating directed family consisting of all open and closed balls.

Proposition 2.8. Suppose that Ψ is unpackable. Then any 2-consistent family of Swiss cheeses is consistent.

Proof. Let F = {S_{1}, …, S_{n}} be a finite family of Swiss cheeses, and suppose F is 2-consistent. Write them each as S_{i} = A^{i} \ (B_{1}^{i} ∪ ... ∪ B_{k_{i}}^{i}).

Since F is 2-consistent, the set of outer balls {A^{1}, …, A^{n}} is 2-consistent; as they are balls, this means they must form a chain. Possibly after renumbering, we may assume A^{1} ⊆ A^{2} ⊆ … ⊆ A^{n}.

If the family F were inconsistent, then we would have that A_{1} ⊆ ⋃ B_{j}^{i}; since the sets B_{j}^{i} are balls and Ψ is unpackable, A_{1} would be contained in one of them, A_{1} ⊆ B_{j}^{i}. But then S_{1} ∩ S_{i} = ∅, violating 2-consistency. □

In the case when Ψ is unpackable, we also have a notion of generic types for balls:

Definition 2.9. Suppose Ψ is unpackable. Let B be a non-empty ball, defined over a model M of T. The generic type of (the interior of) B over M is the unique complete type p_{B} ∈ S_{1}(M) such that:

an M-definable ball C is in p_{B} if and only if B ⊆ C.

(The above condition defines a unique type by VC-minimality, and consistency follows from unpackability.)

Remark 2.10. Similarly, the generic type of the exterior of B can be defined as the unique type p ∈ S_{1}(M) with the property that an M-definable ball C is in p if and only if B ⊊ C.

The following theorem is modeled after a result of Holly on valued fields in [6]. The proof presented here is due to A. Dolich.

Theorem 2.11 (Dolich, unpublished). Suppose Ψ is unpackable. Then:

(1) If S is a Swiss cheese, there exist a unique ball A and a unique set of non-empty balls {A_{1}, …, A_{n}} so that S = A \ (A_{1} ∪ ... ∪ A_{n}).

(2) Every definable set has a unique non-trivial Swiss cheese decomposition.

Proof. We establish the theorem by simply rewriting Section 3 of [6]. First, note that wherever [6] has “disc” we use “ball”, and that we also use “outer ball” in place of “block”. We list the necessary changes (any results we do not mention follow mutatis mutandis in our situation):

• Note 3.4: (ii) and (iv) are not relevant to our situation and they are not necessary for any of the ensuing proofs.

• Corollary 3.9: This is not relevant in our situation and plays no role in the rest of the proof.

• Definition 3.10: Should now read: Let S be a subset of a valued field. Points b, c ∈ S are v-connected in S if there are n ≥ 0 and balls D_{1} …, D_{n} and a ball D so that D_{1}, …, D_{n} ⊊ D such that b, c ∈ D \ (D_{1} ∪ ⋯ ∪ D_{n}) ⊆ S.

• Lemma 3.16: Has no simple translation to our situation; wherever it is used we will give alternate arguments.

• Lemma 3.17: We need a different argument for the final paragraph. We have b, c ∈ D\(D_{1}∪⋯∪D_{m}) ⊆ S and that D_{1}∪⋯∪D_{m} cover B\(C_{1}∪⋯∪C_{n}). Also, if D_{i} ∩ B ≠ ∅, then B ⊈ D_{i}. Let D_{1}, …, D_{l} list all the D_{i}’s that intersect B non-trivially. Thus D_{1} ∪ ⋯ ∪ D_{l} ⊆ B. We have that

B \ (C_{1} ∪ ⋯ ∪ C_{n}) ⊆ D_{1} ∪ ⋯ ∪ D_{l} ⊆ B;

from this it follows that B = D_{1} ∪ ⋯ ∪ D_{l} ∪ C_{1} ∪ ⋯ ∪ C_{n}, violating unpackability.

• Lemma 3.18: We need to modify the case where B ∩ C = ∅, which uses Lemma 3.16. Suppose that S ∪ T is v-connected. Pick b ∈ S and c ∈ T. Then we may find a Swiss cheese U = A \ (A_{1} ∪ ⋯ ∪ A_{l}) so that b, c ∈ U ⊆ S ∪ T. Note that A ∩ B ≠ ∅ and A ∩ C ≠ ∅. We can not have that A ⊆ B or A ⊆ C, so B ∪ C ⊆ A. Thus we have that A \ (A_{1} ∪ ⋯ ∪ A_{l}) ⊆ B ∪ C ⊆ A, from which it follows that A = B ∪ C ∪ A_{1} ∪ ⋯ ∪ A_{l}, contradicting unpackability.

• Lemma 3.19: This is the last statement requiring a change. We must rework the third paragraph. Fix D_{1}, …, D_{k}, the maximal sets under containment. Note that these sets are pairwise disjoint. Pick b_{i} ∈ D_{i} for 1 ≤ i ≤ k. If S is v-connected there is a Swiss cheese U = A \ (A_{1} ∪ ⋯ ∪ A_{l}) so that b_{i} ∈ U ⊆ S_{1} ∪ ⋯ ∪ S_{n} for each i. Thus A ∩ D_{i} ≠ ∅ for each 1 ≤ i ≤ k. Note that we can not have A ⊆ D_{i} for any i, and so D_{1} ∪⋯∪D_{k} ⊆ A. Now we have that U ⊆ D_{1} ∪⋯∪D_{k} ⊆ A, which implies that A = D_{1} ∪⋯∪D_{k} ∪A_{1} ∪⋯∪A_{l}, once again contradicting unpackability.

□

So in the case where Ψ is unpackable, Swiss cheese decompositions are canonical. If τ(x, \overline{a}) decomposes as S_{1} ˙∪ ⋯ ˙∪ S_{n}, we may refer to the outer balls of S_{1}, …, S_{n} as the outer balls of τ(x, \overline{a}).

3. Layers

In this section we fix a complete VC-minimal theory T, its generating directed family Ψ, and a large saturated model of 𝕌 of T.

If φ(x) is a formula over a set A, then in general, unless A is a model, the Swiss cheeses in its Swiss cheese decomposition need not be definable over A. This leads us to consider uballs, finite unions of balls, in place of balls.

Definition 3.1.

(1) A definable set C ⊆ 𝕌 is a uball if C = B_{0} ∪ ⋯ ∪ B_{n}, where B_{0}, …, B_{n} are balls.

(2) A definable set D ⊆ 𝕌 is a ucheese if D = C_{1} \ C_{2}, where C_{1} and C_{2} are uballs.

Remark 3.2.

• The intersection of two uballs is a uball.

• If S is a Swiss cheese and B is a uball, then S \ B is a (possibly empty) Swiss cheese.

• A ucheese is the union of finitely many Swiss cheeses whose outer balls are disjoint.

• Assume Ψ is unpackable. If D is a non-empty ucheese, then there exist unique uballs C_{1} and C_{2} such that D = C_{1} \ C_{2} and each ball of C_{2} is properly contained in a ball of C_{1}. The set C_{1} is called the outer uball of D, and C_{2} is the inner uball of D.

Theorem 3.3 (Layer Decomposition). Suppose Ψ is unpackable. For every formula φ(x, \overline{y}) there exist formulae L_{0}^{φ}(x, \overline{y}), …, L_{s}^{φ}(x, \overline{y}) over ∅ such that for any parameter tuple \overline{a} in any model of T:

(1) each L_{i}^{φ}(x, \overline{a}) defines a ucheese;

(2) φ(x, \overline{a}) = ⋃_{i=0}^{s} L_{i}^{φ}(x, \overline{a});

(3) for i ≥ 1 each outer ball of L_{i}^{φ}(x, \overline{a}) is properly contained in a hole of

L_{i−1}^{φ}(x, \overline{a}).

In particular, if we denote the outer and inner uballs of L_{i}^{φ}(x, \overline{a}) by λ_{i}^{+}(x, \overline{a}) and λ_{i}^{−}(x, \overline{a}), respectively, we get that

λ_{s}^{−}(x, \overline{a}) ⊆ λ_{s}^{+}(x, \overline{a}) ⊆ λ_{s−1}^{−}(x, \overline{a}) ⊆ ⋯ ⊆ λ_{1}^{+}(x, \overline{a}) ⊆ λ_{0}^{−}(x, \overline{a}) ⊆ λ_{0}^{+}(x, \overline{a}).

(When it is clear which formula φ we are referencing, we will simply write L_{i}(x, \overline{y}).)

The sets L_{i}(x, \overline{a}) are called the layers of φ(x, \overline{a}). The outer layer L_{0}(x, \overline{a}) is the union of all those Swiss cheeses of φ(x, \overline{a}) not contained in any others; L_{1}(x, \overline{a}) is the outer layer of φ(x, \overline{a}) \ L_{0}(x, \overline{a}), and so on. Each layer is properly contained in the holes of the previous layer.

Proof. Fix a formula φ(x, \overline{y}), and fix the finite set Ψ_{0} ⊆ Ψ as in Theorem 2.6. We construct formulae λ_{i}^{+}(x, \overline{y}) and λ_{i}^{−}(x, \overline{y}) defining the outer and inner uballs of L_{i}(x, \overline{y}), respectively. We need two claims.

Claim 3.4. For every formula τ(x, \overline{z}) ∈ Ψ, there is a formula O_{φ,τ} (\overline{y}, \overline{z}) such that for any parameter tuples \overline{a} and \overline{b} in any model of T, the formula O_{φ,τ} (\overline{a}, \overline{b}) holds iff τ(x, \overline{b}) defines the outer ball of a Swiss cheese of φ(x, \overline{a}).

Proof. Any outer ball of a Swiss cheese of φ(x, \overline{a}) must be an instance of Ψ_{0}. So, to specify that τ(x, \overline{b}) defines an outer ball, it suffices to say that for any instance ψ(x, \overline{c}) of Ψ_{0}:

• if ψ(x, \overline{c}) properly contains τ(x, \overline{b}), then ψ(x, \overline{c}) \ τ(x, \overline{b}) contains a point

not in φ(x, \overline{a}); and

• if ψ(x, \overline{c}) is properly contained in τ(x, \overline{b}), then τ(x, \overline{b}) \ ψ(x, \overline{c}) contains a

point from φ(x, \overline{a}).

Both of these conditions are expressible by a first-order formula. (The empty ball will usually meet these conditions, so we will also specify that τ(x, \overline{b}) ≠ ∅.) □

Claim 3.5. For every formula τ(x, \overline{z}) ∈ Ψ, there is a formula H_{φ,τ} (\overline{y}, \overline{z}) such that for any parameter tuples \overline{a} and \overline{b}, H_{φ,τ} (\overline{a}, \overline{b}) holds iff τ(x, \overline{b}) defines a hole in a Swiss cheese of φ(x, \overline{a}).

Proof. Similar to the previous claim. □

Continuing with the proof of Theorem 3.3, the formulae λ_{i}^{+} and λ_{i}^{−} can be written in terms of the formulae O and H. Let λ_{0}^{+}(x, \overline{y}) be the formula:

⋁_{ψ(x,\overline{z})∈Ψ_{0}} ∃\overline{z}[O_{φ,ψ}(\overline{y}, \overline{z}) ∧ ψ(x, \overline{z})]

and let λ_{0}^{−}(x, \overline{y}) be the formula:

⋁_{ψ(x,\overline{z})∈Ψ_{0}} ∃\overline{z}[H_{φ,ψ}(\overline{y}, \overline{z}) ∧ ψ(x, \overline{z})].

Then for any \overline{a}, the set L_{0}(x, \overline{a}) = λ_{0}^{+}(x, \overline{a})\λ_{0}^{−}(x, \overline{a}) will be a single ucheese, made up of the “outer” Swiss cheeses of φ(x, \overline{a}) - those which are not contained in the holes of any other Swiss cheese of φ(x, \overline{a}).

For the next layer, use the same formulae, but relativized to φ_{1}(x, \overline{y}) = φ(x, \overline{y}) ∧

¬L_{0}(x, \overline{y}). So, let λ_{1}^{+}(x, \overline{y}) be the formula ⋁_{ψ(x,\overline{z})∈Ψ_{0}} ∃\overline{z}[O_{φ_{1},ψ}(\overline{y}, \overline{z}) ∧ ψ(x, \overline{z})], and

let λ_{1}^{−}(x, \overline{y}) be the formula ⋁_{ψ(x,\overline{z})∈Ψ_{0}} ∃\overline{z}[H_{φ_{1},ψ}(\overline{y}, \overline{z}) ∧ ψ(x, \overline{z})]. Continuing in this

fashion, the formulae L_{i}(x, \overline{y}) = λ_{i}^{+}(x, \overline{y})\λ_{i}^{−}(x, \overline{y}) will have the desired properties.

Finally, we know by Theorem 2.6 that there is a uniform bound on the number of balls in Swiss cheeses of any instance of φ(x, \overline{y}). Thus, by induction on the number of balls in Swiss cheeses, after some bounded number s of steps the subsequent sets L_{i}(x, \overline{y}) must all be empty, and φ(x, \overline{a}) = ⋃_{i=0}^{s} L_{i}(x, \overline{a}) for all \overline{a}. □

Remark 3.6. Some useful facts about layer decompositions:

• If φ(x, \overline{a}) defines a uball, then λ_{0}^{+}(x, \overline{a}) = L_{0}(x, \overline{a}) = φ(x, \overline{a}) and λ_{0}^{−}(x, \overline{a}) = ∅.

• If B_{1} and B_{2} are uballs, and each ball of B_{2} is properly contained in a ball of B_{1}, then the layer decomposition of B_{1} \ B_{2} is λ_{0}^{+} = B_{1}, λ_{0}^{−} = B_{2}.

• We can characterize the layers of ¬φ in terms of those of φ: in general, if φ(x, \overline{a}) = ⋃_{i=0}^{s} L_{i}^{φ}(x, \overline{a}) = ⋃_{i=0}^{s} λ_{i}^{+}(x, \overline{a}) \ λ_{i}^{−}(x, \overline{a}), then as sets, the layers of ¬φ(x, \overline{a}) are ¬λ_{0}^{+}(x, \overline{a}), (λ_{0}^{−}(x, \overline{a}) ∧ ¬λ_{1}^{+}(x, \overline{a})), …, (λ_{s−1}^{−}(x, \overline{a}) ∧ ¬λ_{s}^{+}(x, \overline{a})), and λ_{s}^{−}(x, \overline{a}). The numbering will vary slightly, depending on whether or not λ_{0}^{+}(x, \overline{a}) is equivalent to x = x and whether or not λ_{s}^{−}(x, \overline{a}) is empty, but roughly, L_{i}^{¬φ} = λ_{i−1}^{−} \ λ_{i}^{+}.

4. Irreducible uballs

In this section T denotes a complete VC-minimal theory with generating directed family Ψ. Let 𝕌 be a large saturated model of T.

Definition 4.1. Let A ⊆ 𝕌 be a small set.

(1) A uball B is definable over A if there is a formula over A defining B.

(2) A uball B which is definable over A is reducible over A if there exist nonempty disjoint uballs C_{1} and C_{2} which are definable over A such that B = C_{1} ∪ C_{2}.

(3) A uball B which is definable over A is irreducible over A (or A-irreducible) if it is not reducible over A.

(4) An A-irreducible ucheese is a set of the form C_{1} \ C_{2}, where C_{1} and C_{2} are uballs definable over A and C_{1} is irreducible over A.

Remark 4.2. If Ψ is unpackable and B is a ball which is definable over A, then B is irreducible over A.

Proposition 4.3. Suppose that Ψ is unpackable. Then any uball C which is definable over A is the disjoint union of finitely many uballs which are irreducible over A.

Proof. Follows from Remark 4.2 by induction on the number of balls in C. □

Theorem 4.4. (Irreducible decomposition) Suppose that Ψ is unpackable. Then every A-definable set is the disjoint union of finitely many A-irreducible ucheeses.

Proof. Fix an A-definable set φ(x, \overline{a}). For each layer L_{i}(x, \overline{a}) of φ(x, \overline{a}), write its outer uball λ_{i}^{+}(x, \overline{a}) as the disjoint union of A-irreducible uballs B_{i}^{0}, B_{i}^{1}, …, B_{i}^{n_{i}}. Then \{B_{i}^{j} \ λ_{i}^{−}(x, \overline{a}) : 0 ≤ i ≤ s, 0 ≤ j ≤ n_{i}\} is a set of disjoint A-irreducible ucheeses whose union is φ(x, \overline{a}). □

Note that if M is a model of T, then M-irreducible uballs are the same as balls, and the irreducible decomposition is just the Swiss cheese decomposition. The following results provide further parallels between balls and irreducible uballs:

Proposition 4.5. Suppose Ψ is unpackable. If φ_{0}(x, \overline{a}_{0}) and φ_{1}(x, \overline{a}_{1}) define Airreducible uballs, then one of the following holds:

(i): φ_{0}(x, \overline{a}_{0}) ⊆ φ_{1}(x, \overline{a}_{1});

(ii): φ_{1}(x, \overline{a}_{1}) ⊆ φ_{0}(x, \overline{a}_{0});
(iii): φ_{0}(x, \overline{a}_{0}) ∩ φ_{1}(x, \overline{a}_{1}) = ∅.

Proof. Suppose φ_{0}(x, \overline{a}_{0}) ∩ φ_{1}(x, \overline{a}_{1}) ≠ ∅. Then some ball of φ_{0}(x, \overline{a}_{0}) intersects some ball of φ_{1}(x, \overline{a}_{1}); since they are balls, one is contained in the other. Without loss of generality, some ball of φ_{0}(x, \overline{a}_{0}) is contained in some ball of φ_{1}(x, \overline{a}_{1}).

Let ξ(x, \overline{a}_{0}, \overline{a}_{1}) be the formula which says, “x is in an outer ball of φ_{0}(x, \overline{a}_{0}) which is contained in an outer ball of φ_{1}(x, \overline{a}_{1})”. Then ξ(x, \overline{a}_{0}, \overline{a}_{1}) and φ_{0}(x, \overline{a}_{0}) \ ξ(x, \overline{a}_{0}, \overline{a}_{1}) are A-definable disjoint uballs whose union is φ_{0}(x, \overline{a}_{0}). We know ξ(x, \overline{a}_{0}, \overline{a}_{1}) is non-empty, so φ_{0}(x, \overline{a}_{0})\ξ(x, \overline{a}_{0}, \overline{a}_{1}) must be empty by A-irreducibility.

Hence φ_{0}(x, \overline{a}_{0}) = ξ(x, \overline{a}_{0}, \overline{a}_{1}), and so φ_{0}(x, \overline{a}_{0}) ⊆ φ_{1}(x, \overline{a}_{1}). □

Corollary 4.6. Suppose Ψ is unpackable. The intersection of two A-irreducible ucheeses is an A-irreducible ucheese.

Proposition 4.7. Suppose that Ψ is unpackable. Then any 2-consistent family of A-irreducible ucheeses is consistent.

Proof. Let {S_{1}, S_{2}, …, S_{n}} be a 2-consistent set of A-irreducible ucheeses. Write S_{i} = B_{i} \ C_{i}, where B_{i} and C_{i} are A-definable uballs and B_{i} is A-irreducible. The set {B_{1}, …, B_{n}} must be 2-consistent, so by Proposition 4.5, possibly after renumbering, B_{1} ⊆ B_{2} ⊆ ... ⊆ B_{n}.

For each i, let D_{i} = B_{1} ∩ C_{i}. Because B_{1} \ C_{i} ≠ ∅, D_{i} is an A-definable uball and a proper subset of B_{1}. Since B_{1} is A-irreducible, each ball of D_{i} is a proper subset of a ball of B_{1} (if not, “the balls of B_{1} which equal a ball of D_{i}” and “the balls of B_{1} which do not” would be non-empty A-definable uballs whose union is B_{1}).

So, because Ψ is unpackable, B_{1}\(D_{1}∪⋯∪D_{n}) ≠ ∅; take b ∈ B_{1}\(D_{1}∪⋯∪D_{n}). Then b ∈ B_{i} for all i, and b ∉ C_{i} for all i, so b ∈ ⋂ S_{i}. □

5. Forking

In this section we fix a complete theory T and a large saturated model 𝕌 of T. We will need the following result.

Theorem 5.1. [3, Theorem 1.1] Let T be an NT P_{2} theory (a class which includes NIP and simple theories). Then forking and dividing over models are the same – a formula φ(\overline{x}, \overline{a}) forks over a model M iff it divides over M.

In proving our main result later on, we will also need the following slight modification of the standard definitions of forking and dividing.

Definition 5.2. Fix a |𝕌|^{+}-saturated model 𝕍 ≽ 𝕌, and a small model M ≼ 𝕌 of T. Fix also a tuple \overline{β} ∈ 𝕍 such that tp(\overline{β}/𝕌) is definable over M.

(1) For any formula σ(x, \overline{β}, \overline{d}), where \overline{d} ∈ 𝕌, we say that σ(x, \overline{β}, \overline{d}) \overline{β}-divides over M if there is an M-indiscernible sequence ⟨\overline{d}_{i} : i < ω⟩ in 𝕌, with each \overline{d}_{i} ≡_{M} \overline{d}, such that \{σ(x, \overline{β}, \overline{d}_{i}) : i < ω\} is k-inconsistent for some k.

(2) For any formula σ(x, \overline{β}, \overline{d}), where \overline{d} ∈ 𝕌, we say that σ(x, \overline{β}, \overline{d}) \overline{β}-forks over M if it can be written as the disjunction of finitely many formulae σ_{i}(x, \overline{β}, \overline{c}_{i}), where \overline{c}_{i} ∈ 𝕌, each of which \overline{β}-divides over M.

Notice that in the above definition we are allowed to take M-indiscernible sequences \overline{d}_{i} from 𝕌 only, while \overline{β} does not have to be in 𝕌.

The proof of the following proposition is almost identical to that of [3, Lemma 3.14], and we omit it here. The interested reader will find the proof in the appendix.

Proposition 5.3. Let T be an NT P_{2} theory, and let M, 𝕍, and \overline{β} be as in Definition 5.2. Suppose that for some \overline{a}_{1}, \overline{a}_{2} ∈ 𝕌 the formulae σ_{1}(x, \overline{β}, \overline{a}_{1}) and σ_{2}(x, \overline{β}, \overline{a}_{2}) \overline{β}-divide over M. Then σ_{1}(x, \overline{β}, \overline{a}_{1}) ∨ σ_{2}(x, \overline{β}, \overline{a}_{2}) also \overline{β}-divides over M.

Corollary 5.4. Let T be an NT P_{2} theory, let M, 𝕍, and \overline{β} be as in Definition 5.2, and let \overline{a} ∈ 𝕌. Then a formula σ_{1}(x, \overline{β}, \overline{a}) \overline{β}-forks over M iff it \overline{β}-divides over M.

It is proved in [3] that in NT P_{2} theories, forking equals dividing over any extension base for non-forking. (Recall that a set A ⊆ 𝕌 is called an extension base for non-forking if types over A do not fork over A.) In the following proposition we prove that in a VC-minimal theory (with an unpackable generating directed family), every set is an extension base for non-forking, and hence forking equals dividing over any set.

Proposition 5.5. Let T be a VC-minimal theory, and suppose that Ψ is unpackable. Let A be any set, φ(x, \overline{y}) any formula, and \overline{a} ∈ A. Then φ(x, \overline{a}) does not fork over A.

Proof. Let S_{1}, …, S_{n} be the Swiss cheeses of φ(x, \overline{a}), and let B_{1}, …, B_{n} be their outer balls. For each i = 1, …, n let q_{i} be the generic type p_{B_{i}} of B_{i} over 𝕌 as in Definition 2.9. Note that for each i the formula x ∈ S_{i} is in q_{i}, and so φ(x, \overline{a}) ∈ q_{i}.

Consider any σ ∈ Aut(𝕌/A). Since φ(x, \overline{a}) is over A, it is invariant under σ; since Swiss cheese decompositions are unique, σ must permute S_{1}, …, S_{n}. In particular, any such σ permutes B_{1}, …, B_{n}, and so the orbit of q_{1} under Aut(𝕌/A) is a subset of {q_{1}, …, q_{n}}, and thus finite; it follows that q_{1} does not divide over A. Since 𝕌 is saturated, this implies that q_{1} does not fork over A, and so neither does φ(x, \overline{a}). □

Corollary 5.6. If T is VC-minimal and Ψ is unpackable, then every set is an extension base, and hence forking equals dividing over any set.

Proof. By transitivity of forking, it suffices to check that 1-types over A do not fork over A, which follows from Proposition 5.5. □

The following result about dp-minimal theories is well-known; however, we were unable to find a reference which includes it. We include the proof for completeness.

Proposition 5.7. Let T be dp-minimal. Let A ⊆ 𝕌 be a small set, φ(\overline{x}, \overline{y}) a formula over A, and I = ⟨\overline{b}_{i} : i ∈ ω⟩ an A-indiscernible sequence. If the set \{φ(\overline{x}, \overline{b}_{i}) : i ∈ ω\} is l(\overline{x}) + 1-consistent, then it is consistent.

Proof. First, consider any tuple \overline{a} ∈ 𝕌, and let n = l(\overline{a}). By Theorem 2.7 of [9], the dp-rank of tp(\overline{a}/A) is at most n. It follows from Proposition 2.3 of [9] that for any family I_{0}, …, I_{n} of mutually A-indiscernible sequences, at least one of the sequences I_{k} is indiscernible over A\overline{a}.

Let n = l(\overline{x}). Assume that for an A-indiscernible sequence I = ⟨\overline{b}_{i} : i ∈ ω⟩ the set \{φ(\overline{x}, \overline{b}_{i}) : i ∈ ω\} is n + 1-consistent; we will show that it is consistent.

Let ⟨\overline{c}_{i} : i ∈ ℚ⟩ be an A-indiscernible sequence with the same EM-type over A as I, i.e. for any i_{0} < i_{1} < ⋯ < i_{k} ∈ ℚ we have that tp(\overline{c}_{i_{0}} … \overline{c}_{i_{k}}/A) = tp(\overline{b}_{0} … \overline{b}_{k}/A). We have that the set of formulae \{φ(\overline{x}, \overline{c}_{i}) : i ∈ ℚ\} is n + 1-consistent.

Pick \overline{a} ∈ 𝕌 such that 𝕌 ⊧ ⋀_{i=0}^{n} φ(\overline{a}, \overline{c}_{i}).

For k = 0, …, n, let I_{i} be the indiscernible sequence ⟨\overline{c}_{i} : k − \frac{1}{2} < i < k + \frac{1}{2}⟩. This gives us n + 1 mutually A-indiscernible sequences I_{0}, …, I_{n}. At least one of them, say I_{0}, must be indiscernible over A\overline{a}. So we have that 𝕌 ⊧ φ(\overline{a}, \overline{c}_{i}) for all \overline{c}_{i} ∈ I_{0}, and hence the set \{φ(\overline{x}, \overline{c}_{i}) : i ∈ I_{0}\} is consistent. Since I_{0} has the same EM-type over A as I, the set \{φ(\overline{x}, \overline{b}_{i}) : i ∈ ω\} is consistent as well. □

Corollary 5.8. Let T be dp-minimal. Let M ≼ 𝕌 be a small model, φ(\overline{x}, \overline{y}) a formula over M, and \overline{b} ∈ 𝕌. Then the following conditions are equivalent:

(1) the formula φ(\overline{x}, \overline{b}) does not divide over M;

(2) the formula φ(\overline{x}, \overline{b}) does not fork over M;
(3) the set of formulae \{φ(\overline{x}, \overline{b}′) : \overline{b}′ ≡_{M} \overline{b}, \overline{b}′ ∈ 𝕌\} is consistent;
(4) the set of formulae \{φ(\overline{x}, \overline{b}′) : \overline{b}′ ≡_{M} \overline{b}, \overline{b}′ ∈ 𝕌\} is l(\overline{x}) + 1-consistent.

Proof. The equivalence of (1), (2), and (3) follows from Theorem 1 and Corollary 3.31 in [3].

Obviously (3) implies (4), and (4) implies (1) by the previous proposition. □

The following is the main result of this paper.

Theorem 5.9. Suppose that T is VC-minimal, and suppose that Ψ is unpackable. Let M ≼ 𝕌 be a small model of T. Let φ(\overline{x}, \overline{y}) be any formula, and \overline{c} any parameter tuple from 𝕌. Then the following are equivalent:

(I) φ(\overline{x}, \overline{c}) does not fork over M; (II) there is a global type p ∈ S\overline{x}(𝕌) which is definable over M with φ(\overline{x}, \overline{c}) ∈ p.

Proof. (II) ⇒ (I). Straightforward.

(I) ⇒ (II). We proceed by induction on l(\overline{x}).

Base Case: x is a single variable.

Suppose that φ(x, \overline{c}) does not fork over M.

Consider the Swiss cheese decomposition of φ(x, \overline{c}). One of the Swiss cheeses must not divide over M, and thus does not fork over M. Replace φ(x, \overline{c}) with this Swiss cheese; any type containing it will also contain the original φ(x, \overline{c}). We will henceforth assume that φ(x, \overline{c}) is a single Swiss cheese; it follows that \{φ(x, \overline{c}′) : \overline{c}′ ≡_{M} \overline{c}, \overline{c}′ ∈ 𝕌\} is consistent by Corollary 5.8. In particular, note that the set \{φ(x, \overline{c}′) : \overline{c}′ ≡_{M} \overline{c}, \overline{c}′ ∈ 𝕌\} is 2-consistent.

Letting q(\overline{y}) = tp(\overline{c}/M), we have that q(\overline{y}_{1}) ∪ q(\overline{y}_{2}) ⊢ ∃x [φ(x, \overline{y}_{1}) ∧ φ(x, \overline{y}_{2})]. By Compactness, there must be a single formula θ(\overline{y}) ∈ q(\overline{y}) with parameters in M such that θ(\overline{y}_{1}) ∧ θ(\overline{y}_{2}) ⊢ ∃x [φ(x, \overline{y}_{1}) ∧ φ(x, \overline{y}_{2})]. Modifying θ(\overline{y}) if necessary, we may also assume it implies that φ(x, \overline{y}) is a single Swiss cheese.

Using θ, we will build the desired type p. Informally, it describes points which are generic in the set ⋂_{\overline{c}′∈θ(𝕌)} φ(x, \overline{c}′).

First, build a complete Ψ-type p^{∗}(x) over 𝕌, such that a 𝕌-definable ball B will be in p^{∗} if φ(x, \overline{c}′) ⊆ B for some \overline{c}′ ∈ θ(𝕌); otherwise, the complement of B will be in p^{∗}. Then p^{∗} is consistent: if not, by Compactness there is some finite part of p^{∗}, \{ψ_{i}(x, \overline{d}_{i}): i = 1, …, n\} ∪ \{¬ψ_{i}(x, \overline{d}_{i}): i = n + 1, …, m\} which is inconsistent. Let \overline{c}_{1}, …, \overline{c}_{n} ∈ θ(𝕌) witness that ψ_{1}(x, \overline{d}_{1}), …, ψ_{n}(x, \overline{d}_{n}) are in p^{∗}: φ(x, \overline{c}_{i}) ⊆ ψ_{i}(x, \overline{d}_{i}) for each i = 1, …, n. As \{φ(x, \overline{c}_{i}) : i = 1, …, n\} is a 2-consistent set of Swiss cheeses, their outer balls must form a chain; let B be the smallest of the outer balls. It follows that the ball B would be covered by finitely many other balls (the holes of each φ(x, \overline{c}_{i}) and the balls \{ψ_{i}(x, \overline{d}_{i}): i = n + 1, …, m\}), contradicting unpackability.

We also get that p^{∗} is definable over M: for any ψ(x, \overline{z}) ∈ Ψ and any choice of parameters for \overline{z} from 𝕌, ψ(x, \overline{z}) ∈ p^{∗} if and only if 𝕌 ⊧ ∃\overline{y}[θ(\overline{y})∧φ(x, \overline{y}) ⊆ ψ(x, \overline{z})].

By VC-minimality, p^{∗} extends uniquely to a complete type p ∈ S_{1}(𝕌). Since p is generated by p^{∗}, p is definable over M (e.g. by Lemma 2.3.1 from [7]). Finally, according to the definition of p^{∗}, the outer ball of φ(x, \overline{c}) is in p^{∗}, but, since \{φ(x, \overline{c}′) : \overline{c}′ ∈ θ(𝕌)\} is 2-consistent, each of the holes of φ(x, \overline{c}) is not; thus, φ(x, \overline{c}) ∈ p. □

Inductive step: Assume that (I) ⇒ (II) holds for all formulae in which l(\overline{x}) = n. We prove it here for formulae with l(\overline{x}) = n + 1.

Let φ(\overline{x}, \overline{c}) = φ(x_{0}, x_{1}, …, x_{n}, \overline{c}), and suppose φ(\overline{x}, \overline{c}) does not fork over M. By Corollary 5.8, the family

\{φ(\overline{x}, \overline{c}′): \overline{c}′ ≡_{M} \overline{c}, \overline{c}′ ∈ 𝕌\}

is consistent. In particular, this family is 2(n + 1)-consistent.

Take θ(\overline{y}) ∈ tp(\overline{c}/M) to be a formula guaranteeing 2(n + 1)-consistency:

𝕌 ⊧ ⋀_{i=1}^{2(n+1)} θ(\overline{y}_{i}) → ∃x_{0}∃x_{1} … ∃x_{n} [ ⋀_{i=1}^{2(n+1)} φ(\overline{x}, \overline{y}_{i})] .

Let φ^{∗}(x_{1}, …, x_{n}, \overline{y}_{1}, \overline{y}_{2}) be the formula

φ^{∗}(x_{1}, …, x_{n}, \overline{y}_{1}, \overline{y}_{2}) = ∃x_{0}[φ(x_{0}, x_{1}, …, x_{n}, \overline{y}_{1}) ∧ φ(x_{0}, x_{1}, …, x_{n}, \overline{y}_{2})].

Then the set \{φ^{∗}(x_{1}, …, x_{n}, \overline{c}_{1}, \overline{c}_{2}) : \overline{c}_{1}, \overline{c}_{2} ∈ θ(𝕌)\} is n+1-consistent, and so for any choice of tuples \overline{c}_{1}, \overline{c}_{2} ∈ θ(𝕌), we have that the family \{φ^{∗}(x_{1}, …, x_{n}, \overline{c}′_{1}, \overline{c}′_{2}) :

\overline{c}′_{1}\overline{c}′_{2} ≡_{M} \overline{c}_{1}\overline{c}_{2}, \overline{c}′_{1}, \overline{c}′_{2} ∈ 𝕌\} is n + 1-consistent. It follows via Corollary 5.8 that φ^{∗}(x_{1}, …, x_{n}, \overline{c}_{1}, \overline{c}_{2}) does not fork over M for each \overline{c}_{1}, \overline{c}_{2} ∈ θ(𝕌).

Applying the inductive hypothesis, we get that for each pair \overline{c}_{1}, \overline{c}_{2} ∈ θ(𝕌), there is a type q_{\overline{c}_{1},\overline{c}_{2}} ∈ S_{n}(𝕌) which contains φ^{∗}(x_{1}, …, x_{n}, \overline{c}_{1}, \overline{c}_{2}) and which is definable over M.

Claim 5.10. There are finitely many M-definable types q_{1}, …, q_{k} ∈ S_{n}(𝕌) such that for every \overline{c}_{1}, \overline{c}_{2} ∈ θ(𝕌), the formula φ^{∗}(x_{1}, …, x_{n}, \overline{c}_{1}, \overline{c}_{2}) is contained in one of the types q_{1}, …, q_{k}.

Proof. Since each type q_{\overline{c}_{1},\overline{c}_{2}} is M-definable, for each \overline{c}_{1}, \overline{c}_{2} ∈ θ(𝕌) there is a formula d_{q_{\overline{c}_{1},\overline{c}_{2}}} (\overline{y}_{1}, \overline{y}_{2}) over M which defines φ^{∗} for the type q_{\overline{c}_{1},\overline{c}_{2}}. Any \overline{c}_{1}, \overline{c}_{2} taken from θ(𝕌) must satisfy d_{q_{\overline{c}_{1},\overline{c}_{2}}} (\overline{y}_{1}, \overline{y}_{2}), and so the set of formulae

\{θ(\overline{y}_{1}) ∧ θ(\overline{y}_{2})\} ∪ \{¬d_{q_{\overline{c}_{1},\overline{c}_{2}}} (\overline{y}_{1}, \overline{y}_{2}) : \overline{c}_{1}, \overline{c}_{2} ∈ θ(𝕌)\}

has no realization in 𝕌.

Since every formula d_{q_{\overline{c}_{1},\overline{c}_{2}}} (\overline{y}_{1}, \overline{y}_{2}) is over M, by Compactness, there are finitely many types q_{1}, …, q_{k} taken from among the types \{q_{\overline{c}_{1},\overline{c}_{2}} : \overline{c}_{1}, \overline{c}_{2} ∈ θ(𝕌)\} such that

\{θ(\overline{y}_{1}) ∧ θ(\overline{y}_{2}), ¬d_{q_{1}}(\overline{y}_{1}, \overline{y}_{2}), …, ¬d_{q_{k}}(\overline{y}_{1}, \overline{y}_{2})\}

is inconsistent, and so 𝕌 ⊧ [θ(\overline{y}_{1}) ∧ θ(\overline{y}_{2})] → ⋁_{i=1}^{k} d_{q_{i}}(\overline{y}_{1}, \overline{y}_{2}). □

Henceforth, we will work in a |𝕌|^{+}-saturated elementary extension 𝕍 ≽ 𝕌.

Let \overline{X} denote the tuple of variables x_{1}x_{2} … x_{n}, and let q_{1}(\overline{X}), …, q_{k}(\overline{X}) ∈ S_{n}(𝕌) be M-definable types as in Claim 5.10. Within 𝕍, choose realizations of q_{1}, …, q_{k} as follows: let \overline{β}_{1} ⊧ q_{1}. We know q_{2} is an M-definable type; use that same definition scheme to extend q_{2} to a type over 𝕌\overline{β}_{1}, and take \overline{β}_{2} to realize the extended type q_{2}|𝕌\overline{β}_{1}. Similarly, let \overline{β}_{3} ⊧ q_{3}|𝕌\overline{β}_{1}\overline{β}_{2}, and so on, up through \overline{β}_{k} ⊧ q_{k}|𝕌\overline{β}_{1} … \overline{β}_{k−1}. Finally, let \overline{β} be the tuple \overline{β}_{1} … \overline{β}_{k}. It follows that the type tp(\overline{β}/𝕌) is definable over M.

Remark 5.11. Since the type tp(\overline{β}/𝕌) is definable over M, for any \overline{d}, \overline{d}′ ∈ 𝕌, we have that \overline{d} ≡_{M} \overline{d}′ iff \overline{d} ≡_{M\overline{β}} \overline{d}′.

Let \overline{X}_{1}, …, \overline{X}_{k} be k disjoint copies of \overline{X}, and let φ̂(x_{0}, \overline{X}_{1}, …, \overline{X}_{k}, \overline{y}) be the

formula ⋁_{i=1}^{k} φ(x_{0}, \overline{X}_{i}, \overline{y}). Consider the set \{φ̂(x_{0}, \overline{β}, \overline{c}′): \overline{c}′ ∈ θ(𝕌)\}. For any \overline{c}_{1}, \overline{c}_{2} ∈

θ(𝕌), there must be some j such that φ^{∗}(\overline{X}, \overline{c}_{1}, \overline{c}_{2}) ∈ q_{j}, so 𝕍 ⊧ ∃x_{0}[φ(x_{0}, \overline{β}_{j}, \overline{c}_{1}) ∧

φ(x_{0}, \overline{β}_{j}, \overline{c}_{2})]. This gives that 𝕍 ⊧ ∃x_{0}[ ⋁_{i=1}^{k} φ(x_{0}, \overline{β}_{i}, \overline{c}_{1}) ∧ ⋁_{i=1}^{k} φ(x_{0}, \overline{β}_{i}, \overline{c}_{2})],

that is, 𝕍 ⊧ ∃x_{0}[φ̂(x_{0}, \overline{β}, \overline{c}_{1}) ∧ φ̂(x_{0}, \overline{β}, \overline{c}_{2})].

So, the family \{φ̂(x_{0}, \overline{β}, \overline{c}′) : \overline{c}′ ∈ θ(𝕌)\} is 2-consistent. (Note that we only consider tuples \overline{c}′ in 𝕌, and since \overline{β} is not in 𝕌 this is not a definable family.)

Remark 5.12. Our strategy now is to construct a type r(x) ∈ S_{1}(𝕌\overline{β}) which contains φ̂(x, \overline{β}, \overline{c}) and which is definable over M\overline{β} – i.e. for every formula σ(x, \overline{v}, \overline{z}), there is a formula d_{r}(\overline{v}, \overline{z}) over M such that for any \overline{e} ∈ 𝕌, we have that σ(x, \overline{β}, \overline{e}) ∈ r(x) iff 𝕍 ⊧ d_{r}(\overline{β}, \overline{e}). We proceed as in the base case. However, since 𝕌\overline{β} is not a model, we can not in general decompose φ̂(x, \overline{β}, \overline{c}) into Swiss cheeses which are defined over 𝕌\overline{β}; instead, we will use 𝕌\overline{β}-irreducible ucheeses. We will also work with \overline{β}-forking and \overline{β}-dividing.

First, note that φ̂(x, \overline{β}, \overline{c}) does not \overline{β}-divide over M: let I = ⟨\overline{c}_{0} = \overline{c}, \overline{c}_{1}, \overline{c}_{2}, … ⟩ ⊆ 𝕌 be any M-indiscernible sequence. Then I is indiscernible over M\overline{β} by Remark 5.11. Since we know \{φ(x, \overline{β}, \overline{c}_{i}) : i ∈ ω\} is 2-consistent, by Proposition 5.7 it must be consistent. Hence, φ̂(x, \overline{β}, \overline{c}) does not \overline{β}-fork over M.

As φ̂(x, \overline{β}, \overline{c}) is a formula over 𝕌\overline{β}, by Theorem 4.4 it decomposes into finitely many disjoint 𝕌\overline{β}-irreducible ucheeses. One of these ucheeses must not \overline{β}-divide over M; let τ(x, \overline{β}, \overline{d}) be the formula defining this 𝕌\overline{β}-irreducible ucheese. By Corollary 5.4, τ(x, \overline{β}, \overline{d}) does not \overline{β}-fork over M. Notice that 𝕍 ⊧ τ(x, \overline{β}, \overline{d}) → φ̂(x, \overline{β}, \overline{c}).

Claim 5.13. The family \{τ(x, \overline{β}, \overline{d}′) : \overline{d}′ ≡_{M} \overline{d}, \overline{d}′ ∈ 𝕌\} is 2-consistent.

Proof. This proof is modeled on the proof of a similar result in [8] (see also [1]).

Since τ(x, \overline{β}, \overline{d}) does not \overline{β}-fork over M, there is a complete type Γ(x) ∈ S_{1}(M\overline{β}) that does not \overline{β}-fork over M, i.e. every formula in Γ(x) does not \overline{β}-fork.

Let \overline{d}′ ∈ 𝕌 with \overline{d}′ ≡_{M} \overline{d}. It suffices to show that τ(x, \overline{β}, \overline{d}′) ∈ Γ for any such \overline{d}′. Suppose not: assume that ¬τ(x, \overline{β}, \overline{d}′) ∈ Γ. Let q = tp(\overline{d}/M), and let q^{∗} ∈ S(𝕌) be a coheir of q. As a coheir, q^{∗} is an M-invariant type

Let I = ⟨\overline{d}_{1}, \overline{d}_{2}, \overline{d}_{3}, … ⟩ ⊆ 𝕌 be a Morley sequence of q^{∗} over M\overline{d} \overline{d}′, i.e. for all i, \overline{d}_{i+1} ⊧ q^{∗} ↾ M\overline{d} \overline{d}′ \overline{d}_{1} … \overline{d}_{i}. Note that both \overline{d}I and \overline{d}′I are also Morley sequences of q^{∗} over M. Since q^{∗} is M-invariant, the sequences \overline{d}I and \overline{d}′I are both M-indiscernible.

Now, consider τ(x, \overline{β}, \overline{d}_{1}).

Case 1: τ(x, \overline{β}, \overline{d}_{1}) ∈ Γ.

Let \overline{d}_{0} = \overline{d}′. Since \overline{d}′I is M-indiscernible, so is J = ⟨\overline{d}_{0}\overline{d}_{1}, \overline{d}_{2}\overline{d}_{3}, \overline{d}_{4}\overline{d}_{5}, … ⟩. Because ¬τ(x, \overline{β}, \overline{d}_{0}) ∧ τ(x, \overline{β}, \overline{d}_{1}) is in Γ, it does not \overline{β}-divide over M, and so the set \{¬τ(x, \overline{β}, \overline{d}_{2i}) ∧ τ(x, \overline{β}, \overline{d}_{2i+1}) : i ∈ ω\} is consistent. Let a ∈ 𝕍 realize it.

Then τ(a, \overline{β}, \overline{d}_{i}) is true for all odd values of i, and false for all even values of i, and so τ(x, \overline{v}, \overline{w}) has infinite alternation number, violating NIP.

Case 2: τ(x, \overline{β}, \overline{d}_{1}) ∉ Γ. Setting \overline{d}_{0} = \overline{d} leads to a similar contradiction. □

So for any \overline{d}_{1}, \overline{d}_{2} ∈ 𝕌, if \overline{d}_{1} ≡_{M} \overline{d}_{2} ≡_{M} \overline{d}, then 𝕍 ⊧ ∃x [τ(x, \overline{β}, \overline{d}_{1}) ∧ τ(x, \overline{β}, \overline{d}_{2})], and so this formula is in tp(\overline{β}/𝕌). Since this type is definable over M, there is a formula δ(\overline{w}_{1}, \overline{w}_{2}) over M such that for any \overline{d}_{1}, \overline{d}_{2} ∈ 𝕌, we have that 𝕌 ⊧ δ(\overline{d}_{1}, \overline{d}_{2}) if and only if 𝕍 ⊧ ∃x [τ(x, \overline{β}, \overline{d}_{1}) ∧ τ(x, \overline{β}, \overline{d}_{2})]. Again letting q(\overline{w}) = tp(\overline{d}/M), for \overline{d}_{1}, \overline{d}_{2} ∈ 𝕌 we have that 𝕌 ⊧ q(\overline{d}_{1}), q(\overline{d}_{2}) implies 𝕌 ⊧ δ(\overline{d}_{1}, \overline{d}_{2}). By Compactness, there is a formula χ(\overline{w}) ∈ q(\overline{w}) such that 𝕌 ⊧ χ(\overline{w}_{1}) ∧ χ(\overline{w}_{2}) → δ(\overline{w}_{1}, \overline{w}_{2}).

Thus, for any \overline{d}_{1}, \overline{d}_{2} ∈ 𝕌, if 𝕌 ⊧ χ(\overline{d}_{1})∧χ(\overline{d}_{2}) then 𝕍 ⊧ ∃x [τ(x, \overline{β}, \overline{d}_{1}) ∧ τ(x, \overline{β}, \overline{d}_{2})]. Further, let m be the number of outer balls in τ(x, \overline{β}, \overline{d}). Let ρ(\overline{v}, \overline{w}) be a formula

over ∅ saying that the number of outer balls in τ(x, \overline{v}, \overline{w}) is m. Since tp(\overline{β}/𝕌) is definable over M, there is a formula ρ′(\overline{w}) over M such that for \overline{e} ∈ 𝕌 we have that 𝕌 ⊧ ρ′(\overline{e}) iff τ(x, \overline{β}, \overline{e}) has m outer balls. Adjusting the formula χ(\overline{w}) if necessary, we may assume that for any \overline{e} ∈ χ(𝕌), the set τ(x, \overline{β}, \overline{e}) is a ucheese with m outer balls.

We need one final claim before using χ to construct the desired type r(x).

Claim 5.14. For all \overline{e} ∈ χ(𝕌), the set defined by τ(x, \overline{β}, \overline{d}) ∩ τ(x, \overline{β}, \overline{e}) is a 𝕌\overline{β}- irreducible ucheese, and its outer uball contains either τ(x, \overline{β}, \overline{d}) or τ(x, \overline{β}, \overline{e}).

Proof. Certainly τ(x, \overline{β}, \overline{e}) is a ucheese with m outer balls, and τ(x, \overline{β}, \overline{d})∩τ(x, \overline{β}, \overline{e}) ≠ ∅. Write τ(x, \overline{β}, \overline{d}) = B \ B_{1} and τ(x, \overline{β}, \overline{e}) = C \ C_{1}, where B, C, B_{1}, and C_{1} are 𝕌\overline{β}-definable uballs, B and C have m balls each, and B is 𝕌\overline{β}-irreducible.

Since (B \ B_{1}) ∩ (C \ C_{1}) ≠ ∅, some ball of B intersects some ball of C. If some ball of B does not intersect C, then the union of the balls of B which intersect C and the union of those which do not will be disjoint non-empty 𝕌\overline{β}-definable uballs whose union is B, contradicting the irreducibility of B.

So, every ball of B intersects some ball of C. There are two possibilities: • every ball of B is contained in some ball of C;

• every ball of B contains some ball of C. (If it were a mix of the two, we would again violate the irreducibility of B.)

If every ball of B is contained in some ball of C, then B ⊆ C; so, (B \ B_{1}) ∩ (C \ C_{1}) = (B ∩ C) \ (B_{1} ∪ C_{1}) = B \ (B_{1} ∪ C_{1}) is a 𝕌\overline{β}-irreducible ucheese.

If every ball of B contains some ball of C, then C ⊆ B. Further, C must be 𝕌\overline{β}-irreducible: if D and E are disjoint 𝕌\overline{β}-definable uballs and D ∪ E = C, then “the balls of B which intersect D” and “the balls of B which intersect E” are 𝕌\overline{β}-definable uballs; their union is B, since every ball of B contains some ball of C; and they are disjoint, since B and C have the same number of balls. So, (B \ B_{1}) ∩ (C \ C_{1}) = (B ∩ C) \ (B_{1} ∪ C_{1}) = C \ (B_{1} ∪ C_{1}) is a 𝕌\overline{β}-irreducible ucheese. □

At this point, we start constructing an M\overline{β}-definable type r(x) ∈ S_{1}(𝕌\overline{β}) which contains τ(x, \overline{β}, \overline{d}). Informally, it describes points that are generic in ⋂_{\overline{e}∈χ(𝕌)} τ(x, \overline{β}, \overline{e}).

We can begin by building a partial type r^{∗}(x), consisting of 𝕌\overline{β}-irreducible uballs and their complements. Let r^{∗}(x) be the set of all formulae over 𝕌\overline{β} defining 𝕌\overline{β}- irreducible uballs such that

• an irreducible uball C is in r^{∗} if there is some \overline{e} ∈ χ(𝕌) such that τ(x, \overline{β}, \overline{e}) ⊆ C;

• otherwise, the complement of C is in r^{∗}.

Claim 5.15. The set r^{∗}(x) is consistent.

Proof. Suppose not: then by Compactness, there exist finitely many 𝕌\overline{β}-irreducible uballs A_{1}, …, A_{m_{1}}, B_{1}, …, B_{m_{2}} such that for each A_{i}, the formula x ∈ A_{i} is in r^{∗}; for each B_{i}, the formula x ∉ B_{i} is in r^{∗}; and the set {x ∈ A_{i} : i = 1, … m_{1}} ∪ {x ∉ B_{i} : i = 1, …, m_{2}} is inconsistent.

For each A_{i}, there is some \overline{e}_{i} ∈ χ(𝕌) such that τ(x, \overline{β}, \overline{e}_{i}) ⊆ A_{i}; it follows from Claim 5.13 that the sets A_{1}, …, A_{m_{1}} are 2-consistent. By Proposition 4.5, then, the A_{i}s must form a chain: possibly after renumbering, A_{1} ⊆ A_{2} ⊆ ⋯ ⊆ A_{m_{1}}, and the set {x ∈ A_{1}} ∪ {x ∉ B_{i} : i = 1, …, m_{2}} must be inconsistent.

For each B_{i}, we know that τ(x, \overline{β}, \overline{e}_{1}) ⊈ B_{i}, so A_{1} ⊈ B_{i}; it follows from Proposition 4.5 that either B_{i} ⊊ A_{1} or A_{1} ∩ B_{i} = ∅. Let B_{1}, …, B_{n} be a list of the sets B_{i} which are properly contained in A_{1}.

Then it must be that A_{1} = ⋃_{i=1}^{n} B_{i}, and so the sets B_{1}, …, B_{n} are finitely many 𝕌\overline{β}-definable uballs whose union is A_{1}, contradicting that A_{1} is 𝕌\overline{β}-irreducible. □

By definition the partial type r^{∗} is complete for 𝕌\overline{β}-irreducible uballs. By Theorem 4.4, r^{∗} generates a unique complete type r ∈ S_{1}(𝕌\overline{β}).

Claim 5.16. A 𝕌\overline{β}-definable uball B is in r iff τ(x, \overline{β}, \overline{e}) ⊆ B for some \overline{e} ∈ χ(𝕌).

Proof. Write B = B_{1} ˙∪ … ˙∪B_{k}, where B_{1}, …, B_{k} are 𝕌\overline{β}-irreducible uballs, as per Proposition 4.3.

⇒: Since r is generated by r^{∗}, the uball B is in r iff B_{i} ∈ r^{∗} for some i, in which case there is some \overline{e} ∈ χ(𝕌) with τ(x, \overline{β}, \overline{e}) ⊆ B_{i} ⊆ B.

⇐: Assume there is some \overline{e} ∈ χ(𝕌) such that τ(x, \overline{β}, \overline{e}) ⊆ B. It follows that τ(x, \overline{β}, \overline{e}) ∩ τ(x, \overline{β}, \overline{d}) ⊆ B. By Claim 5.14, τ(x, \overline{β}, \overline{e}) ∩ τ(x, \overline{β}, \overline{d}) is a 𝕌\overline{β}-irreducible ucheese; let C be its outer uball.

For some i, the intersection C ∩ B_{i} is non-empty. Since B_{i} and C are both 𝕌\overline{β}-irreducible uballs, by Proposition 4.5, either C ⊆ B_{i} or B_{i} ⊊ C.

If B_{i} ⊊ C, then since C ⊆ B, the set C intersects some of the other sets B_{j}. Let B_{1}, …, B_{k′} be a list of the sets B_{j} which have non-trivial intersection with C. Then these sets are finitely many disjoint 𝕌\overline{β}-definable uballs whose union is C, contradicting the irreducibility of C.

So, it must be that C ⊆ B_{i}, and since C contains either τ(x, \overline{β}, \overline{e}) or τ(x, \overline{β}, \overline{d}) by Claim 5.14, the uball B_{i} is in r^{∗}, and so B ∈ r. □

We also get several other basic results about r:

• if B and C are uballs, and each ball of C is properly contained in a ball of B, then B \ C ∈ r if and only if B ∈ r and C ∉ r;

• an arbitrary formula σ(x, \overline{β}, \overline{a}) is in r if and only if one of its layers L_{i}^{σ}(x, \overline{β}, \overline{a}) is in r.

Since each layer is a ucheese, we can easily define whether or not it is in r. Fix a formula σ(x, \overline{β}, \overline{z}); recall that tp(\overline{β}/𝕌) is definable over M. For each layer L_{i}(x, \overline{β}, \overline{z}), let δ_{i}^{+}(\overline{w}, \overline{z}) define whether or not the formula χ(\overline{w}) ∧ ∀x [τ(x, \overline{β}, \overline{w}) → λ_{i}^{+}(x, \overline{β}, \overline{z})] is in tp(\overline{β}/𝕌). That is, for parameters \overline{e}, \overline{a} ∈ 𝕌, we have that 𝕌 ⊧ δ_{i}^{+}(\overline{e}, \overline{a}) if and only if 𝕍 ⊧ χ(\overline{e}) ∧ (τ(x, \overline{β}, \overline{e}) ⊆ λ_{i}^{+}(x, \overline{β}, \overline{a})). Similarly, let δ_{i}^{−}(\overline{w}, \overline{z}) define whether or not χ(\overline{w}) ∧ ∀x [τ(x, \overline{β}, \overline{w}) → λ_{i}^{+}(x, \overline{β}, \overline{z})] is in tp(\overline{β}/𝕌).

Then the layer L_{i}(x, \overline{β}, \overline{a}) will be in r if and only if its outer uball λ_{i}^{+}(x, \overline{β}, \overline{a}) is in r, i.e. 𝕌 ⊧ ∃\overline{w} [δ_{i}^{+}(\overline{w}, \overline{a})], and its inner uball λ_{i}^{−}(x, \overline{β}, \overline{a}) is not in r, i.e. 𝕌 ⊧ ¬∃\overline{w} [δ_{i}^{−}(\overline{w}, \overline{a})]. It follows that the entire type r is definable over M\overline{β}. We also get that τ(x, \overline{β}, \overline{d}) ∈ r, since its outer uball must be in r^{∗} but its inner uball must not be by Claim 5.13.

Let a realize r. Then, since τ(x, \overline{β}, \overline{d}) ⊢ φ̂(x, \overline{β}, \overline{c}), we have that 𝕍 ⊧ φ̂(a, \overline{β}, \overline{c}), i.e. 𝕍 ⊧ ⋁_{i=1}^{k} φ(a, \overline{β}_{i}, \overline{c}). Fix a value of i whose disjunct is true.

Let p(x_{0}, x_{1}, …, x_{n}) = tp(a\overline{β}_{i}/𝕌). The type p is in S_{n+1}(𝕌).

Since tp(\overline{β}/𝕌) is definable over M, and r = tp(a/𝕌\overline{β}) is definable over M\overline{β}, it follows that tp(a\overline{β}/𝕌) is definable over M; as p is a subtype of tp(a\overline{β}/𝕌), we get that p is also definable over M.

Finally, since 𝕍 ⊧ φ(a, \overline{β}_{i}, \overline{c}), it must be that φ(x_{0}, x_{1}, …, x_{n}, \overline{c}) ∈ p. □

Appendix A. Proof of Proposition 5.3

Fix an NT P_{2} theory T. Let 𝕌 be a large saturated model of T, 𝕍 ≽ 𝕌 a |𝕌|^{+}- saturated model of T, and M ≼ 𝕌 a small model of T. Fix \overline{β} ∈ 𝕍 such that tp(\overline{β}/𝕌) is definable over M.

We will outline how to modify some parts of the paper [3] to yield the following result.

Proposition. Let \overline{a}_{1}, \overline{a}_{2} ∈ 𝕌, and suppose σ_{1}(x, \overline{β}, \overline{a}_{1}) and σ_{2}(x, \overline{β}, \overline{a}_{2}) \overline{β}-divide over M. Then σ_{1}(x, \overline{β}, \overline{a}_{1}) ∨ σ_{2}(x, \overline{β}, \overline{a}_{2}) also \overline{β}-divides over M.

Recall (see Definition 3.8 of [3]) that a global a global type q(\overline{y}) ∈ S(𝕌) is called strictly invariant over M if it is M-invariant and for any realization \overline{c} of q(\overline{y}) the type tp(𝕌/M\overline{c}) does not fork over M.

Claim. (see Lemma 3.14 of [3]) Let q(\overline{y}) ∈ S(𝕌) be a type which is strictly invariant over M, and let \overline{c} ∈ 𝕌 realize q(\overline{y}) ↾ M. If φ(\overline{x}, \overline{β}, \overline{c}) \overline{β}-divides over M and ⟨\overline{b}_{i}: i ∈ ω⟩ ⊆ 𝕌 is a Morley sequence of the type q(\overline{y}) over M, then the set of formulae \{φ(\overline{x}, \overline{β}, \overline{b}_{i}): i ∈ ω\} is inconsistent.

Proof of the claim. We may assume \overline{c} = \overline{b}_{0}. Let I ⊆ 𝕌 be an M-indiscernible sequence witnessing the \overline{β}-dividing of φ(\overline{x}, \overline{β}, \overline{c}).

For each i ∈ ω, construct a sequence I_{i} = ⟨\overline{c}_{i,j}: j ∈ ω⟩ in 𝕌 as in Lemma 3.14 of [3]. Using Remark 5.11, we obtain that

• each I_{i} is indiscernible over \{I_{j} : j < i\} ∪ \{\overline{c}_{j,0} : i < j\} ∪ M ∪ \{\overline{β}\};

• for each i ∈ ω, I_{i} ≡_{M\overline{β}} I;

• \overline{c}_{i,0} = \overline{b}_{i}. Then, using NT P_{2}, we obtain that for some function η: ω → ω the family

\{φ(\overline{x}, \overline{β}, \overline{c}_{i,η(i)}): i ∈ ω\} is inconsistent.

It follows from the properties above that \overline{c}_{0,η(0)}, \overline{c}_{1,η(1)}, … ≡_{M\overline{β}} \overline{c}_{0,0}, \overline{c}_{1,0}, …, proving the claim. □

Proof of the proposition. Taking \overline{a} = \overline{a}_{1}\overline{a}_{2}, if needed we may assume that \overline{a}_{1} = \overline{a}_{2} = \overline{a}. Since M is a model, by [3, Corollary 3.29], there is a global type q(\overline{y}) ∈ S(𝕌) extending tp(\overline{a}/M) which is strictly invariant over M. Let I = ⟨\overline{b}_{i}: i ∈ ω⟩ ⊆ 𝕌 be a Morley sequence of q(\overline{y}) over M.

Assume σ_{1}(x, \overline{β}, \overline{a})∨σ_{2}(x, \overline{β}, \overline{a}) does not \overline{β}-divide over M. Then the set of formulae \{σ_{1}(x, \overline{β}, \overline{b}_{i}) ∨ σ_{2}(x, \overline{β}, \overline{b}_{i}): i ∈ ω\} is consistent, and we can find α ∈ 𝕍 realizing this set.

Then one of the sets \{i ∈ ω: 𝕍 ⊧ σ_{1}(α, \overline{β}, \overline{b}_{i})\} or \{i ∈ ω: 𝕍 ⊧ σ_{2}(α, \overline{β}, \overline{b}_{i})\} must be infinite, and hence by the previous claim one of σ_{1} and σ_{2} does not \overline{β}-divide over M. □

References

[1] Adler, H. Introduction to theories without the independence property. Archive for Mathematical Logic. To appear.

[2] Adler, H. Theories controlled by formulas of Vapnik-Chervonenkis codimension 1. Preprint, 2008.

[3] Chernikov, A., and Kaplan, I. Forking and dividing in NT P_{2} theories. J. Symbolic Logic. To appear.

[4] Dolich, A. Forking and independence in o-minimal theories. Journal of Symbolic Logic 69(1) (2004), 215–240.

[5] Dolich, A., Goodrick, J., and Lippel, D. dp-minimality: basic facts and examples. Preprint, 2009.

[6] Holly, J. Canonical forms for definable subsets of algebraically closed and real closed valued fields. Journal of Symbolic Logic 40(3) (1995), 843–860.

[7] Hrushovski, E., and Loeser, F. Non-archimedean tame topology and stably dominated types. Preprint, 2011.

[8] Hrushovski, E., and Pillay, A. On NIP and invariant measures. Journal of the European Mathematical Society 13(4) (2011), 1005–1061.

[9] Kaplan, I., Onshuus, A., and Usvyatsov, A. Additivity of the dp-rank. Preprint, 2010.