<<

. 66
( 107 .)



>>

’ Larger(x, y))) ’ Larger(x, y)))
∀x (Dodec(x) ’ ∀y (Tet(y) ’ Larger(x, y))) ∀x (Dodec(x) ’ ∀y (Tet(y)
∃x Dodec(x) ’ Larger(x, y)))
∃x Dodec(x)
∀x (Cube(x) ’ ∀y (Tet(y) ’ Larger(x, y)))
∀x ∀y ∀z ((Larger(x, y) § Larger(y, z))
(Compare this with Exercise 13.9. The ’ Larger(x, z))
crucial di¬erence is the presence of the
∀x (Cube(x) ’ ∀y (Tet(y)
third premise, not the di¬erence in form
’ Larger(x, y)))
of the ¬rst two premises.)




Chapter 13
Some review exercises / 361



Section 13.4
Soundness and completeness
In Chapter 8 we raised the question of whether the deductive system FT was
sound and complete with respect to tautological consequence. The same issues
arise with the full system F , which contains the rules for the quanti¬ers and
identity, in addition to the rules for the truth-functional connectives. Here,
the target consequence relation is the notion of ¬rst-order consequence, rather
than tautological consequence.
The soundness question asks whether anything we can prove in F from soundness of F
premises P1 , . . . , Pn is indeed a ¬rst-order consequence of the premises. The
completeness question asks the converse: whether every ¬rst-order consequence completeness of F
of a set of sentences can be proven from that set using the rules of F .
It turns out that both of these questions can be answered in the a¬rma-
tive. Before actually proving this, however, we need to add more precision
to the notion of ¬rst-order consequence, and this presupposes tools from set
theory that we will introduce in Chapters 15 and 16. We state and prove
the soundness theorem for ¬rst-order logic in Chapter 18. The completeness
theorem for ¬rst-order logic is the main topic of Chapter 19.


Section 13.5
Some review exercises
In this section we present more problems to help you solidify your understand-
ing of the methods of reasoning involving quanti¬ers. We also present some
more interesting problems from a theoretical point of view.

Exercises

Some of the following arguments are valid, some are not. For each, either use Fitch to give a formal
proof or use Tarski™s World to construct a counterexample. In giving proofs, feel free to use Taut Con
if it helps.

13.40 13.41
∃x Cube(x) § Small(d) ∀x (Cube(x) ∨ Small(x))
‚ ‚
∃x (Cube(x) § Small(d)) ∀x Cube(x) ∨ ∀x Small(x)




Section 13.5
362 / Formal Proofs and Quantifiers


13.42 ∀x Cube(x) ∨ ∀x Small(x)

∀x (Cube(x) ∨ Small(x))

Each of the following is a valid argument of a type discussed in Section 10.3. Use Fitch to give a proof
of its validity. You may use Taut Con freely in these proofs.

13.43 13.44
¬∀x Cube(x) ¬∃x Cube(x)
‚ ‚
∃x ¬Cube(x) ∀x ¬Cube(x)

13.45 13.46 (Change of bound variables)
∀x ¬Cube(x)
‚ ‚ ∀x Cube(x)
¬∃x Cube(x)
∀y Cube(y)

13.47 (Change of bound variables) 13.48 (Null quanti¬cation)
‚ ‚
∃x Tet(x)
∃y Tet(y) Cube(b) ” ∀x Cube(b)

13.49 13.50
∃x P(x) ∃x (P(x) § ∀y (P(y) ’ y = x))
‚ ‚
∀x ∀y ((P(x) § P(y)) ’ x = y)
∀x ∀y ((P(x) § P(y)) ’ x = y)
∃x (P(x) § ∀y (P(y) ’ y = x))

13.51 13.52
‚ ‚
∃x (P(x) ’ ∀y P(y)) ¬∃x ∀y [E(x, y) ” ¬E(y, y)]
This result might be called Russell™s
[Hint: Review your answer to Exer-
Theorem. It is connected with the fa-
cise 12.22 where you should have given
mous result known as Russell™s Paradox,
an informal proof of something of this
which is discussed in Section 15.8. In
form.]
fact, it was upon discovering this that
Russell invented the Barber Paradox, to
explain his result to a general public.

13.53 Is ∃x ∃y ¬LeftOf(x, y) a ¬rst-order consequence of ∃x ¬LeftOf(x, x)? If so, give a formal proof.
‚| If not, give a reinterpretation of LeftOf and an example where the premise is true and the
conclusion is false.




Chapter 13
Some review exercises / 363



The next exercises are intended to help you review the di¬erence between ¬rst-order satis¬ability and
true logical possibility. All involve the four sentences in the ¬le Padoa™s Sentences. Open that ¬le now.

13.54 Any three of the sentences in Padoa™s Sentences form a satis¬able set. There are four sets of three
‚ sentences, so to show this, build four worlds, World 13.54.123, World 13.54.124, World 13.54.134,
and World 13.54.234,where the four sets are true. (Thus, for example, sentences 1, 2 and 4 should
be true in World 13.54.124.)

13.55 Give an informal proof that the four sentences in Padoa™s Sentences taken together are incon-
 sistent.

13.56 Is the set of sentences in Padoa™s Sentences ¬rst-order satis¬able, that is, satis¬able with some
 reinterpretation of the predicates other than identity? [Hint: Imagine a world where one of the
blocks is a sphere.]

