ńņš. 47 |

is true or false in the indicated world. Since Tarskiā™s World does not understand the function

symbols, you will not be able to check your answers. We have ļ¬lled in a few of the entries for

you. Turn in the completed table to your instructor.

Malcevā™s Bolzanoā™s Booleā™s Wittgensteinā™s

1. false

2.

3. false

4.

5. true

6.

7.

8. true

9.

10.

Section 9.7

254 / Introduction to Quantification

Figure 9.1: A family tree, with heights.

9.23 Consider the ļ¬rst-order language with function symbols mother and father, plus names for each

of the people shown in the family tree in Figure 9.1. Here are some atomic wļ¬s, each with a

single free variable x. For each, pick a person for x that satisļ¬es the wļ¬, if you can. If there is

no such person indicated in the family tree, say so.

1. mother(x) = ellen

2. father(x) = jon

3. mother(father(x)) = mary

4. father(mother(x)) = john

5. mother(father(x)) = addie

6. father(mother(father(x))) = john

7. father(father(mother(x))) = archie

8. father(father(jim)) = x

9. father(father(mother(claire))) = x

10. mother(mother(mary)) = mother(x)

9.24 Again using Figure 9.1, ļ¬gure out which of the sentences listed below are true. Assume that

the domain of discourse consists of the people listed in the family tree.

1. āx Taller(x, mother(x))

2. āx Taller(father(x), mother(x))

3. āy Taller(mother(mother(y)), mother(father(y)))

4. āz [z = father(claire) ā’ Taller(father(claire), z)]

5. āx [Taller(x, father(x)) ā’ Taller(x, claire)]

Chapter 9

Alternative notation / 255

9.25 Assume you are working in an extension of the ļ¬rst-order language of arithmetic with the

Ć‚ additional predicates Even(x) and Prime(x). Express the following in this language, explicitly

using the function symbol Ć—, as in z Ć— z, rather than z2 . Note that you do not have a predicate

Square(x).

1. No square is prime.

2. Some square is odd.

3. The square of any prime is prime.

4. The square of any prime other than 2 is odd.

5. The square of any number greater than 1 is greater than the number itself.

Submit your sentence ļ¬le.

Section 9.8

Alternative notation

The notation we have been using for the quantiļ¬ers is currently the most

popular. An older notation that is still in some use employs (x) for āx. Thus,

for example, in this notation our

āx [Tet(x) ā’ Small(x)]

would be written:

(x) [Tet(x) ā’ Small(x)]

Another notation that is occasionally used exploits the similarity between

universal quantiļ¬cation and conjunction by writing x instead of āx. In this

notation our sentence would be rendered:

x [Tet(x) ā’ Small(x)]

Finally, you will sometimes encounter the universal quantiļ¬er written Ī x, as

in:

Ī x [Tet(x) ā’ Small(x)]

Similar variants of āx are in use. One version writes (āx) or (Ex). Other

versions write x or Ī£x. Thus the following are notational variants of one

another.

āx [Cube(x) ā§ Large(x)]

(Ex)[Cube(x) ā§ Large(x)]

x [Cube(x) ā§ Large(x)]

Ī£x [Cube(x) ā§ Large(x)]

Section 9.8

256 / Introduction to Quantification

Remember

The following table summarizes the alternative notations.

Our notation Common equivalents

Ā¬P ā¼ P, P, !P, Np

Pā§Q P&Q, P&&Q, P Ā· Q, PQ, Kpq

PāØQ P | Q, P Q, Apq

Pā’Q P ā Q, Cpq

Pā”Q P ā” Q, Epq

āx S(x) (x)S(x), x S(x), Ī x S(x)

āx S(x) (āx)S(x), (Ex)S(x), x S(x), Ī£x S(x)

Exercises

9.26 (Overcoming dialect diļ¬erences) The following are all sentences of fol. But theyā™re in diļ¬erent

Ć‚ dialects. Start a new sentence ļ¬le in Tarskiā™s World and translate them into our dialect.

1. ā¼ (x)(P(x) ā Q(x))

2. Ī£y((P(y) ā” Q(y)) & R(y))

3. x P(x) ā” x P(x)

Chapter 9

Chapter 10

The Logic of Quantiļ¬ers

We have now introduced all of the symbols of ļ¬rst-order logic, though weā™re

nowhere near ļ¬nished learning all there is to know about them. Before we

go on, we should explain where the āļ¬rst-orderā in āļ¬rst-order logicā comes ļ¬rst-order logic

from. It has to do with the kinds of things that our quantiļ¬ers quantify over.

In fol we are allowed to say things like āx Large(x), that is, there is something

that has the property of being large. But we canā™t say things like there is some

property that Max has: āP P(max).

First-order quantiļ¬ers allow us to make quantity claims about ordinary

objects: blocks, people, numbers, sets, and so forth. (Note that we are very

liberal about what an ordinary object is.) If, in addition, we want to make

quantity claims about properties of the objects in our domain of discourseā”

say we want to claim that Max and Claire share exactly two propertiesā”then

