Lecture Notes 11: Derivations with Multiple Quantifiers

Negation Rules

If a quantifier has a negation in front of it, we cannot use ∃O or ∀O. Remember our rules apply only to whole lines.

However, we now introduce new rules that allow us to make use of statements that begin with negations of quantifiers in front.

(These rules are redundant, but very helpful.)

A little reflection shows these rules to be valid.

If it’s not true that everything is F, then something must not be F.

If it’s not true that something is F, then everything must not be F.

Consider these arguments:

Not everything is colored.
Therefore, something is not colored.

It’s not true that something is omnipotent.
Therefore, everything is not omnipotent.

These arguments exemplify the patterns of reasoning above.

Another way of putting these rules is that you can “push” a negation through a quantifier if you change the quantifier.

However, you must change the quantifier. One cannot go from ~∀x…x… to ∀x~…x…!

Yes, we get a double negation at line 7.

The rule only pushes the negation through: it cannot eliminate it.

Multiple Quantifiers, Relational Quantification

Nothing special is needed to do problems with multiple quantifiers. Take them one at a time, and treat the letters that occur in different places as different when they’re different, and the same when they’re the same.

Also remember you can’t apply the rules to parts of lines.

Here’s a problem using two universal derivations, one right after another.

At line 3, you only change the “x”s to “a”, and at line 4 you only change the “y”s to “b”. We push negations through one at a time as well.

Only the “x”s change at line 6.

Here’s my favorite problem:

Everyone loves a lover.
Someone loves someone.
Therefore, everyone loves everyone.

The key to the problem is realizing that you can use the first premise more than once, and that you can juggle the names around as needed.

We can show everyone loves everyone by showing that, for arbitrary “people” a and b, a loves b. We do this by going through the universal statement twice. Since someone loves someone, we give them names, and call them c and d. Since c loves d, c is a lover. Since c is a lover, everyone loves c. If everyone loves c, everyone, including b, is a lover. If b is a lover, everyone, including a, loves b. So a loves b, and everyone loves everyone.