Is NIP closed under $\exists$? **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?

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!