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