# 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 -f.s.*, 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 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.’