Is existential second-order logic ‘closed’ under negation

logicpredicate-logicsecond-order-logic

I am working through Exercise 1.5 in Chapter XIII of the book 'Mathematical Logic' by Ebbinghaus-Flum-Thomas, which concerns existential second-order logic. In particular, I am stuck on part (c) of this question, which says to show that existential second-order logic is not 'Boolean', meaning that it is not 'closed' under negation and/or disjunction. My intuition suggests to me that existential second-order logic will not be closed under negation, but so far I have not been able to make any progress on proving this.

So is there an obvious example of a symbol set $S$ and an existential second-order sentence $\varphi$ over $S$ for which there is no existential second-order sentence $\psi$ that is equivalent to $\neg\varphi$?

Best Answer

Yes, your intuition is right: existential second-order logic is not closed under negation.

In my opinion, the easiest way to see this is to note that ultrapowers preserve existential second-order sentences: if $\varphi$ is existential second-order and $\mathcal{A}\models\varphi$ then $\prod \mathcal{A}/\mathcal{U}\models\varphi$ for every ultrafilter $\mathcal{U}$.

  • It's a good exercise to check this. Note that this is one-way: satisfaction of an ESO sentence in the ultrapower doesn't imply satisfaction in the original structure. Moreover, this result is more-or-less a proof that ESO is compact!

Now we just need an ESO sentence whose negation is not preserved by ultrapowers. And here we're in a classic situation: one of the standard ultrapower examples is that if $\alpha$ is an infinite well-ordering and $\mathcal{U}$ is a non-countably-complete ultrafilter then $\prod\alpha/\mathcal{U}$ is an ill-founded linear order. Having no descending sequences is a negated ESO property, and so we're done.

Alternatively, you can prove the compactness of ESO via Henkinization. The fact that ESO is not closed under negation is then an immediate consequence of the non-compactness of USO (= universal second-order logic). The latter is easy to see: let $\theta_n$ be the first-order sentence saying that there are at least $n$ distinct objects, and let $\psi$ be the USO sentence saying that the domain is finite. Then $\{\theta_n:n\in\mathbb{N}\}\cup\{\psi\}$ is finitely satisfiable but not satisfiable.

(It's a good exercise to pin down where Henkinization breaks if we try to apply it to show the compactness of USO.)

Related Question