<<

. 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
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
( 107 .)



>>