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 )