3. (Replacing bound variables) For any w¬ P(x) and variable y that does

not occur in P(x):

(a) ∀x P(x) ” ∀y P(y)

(b) ∃x P(x) ” ∃y P(y)

Exercises

10.23 (Null quanti¬cation) Open Null Quanti¬cation Sentences. In this ¬le you will ¬nd sentences

‚ in the odd numbered slots. Notice that each sentence is obtained by putting a quanti¬er in front

Chapter 10

The axiomatic method / 283

of a sentence in which the quanti¬ed variable is not free.

1. Open G¨del™s World and evaluate the truth of the ¬rst sentence. Do you understand why

o

it is false? Repeatedly play the game committed to the truth of this sentence, each time

choosing a di¬erent block when your turn comes around. Not only do you always lose,

but your choice has no impact on the remainder of the game. Frustrating, eh?

2. Check the truth of the remaining sentences and make sure you understand why they have

the truth values they do. Play the game a few times on the second sentence, committed

to both true and false. Notice that neither your choice of a block (when committed to

false) nor Tarski™s World™s choice (when committed to true) has any e¬ect on the game.

3. In the even numbered slots, write the sentence from which the one above it was obtained.

Check that the even and odd numbered sentences have the same truth value, no matter

how you modify the world. This is because they are logically equivalent. Save and submit

your sentence ¬le.

Some of the following biconditionals are logical truths (which is the same as saying that the two sides of

the biconditional are logically equivalent); some are not. If you think the biconditional is a logical truth,

create a ¬le with Fitch, enter the sentence, and check it using FO Con. If the sentence is not a logical

truth, create a world in Tarski™s World in which it is false. Submit the ¬le you create.

10.24 (∀x Cube(x) ∨ ∀x Dodec(x)) 10.25 ¬∃z Small(z) ” ∃z ¬Small(z)

‚ ‚

” ∀x (Cube(x) ∨ Dodec(x))

10.26 ∀x Tet(b) ” ∃w Tet(b) 10.27 ∃w (Dodec(w) § Large(w))

‚ ‚ ” (∃w Dodec(w) § ∃w Large(w))

10.28 ∃w (Dodec(w) § Large(b)) 10.29 ¬∀x (Cube(x) ’ (Small(x) ∨ Large(x)))

‚ ‚

” (∃w Dodec(w) § Large(b)) ” ∃z (Cube(z) § ¬Small(z) § ¬Large(z))

Section 10.5

The axiomatic method

As we will see in the coming chapters, ¬rst-order consequence comes much

closer to capturing the logical consequence relation of ordinary language than

does tautological consequence. This will be apparent from the kinds of sen-

tences that we can translate into the quanti¬ed language and from the kinds

of inference that turn out to be ¬rst-order valid.

Still, we have already encountered several arguments that are intuitively

valid but not ¬rst-order valid. Let™s look at an example where the replacement

Section 10.5

284 / The Logic of Quantifiers

method reveals that the conclusion is not a ¬rst-order consequence of the

premises:

∀x (Cube(x) ” SameShape(x, c))

Cube(c)

Using the replacement method, we substitute meaningless predicate symbols,

say P and Q, for the predicates Cube and SameShape. The result is

∀x (P(x) ” Q(x, c))

P(c)

which is clearly not a valid argument. If we wanted the conclusion of our

argument to be a ¬rst-order consequence of the premises, we would need to

add a new premise or premises expressing facts about the predicates involved

in the original inference. For the present argument, here is what we might do:

∀x (Cube(x) ” SameShape(x, c))

∀x SameShape(x, x)

Cube(c)

The premise we™ve added is clearly justi¬ed by the meaning of SameShape.

What™s more, the replacement method now gives us

∀x (P(x) ” Q(x, c))

∀x Q(x, x)

P(c)

which is logically valid no matter what the predicates P and Q mean. The

conclusion is a ¬rst-order consequence of the two premises.

This technique of adding a premise whose truth is justi¬ed by the meanings

of the predicates is one aspect of what is known as the axiomatic method. It is

axiomatic method

often possible to bridge the gap between the intuitive notion of consequence

and the more restricted notion of ¬rst-order consequence by systematically

expressing facts about the predicates involved in our inferences. The sentences

used to express these facts are sometimes called meaning postulates, a special

type of axiom.

meaning postulates

Suppose we wanted to write out axioms that bridged the gap between ¬rst-

order consequence and the intuitive notion of consequence that we™ve been

using in connection with the blocks language. That would be a big task, but

Chapter 10

The axiomatic method / 285

we can make a start on it by axiomatizing the shape predicates. We might

begin by taking four basic shape axioms as a starting point. These axioms

express the fact that every block has one and only one shape.

Basic Shape Axioms:

1. ¬∃x (Cube(x) § Tet(x))

2. ¬∃x (Tet(x) § Dodec(x)) basic shape axioms

3. ¬∃x (Dodec(x) § Cube(x))

4. ∀x (Tet(x) ∨ Dodec(x) ∨ Cube(x))

The ¬rst three axioms stem from the meanings of our three basic shape

predicates. Being one of these shapes simply precludes being another. The

fourth axiom, however, is presumably not part of the meaning of the three

