# 6.1: Multiple Quantification and Harder Problems

In chapter 5 I wanted you to focus on understanding the basic rules for quantifiers. So there I avoided the complications that arise when we have sentences, such as '(Vx)(Vy)(Px & Py)', which stack one quantifier on top of another. Such sentences involve no new principles. It's just a matter of keeping track of the main connective. For example, '(Vx)(Vy)(Px & Qy)' is a universally quantified sentence, with '(Vx)' as the main connective. You practiced forming substitution instances of such sentences in chapter 3. The substitution instance of '(Vx)(Vy)(Px & Qy)' formed with 'a' (a sentence you could write when applying VE) is '(Vy)(Pa & Qy)'.

You will see how to deal with such sentences most quickly by just looking at a few examples. So let's write a derivation to establish the validity of

(Vx)(Vy)(Px & Qy) 1 | (Vx)(Vy)(Px & Qy) P
(Vx)Px & (Vx)Qx 2 | (Vx)(Pâ & Qy) 1, VE
3 | Pâ & Qb̂ 1, VE
4 | Pâ 1, VE
5 | Qb̂ 1, VE
6 | (Vx)Px 1, VE
7 | (Vx)Qx 1, VE
8 | (Vx)Px & (Vx)Qx 1, VE

In line 2 I applied VE by forming the substitution instance of 1 using the name 'a'. Then in line 3 I formed a substitution instance of the universally quantified line 2.

Let's look at an example of multiple existential quantification. The basic ideas are the same. But observe that in order to treat the second existential quantifier, we must start a sub-sub-derivation:

(∃x)(∃y)(Px & Qy)
(∃x)Px & (∃x)Qx

1 | (∃x)(∃y)(Px & Qy) P
2 | a| (∃y)(Pa & Qy) A
3 | | b| Pa & Qb A
4 | | | Pa 3, &E
5 | | | Qb 3, &E
6 | | | (∃x)Px 4, ∃I
7 | | | (∃x)Qx 5, ∃I
8 | | 3| (∃x)Px & (∃x)Qx 6, 7, &I
9 | 2| (∃x)Px & (∃x)Qx 2, 3-8, ∃E
10 1| ∃x)Px & (∃x)Qx 1, 2-9, ∃E

In line 2 I wrote down '(∃y)(Pa & Qy)', a substitution instance of line 1, formed with 'a', substituted for 'x', which is the variable in the main connective, '(∃x)', of line 1. Since I plan to appeal to 3E in application to line 1, I make '(∃y)(Pa & Qy)' the assumption of a subderivation with 'a' an isolated name. I then do the same thing with '(∃y)(Pa & Qy)', but because this is again an existentially quantified sentence to which I will want to apply 3E, I must make my new substitution instance, 'Pa & Qb', the assumption of a sub-sub-derivation, this time with 'b' the isolated name.

In the previous example, I would have been allowed to use 'a' for the second as well as the first substitution instance, since I was applying VE. But, in the present example, when setting up to use two applications of ∃E, I must use a new name in each assumption. To see why, let's review what conditions must be satisfied to correctly apply ∃E to get line 9. I must have an existentially quantified sentence (line 2) and a subderivation (sub-sub-derivation 3), the assumption of which is a substitution instance of the existentially quantified sentence. Furthermore, the name used in forming the substitution instance must be isolated to the subderivation. Thus, in forming line 3 as a substitution instance of line 2, I can't use 'a'. I use the name 'b' instead. The 'a' following 'P' in line 3 does not violate the requirement. 'a' got into the picture when we formed line 2, the substitution instance of line 1, and you will note that 'a' is indeed isolated to subderivation 2, as required, since sub-sub-derivation 3 is part of subderivation 2.

Here's another way to see the point. I write line 3 as a substitution instance of line 2. Since I will want to apply ∃E, the name I use must be isolated to subderivation 3. If I tried to use 'a' in forming the substitution instance of line 2, I would have had to put an 'a' (the "isolation flag") to the left of scope line 3. I would then immediately see that I had made a mistake. 'a' as an isolation flag means that 'a' can occur only to the right. But 'a' already occurs to the left, in line 2. Since I use 'b' as my new name in subderivation 3, I use 'b' as the isolation flag there. Then the 'a' in line 3 causes no problem: All occurrences of 'a' are to the right of scope line 2, which is the line flagged by 'a'.

All this is not really as hard to keep track of as it might seem. The scope lines with the names written at the top to the left (the isolation flags) do all the work for you. 'a' can only appear to the right of the scope line on which it occurs as an isolation flag. 'b' can only occur to the right of the scope line on which it occurs as an isolation flag. That's all you need to check.

Make sure you clearly understand the last two examples before continuing. They fully illustrate, in a simple setting, what you need to understand about applying the quantifier rules to multiply quantified sentences.

Once you have digested these examples, let's try a hard problem. The new example also differs from the last two in that it requires repeated use of a quantifier introduction rule instead of repeated use of a quantifier elimination rule. In reading over my derivation you might well be baffled as to how I figured out what to do at each step. Below the problem I explain the informal thinking I used in constructing this derivation, so that you will start to learn how to work such a problem for yourself.

