that b is a tove. By the ¬rst premise, we see that b is mimsy. Thus, b is both slithy

and mimsy. Hence, something is both slithy and mimsy.

Section 12.3

328 / Methods of Proof for Quantifiers

12.2 ∀x [Brillig(x) ’ (Mimsy(x) § Slithy(x))]

∀y [(Slithy(y) ∨ Mimsy(y)) ’ Tove(y)]

∀x [Tove(x) ’ (Outgrabe(x, b) § Brillig(x))]

∀z [Brillig(z) ” Mimsy(z)]

Purported proof: In order to prove the conclusion, it su¬ces to prove the logically

equivalent sentence obtained by conjoining the following two sentences:

(1) ∀x [Brillig(x) ’ Mimsy(x)]

(2) ∀x [Mimsy(x) ’ Brillig(x)]

We prove these by the method of general conditional proof, in turn. To prove (1), let

b be anything that is brillig. Then by the ¬rst premise it is both mimsy and slithy.

Hence it is mimsy, as desired. Thus we have established (1).

To prove (2), let b be anything that is mimsy. By the second premise, b is also tove.

But then by the ¬nal premise, b is brillig, as desired. This concludes the proof.

12.3 ∀x [(Brillig(x) § Tove(x)) ’ Mimsy(x)]

∀y [(Tove(y) ∨ Mimsy(y)) ’ Slithy(y)]

∃x Brillig(x) § ∃x Tove(x)

∃z Slithy(z)

Purported proof: By the third premise, we know that there are brillig toves. Let b

be one of them. By the ¬rst premise, we know that b is mimsy. By the second premise,

we know that b is slithy. Hence, there is something that is slithy.

The following exercises each contains an argument; some are valid, some not. If the argument is valid,

give an informal proof. If it is not valid, use Tarski™s World to construct a counterexample.

12.4 12.5

∀y [Cube(y) ∨ Dodec(y)] ∀y [Cube(y) ∨ Dodec(y)]

‚| ‚|

∀x [Cube(x) ’ Large(x)] ∀x [Cube(x) ’ Large(x)]

∃x ¬Large(x) ∃x ¬Large(x)

∃x Dodec(x) ∃x [Dodec(x) § Small(x)]

12.6 12.7

∀x [Cube(x) ∨ Dodec(x)] ∀x [Cube(x) ∨ Dodec(x)]

‚| ‚|

∀x [¬Small(x) ’ Tet(x)] ∀x [Cube(x) ’ (Large(x) § LeftOf(c, x))]

∀x [¬Small(x) ’ Tet(x)]

¬∃x Small(x)

∃z Dodec(z)

Chapter 12

Proofs involving mixed quantifiers / 329

12.8 ∀x [Cube(x) ∨ (Tet(x) § Small(x))]

‚| ∃x [Large(x) § BackOf(x, c)]

∃x [FrontOf(c, x) § Cube(x)]

12.9 ∀x [(Cube(x) § Large(x)) ∨ (Tet(x) § Small(x))]

‚| ∀x [Tet(x) ’ BackOf(x, c)]

∀x [Small(x) ’ BackOf(x, c)]

12.10 ∀x [Cube(x) ∨ (Tet(x) § Small(x))]

‚| ∃x [Large(x) § BackOf(x, c)]

∀x [Small(x) ’ ¬BackOf(x, c)]

Section 12.4

Proofs involving mixed quanti¬ers

There are no new methods of proof that apply speci¬cally to sentences with

mixed quanti¬ers, but the introduction of mixed quanti¬ers forces us to be

more explicit about some subtleties having to do with the interaction of meth-

ods that introduce new names into a proof: existential instantiation, general

conditional proof, and universal generalization. It turns out that problems can

arise from the interaction of these methods of proof.

Let us begin by illustrating the problem. Consider the following argument:

∃y [Girl(y) § ∀x (Boy(x) ’ Likes(x, y))]

