ADDITIVITY OF THE DP-RANK

ITAY KAPLAN, ALF ONSHUUS, AND ALEXANDER USVYATSOV

Abstract. The main result is the prove of the linearity of the dp-rank. We also prove that the study of theories of finite dp-rank cannot be reduced to the study of its dp-minimal types and discuss the possible relations between dp-rank and VC-density.

1. introduction

There have been many different definitions of dp-rank and dp-minimality (dprank one), equivalent in the case of dp-minimality and otherwise quite close to each other. This paper is about dp-rank and types with finite dp-rank. It seems clear at this point that there are two equivalent definitions of dp-rank and that part of the strength of this concept is the interaction of both. We are talking about the “standard” independent array definition (see Definition 1.2) which is very useful when one wants to deal with formulas, and a very simple implication of this one (see Definition 1.1) which can be found, for the dp-minimal case, in Simon’s paper ([6]), but which as far as we know has never been stated for dp-rank greater than one.

It follows from the definition that dp-rank is either finite or unbounded and (as is usual with ranks) it does not imply much for types with unbounded rank, which is why we work with types with finite rank. We will show many of the results known for dp-minimal types can be proved also for types with finite ranks with basically the same ideas (we will mention a couple of such extensions). However, even though the proofs can be generalized, we can show that the implications per se cannot be made formaly: Example 1.3 shows that there are theories with types of finite rank but no dp-minimal types.

Finally, there has been some recent developments with VC-density which prompts to ask the question of whether or not there is a relation between this two notions. In particular, can one characterize theories with finite dp-rank (which Shelah calls strongly dependent theories in [4]) in terms of VC-density? If we know that every type p(x) in models of a theory T have dp-rank n, does this say anything about the VC-density of the types? We address some of this questions in the final section.

Definition 1.1. Let p(x) be any type over a set A. We will say that p(x) has dp-rank k if given any realization a of p and any k + 1 mutually A-indiscernible sequences at least one of them is indiscernible over Aa.

Even though this is a very useful characterization, it is also good to have a more syntactic version. The following definitions were motivated by the original definition of strong dependence by Shelah (see e.g. [5]) and appear in [7] and [3]. In the definitions below we denote tuples by x̄, ā (in order to stress the difference between singletons and finite tuples of arbitrary length).

Definition 1.2. A randomness pattern of depth κ for a (partial) type p over a set A is an array ⟨b̄_{i}^{α}: α < κ⟩_{i<ω} and formulae φ_{α}(x̄, ȳ_{α}) for α < κ such that

(1) The sequences I^{α} = ⟨b̄_{i}^{α}⟩_{i<ω} are mutually indiscernible over A; that is, I^{α} is indiscernible over AI^{≠α}.

(2) length(b̄_{i}^{α}) = length(ȳ_{α})

(3) for every η ∈ ^{κ}ω, the set

Γ_{η} = {φ_{α}(x̄, b̄_{η}^{α})}_{α<κ} ∪ {¬φ_{α}(x̄, b̄_{i}^{α})}_{α<κ,i<ω,i≠η(α)}

is consistent with p.

One can define the dependence rank of of a (partial) type p over a set A as the supremum of all κ such that there exists a randomness pattern for p of depth κ. The equivalence between this and 1.1 for the dp-rank one case is included in Lemma 1.4 of [6]. The proof is exactly the same for all dp-ranks.

It follows from Definition 1.2, by compactness, that if a type has dp-rank greater than omega, it has dp-rank greater than any ordinal α. So the only “structure” case (to use some of Shelah’s terminology) is the finite rank.

As we mentioned above, one might be drawn to think that all the theory of strongly dependent theories can be decomposed into the theory of dp-rank 1 types. This, however is not the case.

Example 1.3. Consider the model companion of the theory of an infinite set with two dense linear orders. It is not hard to show that every one type has dp-rank 2, and there are no dp-rank one types:

First of all, the theory exists and has elimination of quantifiers in the language L := {<_{1}, <_{2}}, so tp(a/A) can be understood by formulas of the form x <_{1} a, x >_{1} a, x <_{2} a, x >_{2} a, and x = a for suitable choices of a ∈ A.

It is not hard to show now that given any model M then any 1-variable type p(x) ∈ S(M) has dp-rank 2. Given any such set, we need to find mutually indiscernible sequences ⟨a_{i}⟩ and ⟨b_{j}⟩ such that

• Both p(x) ∪ {x_{1} > a_{i}} and p(x) ∪ {x <_{1} a_{i}} are consistent,

• both p(x) ∪ {x_{2} > b_{j}} and p(x) ∪ {x <_{2} b_{j}} are consistent,

• p(x) ∪ T h(M) ⊢ x <_{1} b_{j}, and

• p(x) ∪ T h(M) ⊢ x <_{2} a_{j}. Such a_{i} and b_{j} can be found by the definition of a model companion. This implies that every type in this theory has dp-rank 2 and in particular that

there are no dp-minimal types.

2. linearity of the dp-rank

The purpose of the following results will be to show that given a_{1}, …, a_{n} realizations of types (over A) of dp-rank k, then the dp-rank of the type tp(a_{1} … a_{n}/A) is less than or equal to nk.

The following is a first technical lemma towards proving the good behavior of the dp-rank on tuples.

Lemma 2.1. Let a be any tuple such that tp(a/A) is dp-minimal, let B ⊃ A, and let I be a set of mutually B-indiscernible sequences. Then for any n given any n + 1 mutually B-indiscernible sequences in I at least n of them are mutually indiscernible over Ba.

Proof. We will do an induction on n. Since any extension of a dp-minimal type is dp-minimal (or algebraic), if n = 1 there is nothing to prove.

Assume now that I := {I_{1}, … I_{n+1}} is a set of mutually B-indiscernible sequences for B ⊃ A. By definition {I_{1}, … I_{n}} are mutually indiscernible over BI_{n+1} so we can, by induction hypothesis, find n − 1 of the I_{j}’s which are mutually indiscernible over BI_{n+1}a; we may assume without loss of generality that {I_{1}, …, I_{n−1}} are mutually indiscernible over BI_{n+1}a. If I_{n+1} was indiscernible over {a} ∪ B ∪ ⋃{I_{1}, …, I_{n−1}} the sequence {I_{1}, …, I_{n−1}, I_{n+1}} would satisfy the conditions of the claim, so we may assume that this is not the case. Since non indiscernibility can be witnessed by a finite sequence, we will assume for the rest of the proof that I_{n+1} is not indiscernible over Bab̄ for some b̄ ∈ ⋃{I_{1}, …, I_{n−1}} and that {I_{1}, …, I_{n−1}} are mutually indiscernible over I_{n+1}b̄a.

Claim 2.2. We may assume that I_{n+1} is not indiscernible over Ba.

Proof. For each k with 1 ≤ k < n we will inductively define a “continuation” I_{k}^{∗} of I_{k} in the following way:

Suppose we have picked I_{j}^{∗} for j < k, and let I_{k} := ⟨a_{i}⟩_{i∈J}. Then we define I_{k}^{∗} := ⟨a_{i}^{∗}⟩_{i∈ω} choosing a_{i}^{∗} inductively for i ∈ ω such that

a_{i}^{∗} ⊧ Avg (I_{k}, B ∪ ⋃_{i=1}^{n} I_{i} ∪ ⋃_{j=1}^{k−1} I_{j}^{∗} ∪ {a}) .

It follows that

• {I_{1}ˆ I_{1}^{∗}, …, I_{n−1}ˆ I_{n−1}^{∗}, I_{n}, I_{n+1}} is a set of B-indiscernible sequences,

• {I_{1}ˆ I_{1}^{∗}, …, I_{n−1}ˆ I_{n−1}^{∗}} is indiscernible over I_{n+1}Ba, and

