. 93
( 107 .)


Intro. Intro.

18.16 Prove the inductive step in the sound- 18.17 Prove the inductive step in the sound-
ness proof corresponding to the rule ∃ ness proof corresponding to the rule ∀
Intro. Intro.

Section 18.4
The completeness of the shape axioms

In Section 12.5 (on page 339), we promised to convince you that the ten
axioms we gave for shape are complete, that is, that they completely bridged
the gap between ¬rst-order consequence and the intuitive notion of logical
consequence for the blocks language, as far as shape is concerned. We list the
axioms again here for your convenience:

Basic Shape Axioms:

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

2. ¬∃x (Tet(x) § Dodec(x))

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

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

SameShape Introduction Axioms:

Chapter 18
The completeness of the shape axioms / 513

5. ∀x ∀y ((Cube(x) § Cube(y)) ’ SameShape(x, y))

6. ∀x ∀y ((Dodec(x) § Dodec(y)) ’ SameShape(x, y))

7. ∀x ∀y ((Tet(x) § Tet(y)) ’ SameShape(x, y))

SameShape Elimination Axioms:

8. ∀x ∀y ((SameShape(x, y) § Cube(x)) ’ Cube(y))

9. ∀x ∀y ((SameShape(x, y) § Dodec(x)) ’ Dodec(y))

10. ∀x ∀y ((SameShape(x, y) § Tet(x)) ’ Tet(y))

We need to show that any argument that is logically valid in virtue of the
meanings of the shape predicates (and the ¬rst-order quanti¬ers, connectives,
and identity) is ¬rst-order valid once we add these ten axioms as premises.
To show this, it su¬ces to show that any ¬rst-order structure M making the
axioms true is just like one where the means of the four shape predicates is
the intended one.2
The reason this su¬ces is not hard to see. For suppose we have an argument
A that is valid in virtue of the meanings of the shape predicates. We want to
show that the result A of adding the ten axioms gives us an argument that is
¬rst-order valid. To do this, it su¬ces to show that any ¬rst-order structure M
making the original premises and the ten axioms true is just like a structure
M where the predicates mean what they should. Hence, by the presumed
validity of the argument A in the latter such structures, the conclusion holds
in M . But since M is just like M , the conclusion also holds in M. Hence,
since the structure M was an arbitrary one making the original premises and
the ten axioms true, this will show that A is ¬rst-order valid.
So now let us prove our claim about M and M . Recall that M is any
¬rst-order structure making our ten shape axioms true. Let Cu, Do, and T e
be the extensions in M of Cube, Dodec, and Tet, respectively. Axiom 1 insures
that Cu and T e are disjoint. Similarly, by Axioms 2 and 3, all three of the
sets are disjoint from the others. Axiom 4 insures us that everything in the
domain D of M is in one of these three sets.
Recall from Exercise 15.43 that a partition of D is a set P of non-empty
subsets of D with the property that every element of D is in exactly one
member of P. As we saw in that exercise, every such partition is the set of
equivalence classes of an equivalence relation, the relation of being in the same
member of the partition. This applied directly to our setting. Not all of these
2 What “just like” means here is that the structures are isomorphic, a notion we have
not de¬ned. The intuitive notion should be enough to convince you of our claim.

Section 18.4
514 / Advanced Topics in FOL

sets Cu, Do and T e need be non-empty, but if we restrict attention to those
that are, the preceding paragraph shows that we have a partition of D.
Now let S be the extension of SameShape in M. The remaining six axioms
insure that this relation is the equivalence relation generated by our partition.
Replace each object in Cu by a cube, each object in Do by a dodecahedron,
and each object in T e by a tetrahedron, making sure to use distinct blocks to
replace distinct objects of M. This is possible because we have a partition of
D. Call the resulting structure M . The extension of SameShape in M is just
the like S, except with the new blocks. Hence, the meaning of our predicates
is what we want it to be. Since the structures are otherwise unchanged, the
structures satisfy the same sentences of the blocks language.


18.18 Let M be the structure whose domain 18.19 Let M be any ¬rst-order structure mak-
is the natural numbers, where Cube, ing the ¬rst four shape axioms true.
Dodec, and Tet have as extensions the Prove that there is a unique way to in-
sets of natural numbers of the forms 3n, terpret SameShape so as to make all ten
3n + 1, and 3n + 2. Can we interpret axioms true.
SameShape so as to make the ten shape
axioms true? If so, in how many ways
can we do this?

Section 18.5

One important role function symbols play in ¬rst-order logic is as a way of
simplifying (for certain purposes) sentences that have lots of quanti¬ers nested
inside one another. To see an example of this, consider the sentence

∀x ∃y Neighbor(x, y)

Given a ¬xed domain of discourse (represented by a ¬rst-order structure M,
say) this sentence asserts that every b in the domain of discourse has at least
one neighbor c. Let us write this as

M |= Neighbor(x, y)[b, c]

rather than the more formal M |= Neighbor(x, y)[g] where g is the variable
assignment that assigns b to x and c to y. Now if the original quanti¬ed

Chapter 18
Skolemization / 515

sentence is true, then we can pick out, for each b, one of b™s neighbors, say his
nearest neighbor or favorite neighbor. Let f (b) be this neighbor, so that we
have, for every b
M |= Neighbor(x, y)[b, f (b)]
Now, we would like to say the following: if we had a function symbol f ex-
pressing our function f.