13.57 Reinterpret the predicates Tet and Dodec in such a way that sentence 3 of Padoa™s Sentences
 comes out true in World 13.57.124. Since this is the only sentence that uses these predicates,
it follows that all four sentences would, with this reinterpretation, be true in this world. (This
shows that the set is ¬rst-order satis¬able.)

13.58 (Logical truth versus non-logical truth in all worlds) A distinction Tarski™s World helps us to
‚| understand is the di¬erence between sentences that are logically true and sentences that are,
for reasons that have nothing to do with logic, true in all worlds. The notion of logical truth
has to do with a sentence being true simply in virtue of the meaning of the sentence, and so
no matter how the world is. However, some sentences are true in all worlds, not because of
the meaning of the sentence or its parts, but because of, say, laws governing the world. We
can think of the constraints imposed by the innards of Tarski™s World as analogues of physical
laws governing how the world can be. For example, the sentence which asserts that there are at
most 12 objects happens to hold in all the worlds that we can construct with Tarski™s World.
However, it is not a logical truth.
Open Post™s Sentences. Classify each sentence in one of the following ways: (A) a logical
truth, (B) true in all worlds that can be depicted using Tarski™s World, but not a logical truth,
or (C) falsi¬able in some world that can be depicted by Tarski™s World. For each sentence of
type (C), build a world in which it is false, and save it as World 13.58.x, where x is the number
of the sentence. For each sentence of type (B), use a pencil and paper to depict a world in
which it is false. (In doing this exercise, assume that Medium simply means neither small nor
large, which seems plausible. However, it is not plausible to assume that Cube means neither a
dodecahedron nor tetrahedron, so you should not assume anything like this.)




Section 13.5
Chapter 14

More about Quanti¬cation

Many English sentences take the form

QAB

where Q is a determiner expression like every, some, the, more than half the,
at least three, no, many, Max™s, etc.; A is a common noun phrase like cube,
student of logic, thing, etc.; and B is a verb phrase like sits in the corner or
is small.
Such sentences are used to express quantitative relationships between the
set of objects satisfying the common noun phrase and the set of objects satis-
fying the verb phrase. Here are some examples, with the determiner in bold:

Every cube is small.
Some cube is small.
More than half the cubes are small.
At least three cubes are small.
No cube is small.
Many cubes are small.
Max™s cube is small.

These sentences say of the set A of cubes in the domain of discourse and
the set B of small things in the domain of discourse that

every A is a B,
some A is a B,
more than half the A™s are B™s,
at least three A™s are B™s,
no A is a B,
many A™s are B™s, and
Max™s A is a B.

Each of these can be thought of as expressing a kind of binary relation between
A and B.
Linguistically, these words and phrases are known as determiners. The
determiners and
quanti¬ers relation expressed by a determiner is usually, though not always, a quantita-
tive relation between A and B. Sometimes this quantitative relation can be
captured using the fol quanti¬ers ∀ and ∃, though sometimes it can™t. For



364
More about Quantification / 365



example, to express more than half the A™s are B™s, it turns out that we need
to supplement fol to include new expressions that behave something like ∀
and ∃. When we add such expressions to the formal language, we call them
generalized quanti¬ers, since they extend the kinds of quanti¬cation we can generalized quanti¬ers
express in the language.
In this chapter, we will look at the logic of some English determiners
beyond some and all. We will consider not only determiners that can be ex-
pressed using the usual quanti¬ers of fol, but also determiners whose mean-
ings can only be captured by adding new quanti¬ers to fol.
In English, there are ways of expressing quanti¬cation other than deter-
miners. For example, the sentences
Max always eats pizza.
Max usually eats pizza.
Max often eats pizza.
Max seldom eats pizza.
Max sometimes eats pizza.
Max never eats pizza.
each express a quantitative relation between the set of times when Max eats
and the set of times when he eats pizza. But in these sentences it is the adverb
that is expressing quanti¬cation, not a determiner. While we are going to
discuss the logic only of determiners, much of what we say can be extended to adverbial quanti¬cation
other forms of quanti¬cation, including this kind of adverbial quanti¬cation.
In a sentence of the form Q A B, di¬erent determiners express very di¬erent
relations between A and B and so have very di¬erent logical properties. A valid
argument typically becomes invalid if we change any of the determiners. For
instance, while

No cube is small
d is a cube
d is not small

is a valid argument, it would become invalid if we replaced no by any of the
other determiners listed above. On the other hand, the valid argument

Many cubes are small
Every small block is left of d
Many cubes are left of d

remains valid if many is replaced by any of the above determiners other than
no. These are clearly logical facts, things we™d like to understand at a more



Chapter 14
366 / More about Quantification


theoretical level. For example, we™ll soon see that the determiners that can
replace Many in the second argument and still yield a valid argument are the
monotone increasing determiners.
There are two rather di¬erent approaches to studying quanti¬cation. One
approaches to
quanti¬cation approach studies determiners that can be expressed using the existing re-
sources of fol. In the ¬rst three sections, we look at several important English
determiners that can be de¬ned in terms of ∀, ∃, =, and the truth-functional

<<

. 66
( 107 .)



>>