NIP theories (also known as dependent theories or shatterproof theories) are a class of theories generalizing stable theories, but allowing for an ordering. Aside from stable theories, important examples are real closed fields, ACVF, $p$ -adically closed fields, and o-minimal theories.

Definitions[]

Fix some complete theory $T$ , with monster model $\mathbb {U}$ . A formula $\phi (x;y)$ is said to have the independence property if there exist $\langle a_{i}\rangle _{i\in \mathbb {N} }$ and $\langle b_{S}\rangle _{S\subset \mathbb {N} }$ such that for every $i$ and $S$ , $i\in S\iff \mathbb {U} \models \phi (a_{i};b_{S})$ Note that the variables $x$ and $y$ could be tuples, and the location of the semi-colon matters.

A formula is said to be NIP if it does not have the independence property.

It turns out that the following conditions are equivalent:

The formula $\phi (x;y)$ has the independence property.
The formula $\phi ^{\vee }(y;x)$ has the independence property, where $\phi ^{\vee }(y;x)$ means $\phi (x;y)$ .
For every finite sets $U$ and $V$ and $R\subset U\times V$ , there exist $\langle a_{u}\rangle _{u\in U}$ and $\langle b_{v}\rangle _{v\in V}$ such that $\phi (a_{u};b_{v})$ holds if and only if $uRv$ , for every $u$ and $v$ . So every bipartite graph can be embedded into the graph of $\phi (x;y)$ , in some sense.
There is an indiscernible sequence $\langle a_{i}\rangle _{i<\omega }$ and a $b$ such that $\phi (a_{i};b)$ holds if and only if $i$ is odd.

A theory is said to be NIP if no formula has the independence property, i.e., every formula is NIP. A non-trivially equivalent condition is that every formula $\phi (x;y)$ with $x$ a singleton is NIP. That is, when checking NIP, one only needs to check formulas $\phi (x;y)$ with $x$ a singleton. This is a useful criterion when we have some control over one-dimensional definable sets, such as in the case of strongly minimal, o-minimal, or C-minimal theories.

Properties[]

Like most classification-theoretic boundaries, NIP is preserved under adding imaginary sorts (passing to $M^{eq}$ ), under reducts, and under naming parameters with new constant symbols.

Stable theories are NIP. In fact they are exactly the NIP theories which are also simple, or which are also NSOP.

Forking in NIP theories does not have many of the nice properties of forking in simple theories; for example, symmetry can fail, and forking can differ from dividing. However, it is still a useful tool. Here are some of the results on forking and dividing in NIP theories:

Forking is equivalent to Lascar invariance: a global type $p(x)$ forks (i.e., divides) over a base set $C$ if and only if it is Lascar invariant over $C$ . This can be expressed in two equivalent ways: (1) $p(x)$ is $M$ -invariant for every model $M$ containing $C$ ; (2) for every $C$ -indiscernible sequence $\langle b_{i}\rangle _{i\in I}$ and formula $\phi (x;y)$ , whether or not $\phi (x;b_{i})\in p(x)$ does not depend on $i$ . This result was proven by Shelah or Adler or someone.
Forking is equivalent to KP invariance: a global type $p(x)$ forks (i.e., divides) over a base set $C$ if and only if it is $bdd(C)$ -invariant. This was proven by Hrushovski and Pillay.
Forking and dividing agree over models, even on the level of formulas. That is, a formula $\phi (x;b)$ forks over a model $M$ if and only if it divides over $M$ . Moreover, in the o-minimal or c-minimal setting, one can replace "model" with "arbitrary set." These facts were proven by Chernikov and Kaplan (maybe building off the results of Hrushovski and Pillay, in the o-minimal and C-minimal setting).

Some facts from stable group theory generalize to the NIP setting. For example, $G^{00}$ always exists (the smallest type-definable subgroup of bounded index). This was proven by Shelah; a proof appears in a paper by Hrushovski, Peterzil, and Pillay. Maybe $G^{0}$ also exists, depending on what exactly $G^{0}$ means. But $G^{0}$ and $G^{00}$ need not agree, unlike in the stable case. For example, if $G$ is the circle group, or any compact definable group in RCF, then $G^{0}$ is the topological connected component of $G$ , while $G^{00}$ is the infinitesimal neighborhood of the origin.

Also, $G^{000}$ always exists; someone proved it, maybe.