M |= ∀x Neighbor(x, f(x))

This would reduce the quanti¬er string “∀x ∃y” in the original sentence to the
simpler “∀x.” So we need to expand our ¬rst-order language and give ourselves
such a function symbol f to use as a name of f.
This important trick is known as Skolemization, after the Norwegian lo- Skolemization
gician Thoralf Skolem. The function f is called a Skolem function for the Skolem function
original quanti¬ed sentence. The new sentence, the one containing the func-
tion symbol but no existential quanti¬er, is called the Skolem normal form of Skolem normal form
the original sentence.
Notice that we did not say that a sentence is logically equivalent to its
Skolemization. The situation is a little more subtle than that. If our language
allowed existential quanti¬cation to apply to function symbols, we could get
a logically equivalent sentence, namely

∃f ∀x P(x, f(x))

This sort of sentence, however, takes us into what is known as second-order
logic, which is beyond the scope of this book.
Skolem functions, and Skolem normal form, are very important in ad-
vanced parts of logic. We will discuss one application of them later in the
chapter, when we sketch how to apply the resolution method to fol with
One of the reasons that natural language does not get bogged down in lots Skolemization in
natural language
of embedded quanti¬ers is that there are plenty of expressions that act like
function symbols, so we can usually get by with Skolemizations. Possessives,
for example, act as very general Skolem functions. We usually think of the
possessive “apostrophe s” as indicating ownership, as in John™s car. But it re-
ally functions much more generally as a kind of Skolem function. For example,
if we are trying to decide where the group will eat out, then Max™s restaurant
can refer to the restaurant that Max likes best. Or if we are talking about
logic books, we can use Kleene™s book to refer not to one Kleene owns, but to
one he wrote.

Section 18.5
516 / Advanced Topics in FOL


(Simplest case of Skolemization) Given a sentence of the form ∀x ∃y P(x, y)
in some ¬rst-order language, we Skolemize it by choosing a function sym-
bol f not in the language and writing ∀x P(x, f(x)). Every world that makes
the Skolemization true also makes the original sentence true. Every world
that makes the original sentence true can be turned into one that makes
the Skolemization true by interpreting the function symbol f by a func-
tion f which picks out, for any object b in the domain, some object c
such that they satisfy the w¬ P(x, y).


18.20 Discuss the logical relationship between 18.21 Skolemize the following sentence using
the following two sentences. [Hint: One the function symbol f.
is a logical consequence of the other, but
∀z ∃y [(1 + (z — z)) < y]
they are not logically equivalent.]
∀y ∃z ParentOf(z, y) Which of the following functions on nat-
∀y ParentOf(bestfriend(y), y) ural numbers could be used as a Skolem
function for this sentence?
Explain under what conditions the sec-
1. f(z) = z 2
ond would be a Skolemization of the
2. f(z) = z 2 + 1
3. f(z) = z 2 + 2
4. f(z) = z 3

Section 18.6
Uni¬cation of terms
We now turn to a rather di¬erent topic, uni¬cation, that applies mainly to
languages that contain function symbols. Uni¬cation is of crucial importance
when we come to extend the resolution method to the full ¬rst-order language.
The basic idea behind uni¬cation can be illustrated by comparing a couple
of claims. Suppose ¬rst that Nancy tells you that Max™s father drives a Honda,
and that no one™s grandfather drives a Honda. Now this is not true, but there is
nothing logically incompatible about the two claims. Note that if Nancy went
on to say that Max was a father (so that Max™s father was a grandfather)

Chapter 18
Unification of terms / 517

we could then accuse her of contradicting herself. Contrast Nancy™s claim
with Mary™s, that Max™s grandfather drives a Honda, and that no one™s father
drives a Honda. Mary can be accused of contradicting herself. Why? Because
grandfathers are, among other things, fathers.
More abstractly, compare the following pairs, where P is a unary predicate
symbol, f and g are unary function symbols, and a is an individual constant.
First pair: P(f(a)), ∀x ¬P(f(g(x)))
Second pair: P(f(g(a))), ∀x ¬P(f(x))
The ¬rst pair is a logical possibility. It is perfectly consistent to suppose that
the object f (a) has property P but that no object of the form f(g(b)) has
property P . This can only happen, though, if a is not of the form g(b). By con-
trast, the second pair is not a logical possibility. Why? Because if ∀x ¬P(f(x))
holds, so does the instance where we substitute g(a) for x: ¬P(f(g(a))). But
this contradicts P(f(g(a))).
Uni¬cation gives us a useful test to see if sets of claims like the above are uni¬cation
contradictory or not. You look at the terms involved and see whether they are
“uni¬able.” The terms f(a) and f(g(x)) in the ¬rst pair of sentences are not
uni¬able, whereas the terms in the second pair, f(g(a)) and f(x), are uni¬able.
What this means is that in the second case there is a way to substitute a term
for x so that the results coincide. This agreement produces a clash between
the two original sentences. In the ¬rst pair of terms, however, there is no such
way to make the terms coincide. No way of substituting a term in for the
variable x in f(g(x)) is going to give you the term f(a), since a is an individual
These examples motivate the following de¬nition.
De¬nition Terms t1 and t2 are uni¬able if there is a substitution of terms for de¬nition of
uni¬able terms
some or all of the variables in t1 and t2 such that the terms that result from
the substitution are syntactically identical terms.


. 93
( 107 .)