Recognizing whether a sentence is a ¬rst-order validity, or a ¬rst-order

consequence of some premises, is not as routine as with tautologies and tau-

tological consequence. With truth tables, there may be a lot of rows to check,

but at least the number is ¬nite and known in advance. With ¬rst-order va-

lidity and consequence, the situation is much more complicated, since there recognizing ¬rst-

order validity

are in¬nitely many possible circumstances that might be relevant. In fact,

there is no correct and mechanical procedure, like truth tables, that always

answers the question is S a ¬rst-order validity? But there are procedures that

do a pretty good job and we have built one into Fitch; it is the procedure

given as FO Con on the consequence menu. In checking applications of FO

Con, Fitch will never give you the wrong answer, though sometimes it will

get stuck, unable to give you any answer at all.

Unfortunately, judging ¬rst-order validity is no easier for you than for

the computer. But unless a sentence or argument is quite complicated, the

replacement method should result in a successful resolution of the issue, one

that agrees with an application of FO Con.

As we said earlier, we will make the notions of ¬rst-order validity and

¬rst-order consequence more precise later in the book, so that we can prove

theorems involving these notions. But the rough-and-ready characterizations

we™ve given will su¬ce until then. Even with the current description, we can

see the following:

1. If S is a tautology, then it is a ¬rst-order validity. Similarly, if S is a

¬rst-order validity, it is a logical truth. The converse of neither of these

statements is true, though. (See Figure 10.2.)

2. Similarly, if S is a tautological consequence of premises P1 , . . . , Pn , then

it is a ¬rst-order consequence of these premises. Similarly, if S is a ¬rst-

order consequence of premises P1 , . . . , Pn , then it is a logical consequence

of these premises. Again, the converse of neither of these statements is

true.

Let™s try our hand at applying all of these concepts, using the various

consequence mechanisms in Fitch.

Section 10.2

272 / The Logic of Quantifiers

Figure 10.2: The relation between tautologies, ¬rst-order validities, and logical

truths

You try it

................................................................

1. Open the ¬le FO Con 1. Here you are given a collection of premises, plus a

series of sentences that follow logically from them. Your task is to cite sup-

port sentences and specify one of the consequence rules to justify each step.

But the trick is that you must use the weakest consequence mechanism

possible and cite the minimal number of support sentences possible.

2. Focus on the ¬rst step after the Fitch bar, ∀x Cube(x) ’ Cube(b). You will

recognize this as a logical truth, which means that you should not have

to cite any premises in support of this step. First, ask yourself whether

the sentence is a tautology. No, it is not, so Taut Con will not check out.

Is it a ¬rst-order validity? Yes, so change the rule to FO Con and see

if it checks out. It would also check out using Ana Con, but this rule is

stronger than necessary, so your answer would be counted wrong if you

used this mechanism.

3. Continue through the remaining sentences, citing only necessary support-

ing premises and the weakest Con mechanism possible.

4. Save your proof as Proof FO Con 1.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Congratulations

Chapter 10

First-order validity and consequence / 273

Remember

1. A sentence of fol is a ¬rst-order validity if it is a logical truth when you

ignore the meanings of the names, function symbols, and predicates

other than the identity symbol.

2. A sentence S is a ¬rst-order consequence of premises P1 , . . . , Pn if it a

logical consequence of these premises when you ignore the meanings

of the names, function symbols, and predicates other than identity.

3. The Replacement Method is useful for determining whether a sentence

is a ¬rst-order validity and whether the conclusion of an argument is

a ¬rst-order consequence of the premises.

4. All tautologies are ¬rst-order validities; all ¬rst-order validities are

logical truths. Similarly for consequence.

Exercises

10.8 If you skipped the You try it section, go back and do it now. Submit the ¬le Proof FO Con 1.

‚

10.9 Open Carnap™s Sentences and Bolzano™s World.

‚| 1. Paraphrase each sentence in clear, colloquial English and verify that it is true in the

given world.

2. For each sentence, decide whether you think it is a logical truth. If it isn™t, build a

world in which the the sentence comes out false and save it as World 10.9.x, where

x is the number of the sentence. [Hint: You should be able to falsify three of these

sentences.]

3. Which of these sentences are ¬rst-order validities? [Hint: Three are.]

4. For the remaining four sentences (those that are logical truths but not ¬rst-order va-

lidities), apply the Replacement Method to come up with ¬rst-order counterexamples.

Make sure you describe both your interpretations of the predicates and the falsifying

circumstance.

Turn in your answers to parts 1, 3, and 4; submit the worlds you build in part 2.

Section 10.2

274 / The Logic of Quantifiers

Each of the following arguments is valid. Some of the conclusions are (a) tautological consequences of

the premises, some are (b) ¬rst-order consequences that are not tautological consequences, and some are

(c) logical consequences that are not ¬rst-order consequences. Use the truth-functional form algorithm

and the replacement method to classify each argument. You should justify your classi¬cations by turning

in (a) the truth-functional form of the argument, (b) the truth-functional form and the argument with

nonsense predicates substituted, or (c) the truth-functional form, the nonsense argument, and a ¬rst-

