ńņš. 67 |

tions. The second approach is to strengthen fol by allowing a wider range of

quantiļ¬ers, capturing kinds of quantiļ¬cation not already expressible in fol.

In the ļ¬nal three sections, we look brieļ¬‚y at this second approach and its

resulting logic.

Section 14.1

Numerical quantiļ¬cation

We have already seen that many complex noun phrases can be expressed in

terms of ā (which really means āeverythingā, not just āeveryā) and ā (which

means āsomething,ā not āsomeā). For example, Every cube left of b is small

can be paraphrased as Everything that is a cube and left of b is small, a

sentence that can easily be translated into fol using ā, ā§ and ā’. Similarly,

No cube is small can be paraphrased as Everything is such that if it is a cube

then it is not small, which can again be easily translated into fol.

Other important examples of quantiļ¬cation that can be indirectly ex-

pressed in fol are numerical claims. By a ānumerical claimā we mean a one

numerical claims

that explicitly uses the numbers 1, 2, 3, . . . to say something about the rela-

tion between the Aā™s and the Bā™s. Here are three diļ¬erent kinds of numerical

claims:

At least two books arrived this week.

At most two books are missing from the shelf.

Exactly two books are on the table.

First-order languages do not in general allow us to talk directly about

numbers, only about elements of our domain of discourse. The blocks lan-

guage, for example, only talks about blocks, not about numbers. Still, it is

possible to express these three kinds of numerical claims in fol.

Recall that in fol, distinct names do not necessarily refer to distinct

objects. Similarly, distinct variables need not vary over distinct objects. For

example, both of the following sentences can be made true in a world with

Chapter 14

Numerical quantification / 367

one object:

Cube(a) ā§ Small(a) ā§ Cube(b)

āx āy [Cube(x) ā§ Small(x) ā§ Cube(y)]

In order to say that there are at least two cubes, you must ļ¬nd a way to at least two

guarantee that they are diļ¬erent. For example, either of the following would

do:

Cube(a) ā§ Small(a) ā§ Cube(b) ā§ Large(b)

āx āy [Cube(x) ā§ Small(x) ā§ Cube(y) ā§ LeftOf(x, y)]

The most direct way, though, is simply to say that they are diļ¬erent:

āx āy [Cube(x) ā§ Cube(y) ā§ x = y]

This sentence asserts that there are at least two cubes. To say that there are

at least three cubes we need to add another ā and some more inequalities:

āx āy āz [Cube(x) ā§ Cube(y) ā§ Cube(z) ā§ x = y ā§ x = z ā§ y = z]

You will see in the You try it section below that all three of these inequalities

are really needed. To say that there are at least four objects takes four āā™s

and six (= 3 + 2 + 1) inequalities; to say there are at least ļ¬ve takes ļ¬ve āā™s

and 10 (= 4 + 3 + 2 + 1) inequalities, and so forth.

Turning to the second kind of numerical quantiļ¬cation, how can we say

that there are at most two cubes? Well, one way to do it is by saying that at most two

there are not at least three cubes:

Ā¬āx āy āz [Cube(x) ā§ Cube(y) ā§ Cube(z) ā§ x = y ā§ x = z ā§ y = z]

Applying some (by now familiar) quantiļ¬er equivalences, starting with De-

Morganā™s Law, gives us the following equivalent sentence:

āx āy āz [(Cube(x) ā§ Cube(y) ā§ Cube(z)) ā’ (x = y āØ x = z āØ y = z)]

We will take this as our oļ¬cial way of expressing at most two.

Notice that while it took two existential quantiļ¬ers to express there are

at least two cubes, it took three universal quantiļ¬ers to say that there are at

most two cubes. More generally, to translate the determiner at least n into

fol, we need n existential quantiļ¬ers, while to translate at most n we need

n + 1 universal quantiļ¬ers.

To express the sentence there are exactly two cubes, we could paraphrase exactly two

Section 14.1

368 / More about Quantification

it as follows: There are at least two cubes and there are at most two cubes.

Translating each conjunct gives us a rather long sentence using ļ¬ve quantiļ¬ers:

āx āy [Cube(x) ā§ Cube(y) ā§ x = y] ā§

āx āy āz [(Cube(x) ā§ Cube(y) ā§ Cube(z)) ā’ (x = y āØ x = z āØ y = z)]

The same claim can be expressed more succinctly, however, as follows:

āx āy [Cube(x) ā§ Cube(y) ā§ x = y ā§ āz (Cube(z) ā’ (z = x āØ z = y))]

If we translate this into English, we see that it says there are two distinct

objects, both cubes, and that any cube is one of these. This is a diļ¬erent way

of saying that there are exactly two cubes. (We ask you to give formal proofs

of their equivalence in Exercises 14.12 and 14.13.) Notice that this sentence

uses two existential quantiļ¬ers and one universal quantiļ¬er. An equivalent

way of saying this is as follows:

āx āy [x = y ā§ āz (Cube(z) ā” (z = x āØ z = y))]

Put in prenex form, this becomes:

āx āy āz [x = y ā§ (Cube(z) ā” (z = x āØ z = y))]

All three expressions consist of two existential quantiļ¬ers followed by a single

universal quantiļ¬er. More generally, to say that there are exactly n objects

satisfying some condition requires n + 1 quantiļ¬ers, n existential followed by

one universal.

You try it

................................................................

1. In this Try It, you will get to examine some of the claims made above in

more detail. Open Whiteheadā™s Sentences.

2. The ļ¬rst sentence says that there are at least two objects and the second

sentence says that there are at most two objects. (Do you see how they

manage to say these things?) Build a model where the ļ¬rst two sentences

are both true.

3. Sentence 3 is the conjunction of the ļ¬rst two. Hence, it asserts, in one

