НАНОБУКВА

<< Предыдущая

стр. 67 (из 107 стр.) ОГЛАВЛЕНИЕ

Следующая >>

connectives, and then analyze their logical properties by means of these defini-
tions. The second approach is to strengthen fol by allowing a wider range of
quantifiers, capturing kinds of quantification not already expressible in fol.
In the final three sections, we look briefly at this second approach and its
resulting logic.


Section 14.1
Numerical quantification
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 quantification 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 different 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 different. 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 different:

∃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 five takes five ∃’s
and 10 (= 4 + 3 + 2 + 1) inequalities, and so forth.
Turning to the second kind of numerical quantification, 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) quantifier 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 official way of expressing at most two.
Notice that while it took two existential quantifiers to express there are
at least two cubes, it took three universal quantifiers to say that there are at
most two cubes. More generally, to translate the determiner at least n into
fol, we need n existential quantifiers, while to translate at most n we need
n + 1 universal quantifiers.
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 five quantifiers:

∃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 different 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 quantifiers and one universal quantifier. 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 quantifiers followed by a single
universal quantifier. More generally, to say that there are exactly n objects
satisfying some condition requires n + 1 quantifiers, 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 confirm
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 different from the fifth 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 quantification, 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 official
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 wff 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-
tifier; wffs in which it occurs are just abbreviations for longer wffs involving
the old quantifiers.
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 quantification.

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 (из 107 стр.) ОГЛАВЛЕНИЕ

Следующая >>

© Copyright | nanobukva.ru

Design by Reality Software