ńņš. 66 |

ā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 |