sentence, that there are exactly two objects. Check to see that it is true

in the world you have just built.

Chapter 14

Numerical quantification / 369

4. The fourth sentence is in fact equivalent to the third sentence. It is a

shorter way of saying that there are exactly two objects. Play the game

three times with this sentence, committed to true each time. First play it

in a world with one object, then in a world with two objects, then in a

world with three objects. You will be able to win only in the second world.

5. Sentence 5 appears, at ļ¬rst sight, to assert that there are at least three

objects, so it should be false in a world with two objects. Check to see if

it is indeed false in such a world. Why isnā™t it? Play the game to conļ¬rm

your suspicions.

6. The sixth sentence actually manages to express the claim that there are at

least three objects. Do you see how itā™s diļ¬erent from the ļ¬fth sentence?

Check to see that it is false in the current world, but is true if you add a

third object to the world.

7. The seventh sentence says that there are exactly three objects in the world.

Check to see that it is true in the world with three objects, but false if you

either delete an object or add another object.

8. Sentence 8 asserts that a is a large object, and in fact the only large object.

To see just how the sentence manages to say this, start with a world with

three small objects and name one of them āa.ā Play the game committed

to true to see why the sentence is false. You can quit the game as soon as

you understand why the sentence is false. Now make a large. Again play

the game committed to true and see why you can now win (does it matter

which block Tarski picks?). Finally, make one of the other objects large as

well, and play the game committed to true to see why it is false.

9. Sentence 8 asserted that a was the only large object. How might we say

that there is exactly one large object, without using a name for the ob-

ject? Compare sentence 8 with sentence 9. The latter asserts that there is

something that is the only large object. Check to see that it is true only

in worlds in which there is exactly one large object.

10. If you have understood sentence 9, you should also be able to understand

sentence 10. Construct a world in which sentence 10 is true. Save this

world as World Numerical 1.

11. Sentence 11 says there is exactly one medium dodecahedron, while sentence

12 says there are at least two dodecahedra. There is nothing incompatible

about these claims. Make sentences 11 and 12 true in a single world. Save

the world as World Numerical 2.

Section 14.1

370 / More about Quantification

12. Sentence 13 is another way to assert that there is a unique dodecahedron.

That is, sentence 13 is equivalent to sentence 10. Can you see why? Check

three worlds to see that the two sentences are true in the same worlds,

those in which there is a single dodecahedron.

13. Sentence 14 says that there are exactly two tetrahedra. Check that it is

true in such worlds, but false if there are fewer or more than two.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Congratulations

Numerical quantiļ¬cation, when written out in full in fol, is hard to read

abbreviations for

numerical claims because of all the inequalities, especially when the numbers get to be more

than 3 or 4, so a special notation has become fairly common:

ā—¦ āā„n x P(x) for the fol sentence asserting āThere are at least n objects

satisfying P(x).ā

ā—¦ āā¤n x P(x) for the fol sentence asserting āThere are at most n objects

satisfying P(x).ā

ā—¦ ā!n x P(x) for the fol sentence asserting āThere are exactly n objects

satisfying P(x).ā

It is important to remember that this notation is not part of the oļ¬cial

language of fol, but an abbreviation for a much longer fol expression.

The special case of n = 1 is important enough to warrant special comment.

The assertion that there is exactly one object satisfying some condition P(x)

exactly one

can be expressed in fol as follows:

āx [P(x) ā§ āy (P(y) ā’ y = x)]

as long as y does not occur already in the wļ¬ P(x). According to the con-

ventions we have just established, this should be abbreviated as ā!1x P(x). In

practice, though, this is used so often that it is further shortened to ā!x P(x).

It is read āthere is a unique x such that P (x).ā Again, this is not a new quan-

tiļ¬er; wļ¬s in which it occurs are just abbreviations for longer wļ¬s involving

the old quantiļ¬ers.

We started out with the goal of learning how to express claims of the form

Q A B where Q is a numerical determiner and A is any common noun. But all

we have seen so far is how to express claims of the form there are at least/at

most/exactly n things satisfying P. Having learned how to do this, however,

itā™s easy to express claims of the desired form. For example, to say At least

n cubes are small, we say There are at least n things that are small cubes.

Chapter 14

Numerical quantification / 371

Similarly, to say There are at most n cubes that are small, we say There are

at most n things that are small cubes. Finally, to say There are exactly n cubes

that are small, we say There are exactly n things that are small cubes. These

observations probably seem so obvious that they donā™t require mentioning.

But we will soon see that nothing like this holds for some determiners, and that

the consequences are rather important for the general theory of quantiļ¬cation.

Remember

The notations āā„n , āā¤n , and ā!n are abbreviations for complex fol ex-

pressions meaning āthere are at least/at most/exactly n things such that

. . . .ā

Exercises

14.1 If you skipped the You try it section, go back and do it now. Submit the ļ¬les World Numerical 1

Ć‚ and World Numerical 2.

14.2 Give clear English translations of the following sentences of fol. Which of the following are

logically equivalent and which are not? Explain your answers.

1. ā!x Tove(x) [Remember that the notation ā! is an abbreviation, as explained above.]

2. āx āy [Tove(y) ā’ y = x]

3. āx āy [Tove(y) ā” y = x]

4. āx āy [(Tove(x) ā§ Tove(y)) ā’ x = y]

5. āx āy [(Tove(x) ā§ Tove(y)) ā” x = y]

14.3 (Translating numerical claims) In this exercise we will try our hand at translating English

Ć‚ sentences involving numerical claims.

ā—¦ Using Tarskiā™s World, translate the following English sentences.

1. There are at least two dodecahedra.

2. There are at most two tetrahedra.

3. There are exactly two cubes.

4. There are only three things that are not small.

ńņš. 67 |