Characterizations of monadic NIP
Abstract
We give several characterizations of when a complete first-order theory is monadically NIP, i.e. when expansions of by arbitrary unary predicates do not have the independence property. The central characterization is a condition on finite satisfiability of types. Other characterizations include decompositions of models, the behavior of indiscernibles, and a forbidden configuration. As an application, we prove non-structure results for hereditary classes of finite substructures of non-monadically NIP models that eliminate quantifiers.
1. Introduction
It is well known that many first-order theories whose models are tame can become unwieldy after naming a unary predicate. Arguably the best known example of this is the field of complex numbers. Its theory is uncountably categorical, but after naming a predicate for the real numbers, the expansion becomes unstable. A more extreme example is the theory of infinite dimensional vector spaces over a finite field, in a relational language. The theory is totally categorical, but if, in some model one names a basis , then by choosing specified sum sets of basis elements, one can code arbitrary bipartite graphs in expansions of , by unary predicates.
As part of a larger project in Reference 2, Baldwin and Shelah undertook a study of this phenomenon. They found that a primary dividing line is whether admits coding i.e., there are three subsets of a model of and a formula that defines a pairing function If one can find such a configuration in a model . of some monadic expansions of , are wild. The primary focus in Reference 2 was monadically stable theories, i.e. theories that remain stable after arbitrary expansions by unary predicates. Clearly, the two theories described above are stable, but not monadically stable. They offered a characterization of monadically stable theories within the stable theories via a condition on the behavior of non-forking. This allowed them to prove that monadic stability yields a dividing line within stable theories: models of monadically stable theories are well-structured and admit a nice decomposition into trees of submodels, while if a theory is stable but not monadically stable then it encodes arbitrary bipartite graphs in a unary expansion, and so is not even monadically NIP.
A theory is NIP if it does not have the independence property, and is monadically NIP if every expansion of a model of by unary predicates is also NIP. The behavior of NIP theories has been extensively studied, see e.g., Reference 13. Soon after Reference 2, Shelah further studied monadically NIP theories in Reference 11, where he showed they satisfy a condition on the behavior of finite satisfiable types paralleling the condition on the behavior of non-forking in monadically stable theories. He was then able to use this to produce a linear decomposition of models of monadically NIP theories, akin to a single step of the tree decomposition in monadically stable theories.
We dub Shelah’s condition on the behavior of finite satisfiability the f.s. dichotomy, and we consider it to be the fundamental property expressible in the original language describing the dichotomous behavior outlined above. We show the f.s. dichotomy characterizes monadically NIP theories and provide several other characterizations, including admitting a linear decomposition in the style of Shelah, a forbidden configuration, and conditions on the behavior of indiscernible sequences after adding parameters. Definitions for the following theorem may be found in Definitions 3.9, 3.1, 3.4, and 3.8. Of note is that all but the first two conditions refer to the theory itself, rather than unary expansions.
We believe that monadic NIP (or perhaps a quantifier-free version) is an important dividing line in the combinatorics of hereditary classes, and provides a general setting for the sort of decomposition arguments common in structural graph theory. For example, see the recent work on bounded twin-width in the ordered binary case, where it coincides with monadic NIP Reference 4Reference 15. Here, we mention the following conjecture, adding monadic NIP to a question of Macpherson Reference 9, Question 2.2.7.
From Theorem 1.1, we see that if is not monadically NIP then it admits coding on tuples. This allows us to prove the following non-structure theorem in Section 5 (with Definition 5.1 defining the relevant terms), in particular confirming and a weak form of from the conjecture, although without any assumption of -categoricity.
We also show the following, partially explaining the importance of monadic model-theoretic properties for the study of hereditary classes.
In Section 2, we review basic facts about finite satisfiability, and introduce sequences, which are closely related to, but more general than Morley sequences. The results of this section apply to an arbitrary theory, and so may well be of interest beyond monadic NIP. Section -f.s.3 introduces the f.s. dichotomy and proves the equivalence of (3)–(6) from Theorem 1.1. Much of these two sections is an elaboration on the terse presentation of Reference 11, although there are new definitions and results, particularly in Subsection 3.2, which deals with the behavior of indiscernibles in monadically NIP theories. In Section 4 we finish proving the main theorem by giving a type-counting argument that the f.s. dichotomy implies monadic NIP, and by showing that if admits coding on tuples then it admits coding in a unary expansion. In Section 5, we prove Theorems 1.2 and 1.3.
We are grateful to Pierre Simon, with whom we have had numerous insightful discussions about this material. In particular, the relationship between monadic NIP and indiscernible-triviality was suggested to us by him.
1.1. Notation
Throughout this paper, we work in a large, sufficiently saturated, sufficiently homogeneous model of a complete theory , We routinely consider . when is an infinite set. To make this notion precise, we (silently) fix an enumeration of (of ordinal order type) and an enumeration with Then . for all subsequences and is the corresponding subsequence of .
2. sequences -f.s.
Forking independence and Morley sequences are fundamental tools in the analysis of monadically stable theories in Reference 2. These are less well-behaved outside the stable setting, but in any theory we may view ‘ is finitely satisfiable in as a statement that ’ is (asymmetrically) independent from over Following .Reference 11, we will use finite satisfiability in place of non-forking, and indiscernible sequences in place of Morley sequences. Throughout Section -.f.s.2, we make no assumptions about the complexity of .
2.1. Preliminary facts about sequences -f.s.
For the whole of this section, fix a small (typically, ).
One way of producing finitely satisfiable types in comes from average types.
It is easily checked that is a complete type over that is finitely satisfied in We record a few basic facts about types that are finitely satisfied in . Proofs can be found in either Section VII.4 of .Reference 12 or in Reference 13.
Note that for any , is an sequence over -f.s. if and only if the concatenation is an sequence. -f.s.
We note two useful operations on sequences over -f.s. ‘Shrinking’ and ‘Condensation’. ,
In particular, removing a set of from the sequence is an instance of Shrinking. ’s
Here is one general result, whose verification is just bookkeeping.
The next lemma is not used later, but shows that if then decomposing , as an sequence gives a chain of elementary substructures approximating -f.s. .
The following argument is contained in the proof of Reference 11, Part I Lemma 2.6, but the statement here is slightly more general. (The paper Reference 11 is divided into Part I and Part II, with overlapping numbering schemes.)
2.2. full for non-splitting
The relevance of fullness is that, whenever is full, every complete type has a unique extension to any set that does not split over Keeping in mind finite satisfiability as an analogue of non-forking, the next lemma says that ‘types over . that are finitely satisfied in are stationary.’
We glean two results from Lemma 2.14. The first bounds the number of types realized in an sequence, independent of either -f.s. or .
The second is a refinement of the type structure of an sequence over a full -f.s. .
The following is essentially part of the statement of Reference 11, Part I Lemma 2.6.
2.3. sequences and indiscernibles -f.s.
In this subsection, we explore the relation between sequences and indiscernibles. An -f.s. sequence need not be indiscernible (for example, the tuples can realize different types), but when it is, it gives a special case of a Morley sequence in the sense of -f.s.Reference 13.
We first show indiscernible sequences can always be viewed as sequences over some model -f.s. .
Armed with this lemma, we characterize when an infinite is both an sequence and is indiscernible over -f.s (A paradigm of an indiscernible sequence over . that is not an sequence is where -f.s. is an equivalence relation with infinitely many, infinite classes and is a sequence from some not represented in -class .)
Using Lemma 2.19, we obtain a strengthening of Lemma 2.18. The lemma below can be proved by modifying the proof of Lemma 2.10, but the argument here is fundamental enough to bear repeating.
Next, we recall the following characterization of indiscernibility. The relevant concepts first appeared in the proof of Theorem 4.6 of Reference 10 and a full proof appears in Reference 12, Lemma I, 2.5.
By contrast, if and is an sequence over -f.s. then (2) is satisfied, but (1) may fail. In the case where , is full, (1) reduces to a question about types over .
In terms of existence of such sequences, we have the following.
3. The f.s. dichotomy
We begin this section with the central dividing line of this paper. Although unnamed, the concept appears in Lemma II 2.3 of Reference 11.
It would be equivalent to replace , by sets in the definition above, and this form will often be used. Much of the utility of the f.s. dichotomy is via the following extension lemma.
It is evident that Lemma 3.2 extends to sequences -f.s. over an arbitrary base .
In Reference 2, Theorem 4.2.6, the f.s. dichotomy appears as a statement about the behavior of forking rather than non-forking. Namely, forking dependence is totally trivial and transitive on singletons. We may derive similar consequences for dependence from the f.s. dichotomy. This is stated in Reference 3, Corollary 5.22, although missing the necessary condition of full .
In the stable case, forking dependence is symmetric as well and so yields an equivalence relation on singletons, which is used in Reference 2 to decompose models into trees of submodels. In general, the f.s. dichotomy shows finite satisfiability yields a quasi-order on singletons when working over a full Taking the classes of this quasi-order in order naturally gives an irreducible decomposition of . over in the sense of the next subsection, but we sometimes wish to avoid having to work over a full .
3.1. Decompositions of models
In this subsection, we characterize the f.s. dichotomy in terms of extending partial decompositions to full decompositions of models.
By iterating Lemma 3.2 for every for a given set we obtain:
We note that at the end of Reference 2, Baldwin and Shelah conjecture that models of monadically NIP theories should admit tree decompositions like those they describe for monadically stable theories, but with order-congruences in place of full congruences.
3.2. Preserving indiscernibility
We begin with some definitions. The definition of dp-minimality given here may be non-standard, but it is proven equivalent to the usual definition with Fact 2.10 of Reference 6.
As mentioned in the introduction, the notion of a theory admitting coding was the central dividing line of Reference 2. We weaken the definition here to allow the sequences to consist of tuples. Note that even the theory of equality would admit the further weakening of also allowing to consist of tuples.
A convenient variant for this subsection is a joined tuple-coding configuration, which consists of a formula (with parameters) a sequence , indiscernible over the parameters of indexed by an infinite linear order , and a set , such that for , Given a joined tuple-coding configuration, indexed by a countable, dense . we may construct a tuple-coding configuration by keeping , fixed, choosing open intervals with and letting , and Conversely, given a tuple-coding configuration with . we may construct a joined tuple-coding configuration by considering the indiscernible sequence whose elements are , restricting , to elements with and replacing , by .
The following configuration appears in Reference 11, Part II Lemma 2.2, and will appear as an intermediate between a failure of the f.s. dichotomy and a tuple-coding configuration.
We show the equivalence of the existence of these notions with the proposition below. The proof of in the following is essentially from Reference 11, Part II Lemma 2.3, while is based on Reference 15, Lemma C.1. The idea of is that when working over a full types have a unique “generic” extension by Lemma ,2.12. In a failure of the f.s. dichotomy, the extension of to is non-generic, and so can in some sense pick out and from a suitable sequence.
The following observation will be useful in Section 5. A tidy pre-coding configuration is one where for every and The pre-coding configuration constructed in . is tidy, since, choosing so is an sequence, -f.s. implies and are not finitely satisfiable in But if . for then the former type is finitely satisfiable in and if , for then the latter type is. ,
The tidiness property extends to the joined tuple-coding configuration constructed in and so ultimately to the tuple-coding configuration as well. That is, from a failure of the f.s. dichotomy, we construct a tuple-coding configuration with for every and , .
4. The main theorem
We recall the main theorem from the introduction. Note that whereas Clauses (1) and (2) discuss monadic expansions of Clauses (3)–(6) are all statements about , itself.
The following are equivalent for a complete theory with an infinite model.
- (1)
is monadically NIP.
- (2)
No monadic expansion of admits coding.
- (3)
does not admit coding on tuples.
- (4)
has the f.s. dichotomy.
- (5)
For all and every partial , decomposition of -f.s. extends to an (irreducible) decomposition of -f.s. .
- (6)
is dp-minimal and has indiscernible-triviality.
The equivalences of (3)–(6) are by Proposition 3.6 and Proposition 3.11. We note that is easy: Choose a monadic expansion that admits coding, say via an -formula defining a bijection from the countable sets By adding a new unary predicate for a suitable . the formula , can define the edge relation of an arbitrary bipartite graph on and in particular of the generic bipartite graph. Thus, , is not monadically NIP.
Thus, it remains to prove that and which are proved in the next two subsections. ,
4.1. If has the f.s. dichotomy, then is monadically NIP
The type-counting argument in this section is somewhat similar to that in Reference 3, showing that monadic NIP corresponds to the dichotomy of unbounded partition width versus partition width at most Both arguments use the tools from Sections .2 and 3 to decompose the model and count the types realized in a part of the decomposition over its complement. However, while Blumensath decomposes the model into a large binary tree, our decomposition takes a single step.
Suppose is any sequence of pairwise disjoint tuples and suppose is any model. An of -partition is any partition with for each .
For any and let , denote the number of complete types over realized by tuples in .
We will be primarily interested in the case where is very large, and is significantly smaller than The following lemma is similar to Lemma .2.15, removing the requirement that the partition is convex but adding a finiteness condition.
For the rest of this section, recall the notation from the first part of Definition 2.4.
If has the f.s. dichotomy, then for every well-ordering with a maximum element, for every indiscernible sequence of pairwise disjoint tuples and every there is an , -partition of such that for every finite .
By Lemma 2.20, choose a model of size and a full with for which is an sequence over -f.s. (Note that . might not contain By Lemma .)3.5 choose a simple extension of with Thus, . is an of -partition For a given finite . and let , and let As . is an order-congruence over by Lemma 2.17, is determined by and the order type of the finite set There are only finitely many such order types, and as . there are at most , complete types over So . for every finite .
■On the other hand, if a theory has the independence property, then no uniform bound can exist.
Suppose that has IP, as witnessed by with and For every . there is an order-indiscernible and a model , such that for every -partition of , for some finite .
In the monster model, choose an order-indiscernible that is shattered, i.e., there is a set such that holds if and only if Note that for distinct . there is some , such that Let . be any model containing and let be any of -partition As . while , by applying the pigeon-hole principle , times (one for each coordinate of one obtains ) also of size , and a finite , such that for each As . and there are at most types over we can find , of size such that is constant among It follows that . for distinct As . it follows that , .
■To show that the behaviors of Lemma 4.4 and Lemma 4.5 cannot co-exist, we get an upper bound on the number of types realized in a finite monadic expansion. Such a bound is easy for quantifier-free types, and the next lemma inductively steps it up to a bound on all types. The following two lemmas make no assumptions about .
For each define an equivalence relation , on by: if and only if and for every formula of quantifier depth at most Clearly, . if and only if for every To get an upper bound on . for each , let , .
For any , and , , Thus, . .
The second sentence follows from the first as if and only if for every For the first sentence, we give an alternate formulation of . to make counting easier. For each let , be the equivalence relation on given by:
- •
if and only if and and ;
- •
if and only if and, for every there is , such that and vice-versa, ,
For each let , It is clear that . and by the definition of we have for each so the lemma follows from the fact that , if and only if whose verification amounts to proving the following claim. ,
If the quantifier depth of is at most then for all partitions , for all , and for all , if , then , .
By induction on Say . is chosen with the quantifier depth of is at most Fix a partition . and choose , with Assume . There are two cases. If there is some . such that then , by the inductive hypothesis. On the other hand, if there is such that use , to find such that Thus, the inductive hypothesis implies . so again , .
■The following transfer result is the point of the previous lemma. Again, it will be used when is significantly smaller than .
Let be any model and let be any expansion of by finitely many unary predicates. Then .
For each expanding by , unary predicates can increase the number of quantifier-free by at most a finite factor, i.e. -types so , The result now follows from Lemma .4.6.
■Finally, we combine the lemmas above to obtain the goal of this subsection.
If has the f.s. dichotomy, then is monadically NIP.
By way of contradiction assume that is not monadically NIP, but has the f.s. dichotomy. Let be an expansion by finitely many unary predicates that has IP. Choose a cardinal Let . with as in Lemma 4.5, so for any of -partition there is with .
Let be the of -reduct As . remains and -order-indiscernible, has the f.s. dichotomy, choose an -partition of as in Lemma 4.4, so for every Since . is a unary expansion of , for every by Lemma ,4.7. This contradicts our ability to find an from the previous paragraph for the chosen of -partition .
■Lemma 2.15 and the arguments in this subsection seem to indicate that, for a generalization of the structural graph-theoretic notion of neighborhood-width Reference 7 similar to Blumensath’s generalization of clique-width Reference 3, monadic NIP should correspond to a dichotomy between bounded and unbounded neighborhood-width.
4.2. From coding on tuples to coding on singletons
This subsection provides the final step, in proving Theorem ,4.1 by showing that if admits coding on tuples, then some monadic expansion admits coding (i.e., on singletons). For the result of this subsection, since admitting coding on tuples immediately implies is not monadically NIP, we could finish by Reference 2, Theorem 8.1.8, which states that if has IP then this is witnessed on singletons in a unary expansion. But the number of unary predicates used would depend on the length of the tuples in the tuple-coding configuration, which would weaken the results of Section 5.
Deriving non-structure results in a universal theory from the existence of a bad configuration is made much more involved if the configuration can occur on tuples. If one is willing to add unary predicates, arguments such as that from Reference 2 mentioned above will often bring the configuration down to singletons. A general result in this case is Reference 3, Theorem 4.6 that (under mild assumptions) there is a formula defining the tuples of an indiscernible sequence in the expansion adding a unary predicate for each “coordinate strip” of the sequence. The results of Reference 14 indicate the configuration can often be brought down to singletons just by adding parameters, instead of unary predicates, but these arguments seem difficult to adapt to tuple-coding configurations. Another approach, which we use here, is to take an instance of the configuration where the tuples have minimal length, and argue that the tuples then in many ways behave like singletons.
Given a tuple-coding configuration indexed by disjoint countable dense orderings , an order-preserving permutation of , (resp. naturally gives rise to permutation of ) (resp. call such permutations of ); and standard permutations.
A tuple-coding configuration as above is regular if
whenever (including cases with ), is a standard permutation of corresponding to an element of fixing and , is a standard permutation of corresponding to an element of fixing .
By Ramsey and compactness, if admits coding on tuples via the formula then it admits a regular tuple-coding configuration via the same formula , .
Let be a tuple-coding configuration with countable, dense. The pair with is a witness for if there are open intervals with such that for all we have , .
A tuple-coding configuration has unique witnesses up to permutation if for every the only witnesses for , are of the form for some a permutation of and some a permutation of
Let be a regular tuple-coding configuration for with , minimal. Then this configuration has unique witnesses up to permutation.
Suppose not, and let be a witness for such that , for any First, if either . or then regularity immediately implies that , is not a witness. So let be the subsequence of intersecting and , the subsequence of intersecting Either . or so assume the former.
Let be an open interval such that Let . be the formula obtained by starting with and then replacing the subtuple , with the variables so we have plugged the elements of ; as parameters into For each . let , be the restriction of to the coordinates corresponding to Then . is also a regular tuple-coding configuration, contradicting the minimality of .
■The following Lemma completes the proof of Theorem 4.1.
Suppose admits coding on tuples. Then admits coding in an expansion by three unary predicates.
Choose a tuple-coding configuration
with as small as possible. By the remarks following Definition 4.9. we may assume this configuration is regular, so by Lemma 4.11, it has unique witnesses up to permutation. Let and let be the expansion of interpreting as , as and , as itself. Let
Let be the first coordinate of and , the first coordinate of Then . and , witness coding in via the -formula .
■5. Finite structures
In this section, we restrict the language of the theories we consider to be relational (i.e., no function symbols) with only finitely many constant symbols.
For a complete theory and , the isomorphism types of finite substructures of , do not depend on the choice of so we let , denote this class of isomorphism types.
The growth rate of (sometimes called the profile or (unlabeled) speed) is the function counting the number of isomorphism types with elements in .
We also investigate under the quasi-order of embeddability. We say is well-quasi-ordered (wqo) if this class does not contain an infinite antichain, and we say is if -wqo is wqo for every expansion of any model of by unary predicates that partition the universe.
The definition of is sometimes given for an arbitrary hereditary class -wqo rather than an age, with if the class -wqo containing every partition of every structure of by at most unary predicates remains wqo. Our definition is possibly weaker, but then its failure is stronger.
Let Then . is wqo, but not 2-wqo, since contains arbitrarily long finite paths, and marking the endpoints of these paths with a unary predicate gives an infinite antichain.
By contrast, if then , can be shown to be for all -wqo .
The following lemma shows that when considering adding finitely many parameters is no worse than adding another unary predicate. -wqo,
Suppose is If -wqo. is an expansion of by finitely many constants, then is -wqo.
Suppose an expansion by constants is not as witnessed by an infinite antichain -wqo, in a language expanding the initial language by the constants and by unary predicates. Let be the structure obtained from by forgetting the constants, but naming their interpretations by a single new unary predicate. As is -wqo, contains an infinite chain under embeddings. As there are only finitely many permutations of the constants, some embedding in the chain must preserve them, contradicting that is an antichain.
■In both Theorems 5.3 and 5.6, the assumption that has quantifier elimination is only used to get that the formula witnessing that admits coding on tuples is quantifier-free, and the formula witnessing the order property in the stability part of Theorem 5.6, so the hypotheses of the theorems can be weakened to only these specific formulas being quantifier-free. This weakened assumption is used in Reference 15. From the proof of Proposition 3.11, if the failure of the f.s. dichotomy is witnessed by quantifier-free formulas, then the formula witnessing coding on tuples will be quantifier-free as well.
If a complete theory has quantifier elimination in a relational language with finitely many constants is not monadically NIP, then has growth rate asymptotically greater than for some and is not 4-wqo.
Since is not monadically NIP, let
be a regular tuple-coding configuration with unique witnesses up to permutation. The only place we use has QE is to choose quantifier-free. Let expand by unary predicates for and , as well as constants for the parameters of and let , be as in the proof of 4.12. Let be the set of finite substructures that can be constructed as follows.
- (1)
Pick , and , .
- (2)
Start with .
- (3)
For every point added in the previous step, add the four elements and where , are closer to than any other element of and , are closer to than any other element of .
- (4)
Add the parameters of .
For any and , .
Since is quantifier-free, it remains to check that if the existential quantifiers in are witnessed in and then they are witnessed in and if the universal fails in , then it fails in From the unary predicates at the beginning of . we may let , and , If . the only tuple in , that can witness is the rest of the tuple which will be in , because it only contains full tuples, and similarly for witnessing Since our configuration has unique witnesses up to permutation, if the universal quantifier fails in . this is witnessed by an element , with and By regularity, this failure is also witnessed by some element in . .
■Given a bipartite graph with edges and no isolated vertices, we may encode it as a structure by starting with tuples for each point in one part and tuples for each point in the other part, and including whenever we want to encode an edge between and Note that . and this encoding preserves isomorphism in both directions. In the proof of ,Reference 8, Theorem 1.5, the asymptotic growth rate of such graphs is shown to be at least which gives the desired growth rate for , with the constant depending on the length of the tuples in the tuple-coding configuration. Since expanding by finitely many unary predicates and constants increases the growth rate by at most an exponential factor, we also get the desired growth rate for .
Furthermore, if embeds into then , must be a (possibly non-induced) subgraph of So we get that . is not wqo by encoding even cycles. We expanded by three unary predicates, and by Lemma 5.2 the parameters may be replaced by another unary predicate while still preserving the failure of wqo, so we get that is not 4-wqo.
■There is a homogeneous structure, with automorphism group in its product action, that is not monadically NIP and whose growth rate is the number of bipartite graphs with a prescribed bipartition, edges, and no isolated vertices. So the lower bound in this theorem cannot be raised above the growth rate of such graphs. Precise asymptotics for this growth rate are not known, although it is slower than and Reference 5, Theorem 7.1 improves Macpherson’s lower bound to for every .
If Conjecture 1 from the Introduction (in particular is confirmed, then the lower bound on the growth rate in Theorem )5.3 would also confirm Reference 8, Conjecture 3.5 that for homogeneous structures there is a gap from exponential growth rate to growth rate at least for some .
Theorem 5.3 is somewhat surprising. Since passing to substructures can be simulated by adding unary predicates, it is clear that if is monadically tame, then should be tame. However, unary predicates can do more, so it seems plausible that could be tame even though is not monadically tame. Our next theorem gives some explanation for why this does not occur, at least when assuming quantifier elimination.
First we need to define stability and NIP for hereditary classes. The following definition is standard and appears, for example, in Reference 15, §8.1.
For a formula and a bipartite graph we say a structure , encodes via if there are sets such that .
A class of structures has IP if there is some formula such that for every finite, bipartite graph there is some , encoding via Otherwise, . is NIP.
A class of structures is unstable if there is some formula such that for every finite half-graph there is some , encoding via Otherwise, . is stable.
Equivalently, by compactness arguments, is NIP (resp. stable) if and only if every completion of the common theory of structures in , is. Note that it suffices to witness that , has IP or is unstable using a formula with parameters, since we can remove them by appending the parameters to each .
The sort of collapse between monadic NIP and NIP in hereditary classes observed in Theorem 5.6 occurs for binary ordered structures Reference 15, since there the formula giving coding on tuples is quantifier-free. It also occurs for monotone graph classes (i.e. specified by forbidding non-induced subgraphs), where NIP actually collapses to monadic stability, and agrees with nowhere-denseness Reference 1.
Suppose that a complete theory in a relational language with finitely many constants has quantifier elimination. Then is NIP if and only if is monadically NIP, and is stable if and only if is monadically stable.
We first consider the NIP case.
Suppose has IP, as witnessed by the formula By compactness, there is a model . of the universal theory of in which encodes the generic bipartite graph. But then is a substructure of some and naming a copy of , in by a unary predicate and relativizing to gives a unary expansion of with IP.
Suppose is not monadically NIP, witnessed by a tuple-coding configuration , with , quantifier-free and containing parameters By Remark .3.12, we may also assume the configuration is tidy. For any bipartite graph let , contain tuples from , and corresponding to the two parts of and an element of , for each edge of so that encodes on But by tidiness, . encodes on as well.
For the stable case, the backwards direction is the same except using the infinite half-graph in place of the generic bipartite graph. For the forwards direction, if is unstable then by quantifier-elimination is also unstable. If is stable but not monadically stable, then by Reference 2, Lemma 4.2.6 is not monadically NIP, so we are finished by the NIP case.
■