<<

. 96
( 107 .)



>>

such that Mh |= S for all ¬rst-order sentences S assigned true by h.
This construction of the structure Mh from the truth assignment h is
sometimes called the Henkin construction. ¬nal steps
Let us show how we can use these results to prove the Completeness
Theorem. Assume that T and S are all from the original language L
and that S is a ¬rst-order consequence of T . We want to prove that
T S. By assumption, there can be no ¬rst-order structure in which all
of T ∪ {¬S} is true. By the Henkin Construction there can be no truth
assignment h which assigns true to all sentences in T ∪ H ∪ {¬S}; if
there were, then the ¬rst-order structure Mh would make T ∪ {¬S} true.
Hence S is a tautological consequence of T ∪ H.3 The Completeness
Theorem for propositional logic tells us there is a formal proof p of S
from T ∪ H. The Elimination Theorem tells us that using the quanti¬er
rules, we can transform p into a formal proof p of S from premises in
T . Hence, T S, as desired.
The next few sections of this chapter are devoted to ¬lling in the details
of this outline. We label the sections to match the names used in our outline.


Section 19.2
Adding witnessing constants
Given any ¬rst-order language K, we construct a new ¬rst-order language K .
The language K will have the same symbols as K except that it will have a
lot of new constant symbols. For example, if K is our blocks language, then
in K will be able to say things like the following:
1. ∃x (Small(x) § Cube(x)) ’ Small(c1 ) § Cube(c1 )
2. ∃z (z = a § z = b) ’ (c2 = a § c3 = b)
3. ∃y Between(y, a, b) ’ Between(c3 , a, b)
4. ∃x ∃y Between(a, x, y) ’ ∃y Between(a, c4 , y)
More generally, for each w¬ P of L with exactly one free variable, form a new
constant symbol cP , making sure to form di¬erent names for di¬erent w¬s.
This constant is called the witnessing constant for P. witnessing constant
for P
3 In this chapter we are using the notions of tautology and tautological consequence
de¬ned in Section 10.1, in which every sentence starting with a quanti¬er is treated as
atomic.




Section 19.2
530 / Completeness and Incompleteness


You might wonder just how we can form all these new constant symbols.
How do we write them down and how do we make sure that distinct w¬s
get distinct witnessing constants? Good question. There are various ways we
could arrange this. One is simply to use a single symbol c not in the language
K and have the new symbol be the expression c with the w¬ as a subscript.
Thus, for example, in our above list, the constant symbol c1 would really be
the symbol
c(Small(x)§Cube(x))
This is a pretty awkward symbol to write down, but it at least shows us how
we could arrange things in principle.
The language K consists of all the symbols of K plus all these new wit-
the language K
nessing constants. Now that we have all these new constant symbols, we can
use them in w¬s. For example, the language K allows us to form sentences
like
Smaller(a, cBetween(x,a,b) )
But then we also have sentences like

∃x Smaller(x, cBetween(x,a,b) )

so we would like to have a witnessing constant symbol subscripted by

Smaller(x, cBetween(x,a,b) )

Unfortunately, this w¬ , while in K , is not in our original language K, so we
have not added a witnessing constant for it in forming K .
Bummer. Well, all is not lost. What we have to do is to iterate this con-
struction over and over again. Starting with a language L, we de¬ne an in¬nite
sequence of larger and larger languages

L0 ⊆ L1 ⊆ L2 ⊆ . . .

where L0 = L and Ln+1 = Ln . That is, the language Ln+1 results by applying
the above construction to the language Ln . Finally, the Henkin language LH
the Henkin language
LH for L consists of all the symbols of Ln for any n = 0, 1, 2, 3, . . ..
Each witnessing constant cP is introduced at a certain stage n ≥ 1 of this
construction. Let us call that stage the date of birth of cP . When we come to
date of birth of
witnessing constants proving the Elimination Theorem it will be crucial to remember the following
fact, which is obvious from the construction of LH .

Lemma 1. (Date of Birth Lemma) Let n + 1 be the date of birth of cP . If Q
is any w¬ of the language Ln , then cP does not appear in Q.




Chapter 19
The Henkin theory / 531



Exercises


19.1 This exercise and its companion (Exercise 19.2) are intended to give you a better feel for why
 we have to keep iterating the witnessing constant construction. It deals with the constants that
would turn out to be important if our original set T contained the sentence ∀x ∃y Larger(x, y).
Write out the witnessing constants for the following w¬s, keeping track of their dates of birth.
The constant symbol a is taken from the original language L.
1. Larger(a, x)
2. Larger(c1 , x), where c1 is your constant from 1.
3. Larger(c2 , x), where c2 is your constant from 2.
4. Larger(c3 , x), where c3 is your constant from 3.



Section 19.3
The Henkin theory

We have added witnessing constants for each w¬ P with exactly one free
variable. The free variable of P is going to be important in what follows so we
often write the w¬ in a way that reminds us of the free variable, namely, as
P(x).4 Consequently, its witnessing constant is now denoted by cP(x) . Notice
that by iterating our construction in¬nitely often, we have managed to arrange
things so that for each w¬ P(x) of LH with exactly one free variable, the
witnessing constant cP(x) is also in LH . This allows us to form the sentence