∀x [Boy(x) ’ ∃y (Girl(y) § Likes(x, y))]

If the domain of discourse were the set of children in a kindergarten class, the

conclusion would say every boy in the class likes some girl or other, while the

premise would say that there is some girl who is liked by every boy. Since this

is valid, let™s start by giving a proof of it.

Proof: Assume the premise. Thus, at least one girl is liked by every

boy. Let c be one of these popular girls. To prove the conclusion we

will use general conditional proof. Assume that d is any boy in the

class. We want to prove that d likes some girl. But every boy likes

c, so d likes c. Thus d likes some girl, by existential generalization.

Since d was an arbitrarily chosen boy, the conclusion follows.

Section 12.4

330 / Methods of Proof for Quantifiers

This is a perfectly legitimate proof. The problem we want to illustrate,

however, is the super¬cial similarity between the above proof and the following

incorrect “proof” of the argument that reverses the order of the premise and

conclusion:

∀x [Boy(x) ’ ∃y (Girl(y) § Likes(x, y))]

∃y [Girl(y) § ∀x (Boy(x) ’ Likes(x, y))]

This is obviously invalid. The fact that every boy likes some girl or other

doesn™t imply that some girl is liked by every boy. So we can™t really prove

that the conclusion follows from the premise. But the following pseudo-proof

might appear to do just that.

Pseudo-proof: Assume the premise, that is, that every boy likes

some girl or other. Let e be any boy in the domain. By our premise,

e likes some girl. Let us introduce the new name “f” for some girl

that e likes. Since the boy e was chosen arbitrarily, we conclude

that every boy likes f , by general conditional proof. But then, by

existential generalization, we have the desired result, namely, that

some girl is liked by every boy.

This reasoning is fallacious. Seeing why it is fallacious is extremely impor-

tant, if we are to avoid missteps in reasoning. The problem centers on our

conclusion that every boy likes f . Recall how the name “f ” came into the

hidden dependencies

proof. We knew that e, being one of the boys, liked some girl, and we chose

one of those girls and dubbed her with the name “f ”. This choice of a girl

depends crucially on which boy e we are talking about. If e was Matt or Alex,

we could have picked Zoe and dubbed her f . But if e was Eric, we couldn™t

pick Zoe. Eric likes one of the girls, but certainly not Zoe.

The problem is this. Recall that in order to conclude a universal claim

based on reasoning about a single individual, it is imperative that we not

appeal to anything speci¬c about that individual. But after we give the name

“f ” to one of the girls that e likes, any conclusion we come to about e and

f may well violate this imperative. We can™t be positive that it would apply

equally to all the boys.

Stepping back from this particular example, the upshot is this. Suppose

we assume P(c), where c is a new name, and prove Q(c). We cannot conclude

∀x [P(x) ’ Q(x)] if Q(c) mentions a speci¬c individual whose choice depended

on the individual denoted by c. In practice, the best way to insure that no

such individual is speci¬cally mentioned is to insist that Q(c) not contain any

name that was introduced by existential instantiation under the assumption

that P(c).

Chapter 12

Proofs involving mixed quantifiers / 331

Figure 12.1: A circumstance in which ∀x [Boy(x) ’ ∃y (Girl(y) § Likes(x, y))].

A similar restriction must be placed on the use of universal generalization.

Recall that universal generalization involves the introduction of a new con-

stant, say c, standing for an arbitrary member c of the domain of discourse.

We said that if we could prove a sentence S(c), we could then conclude ∀x S(x). a new restriction

However, we must now add the restriction that S(c) not contain any constant

introduced by existential instantiation after the introduction of the constant

c. This restriction prevents invalid proofs like the following.

Pseudo-proof: Assume ∀x ∃y Adjoins(x, y). We will show that, ig-

noring the above restriction, we can “prove” ∃y ∀x Adjoins(x, y). We

