<<

. 49
( 107 .)



>>


10.4 ∀x Cube(x) ’ ∃y Small(y)
 ¬∃y Small(y)
¬∀x Cube(x)

10.5 ∀x (Tet(x) ’ LeftOf(x, b)) ∨ ∀x (Tet(x) ’ RightOf(x, b))
 ∃x (Tet(x) § SameCol(x, b)) ’ ¬∀x (Tet(x) ’ LeftOf(x, b))
∀x (Tet(x) ’ RightOf(x, b)) ’ ¬∃x (Tet(x) § SameCol(x, b))
¬∃x (Tet(x) § SameCol(x, b))

10.6 ∃x (Cube(x) § Large(x)) ’ (Cube(c) § Large(c))
 Tet(c) ’ ¬Cube(c)
Tet(c)
∀x ¬(Cube(x) § Large(x))




Section 10.1
266 / The Logic of Quantifiers


10.7 ∃x (Cube(x) § Large(x)) ’ (Cube(c) § Large(c))
 ∀x ¬(Cube(x) § Large(x)) ” ¬∃x (Cube(x) § Large(x))
Tet(c) ’ ¬Cube(c)
Tet(c)
∀x ¬(Cube(x) § Large(x))

[In 10.6 and 10.7, we could think of the ¬rst premise as a way of introducing a new constant, c, by
means of the assertion: Let the constant c name a large cube, if there are any; otherwise, it may name
any object. Sentences of this sort are called Henkin witnessing axioms, and are put to important use
in proving completeness for F. The arguments show that if a constant introduced in this way ends up
naming a tetrahedron, it can only be because there aren™t any large cubes.]



Section 10.2
First-order validity and consequence
When we ¬rst discussed the intuitive notions of logical truth and logical con-
sequence, we appealed to the idea of a logically possible circumstance. We
described a logically valid argument, for example, as one whose conclusion is
true in every possible circumstance in which all the premises are true. When
we needed more precision than this description allowed, we introduced truth
tables and the concepts of tautology and tautological consequence. These
concepts add precision by modeling possible circumstances as rows of a truth
table. We have seen that this move does a good job of capturing the intu-
itive notions of logical truth and logical consequence”provided we limit our
attention to the truth-functional connectives.
Unfortunately, the concepts of tautology and tautological consequence
don™t get us far in ¬rst-order logic. We need a more re¬ned method for ana-
lyzing logical truths and logically valid arguments when they depend on the
quanti¬ers and identity. We will introduce these notions in this chapter, and
develop them in greater detail in Chapter 18. The notions will give us, for
¬rst-order logic, what the concepts of tautology and tautological consequence
gave us for propositional logic: precise approximations of the notions of logical
truth and logical consequence.
First, a terminological point. It is a regrettable fact that there is no single
term like “tautological” that logicians consistently use when applying the
various logical notions to ¬rst-order sentences and arguments. That is, we
don™t have a uniform way of ¬lling out the table:




Chapter 10
First-order validity and consequence / 267



Propositional logic First-order logic General notion
Tautology ?? Logical truth
Tautological consequence ?? Logical consequence
Tautological equivalence ?? Logical equivalence
One option would be to use the terms ¬rst-order logical truth, ¬rst-order
logical consequence, and ¬rst-order logical equivalence. But these are just too
much of a mouthful for repeated use, so we will abbreviate them. Instead of
¬rst-order logical consequence, we will use ¬rst-order consequence or simply ¬rst-order consequence
FO consequence, and for ¬rst-order logical equivalence, we™ll use ¬rst-order
(or FO) equivalence. We will not, however, use ¬rst-order truth for ¬rst-order
logical truth, since this might suggest that we are talking about a true (but
not logically true) sentence of ¬rst-order logic.
For ¬rst-order logical truth, it is standard to use the term ¬rst-order va-
lidity. This may surprise you, since so far we™ve only used “valid” to apply ¬rst-order validity
to arguments, not sentences. This is a slight terminological inconsistency, but
it shouldn™t cause any problems so long as you™re aware of it. In ¬rst-order
logic, we use valid to apply to both sentences and arguments: to sentences
that can™t be false, and to arguments whose conclusions can™t be false if their
premises are true. Our completed table, then, looks like this:

Propositional logic First-order logic General notion
Tautology FO validity Logical truth
Tautological consequence FO consequence Logical consequence
Tautological equivalence FO equivalence Logical equivalence
So what do we mean by the notions of ¬rst-order validity, ¬rst-order con-
sequence and ¬rst-order equivalence? These concepts are meant to apply to
those logical truths, consequences, and equivalences that are such solely in
virtue of the truth-functional connectives, the quanti¬ers, and the identity
symbol. Thus, for purposes of determining ¬rst-order consequence, we ignore
the speci¬c meanings of names, function symbols, and predicates other than
identity.
There are two reasons for treating identity along with the quanti¬ers and identity
connectives, rather than like any other predicate. The ¬rst is that almost
all ¬rst-order languages use =. Other predicates, by contrast, vary from one
¬rst-order language to another. For example, the blocks language uses the
binary predicate LeftOf, while the language of set theory uses ∈, and the
language of arithmetic uses <. This makes it a reasonable division of labor to
try ¬rst to understand the logic implicit in the connectives, quanti¬ers, and
identity, without regard to the meanings of the other predicates, names, and



Section 10.2
268 / The Logic of Quantifiers


function symbols. The second reason is that the identity predicate is crucial for
expressing many quanti¬ed noun phrases of English. For instance, we™ll soon
see how to express things like at least three tetrahedra and at most four cubes,
but to express these in fol we need identity in addition to the quanti¬ers ∀
and ∃. There is a sense in which identity and the quanti¬ers go hand in hand.
If we can recognize that a sentence is logically true without knowing the
meanings of the names or predicates it contains (other than identity), then
we™ll say the sentence is a ¬rst-order validity. Let™s consider some examples
from the blocks language:

