<<

. 61
( 107 .)



>>

all and only the men of the town who did not shave themselves. We might
formalize this in fol as follows:

∃z ∃x [BarberOf(x, z) § ∀y (ManOf(y, z) ’ (Shave(x, y) ” ¬Shave(y, y))]

Now there does not on the face of it seem to be anything logically inco-
herent about the existence of such a town. But here is a proof that there can
be no such town.

Purported proof: Suppose there is such a town. Let™s call it Hoosier-
ville, and let™s call Hoosierville™s barber Fred. By assumption, Fred
shaves all and only those men of Hoosierville who do not shave them-
selves.
Now either Fred shaves himself, or he doesn™t. But either possibility
leads to a contradiction, as we now show. As to the ¬rst possibility, if



Section 12.4
334 / Methods of Proof for Quantifiers


Fred does shave himself, then he doesn™t, since by the assumption he
does not shave any man of the town who shaves himself. So now as-
sume the other possibility, namely, that Fred doesn™t shave himself.
But then since Fred shaves every man of the town who doesn™t shave
himself, he must shave himself. We have shown that a contradiction
follows from each possibility. By proof by cases, then, we have estab-
lished a contradiction from our original assumption. This contradic-
tion shows that our assumption is wrong, so there is no such town.
The con¬‚ict between our intuition that there could be such a town on the
one hand, and the proof that there can be none on the other hand, has caused
this result to be known as the Barber Paradox.
Barber Paradox
Actually, though, there is a subtle sexist ¬‚aw in this proof. Did you spot
it? It came in our use of the name “Fred.” By naming the barber Fred, we
implicitly assumed the barber was a man, an assumption that was needed to
complete the proof. After all, it is only about men that we know the barber
shaves those who do not shave themselves. Nothing is said about women,
children, or other inhabitants of the town.
The proof, though ¬‚awed, is not worthless. What it really shows is that if
there is a town with such a barber, then that barber is not a man of the town.
The barber might be a woman, or maybe a man from some other town. In other
words, the proof works ¬ne to show that the following is a ¬rst-order validity:


¬∃z ∃x [ManOf(x, z) § ∀y (ManOf(y, z) ’ (Shave(x, y) ” ¬Shave(y, y))]
There are many variations on this example that you can use to amaze,
amuse, or annoy your family with when you go home for the holidays. We
give a couple examples in the exercises (see Exercises 12.13 and 12.28).

Exercises

These exercises each contain a purported proof. If it is correct, say so. If it is incorrect, explain what
goes wrong using the notions presented above.

12.11

There is a number greater than every other number.
Purported proof: Let n be an arbitrary number. Then n is less than some other
number, n + 1 for example. Let m be any such number. Thus n ¤ m. But n is an
arbitrary number, so every number is less or equal m. Hence there is a number that
is greater than every other number.




Chapter 12
Proofs involving mixed quantifiers / 335



12.12 ∀x [Person(x) ’ ∃y ∀z [Person(z) ’ GivesTo(x, y, z)]]

∀x [Person(x) ’ ∀z (Person(z) ’ ∃y GivesTo(x, y, z))]
Purported proof: Let us assume the premise and prove the conclusion. Let b be an
arbitrary person in the domain of discourse. We need to prove

∀z (Person(z) ’ ∃y GivesTo(b, y, z))

Let c be an arbitrary person in the domain of discourse. We need to prove

∃y GivesTo(b, y, c)

But this follows directly from our premise, since there is something that b gives to
everyone.

12.13 Harrison admires only great actors who do not admire
 themselves
Harrison admires all great actors who do not admire
themselves.
Harrison is not a great actor.
Purported proof: Toward a proof by contradiction, suppose that Harrison is a great
actor. Either Harrison admires himself or he doesn™t. We will show that either case
leads to a contradiction, so that our assumption that Harrison is a great actor must be
wrong. First, assume that Harrison does admire himself. By the ¬rst premise and our
assumption that Harrison is a great actor, Harrison does not admire himself, which
is a contradiction. For the other case, assume that Harrison does not admire himself.
But then by the second premise and our assumption that Harrison is a great actor,
Harrison does admire himself after all. Thus, under either alternative, we have our
contradiction.

12.14

There is at most one object.
Purported proof: Toward a proof by contradiction, suppose that there is more than
one object in the domain of discourse. Let c be any one of these objects. Then there is
some other object d, so that d = c. But since c was arbitrary, ∀x (d = x). But then, by
universal instantiation, d = d. But d = d, so we have our contradiction. Hence there
can be at most one object in the domain of discourse.




Section 12.4
336 / Methods of Proof for Quantifiers


12.15 ∀x ∀y ∀z [(Outgrabe(x, y) § Outgrabe(y, z)) ’ Outgrabe(x, z)]
 ∀x ∀y [Outgrabe(x, y) ’ Outgrabe(y, x)]
∃x ∃y Outgrabe(x, y)
∀x Outgrabe(x, x)
Purported proof: Applying existential instantiation to the third premise, let b and
c be arbitrary objects in the domain of discourse such that b outgrabes c. By the
second premise, we also know that c outgrabes b. Applying the ¬rst premise (with
x = z = b and y = c we see that b outgrabes itself. But b was arbitrary. Thus by
universal generalization, ∀x Outgrabe(x, x).

The next three exercises contain arguments from a single set of premises. In each case decide whether
or not the argument is valid. If it is, give an informal proof. If it isn™t, use Tarski™s World to construct
a counterexample.

12.16 ∀x ∀y [LeftOf(x, y) ’ Larger(x, y)]
‚| ∀x [Cube(x) ’ Small(x)]
∀x [Tet(x) ’ Large(x)]
∀x ∀y [(Small(x) § Small(y)) ’ ¬Larger(x, y)]
¬∃x ∃y [Cube(x) § Cube(y) § RightOf(x, y)]

12.17 ∀x ∀y [LeftOf(x, y) ’ Larger(x, y)]
‚| ∀x [Cube(x) ’ Small(x)]
∀x [Tet(x) ’ Large(x)]
∀x ∀y [(Small(x) § Small(y)) ’ ¬Larger(x, y)]
∀z [Medium(z) ’ Tet(z)]

12.18 ∀x ∀y [LeftOf(x, y) ’ Larger(x, y)]
‚| ∀x [Cube(x) ’ Small(x)]
∀x [Tet(x) ’ Large(x)]
∀x ∀y [(Small(x) § Small(y)) ’ ¬Larger(x, y)]
∀z ∀w [(Tet(z) § Cube(w)) ’ LeftOf(z, w)]

The next three exercises contain arguments from a single set of premises. In each, decide whether the
argument is valid. If it is, give an informal proof. If it isn™t valid, use Tarski™s World to build a coun-
terexample.




Chapter 12
Proofs involving mixed quantifiers / 337



12.19 12.20
∀x [Cube(x) ’ ∃y LeftOf(x, y)] ∀x [Cube(x) ’ ∃y LeftOf(x, y)]
‚| ‚|
¬∃x ∃z [Cube(x) § Cube(z) § LeftOf(x, z)] ¬∃x ∃z [Cube(x) § Cube(z) § LeftOf(x, z)]
∃x ∃y [Cube(x) § Cube(y) § x = y] ∃x ∃y [Cube(x) § Cube(y) § x = y]
∃x ∃y ∃z [BackOf(y, z) § LeftOf(x, z)] ∃x ¬Cube(x)

12.21 ∀x [Cube(x) ’ ∃y LeftOf(x, y)]
‚| ¬∃x ∃z [Cube(x) § Cube(z) § LeftOf(x, z)]
∃x ∃y [Cube(x) § Cube(y) § x = y]
∃x ∃y (x = y § ¬Cube(x) § ¬Cube(y))

12.22 Is the following logically true?
‚|
∃x [Cube(x) ’ ∀y Cube(y)]

If so, given an informal proof. If not, build a world where it is false.

12.23 Translate the following argument into fol and determine whether or not the conclusion follows
 from the premises. If it does, give a proof.

Every child is either right-handed or intelligent.
No intelligent child eats liver.
There is a child who eats liver and onions.
There is a right-handed child who eats onions.

In the next three exercises, we work in the ¬rst-order language of arithmetic with the added predicates
Even(x), Prime(x), and DivisibleBy(x, y), where these have the obvious meanings (the last means that the
natural number y divides the number x without remainder.) Prove the result stated in the exercise. In
some cases, you have already done all the hard work in earlier problems.

12.25 ∀x [Even(x) ” Even(x2 )]
12.24 ∃y [Prime(y) § Even(y)]
 

12.26 ∀x [DivisibleBy(x2 , 3) ’ DivisibleBy(x2 , 9)]


12.27 Are sentences (1) and (2) in Exercise 9.19 on page 250 logically equivalent? If so, give a proof.
 If not, explain why not.

12.28 Show that it would be impossible to construct a reference book that lists all and only those
 reference books that do not list themselves.




Section 12.4
338 / Methods of Proof for Quantifiers


12.29 Call a natural number a near prime if its prime factorization contains at most two distinct
 primes. The ¬rst number which is not a near prime is 2 — 3 — 5 = 30. Prove

∀x ∃y [y > x § ¬NearPrime(y)]

You may appeal to our earlier result that there is no largest prime.



Section 12.5
Axiomatizing shape
Let™s return to the project of giving axioms for the shape properties in Tarski™s
World. In Section 10.5, we gave axioms that described basic facts about the
three shapes, but we stopped short of giving axioms for the binary relation
SameShape. The reason we stopped was that the needed axioms require mul-
tiple quanti¬ers, which we had not covered at the time.
How do we choose which sentences to take as axioms? The main consid-
eration is correctness: the axioms must be true in all relevant circumstances,
correctness of axioms
either in virtue of the meanings of the predicates involved, or because we have
restricted our attention to a speci¬c type of circumstance.
The two possibilities are re¬‚ected in our ¬rst four axioms about shape,
which we repeat here for ease of reference:
Basic Shape Axioms:

1. ¬∃x (Cube(x) § Tet(x))

2. ¬∃x (Tet(x) § Dodec(x))

3. ¬∃x (Dodec(x) § Cube(x))

4. ∀x (Tet(x) ∨ Dodec(x) ∨ Cube(x))
The ¬rst three of these are correct in virtue of the meanings of the predicates;
the fourth expresses a truth about all worlds of the sort that can be built in
Tarski™s World.
Of second importance, just behind correctness, is completeness. We say
completeness of axioms
that a set of axioms is complete if, whenever an argument is intuitively
valid (given the meanings of the predicates and the intended range of cir-
cumstances), its conclusion is a ¬rst-order consequence of its premises taken
together with the axioms in question.
The notion of completeness, like that of correctness, is not precise, depend-
ing as it does on the vague notions of meaning and “intended circumstances.”



Chapter 12
Axiomatizing shape / 339



For example, in axiomatizing the basic shape predicates of Tarski™s World,
there is an issue about what kinds of worlds are included among the intended
circumstances. Do we admit only those having at most twelve objects, or do
we also consider those with more objects, so long as they have one of the
three shapes? If we make this latter assumption, then the basic shape axioms
are complete. This is not totally obvious, but we will justify the claim in

<<

. 61
( 107 .)



>>