begin by taking c as a name for an arbitrary member of the do-

main. By universal instantiation, we get ∃y Adjoins(c, y). Let d be

such that Adjoins(c, d). Since c stands for an arbitrary object, we

have ∀x Adjoins(x, d). Hence, by existential generalization, we get

∃y ∀x Adjoins(x, y).

Can you spot the fallacious step in this proof ? The problem is that we

generalized from Adjoins(c, d) to ∀x Adjoins(x, d). But the constant d was in-

troduced by existential instantiation (though we did not say so explicitly) after

the constant c was introduced. Hence, the choice of the object d depends on

which object c we are talking about. The subsequent universal generalization

is just what our restriction rules out.

Let us now give a summary statement of the main methods of proof in-

volving the ¬rst-order quanti¬ers.

Section 12.4

332 / Methods of Proof for Quantifiers

Remember

Let S(x), P(x), and Q(x) be w¬s.

1. Existential Instantiation: If you have proven ∃x S(x) then you may

choose a new constant symbol c to stand for any object satisfying S(x)

and so you may assume S(c).

2. General Conditional Proof: If you want to prove ∀x [P(x) ’ Q(x)] then

you may choose a new constant symbol c, assume P(c), and prove

Q(c), making sure that Q does not contain any names introduced by

existential instantiation after the assumption of P(c).

3. Universal Generalization: If you want to prove ∀x S(x) then you may

choose a new constant symbol c and prove S(c), making sure that S(c)

does not contain any names introduced by existential instantiation

after the introduction of c.

Two famous proofs

There are, of course, endless applications of the methods we have discussed

above. We illustrate the correct uses of these methods with two famous exam-

ples. One of the examples goes back to the ancient Greeks. The other, about a

hundred years old, is known as the Barber Paradox and is due to the English

logician Bertrand Russell. The Barber Paradox may seem rather frivolous, but

the result is actually closely connected to Russell™s Paradox, a result that had

a very signi¬cant impact on the history of mathematics and logic. It is also

connected with the famous result known as G¨del™s Theorem. (We™ll discuss

o

Russell™s Paradox in Chapter 15, and G¨del™s Theorem in the ¬nal section of

o

the book.)

Euclid™s Theorem

Recall that a prime number is a whole number greater than 1 that is not

divisible by any whole numbers other than 1 and itself. The ¬rst ten primes

are 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29. The prime numbers become increasingly

scarce as the numbers get larger. The question arises as to whether there is

a largest one, or whether the primes go on forever. Euclid™s Theorem is the

Euclid™s Theorem

statement that they go on forever, that there is no largest prime. In fol, we

might put it this way:

∀x ∃y [y ≥ x § Prime(y)]

Chapter 12

Proofs involving mixed quantifiers / 333

Here the intended domain of discourse is the natural numbers, of course.

Proof: We see that this sentence is a mixed quanti¬er sentence of

just the sort we have been examining. To prove it, we let n be an

arbitrary natural number and try to prove that there exists a prime

number at least as large as n. To prove this, let k be the product

of all the prime numbers less than n. Thus each prime less than n

divides k without remainder. So now let m = k + 1. Each prime

less than n divides m with remainder 1. But we know that m can

be factored into primes. Let p be one of these primes. Clearly, by

the earlier observation, p must be greater than or equal to n. Hence,

by existential generalization, we see that there does indeed exist a

prime number greater than or equal to n. But n was arbitrary, so we

have established our result.

Notice the order of the last two steps. Had we violated the new condi-

tion on the application of general conditional proof to conclude that p is a

prime number greater than or equal to every natural number, we would have

obtained a patently false result.

Here, by the way, is a closely related conjecture, called the Twin Prime Twin Prime Conjecture

Conjecture. No one knows whether it is true or not.

∀x ∃y [y > x § Prime(y) § Prime(y + 2)]

The Barber Paradox

There was once a small town in Indiana where there was a barber who shaved