A version of Baldwin-Saxl exists for NIP groups. It says that if $G$ is a type-definable group in an NIP theory, and $\phi (x;y)$ is a formula, then there is an integer $n$ such that any finite intersection of relatively definable subgroups cut out by $\phi (x;y)$ is an intersection of at most $n$ of them.

Generically stable types[]

In NIP theories, there is a well-defined notion of generically stable types, which have many of the properties of types in stable theories. A global $C$ -invariant type is said to be generically stable if it satisfies one of the following equivalent conditions:

The type $p(x_{1})\otimes p(x_{2})$ equals $p(x_{2})\otimes p(x_{1})$ .
For every global invariant type $q(y)$ , we have $p(x)\otimes q(y)=q(y)\otimes p(x)$ .
The Morley sequence of $p$ is totally indiscernible (over the empty set)
$p(x)$ is definable, and finitely satisfiable in some small set.
$p(x)$ is definable, and finitely satisfiable in every small model containing $C$ (todo: check this condition)
[Voting by Morley sequences…]
For every $B\supseteq C$ , $p$ is the unique non-forking extension of $p|B$ .

In light of the last bullet point, it makes sense to say that a complete type $p$ over a set $C$ is generically stable: this means that $p$ is stationary, and the unique nonforking global extension of $p$ is generically stable.

Even outside of the NIP setting, there is a notion of a generically stable type, but it is much more constrained, and the above equivalences fail.

Generically stable types are equivalent to stably dominated types in ACVF, and play an important role there. But there are many theories, such as RCF and $p$ -adically closed fields, in which all generically stable types are trivial. In these settings, one must instead look at generically stable measures…

Keisler measures[]

"Smooth measures" exist.

Also, all measures are Borel type-definable.

[Counting types; dependent dreams]{#Counting_types;_dependent_dreams .mw-headline}[]

If $\kappa$ is a cardinal, $ded(\kappa )$ is something like the supremum of cardinals $\lambda$ such that there is a linear order of cardinality $\kappa$ which has at least $\lambda$ -many Dedekind cuts. Under some set-theoretic assumptions, $ded(\kappa )=2^{\kappa }$ for every $\kappa$ , though under other set-theoretic assumptions, one has $ded(\kappa )<2^{\kappa }$ for some $\kappa$ . At any rate, ZFC does not decide the matter.

Shelah proved (something like) the following result:

If $T$ is NIP, then the number of types over a set of size $\kappa$ is at most $ded(\kappa )$ , for (some/all/sufficiently large?) $\kappa$ .
If $T$ is not NIP, then for every $\kappa$ there is a set of size $\kappa$ such that there are $2^{\kappa }$ -many types over said set.

Consequently, one can characterize NIP theories (in some models of ZFC) by a type-counting description, in the same way that one can characterize stable theories by counting types.

Wait, maybe the above result was for $\phi (x;y)$ types, where $\phi (x;y)$ is a NIP or non-NIP formula…

(Historical note: the original proof that NIP could be checked on formulas $\phi (x;y)$ with $x$ a singleton, was using this criterion?)

Types over finite sets[]

NIP formulas can be characterized by counting types over finite sets. If $\phi (x;y)$ is a formula, consider the function $f:\mathbb {N} \to \mathbb {N}$ which maps $n$ to the maximum number of $\phi$ -types over a set of size $n$ . The Sauer-Shelah lemma says that one of two things happens:

$f(n)=2^{n}$ for every $n$ , in which case $\phi (x;y)$ has the independence property.
$f(n)$ grows polynomially, in which case $\phi (x;y)$ is NIP.

It is conjectured that the polynomial growth can be witnessed by a uniform definability of types over finite sets. Specifically, it is conjectured that if $\phi (x;y)$ is an NIP formula, then there is some formula $\psi (y;y_{1},\ldots ,y_{n})$ such that for every finite set $A$ and every $\phi$ -type $p(x)$ over $A$ , there exist $b_{1},\ldots ,b_{n}\in A$ such that for $b\in A$ , the formula $\phi (x;b)$ is in $p(x)$ if and only if $\psi (b;b_{1},\ldots ,b_{n})$ holds. So $\psi (-;b_{1},\ldots ,b_{n})$ is the $\phi$ -definition of $p(x)$ . Of course any type over a finite set is definable over that set, but the conjecture is that the definition can be chosen uniformly across all finite sets. This conjecture turns out to be equivalent to a conjecture in machine learning.

The conjecture is known in the case when the ambient theory is NIP, i.e., when all formulas are NIP. This was proven by… ::: ::: :::