• I_{n+1} is not indiscernible over Bab̄ for some b̄ ∈ ⋃{I_{1}, …, I_{n−1}}.

Since {I_{1}ˆ I_{1}^{∗}, …, I_{n−1}ˆ I_{n−1}^{∗}} is indiscernible over I_{n+1}Ba there is an automorphism fixing I_{n+1}Ba and sending b̄ to some b̄′ ∈ ⋃{I_{1}^{∗}, …, I_{n−1}^{∗}}. Now we have

• {I_{1}, …, I_{n−1}, I_{n}, I_{n+1}} is a set of Bb̄′-indiscernible sequences,
• {I_{1}, …, I_{n−1}} is indiscernible over I_{n+1}Bb̄′a, and
• I_{n+1} is not indiscernible over Bb′a,

which, replacing B with Bb̄′, is precisely the conditions we started with plus the conclusion of the claim. Since any n-subset of mutually Bb′a-indiscernible sequences of {I_{1}, …, I_{n−1}, I_{n}, I_{n+1}} would in particular be Ba-indiscernible, the claim is proved. □

Now the lemma follows almost immediately. Since {I_{2}, I_{3} …, I_{n}, I_{n+1}} are mutually indiscernible over I_{1}B there must, by induction hypothesis, be a subset of n − 1 mutually I_{1}Ba-indiscernible sequences. But such set cannot contain I_{n+1} since, by hypothesis given in Claim 2.2, this sequence is not (by itself) indiscernible over Ba. So {I_{2}, I_{3} …, I_{n}} are mutually indiscernible over I_{1}Ba. In exactly the same way we can prove that {I_{1}, I_{3} …, I_{n}} are mutually indiscernible over I_{2}Ba which in particular implies that I_{1} is indiscernible over B ∪ {I_{2}, I_{3} …, I_{n}} ∪ {a}. So {I_{1}, I_{2}, I_{3} …, I_{n}} are mutually indiscernible over Ba as required. □

The following result, which from which the main result of this section will follow easily, is a generalization of the previous one.

Proposition 2.3. Let a be an element such that tp(a/A) has dp-rank k and let I := {I_{1}, … I_{m}} be mutually B-indiscernible sequences with m > nk. Then there is an n-subset of I of sequences which are mutually indiscernible over Ba.

To prove Proposition 2.3, we rephrased the statement in a way that will allow us to do an easy induction. For this we will need to following definition.

Definition 2.4. Let I := {I_{1}, … I_{m}} be mutually A-indiscernible sequences and let a be any tuple. We will say that I, a satisfies S_{k,n} if the following conditions hold:

• |I| > nk,

• For any B ⊃ A such that I := {I_{1}, … I_{m}} are still mutually indiscernible over B, then given any nk + 1 sequences in I at least n one of them remain mutually indiscernible over Ba.

So in particular with this notation, a type p(x) has dp-rank less than or equal to k if and only if for any realization a of p(x) and every set I of mutually indiscernible sequences where |I| > k we have that I, a satisfies S_{k,1}.

With this notation we can state a generalization of Proposition 2.3, the prove of which will admit a clear induction argument.

Proposition 2.5. Let a be an element and let I := {I_{1}, … I_{m}} be mutually Aindiscernible sequences with m > Nk such that I, a satisfies S_{k,1}. Then I := {I_{1}, … I_{m}} satisfies S_{k,n} for all n ≤ N.

Proof. Notice that in Lemma 2.1 we proved the result for k = 1. We will do an induction on k.

Let a and I′ := {I_{1}, … I_{nk}} be as in the statement of the lemma. By symmetry of the proofs, it is enough to show that given any B ⊃ A such that {I_{1}, … I_{nk}} are mutually indiscernible over B, there is an n-subset of I′ which is mutually indiscernible over Ba. Suppose that we are given such a B and that there are n sequences in I′ which are not mutually indiscernible over Ba (otherwise we are clearly done), and we may assume without loss of generality that these are I_{1}, I_{2}, …, I_{n}; in fact, we may assume that I_{1} is not indiscernible over I_{2} … I_{n}Ba.

