ńņš. 49 |

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 |