. 60
( 107 .)


discourse is slithy. Let b be one of these slithy things. By the second premise, we know
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

∀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


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
Russell™s Paradox in Chapter 15, and G¨del™s Theorem in the ¬nal section of
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


. 60
( 107 .)