Now, consider the set {I_{1}, I_{n+1}, …, I_{nk}} a set of mutually indiscernible sequences over I_{2}, …, I_{n}. We are assuming that I′, a satisfies S_{k,1} over B so in particular {I_{1}, I_{n+1}, …, I_{nk}}, a should satisfy S_{k,1} over AI_{2} … I_{n}.

Claim 2.6. {I_{n+1}, …, I_{nk}}, a satisfies S_{k−1,1} over BI_{2} … I_{n}.

Proof. Given any k subset of {I_{n+1}, …, I_{nk}} one can add I_{1} to it and by definition such a set must contain a sequence which is indiscernible over BI_{2} … I_{n}a, which by hypothesis cannot be I_{1}. □

By induction hypothesis, we know that {I_{n+1}, …, I_{nk}, a} satisfies S_{k−1,n} over BI_{2} … I_{n} and since |{I_{n+1}, …, I_{nk}}| = (k − 1)n we know that in particular there is a n-subset of sequences which are mutually BI_{2} … I_{n}a-indiscernible. Such a set will also be a set of mutually Ba-indiscernible sequences as required. □

Theorem 2.7. Let a_{1}, …, a_{n} be elements such that rk −dp(tp(a_{i}/A)) ≤ k for all i. Then rk −dp(tp(a_{1} … a_{n}/A)) ≤ nk.

Proof. Let I := {I_{1}, …, I_{nk+1}} be mutually A-indiscernible sequences. By induction and Proposition 2.3 it is easy to see that for any i there is a subset I_{i+1} of I_{i} of size |I_{i}| − k = nk + 1 − ik which are mutually indiscernible over Aa_{1} … a_{i+1}. So for I_{n} will be a single indiscernible sequence in I indiscernible over Aa_{1} … a_{n}. By definition of dp-rank, the theorem follows. □

3. VC-density

A recent result by Aschenbrenner, Dolich, Haskell, Macpherson and Starchenko, shows that in many of the well behaved theories with NIP, the VC-density can be calculated and in most cases it is linear. Before we continue to explain how this relates to the theorem about dp-rank we will need some definitions.

Definition 3.1. Let C be a large κ-saturated model of T, let Δ be a finite set of formulas in the language of T, and let p(y) be a (partial) type over a set of parameters of cardinality less than κ. The VC-dimension of p(y) with respect to Δ is greater than or equal to n if there is a set A of size n such that for any A_{0} ⊂ A there is some b ⊧ p(y) and some δ(x, y) ∈ Δ such that for any a′ ∈ A we have

C ⊧ δ(a′, b) ⇔ a′ ∈ A_{0}.

Whenever this happens we will say that Δ shatters A with realizations of p(y).

We will say that the VC-dimension of p(y) with respect to Δ is n if the V Cdimension is greater than or equal to n but not greater than or equal to n + 1.

Notice that if Δ shatters a set A with respect to p(y) ∈ S_{k}(B), then every subset of A is definable as

φ(C, b) ∩ A

where b varies among realizations of p(y). This is of course equivalent to say that p(y) is consistent with 2^{|A|} different Δ-types over A. Let S_{Δ}^{p(y)}(A) be the set of all Δ-types over A consistent with p(y). With this notation, the V C-dimension of p(y) is greater than n if and only if

|S_{Δ}^{p(y)}(A)| = 2^{|A|}

for some A of size greater than n.

We are slowly getting to V C-density. It was proved (apparently independently by Sauer, Shelah, and Vapnis-Chervonenkis) that if the VC-dimension of Δ with respect to p(y) is equal to d, then

|S_{Δ}^{p(y)}(A)| < |A|^{d}

