ńņš. 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 briefly 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 |