(Vx)Px ⊃ (∃x)Qx
(∃x)(∃y)(Px ⊃ Qy)

1 | (Vx)Px ⊃ (∃x)Qx P
2 | | ~(∃x)(∃y)(Px ⊃ Qy) A
3 | | | ~Pa A
4 | | | ~Qb ⊃ ~Pa ⊃, W
5 | | | Pa ⊃ Qb 4, CP
6 | | | (∃y)(Pa ⊃ Qy) 5, ∃I
7 | | | (∃x)(∃y)(Px ⊃ Qy) 6, ∃I
8 | | | ~(∃x)(∃y)(Px ⊃ Qy) 2, R
9 | | Pâ 3-8, RD
10 | | (Vx)Px 9, VI
11 | | | (∃x)Qx A
12 | | | b| Qb A
13 | | | | Pa ⊃ Qb 12, W
14 | | | | (∃y)(Pa ⊃ Qy) 13, ∃I
15 | | | | (∃x)(∃y)(Px ⊃ Qy) 14, ∃I
16 | | | (∃x)(∃y)(Px ⊃ Qy) 11, 12-15, ∃E
17 | | | ~(∃x)(∃y)(Px ⊃ Qy) 2, R
18 | | ~(∃x)Qx 11-17, ~I
19 | | (Vx)Px ⊃ (∃x)Qx 1, R
20 | | (∃x)Qx 10, 19, ⊃E
21 | (∃x)(∃y)(Px ⊃ Qy) 2-20, RD

My basic strategy is reductio, to assume the opposite of what I want to prove. From this I must get a contraction with the premise. The premise is a conditional, and a conditional is false only if its antecedent is true and its consequent is false. So I set out to contradict the original premise by deriving its antecedent and the negation of its consequent from my new assumption.

To derive (Vx)Px (line 10), the premise's antecedent, I need to derive Pâ. I do this by assuming ~Pa from which I derive line 7, which contradicts line 2. To derive ~(∃x)Qx (line 18), the negation of the premise's consequent, I assume (∃x)Qx (line 11), and derive a contradiction, so that I can use ~I. This proceeds by using ∃E, as you can see in lines 11 to 16.

Now it's your turn to try your hand at the following exercises. The problems start out with ones much easier than the last example-and gradually get harder!

Exercise

6-1. Provide derivations to establish the validity of the following argument (a):

(a) (∃x)Lxx (a-1) (Vx)Lxx
(∃x)(∃y)Lxy (Vx)(Vy)Lyx

Note that the argument, (a-1) is invalid. Prove that this argument is invalid by giving a counterexample to it (that is, an interpretation in which the premise is true and the conclusion is false). Explain why you can't get from (Vx)Lxx to (Vx)(Vy)Lxy by using VE and VI as you can get from (∃x)Lxx to (∃x)(∃y)Lxy by using ∃E and ∃I.

b) (Vx)(Vy)Lxy b-1) (∃x)(∃y)Lxy
(Vx)Lxx (∃x)Lxx

Note that the argument, (b-1) is invalid. Prove that this argument is invalid by giving a counterexample to it. Explain why you can't get from (∃x)(∃y)Lxy to (∃x)Lxx by using ∃E and ∃I as you can get from (Vx)(Vy)Lxy to (Vx)Lxx by using VE and VI.

c) (Vx)(Vy)Lxy d) (∃x)(∃y)Lxy e) (∃x)(Vy)Lxy e-1) (Vy)(∃x)Lxy
(Vy)(Vx)Lxy (∃y)(∃x)Lxy (Vy)(∃x)Lxy (∃x)(Vy)Lxy

Note that the converse argument, (e-1) is invalid. Prove this by providing a counterexample.

f) (Vx)Px & (Vx)Qx g) (∃x)Px & (∃x)Qx h) (Vx)Px v (Vx)Qx
(Vx)(Vy)(Px & Qy) (∃x)(∃y)(Px & Qy) (Vx)(Vy)(Px v Qy)

i) (∃x)Px v (x)Qx j) (∃x)(∃y)(Px v Qy) k) (Vx)(Vy)(Lxy ⊃ ~Lxy)
(∃x)(∃y)(Px v Qy) (∃x)Px v (∃x)Qx (Vy)~Lxx

l) (Vx)(Vy)(Px ⊃ Qy) m) (∃x)(∃y)(Px ⊃ Qy) n) (∃x)(Vy)(Px ⊃ Qy)
(∃x)Px ⊃ (Vx)Qx (Vx)Px ⊃ (∃x)Qx (Vx)Px ⊃ (Vx)Qx

o) (Vx)(∃y)(Px ⊃ Qy) p) (Vx)Px ⊃ (Vx)Qx q) (Vx)(Vy)(Px v Qy)
(∃x)Px ⊃ (∃x)Qx (∃x)(Vy)(Px ⊃ Qy) (Vx)Px v (Vx)Qy

r) (∃x)(Vy)Jxy
(∃y)(∃z)(Hzy & ~Py)
(Vz)(Vw)[(Jzw & ~Pw) ⊃ Gz]
(∃z)Gz