for all A of size greater than d. This prompted the definition of V C-density as the limit of the infimum of the degrees of the rational power functions that bound the V C-dimension in terms of |A|. The definition is as follows.

Definition 3.2. Let C, Δ and p(y) be as in Definition 3.1 and assume further that all the formulas in δ have the variable tuple x of the same a-rity r. The VC_{n}-density of Δ with respect to p(y) is greater than or equal to r if

sup_{A} \{d : \frac{|S_{Δ}^{p(y)}(A)|}{|A|^{r}} \} is bounded for all |A| > n

where A varies among sets of r-tuples.

As usual, the VC_{n}-density of p(y) with respect to Δ is equal to q ∈ ℝ if and only if it is greater than or equal to q but not greater than or equal to r for all r ∈ ℝ, r > q.

Finally, the VC-density of p(y) with respect to Δ is equal to the limit as n ∈ ℕ tends to ∞ of the V C_{n}-density of p(y) with respect to Δ.

Remark 3.3. Since model theory usually works with types over some parameter set and not over tuples, bounding the arity of the formulas and forcing the parameter set A to be a set of r-tuples may seem a little odd at first. However, if for example x := x̄ is for example a tuple x_{1}, x_{2} the instances of A that would go into each δ ∈ Δ are not elements but pairs of elements, so we should be comparing the growth to 2^{|A|^{2}} (or (|A|^{2})^{d}) as opposed to 2^{|A|} (or |A|^{d}) (in Example 3.4 we show that this can in fact make a big difference). One could, instead restricting A as we did in the definition, normalize the V C-density by dividing by the size of the largest x-tuple appearing in any formula in Δ. This would allow A to be a normal parameter set (of singletons) and for most purposes the two definitions work equally well. However, the given definition allows the proofs to be a little cleaner, which we believe is the reason it was also the definition given in [1] and [2].

Let us look a little more into what was said in Remark 3.3.