∃x P(x) ’ P(cP(x) )

in LH . This sentence is known as the Henkin witnessing axiom for P(x). The witnessing axioms
intuitive idea is that ∃x P(x) ’ P(cP(x) ) asserts that if there is something that
satis¬es P(x), then the object named by cP(x) provides an example (or “wit-
ness”) of one such.

Lemma 2. (Independence lemma) If cP and cQ are two witnessing constants
and the date of birth of cP is less than or equal to that of cQ , then cQ does
not appear in the witnessing axiom of cP .

Proof: If the date of birth of cP is less than that of cQ , the result
follows from the date of birth lemma. If they have the same date
4 Really,
we should be writing this as P(ν), where ν can be any of the variables of our
language, not just the variable x. We are using x here as a representative variable of our
language.




Section 19.3
532 / Completeness and Incompleteness


of birth, it follows from the fact that di¬erent w¬s of a language K
have distinct new witnessing constants in K .

De¬nition The Henkin theory H consists of all sentences of the following ¬ve
Henkin theory H
forms, where c and d are any constants and P(x) is any formula (with exactly
one free variable) of the language LH :
H1: All Henkin witnessing axioms

∃x P(x) ’ P(cP(x) )

H2: All sentences of the form

P(c) ’ ∃x P(x)

H3: All sentences of the form

¬∀x P(x) ” ∃x ¬P(x)

H4: All sentences of the form
c=c

H5: All sentences of the form

(P(c) § c = d) ’ P(d)

Notice that there is a parallel between these sentences of H and the quan-
connection to
quanti¬er rules ti¬er and identity rules of F:
—¦ H1 corresponds roughly to ∃ Elim, in that both are justi¬ed by the
same intuition,

—¦ H2 corresponds to ∃ Intro,

—¦ H3 reduces ∀ to ∃,

—¦ H4 corresponds to = Intro, and

—¦ H5 corresponds to = Elim.
Just what this correspondence amounts to is a bit di¬erent in the various cases.
For example, the axioms of types H2-H5 are all ¬rst-order validities, while this
is not true of H1, of course. The witnessing axioms make substantive claims
about the interpretations of the witnessing constants. The following result,
while not needed in the proof of completeness, does explain why the rest of
the proof has a chance of working.



Chapter 19
The Henkin theory / 533



Proposition 3. Let M be any ¬rst-order structure for L. There is a way to
interpret all the witnessing constants in the universe of M so that, under this
interpretation, all the sentences of H are true.

Proof: (Sketch) The basic idea of the proof is that if M |= ∃x P(x),
then pick any element b of the domain that satis¬es P(x) and let the
witnessing constant cP(x) name b. If M |= ¬∃x P(x), then let cP(x)
name any ¬xed element of the domain. This takes care of the axioms
of type H1. As for the other axioms, they are all logical truths, and
so will turn out to be true no matter how we interpret the new
constants.

The proof of Proposition 3 is illustrated in Exercise 19.6. The proposition
shows that our strategy has a chance of working by allowing us to show that
even though the theory H says substantive things about the witnessing con-
stants, it does not add any substantive new claims that can be formulated
in the original language L. More precisely (as we ask you to show in Exer-
cise 19.9) if a sentence S of L is a ¬rst-order consequence of T ∪ H, then it
is a ¬rst-order consequence of T alone. This at least makes the Elimination
Theorem plausible.

Exercises


19.2 Write out the witnessing axioms associated with the w¬s in Exercise 19.1.

The next three exercises are designed to help you understand how the theory H ¬lls the gap between
tautological and ¬rst-order consequence. For these exercises we take L to be the blocks language and T
to consist of the following set of sentences:

T = {Cube(a), Small(a), ∃x (Cube(x) § Small(x)) ’ ∃y Dodec(y)}

19.3 19.4
Give informal proofs that both of the Give informal proofs that none of the
 
following are ¬rst-order consequences of following is a tautological consequence
T: of T :
1. ∃x (Cube(x) § Small(x)) 1. ∃x (Cube(x) § Small(x))
2. ∃y Dodec(y) 2. ∃y Dodec(y)
3. Dodec(cDodec(y) )

19.5 Give informal proofs that the sentences
 in Exercise 19.4 are all tautological con-
sequences of T ∪ H.




Section 19.3
534 / Completeness and Incompleteness


19.6 Use Tarski™s World to open Henkin™s Sentences. Take the constants c and d as shorthand for
‚| the witnessing constant cCube(x) and cDodec(x)§Small(x) , respectively.
1. Show that these sentences are all members of H. Identify the form of each axiom from
our de¬nition of H.

2. By (1) and Proposition 3, any world in which c and d are not used as names can be
turned into a world where all these sentences are true. Open Henkin™s World. Name some
blocks c and d in such a way that all the sentences are true. Submit this world.

19.7 Show that for every constant symbol c of LH there is a distinct witnessing constant d such
 that c = d is a tautological consequence of H. [Hint: consider the w¬ c = x.]

19.8 Show that for every binary relation symbol R of L and all constants c, c , d, and d of LH , the
 following is a tautological consequence of H:

(R(c, d) § c = c § d = d ) ’ R(c , d )

<<

. 96
( 107 .)



>>