<<

. 50
( 107 .)



>>


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


<<

. 50
( 107 .)



>>