Example 3.4. Let T be the theory of real closed fields, and consider the type p(y) := {y = y} and the formula δ(x_{1}, x_{y}; y) := y < x_{1} · x_{2}. Then, if A_{n} is the set of the first n primes, there are n(n − 1)/2 δ-types over A_{n} (because there are |B| many δ′(x, y) := y < x-types over B and B := {p_{1} · p_{2}|p_{1}, p_{2} ∈ A_{n}} has size n(n − 1)/2). This means that the VC-dimension of δ (defined with (A being a set of singletons and comparing |S_{δ}^{p(y)}(A)| with |A|^{r}) with respect to x = x is at least 2. But since the parameter set of δ is a 2-tuple of elements of A, we could instead compare |S_{δ}^{p(y)}(A)| with |A^{2}|^{r} which would give us VC-density 1.

The main part of work in [1] was to show that for many theories the V C-density, as defined, was actually quite easy to compute and in many cases it had a linear behavior with respect to the size of the y variables. This work included a very good analysis of VC-density in particular in the real closed field, where they proved the following:

Fact 3.5. Let T be the theory of real closed fields (RCF) and let C be any model. Let Δ(x̄, ȳ) := {δ_{1}(x̄, ȳ), δ_{2}(x̄, ȳ), …, δ_{n}(x̄, ȳ)} where x̄ may be a tuple and ȳ is an n-tuple. Then the VC-density of p(y) with respect to Δ(x̄, ȳ) is less than or equal to n (when we define the VC-density normalizing by the length of x̄).

In particular, the VC-density of any 1-type p(y) with respect to any set of formulas δ(x̄, y) is 1. The following is an easy generalization of a result which can be found in [2].

Observation 3.6. The dp-rank of p(y) is bounded by the maximum (if it exists) VC-density of p(y), where Δ(x, y) varies over any finite set of formulas. In particular, a theory is strongly dependent whenever all of its types have finite (normalized) VC-density.

Proof. Let ⟨I_{1}, …, I_{k}⟩, ⟨φ_{1}, …, φ_{k}⟩ be a randomness pattern witnessing dp-rk(p) ≥ k. Let I′_{i} be the finite sequence of the first n elements of I_{i}, and let Δ = {φ_{1}, …, φ_{k}}. Then the set B = ∪_{i=1}^{k} ⋃ I′_{i} has k · n elements, and for every η: k → n, there is a Δ-type p_{η} over A ∪ B extending p, such that any two such types are contradictory. So for any n, we get n^{k} extensions of p over a set of size k · n. Since k is constant, the definition of V C-density implies that the V C density of p(y) with respect to Δ is at least k. □

We don’t know of any partial converse for the above statement, but any statement which stated a bound for the VC-density in terms of the dp-rank would need to involve achieving finite indiscernible sequences in a way would need some quite impressive combinatorial arguments. Thinking about the possible arguments, it came to our attention that things could be much more manageable if we could concentrate in single variables; by this we mean that both definitions –of dp-rank and VC-density– could be made by looking at the behavior of the realizations of the type with respect to singletons (for precise statements, see the two questions that follow this discussion). We should say that we have no evidence of this other than the lack of examples. However, this sort of result is not uncommon at all in theories with NIP: A theory has NIP if arbitrarily large sets of elements (not tuples) can be shattered, if a dependent theory is unstable then the strict order property can be witnessed with elements, etc. So it would not be too surprising if both VC-density and dp-rank could be defined by just looking at the singletons. We have the following two questions.

Question 3.7. If p(x) is a (partial) type over A of dp-rank greater than n, can this be witnessed by indiscernible sequences of elements? This is, are there I_{1}, …, I_{n} mutually A-indiscernible sequences of singletons and some c ⊧ p(x) such that I_{j} is not indiscernible over Ac for all 1 ≤ j ≤ n.

Question 3.8. Suppose that p(y) is a type such that for all

Δ(x, ȳ) := {δ_{1}(x, ȳ), δ_{2}(x, ȳ), …, δ_{n}(x, ȳ)}

where x is a single variable we have that the VC-density of p(y) with respect to Δ is greater than d. Is d the (normalized) VC-density of p(y) with respect to any Δ?

Notice that Question 3.8 would imply that we could define the VC-density of a type by considering formulas Δ for which x̄ is a singleton, thus avoiding all need of “normalizing”.

If both “conjectures” were true (there is much more hope, we believe, for the first one) we would have many more tools and evidence to prove the converse of Observation 3.6.

References

[1] M. Aschenbrenner, A. Dolich, D. Haskell, D. MacPherson, and S. Starchenko. vc density in some dependent theories. in preparation.

[2] A. Dolich, J. Goodrick, and D. Lippel. Dp-minimal theories: basic facts and examples. arXiv:0910.3189, 2009.

[3] A. Onshuus and A. Usvyatsov. On dp-minimality, strong dependence, and weight. Submitted, 2008.

[4] S. Shelah. Dependent first order theories, continued. Israel J. Math., 173:1–60, 2009.

[5] S. Shelah. Strongly dependent theories. arXiv:0504197, 2009.

[6] P. Simon. On dp-minimal ordered structures. arXiv:0909.4242, 2009.

[7] A. Usvyatsov. Morley sequences in dependent theories. Submitted, 2008.

Itay Kaplan, Einstein Institute of Mathematics, Edmond J. Safra Campus, Givat Ram, The Hebrew University of Jerusalem, Jerusalem, 91904, Israel

Alf Onshuus, Departamento de Matemáticas, Universidad de los Andes, Cra 1 No. 18A-10, Edificio H, Bogotá, 111711, Colombia

URL: http://matematicas.uniandes.edu.co/cv/webpage.php?Uid=aonshuus

Alexander Usvyatsov, Universidade de Lisboa, Centro de Matemática e Aplicacões Fundamentais, Av. Prof. Gama Pinto,2, 1649-003 Lisboa, Portugal

URL: http://www.math.ucla.edu/~alexus