Definition. Let $\mathscr{L}$ be a first-order language. An $\mathscr{L}$-formula $\phi(x,y)$ has independence property (IP) if there are two sequences $(a_i)_{i<\omega}$ and $(b_I)_{i\subset \omega}$ such that $$\models \phi(a_i, b_I) \Leftrightarrow i\in I $$ An $\mathscr{L}$-theory $T$ is called NIP if no formula has the independence property.

I was able to check that NIP is closed under conjunction and disjunction.

Question. Is NIP closed under existential quantifiers?

  • $\begingroup$ So what if you have a formula $P(x, y)$ such that $\forall i, I ~.~ \models P(a_i, b_I) \iff i \in I$ but $\lnot \forall i, I ~.~ \models P(b_i, a_I) \iff i \in I$ ? Furthermore what if there are more than 2 free variables, and one pairing of the free variables with $a_i, b_I$ does have IP but another pairing doesn't? And since I'm asking, should we assume that formulas with no free variables are IP rather than undefined ? $\endgroup$
    – DanielV
    May 11, 2019 at 18:54
  • $\begingroup$ @DanielV IP is defined for a formula with a fixed partition of the free variables. It's certainly possible e.g. for $\varphi(x;y,z)$ to have IP while $\vaphi(x,y;z)$ is NIP. On the other hand, it's a theorem that if $\varphi(x;y)$ has IP, then $\varphi(y;x)$ does too. $\endgroup$ May 11, 2019 at 19:08
  • $\begingroup$ @DanielV Regarding the case of no free variables: more generally, we can allow one or both pieces of the partition of free variables to be empty. But when we do this, the formula will always be NIP (vacuously). Indeed, "$\varphi(x;y)$ has IP" means that there exist families $a_i$ interpreting $x$ and $b_I$ interpreting $y$ such that... Now the empty tuple of variables has exactly one interpretation, so one of our two families will be constant (always the empty tuple from the model), and hence won't witness IP. $\endgroup$ May 11, 2019 at 19:12
  • $\begingroup$ ... of course, it would also be undesirable to decide that by convention every sentence has IP. Then there would be no NIP theories, and for a stupid reason! $\endgroup$ May 11, 2019 at 19:14

1 Answer 1


No. Here's a counterexample:

Consider the random graph as a two-sorted structure with a sort $V$ for vertices, a sort $E$ for edges, and a ternary relation $R\subseteq V\times V\times E$, such that $R(u,v,e)$ holds if and only if $e$ is an edge between $u$ and $v$. Let $T$ be the theory of this structure - then $T$ is bi-interpretable with the theory of the random graph.

So $\exists z\,R(x,y,z)$ has IP (it defines the edge relation of a model of the theory of the random graph), but it's also easy to check that $R(x,y,z)$ does not have IP under any partition of its variables. This is because if you fix the values of any two of the variables, there is at most one value of the third which satisfies the formula. E.g. a formula of the form $R(x,v,e)$ defines a set of size at most $1$, so formulas of this form clearly cannot define arbitrary subsets of an infinite set!


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .