<< Ļšåäūäółą’ ńņš. 47(čē 107 ńņš.)ĪĆĖĄĀĖÅĶČÅ Ńėåäóžłą’ >>
Fill in the following table with trueā™s and falseā™s according to whether the indicated sentence
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
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.

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(čē 107 ńņš.)ĪĆĖĄĀĖÅĶČÅ Ńėåäóžłą’ >>