I happened upon this question Is existential second-order logic 'closed' under negation? about the closure of existential second order logic (ESO) under negation. The answer was that ESO is not closed under negation.
Is existential FOL closed under negation? If so, is there a procedure for finding an existential form for the negation of an existential sentence of FOL? I did a cursory search for information on the subject, but couldn’t find anything.
Best Answer
No, existential FOL is not closed under negation. Note that if it were, then every first-order formula would be equivalent to an existential formula (since first-order formulas are built from atomics by $\land$, $\lor$, $\lnot$, $\exists$, and $\forall$ - three of these operations are allowed in the existential fragment, and $\forall$ can be rewritten as $\lnot \exists \lnot$, so if $\lnot$ keeps us inside the existential fragment, then all formulas are in the existential fragment). We should not expect this to be true!
But let's actually give a simple proof.
Note that existential sentences are preserved under "going up": if $\varphi$ is an existential sentence, $A\models \varphi$, and $A$ is a substructure of $B$, then $B\models \varphi$.
So to find an existential sentence whose negation is not equivalent to an existential sentence, we need to find one whose negation is not preserved under "going up".
Just about any existential sentence which is not quantifier-free will work. For example, in the language with a unary relation symbol $P$, consider $\exists x\,P(x)$. Let $\psi$ be the negation $\lnot \exists x\, P(x)$. Let $A = \{a\}$, with $P^A = \varnothing$, and let $B = \{a,b\}$ with $P^B = \{b\}$. Then $A\models \psi$, but $B\not\models \psi$, so $\psi$ is not equivalent to an existential sentence.