MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.)

share|cite|improve this question
In monadic predicate logic, there are no atomic sentences with two free variables. What's an example of the entailment you're asking about? – MikeC Nov 13 '11 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). – symplectomorphic Nov 13 '11 at 4:36
up vote 5 down vote accepted

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.

share|cite|improve this answer
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! – symplectomorphic Nov 13 '11 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". – Andreas Blass Nov 13 '11 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. – symplectomorphic Nov 14 '11 at 1:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.