# Multiple quantifiers and negation

In a formula of the form ~ for all x, for all y (l(x,y) -> r(x,y)) how do we apply negation to the formula "(l(x,y) -> r(x,y))" ? And similarly if we have a formula with different quantifiers, such as, ~ for all x, there is a y (l(x,y) and r(x,y)).

For the first case, read this and this. The first link treats general quantification (or variation as Russell calls) and existential, and how you can apply rules of symbolism with it. The second link explains the philosophy, or the interpretation, behind the symbolism, which helps you understand what you can and can't do, regarding rules of inference. I.e, the texts contain everything to solve the guy's question, and still give him a general understanding of what he is doing.

For the second case, just consider as being . I.e, consider .

I think you are asking which sentence, logically equivalent to that one, includes ~(Ixy → Rxy). The answer is (∃x)(∃y)~(Ixy → Rxy).

As we move the quantifier in past the (∀x), it becomes (∃x). That is because, to take a simpler example, “~(∀x)Px” means “not everything is P,” while “(∃x)~Px” means that “something is not P,” which amounts to the same thing.

So, equally logically equivalent is the intermediate sentence (∃x)~(∀y)(Ixy → Rxy). Move the negation inward once more and you get (∃x)(∃y)~(Ixy → Rxy).

For your second example, ~(∀x)(∃y)(Ixy & Rxy) is logically equivalent to (∃x)(∀y)~(Ixy & Rxy).

• So the negation applies to all quantifiers? What if we had a formula of the form, ~ for all x, ~ for all y (phi) where both (all, if you have more than two) quantifiers are being negated? Dec 27 '14 at 21:18
• ~(∀x)~(∀y)φ is logically equivalent to (∃x)~~(∀y)φ which is logically equivalent to (∃x)(∀y)φ and (∃x)~(∃y)~φ. Dec 27 '14 at 23:13
• Is the confusion here about binding in quantifier statements? In First Order Logic there is a very precise distinction between "for all x, for all y" and "for all y, for all x". Think of it like this - after each case of "for all x..." there is an implicit bracketing around the rest of the sentence. What ChristopherE should technically have written is ~(∀x(∀y(Ixy → Rxy) ) ), but the bracketing conventions for this make it a little unwieldy so we tend to leave them out and assume that people know how quantifiers bind to their sentences. May 1 '15 at 9:49
• @PaulRoss -- indeed perhaps that's the reason for the confusion, though I wouldn't say that's technically more correct. It depends on particular systems' grammar; mine is grammatical in some systems. But yes, a possible source of confusion. May 1 '15 at 15:32

Switching both quantifiers, applying the definition of implication (the conjunctive form), and removing all resulting double negations, you can obtain:

(1) There exists x such that there exists y such that L(x,y) and ~R(x,y).

(2) There exists x such that for all y, L(x,y) => ~R(x,y).