∀x SameSize(x, x)
∀x Cube(x) ’ Cube(b)
(Cube(b) § b = c) ’ Cube(c)
(Small(b) § SameSize(b, c)) ’ Small(c)

All of these are arguably logical truths of the blocks language, but only
the middle two are ¬rst-order validities. One way to see this is to replace
the familiar blocks language predicates with nonsensical predicates, like those
using nonsense
used in Lewis Carroll™s famous poem Jabberwocky.1 The results would look
predicates to test for
FO validity something like this:

∀x Outgrabe(x, x)
∀x Tove(x) ’ Tove(b)
(Tove(b) § b = c) ’ Tove(c)
(Slithy(b) § Outgrabe(b, c)) ’ Slithy(c)

Notice that we can still see that the second and third sentences must be
true, whatever the predicate Tove may mean. If everything is a tove, and b is
an object in the domain of discourse, then b must surely be a tove. Similarly,
if b is a tove, and c is the same object as b, then c is a tove as well. Contrast
this with the ¬rst and fourth sentences, which no longer look logically true
at all. Though we know that everything is the same size as itself, we have no
idea whether everything outgrabes itself! Just so, the fact that b is slithy and
outgrabes c hardly guarantees that c is slithy. Maybe it is and maybe it isn™t!
1 The full text of Jabberwocky can be found at http://english-server.hss.cmu.edu/ po-
etry/jabberwocky.html. The ¬rst stanza is:

™Twas brillig, and the slithy toves
Did gyre and gimble in the wabe;
All mimsy were the borogoves,
And the mome raths outgrabe.

“Lewis Carroll” was the pen name of the logician Charles Dodgson (after whom both
Carroll™s World and Dodgson™s Sentences were named).




Chapter 10
First-order validity and consequence / 269



The concepts of ¬rst-order consequence and ¬rst-order equivalence work
similarly. For example, if you can recognize that an argument is logically valid
without appealing to the meanings of the names or predicates (other than
identity), then the conclusion is a ¬rst-order consequence of the premises.
The following argument is an example:

∀x (Tet(x) ’ Large(x))
¬Large(b)
¬Tet(b)

This argument is obviously valid. What™s more, if we replace the predicates
Tet and Large with nonsense predicates, say Borogove and Mimsy, the result
is the following:

∀x (Borogove(x) ’ Mimsy(x))
¬Mimsy(b)
¬Borogove(b)

Again, it™s easy to see that if the borogoves (whatever they may be) are
all mimsy (whatever that may mean), and if b is not mimsy, then it can™t
possibly be a borogove. So the conclusion is not just a logical consequence of
the premises, it is a ¬rst-order consequence.
Recall that to show that a sentence was not a tautological consequence
of some premises, it su¬ced to ¬nd a truth-value assignment to the atomic
sentences that made the premises true and the conclusion false. A similar pro-
cedure can be used to show that a conclusion is not a ¬rst-order consequence
of its premises, except instead of truth-value assignments what we look for is
a bit more complicated. Suppose we are given the following argument:

¬∃x Larger(x, a)
¬∃x Larger(b, x)
Larger(c, d)
Larger(a, b)

The ¬rst premise tells you that nothing is larger than a and the second tells you
that b is not larger than anything. If you were trying to build a counterexample
world, you might reason that a must be the largest object in the world (or
one of them) and that b must be the smallest (or one of them). Since the third
premise guarantees that the objects in the world aren™t all the same size, the
conclusion can™t be falsi¬ed in a world in which the premises are true.



Section 10.2
270 / The Logic of Quantifiers




Figure 10.1: A ¬rst-order counterexample.

Is this conclusion a ¬rst-order consequence of the premises? To show that
¬rst-order
counterexamples it™s not, we™ll do two things. First, let™s replace the predicate Larger with a
meaningless predicate, to help clear our minds of any constraints suggested
by the predicate:

¬∃x R(x, a)
¬∃x R(b, x)
R(c, d)
R(a, b)

Next, we™ll describe a speci¬c interpretation of R (and the names a, b,
c, and d), along with a possible circumstance that would count as a coun-
terexample to the new argument. This is easy. Suppose R means likes, and we
are describing a situation with four individuals: Romeo and Juliet (who like
each other), and Moriarty and Scrooge (who like nobody, and the feelings are
mutual).
If we let a refer to Moriarty, b refer to Scrooge, c and d refer to Romeo
and Juliet, then the premises of our argument are all true, though the con-
clusion is false. This possible circumstance, like an alternate truth assignment
in propositional logic, shows that our original conclusion is not a ¬rst-order
consequence of the premises. Thus we call it a ¬rst-order counterexample.
Let™s codify this procedure.
Replacement Method:
replacement method

1. To check for ¬rst-order validity or ¬rst-order consequence, systematically
replace all of the predicates, other than identity, with new, meaningless
predicate symbols, making sure that if a predicate appears more than
once, you replace all instances of it with the same meaningless predicate.
(If there are function symbols, replace these as well.)

2. To see if S is a ¬rst-order validity, try to describe a circumstance, along
with interpretations for the names, predicates, and functions in S, in



Chapter 10
First-order validity and consequence / 271



which the sentence is false. If there is no such circumstance, the original
sentence is a ¬rst-order validity.

3. To see if S is a ¬rst-order consequence of P1 , . . . , Pn , try to ¬nd a cir-
cumstance and interpretation in which S is false while P1 , . . . , Pn are all
true. If there is no such circumstance, the original inference counts as a
¬rst-order consequence.

<<

. 49
( 107 .)



>>