order counterexample.

10.10 Cube(a) § Cube(b)

Small(a) § Large(b)

∃x (Cube(x) § Small(x)) § ∃x (Cube(x) § Large(x))

10.11 Cube(a) § Cube(b)

Small(a) § Large(b)

∃x (Cube(x) § Large(x) § ¬Smaller(x, x))

10.12 10.13

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

¬∃y Small(y) ¬∃y Small(y)

∃x ¬Cube(x) ¬∀x Cube(x)

10.14 10.15

Cube(a) Cube(a)

Dodec(b) ¬Cube(b)

a=b a=b

10.16 10.17

Cube(a) ∀x (Dodec(x) ’ ¬SameCol(x, c))

¬Cube(a)

¬Dodec(c)

a=b

10.18 10.19

∀z (Small(z) ” Cube(z)) ∀z (Small(z) ’ Cube(z))

Cube(d) ∀w (Cube(w) ’ LeftOf(w, c))

Small(d) ¬∃y (Small(y) § ¬LeftOf(y, c))

Chapter 10

First-order equivalence and DeMorgan™s laws / 275

Section 10.3

First-order equivalence and DeMorgan™s laws

There are two ways in which we can apply what we learned about tautolog-

ical equivalence to ¬rst-order sentences. First of all, if you apply the truth-

functional form algorithm to a pair of sentences and the resulting forms are

tautologically equivalent, then of course the original sentences are ¬rst-order

equivalent. For example, the sentence:

¬(∃x Cube(x) § ∀y Dodec(y))

is tautologically equivalent to:

¬∃x Cube(x) ∨ ¬∀y Dodec(y)

When you apply the truth-functional form algorithm, you see that this is just

an instance of one of DeMorgan™s laws.

But it turns out that we can also apply DeMorgan, and similar principles,

inside the scope of quanti¬ers. Let™s look at an example involving the Law of

Contraposition. Consider the sentences:

∀x (Cube(x) ’ Small(x))

∀x (¬Small(x) ’ ¬Cube(x))

A moment™s thought will convince you that each of these sentences is a ¬rst-

order consequence of the other, and so they are ¬rst-order equivalent. But

unlike the previous examples, they are not tautologically equivalent.

To see why Contraposition (and other principles of equivalence) can be

applied in the scope of quanti¬ers, we need to consider the w¬s to which the

principle was applied:

Cube(x) ’ Small(x)

¬Small(x) ’ ¬Cube(x)

Or, more generally, consider the w¬s:

P(x) ’ Q(x)

¬Q(x) ’ ¬P(x)

where P(x) and Q(x) may be any formulas, atomic or complex, containing the

single free variable x.

Now since these formulas are not sentences, it makes no sense to say they

are true in exactly the same circumstances, or that they are logical (or tauto-

logical) consequences of one another. Formulas with free variables are neither

Section 10.3

276 / The Logic of Quantifiers

true nor false. But there is an obvious extension of the notion of logical equiv-

alence that applies to formulas with free variables. It is easy to see that in

any possible circumstance, the above two formulas will be satis¬ed by exactly

the same objects. Here™s a proof of this fact:

Proof: We show this by indirect proof. Assume that in some circum-

stance there is an object that satis¬es one but not the other of these

two formulas. Let™s give this object a new name, say n1 . Consider

the results of replacing x by n1 in our formulas:

P(n1 ) ’ Q(n1)

¬Q(n1) ’ ¬P(n1 )

Since x was the only free variable, these are sentences. But by our

assumption, one of them is true and one is false, since that is how

we de¬ned satisfaction. But this is a contradiction, since these two

sentences are logically equivalent by Contraposition.

We will say that two w¬s with free variables are logically equivalent if, in

logically equivalent w¬s

any possible circumstance, they are satis¬ed by the same objects.2 Or, what

comes to the same thing, two w¬s are logically equivalent if, when you re-

place their free variables with new names, the resulting sentences are logically

equivalent.

The above proof, suitably generalized, shows that when we apply any of our

principles of logical equivalence to a formula, the result is a logically equivalent

formula, one that is satis¬ed by exactly the same objects as the original. This

in turn is why the sentence ∀x (Cube(x) ’ Small(x)) is logically equivalent

to the sentence ∀x (¬Small(x) ’ ¬Cube(x)). If every object in the domain of

discourse (or one object, or thirteen objects) satis¬es the ¬rst formula, then

every object (or one or thirteen) must satisfy the second.

Equipped with the notion of logically equivalent w¬s, we can restate the

principle of substitution of equivalents so that it applies to full ¬rst-order

substitution of

equivalent w¬s logic. Let P and Q be w¬s, possibly containing free variables, and let S(P) be

any sentence containing P as a component part. Then if P and Q are logically

equivalent:

P”Q

then so too are S(P) and S(Q):

S(P) ” S(Q)

2 Though we haven™t discussed satisfaction for w¬s with more than one free variable, a

similar argument can be applied to such w¬s: the only di¬erence is that more than one

name is substituted in for the free variables.

Chapter 10

First-order equivalence and DeMorgan™s laws / 277