we need what is known as second-order quantiļ¬ers. Since our language only second-order

quantiļ¬ers

has ļ¬rst-order quantiļ¬ers, it is known as the language of ļ¬rst-order logic: fol.

Now that weā™ve learned the basics of how to express ourselves using ļ¬rst-

order quantiļ¬ers, we can turn our attention to the central issues of logical

consequence and logical truth:

What quantiļ¬ed sentences are logical truths?

What arguments involving quantiļ¬cation are valid?

What are the valid inference patterns involving quantiļ¬ers?

How can we formalize these valid patterns of inference?

In this chapter we take up the ļ¬rst two questions; the remaining two are

treated in Chapters 12 and 13.

Section 10.1

Tautologies and quantiļ¬cation

Introducing quantiļ¬ers required a much more radical change to the language

than introducing additional truth-functional connectives. Because of the way

quantiļ¬ers work, we had to introduce the notion of a well-formed formula,

something very much like a sentence except that it can contain free vari-

ables. Quantiļ¬ers attach to these wļ¬s, bind their variables, and thereby form

257

258 / The Logic of Quantifiers

sentences from formulas that arenā™t themselves sentences. This is strikingly

diļ¬erent from the behavior of truth-functional operators.

Given how diļ¬erent quantiļ¬ed sentences are from anything weā™ve seen

before, the ļ¬rst thing we need to do is ask how much of the logic of truth

functions applies to sentences containing quantiļ¬ers. In particular, do the

notions of tautology, tautological consequence, and tautological equivalence

apply to our new sentences, and if so, how?

The answer is that these notions do apply to quantiļ¬ed sentences, but they

quantiļ¬ed sentences

and tautological must be applied with care. Students often ignore the presence of quantiļ¬ers

consequence in sentences and try to use what they learned in propositional logic wherever

it seems vaguely applicable. This can be very dangerous. For example, you

might rightly notice that the following arguments are logically valid:

1. āx (Cube(x) ā’ Small(x))

āx Cube(x)

āx Small(x)

2. āx Cube(x)

āx Small(x)

āx (Cube(x) ā§ Small(x))

The ļ¬rst of these is valid because if every cube is small, and everything is

a cube, then everything is small. The second is valid because if everything

is a cube, and everything is small, then everything is a small cube. But are

these arguments tautologically valid? Or, to put it another way, can we simply

ignore the quantiļ¬ers appearing in these arguments and apply the principles

of modus ponens and ā§ Intro?

It doesnā™t take long to see that ignoring quantiļ¬ers doesnā™t work. For ex-

ample, neither of the following arguments is valid, tautologically or otherwise:

3. āx (Cube(x) ā’ Small(x))

āx Cube(x)

āx Small(x)

4. āx Cube(x)

āx Small(x)

āx (Cube(x) ā§ Small(x))

The premises of argument 3 will be true in a world containing a large cube

and a large dodecahedron, but nothing small. The premises of argument 4 will

Chapter 10

Tautologies and quantification / 259

be true in a world containing a large cube and a small dodecahedron, but no

small cube.

These counterexamples not only show that arguments 3 and 4 are invalid,

they also show that 1 and 2 are not tautologically valid, that is, valid solely

in virtue of the meanings of the truth-functional connectives. Clearly, the

meaning of ā is an essential factor in the validity of 1 and 2, for if it were not,

3 and 4 should be valid as well. Or, to put it the other way around, if ā meant

the same thing as ā, then 1 and 2 would be no more valid than 3 and 4.

A similar point can be made about over-hasty applications of the notion

of tautology. For example, the following sentence, which says that either there tautology and

quantiļ¬cation

is a cube or there is something which is not a cube, is logically true:

āx Cube(x) āØ āx Ā¬Cube(x)

But is this sentence a tautology, true simply in virtue of the meanings of

the truth-functional connectives? Again, the answer is no, as we can see by

considering what happens when we replace the existential quantiļ¬er with a

universal quantiļ¬er:

āx Cube(x) āØ āx Ā¬Cube(x)

This sentence says that either everything is a cube or everything is not a

cube, which of course is false in any world inhabited by a mixture of cubes

and non-cubes.

Are there no tautologies in a language containing quantiļ¬ers? Of course

there are, but you donā™t ļ¬nd them by pretending the quantiļ¬ers simply arenā™t

there. For example, the following sentence is a tautology:

āx Cube(x) āØ Ā¬āx Cube(x)

This sentence, unlike the previous one, is an instance of the law of excluded

middle. It says that either everything is a cube or itā™s not the case that ev-

erything is a cube, and thatā™s going to be true so long as the constituent

sentence āx Cube(x) has a deļ¬nite truth value. It would hold equally well if

the constituent sentence were āx Cube(x), a fact you could recognize even if

you didnā™t know exactly what this sentence meant.

Recall that if we have a tautology and replace its atomic sentences by

complex sentences, the result is still a tautology, and hence also a logical

truth. This holds as long as the things we are substituting are sentences that

have deļ¬nite truth values (whether true or not). We can use this observation

ńņš. 47 |