predicates, as there are certainly other possible shapes. Still, if our goal is to

capture reasoning about blocks worlds of the sort that can be built in Tarski™s

World, we will want to include 4 as an axiom.

Any argument that is intuitively valid and involves only the three ba-

sic shape predicates is ¬rst-order valid if we add these axioms as additional

premises. For example, the following intuitively valid argument is not ¬rst-

order valid:

¬∃x Tet(x)

∀x (Cube(x) ” ¬Dodec(x))

If we add axioms 3 and 4 as premises, however, then the resulting argument

is

¬∃x Tet(x)

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

∀x (Tet(x) ∨ Dodec(x) ∨ Cube(x))

∀x (Cube(x) ” ¬Dodec(x))

This argument is ¬rst-order valid, as can be seen by replacing the shape

predicates with meaningless predicates, say P, Q, and R:

¬∃x P(x)

¬∃x (Q(x) § R(x))

∀x (P(x) ∨ Q(x) ∨ R(x))

∀x (R(x) ” ¬Q(x))

Section 10.5

286 / The Logic of Quantifiers

If the validity of this argument is not entirely obvious, try to construct a

¬rst-order counterexample. You™ll see that you can™t.

Let™s look at an example where we can replace some instances of Ana

Con by the basic shape axioms and the weaker FO Con rule.

You try it

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

1. Open the Fitch ¬le Axioms 1. The premises in this ¬le are just the four basic

shape axioms. Below the Fitch bar are four sentences. Each is justi¬ed by

a use of the rule Ana Con, without any sentences cited in support. Verify

that each of the steps checks out.

2. Now change each of the justi¬cations from Ana Con to FO Con. Verify

that none of the steps now checks out. See if you can make each of them

check out by ¬nding a single shape axiom to cite in its support.

3. When you are ¬nished, save your proof as Proof Axioms 1.

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

The basic shape axioms don™t express everything there is to say about the

other shape axioms

shapes in Tarski™s World. We have not yet said anything about the binary

predicate SameShape. At the very least, we would need the following as a ¬fth

axiom:

∀x SameShape(x, x)

We will not in fact add this as an axiom since, as we will see in Chapter 12, it

leaves out essential facts about the relation between SameShape and the basic

shape predicates. When we add these other facts, it turns out that the above

axiom is unnecessary.

Axiomatization has another interesting use that can be illustrated with our

axioms about shape. Notice that if we systematically replace the predicates

Cube, Tet, and Dodec by the predicates Small, Medium, and Large, the resulting

sentences are true in all of the blocks worlds. It follows from this that if we

take any valid argument involving just the shape predicates and perform the

stated substitution, the result will be another valid argument.

Presupposing a range of circumstances

The intuitive di¬erence between the ¬rst three shape axioms and the fourth,

which asserts a general fact about our block worlds but not one that follows

from the meanings of the predicates, highlights an important characteristic

Chapter 10

The axiomatic method / 287

of much everyday reasoning. More often than not, when we reason, we do so

against the background of an assumed range of possibilities. When you reason

about Tarski™s World, it is natural to presuppose the various constraints that assuming a range

of possibilities

have been built into the program. When you reason about what movie to

go to, you implicitly presuppose that your options are limited to the movies

showing in the vicinity.

The inferences that you make against this background may not, strictly

speaking, be logically valid. That is, they may be correct relative to the pre-

supposed circumstances but not correct relative to some broader range of pos-

sibilities. For example, if you reason from ¬Cube(d) and ¬Tet(d) to Dodec(d),

your reasoning is valid within the domain of Tarski™s World, but not relative

to worlds where there are spheres and icosohedra. When you decide that the

latest Harrison Ford movie is the best choice, this may be a correct inference

in your vicinity, but perhaps not if you were willing to ¬‚y to other cities.

In general, background assumptions about the range of relevant circum-

stances are not made an explicit part of everyday reasoning, and this can give background

assumptions

rise to disagreements about the reasoning™s validity. People with di¬erent as-

sumptions may come up with very di¬erent assessments about the validity of

some explicit piece of reasoning. In such cases, it is often helpful to articulate

general facts about the presupposed circumstances. By making these explicit,

we can often identify the source of the disagreement.

The axiomatic method can be thought of as a natural extension of this ev-

eryday process. Using this method, it is often possible to transform arguments

that are valid only relative to a particular range of circumstances into argu-

ments that are ¬rst-order valid. The axioms that result express facts about

the meanings of the relevant predicates, but also facts about the presupposed

circumstances.

The history of the axiomatic method is closely entwined with the his-

tory of logic. You were probably already familiar with axioms from studying

Euclidean geometry. In investigating the properties of points, lines, and geo-

metrical shapes, the ancient Greeks discovered the notion of proof which lies

at the heart of deductive reasoning. This came about as follows. By the time

of the Greeks, an enormous number of interesting and important discoveries

about geometrical objects had already been made, some dating back to the

time of the ancient Babylonians. For example, ancient clay tablets show that

the Babylonians knew what is now called the Pythagorean Theorem. But for

the Babylonians, geometry was an empirical science, one whose facts were

discovered by observation.

Somewhere lost in the prehistory of mathematics, someone had a brilliant

idea. They realized that there are logical relationships among the known facts