# quantifier order in monadic first-order logic

In (polyadic) first-order logic, for any sentence $\psi(x,y)$ with variables $x$ and $y$ free, we have $(\exists y)(\forall x)\psi(x,y)\vDash (\forall x)(\exists y)\psi(x,y)$ but not the reverse entailment. Is the reverse entailment true in monadic predicate logic, however? And if so, how would a proof go?

It strikes me as a little bizarre that I can't find a reference on this point, but perhaps the answer is obvious and I'm just not seeing it. (Heuristically, though, it would seem to be worth making explicit.)

• In monadic predicate logic, there are no atomic sentences with two free variables. What's an example of the entailment you're asking about? Nov 13, 2011 at 4:22
• Yes, that's why I didn't specify the sentences were atomic, though I guess I could have explicitly said molecular. I'm thinking of something simple (in this case it's easy to see the reverse entailment holds): take \psi(x,y) to be (Fx\to Gy). Nov 13, 2011 at 4:36

## 1 Answer

With a monadic predicate $P$, the sentence $(\forall x)(\exists y)(P(x)\iff P(y))$ does not entail $(\exists y)(\forall x)(P(x)\iff P(y))$. In fact, the former is logically valid but the latter fals in any structure where the interpretation of $P$ is neither the empty set nor the whole universe.

• Hah---I realize now I was thinking of every connective but the biconditional. Substitute for the biconditional any other two-place connective and the reverse entailment DOES obtain. Thanks! Nov 13, 2011 at 4:47
• @Matt: I assume you're talking only about formulas with only a single occurrence of a connective; otherwise, you could simulate the biconditional with other connectives. Also, you must be talking about only some "standard" set of connectives, because my example still works if you replace the biconditional by "exclusive or". Nov 13, 2011 at 21:46
• Yes, I wanted to edit my comment as soon as I made it: the original question was motivated by thinking about sentences with a single connective, and by "any other two-place connective" I just meant and, inclusive or, and the material conditional. Thanks. Nov 14, 2011 at 1:01