2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ In monadic predicate logic, there are no atomic sentences with two free variables. What's an example of the entailment you're asking about? $\endgroup$
    – MikeC
    Nov 13, 2011 at 4:22
  • $\begingroup$ 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). $\endgroup$ Nov 13, 2011 at 4:36

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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! $\endgroup$ Nov 13, 2011 at 4:47
  • $\begingroup$ @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". $\endgroup$ Nov 13, 2011 at 21:46
  • $\begingroup$ 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. $\endgroup$ Nov 14, 2011 at 1:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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