Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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). –  Matt Lord Nov 13 '11 at 4:36

1 Answer 1

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|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! –  Matt Lord 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. –  Matt Lord Nov 14 '11 at 1:01

Your Answer

 
discard

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.