ńņš. 98 |

Section 19.4

540 / Completeness and Incompleteness

19.18 Open Exercise 19.17 again. Take the constant c as shorthand for the witnessing constant cCube(x) .

Ć‚ Take T to be the ļ¬rst two premises of this proof. We saw in Exercise 19.6 that the other

sentences are all members of H. The Elimination Theorem thus applies to show that you could

transform your proof from the preceding exercise into a proof from the ļ¬rst two premises, one

that does not need the remaining premises. Open Exercise 19.18 and give such a proof. [If you

were to actually transform your previous proof, using the method we gave, the result would be

a very long proof indeed. Youā™ll be far better oļ¬ giving a new, direct proof.]

Section 19.5

The Henkin Construction

Proposition 3 allows us to take any ļ¬rst-order structure for L and get from it

one for LH that makes all the same sentences true. This, of course, gives rise

to a truth assignment h to all the sentences of LH that respects the truth-

functional connectives: just assign true to all the sentences that are true

in the structure, false to the others. (You may recall that you were asked

to prove this in Exercise 18.11.) The main step in the Henkin proof of the

Completeness Theorem is to show that we can reverse this process.

Theorem (Henkin Construction Lemma) Let h be any truth assignment for

Henkin Construction

Lemma LH that assigns true to all the sentences of the Henkin theory H. There is a

ļ¬rst-order structure Mh such that Mh |= S for all sentences S assigned true

by the assignment h.

In giving the proof of this result, we will assume that our language L

contains only relation symbols and constants, no function symbols. We will

return at the end to explain how to modify the proof if there are function

symbols. The proof of this theorem has two parts. We must ļ¬rst show how

to construct Mh from h and then show that Mh does indeed make true all

constructing Mh the sentences to which h assigned true. To construct Mh , we must do three

things. We must deļ¬ne the domain D of Mh , we must assign to each n-ary

relation symbol R some set R of n-tuples from D, and we must assign to

each name c of LH some element of D. We ļ¬rst give the basic idea of the

construction. This idea wonā™t quite work, so it will have to be modiļ¬ed, but

itā™s useful to see the ļ¬‚awed idea before digging into the details that correct

the ļ¬‚aw.

The basic (ļ¬‚awed) idea in constructing the ļ¬rst-order structure M is to

use the construction of Exercise 18.12, but to count on the fact that h assigns

true to all the sentences in H to get us past the quantiļ¬ers. In more detail,

we build M as follows:

Chapter 19

The Henkin Construction / 541

ā—¦ For the domain of M, use the set of constant symbols of LH .

ā—¦ Let each constant be a name of itself.

ā—¦ To specify the interpretation of a (binary, say) relation symbol R, take

the set R of pairs c, d of constant symbols such that h assigns true

to the sentence R(c, d).

This deļ¬nes a perfectly good ļ¬rst-order structure M. We would like to be

able to prove that M makes true all and only the sentences to which h assigns

true. That is, we would like to show that for any sentence S of LH , M |= S if

and only if h(S) = true. The natural way to prove this would be by induction

on the complexity of the sentence S. Many of the details of the proof work

out. The main problem has to do with identity statements! The problem is a problem: identity

that inevitably there are distinct constants c and d such that h assigns true

to c = d. (See Exercise 19.7.) But M makes this sentence false since c and d

are distinct and name themselves.

This problem is one that is quite familiar in mathematical situations. What

we need to do is to form what mathematicians call a āquotientā of M. What

this means is that we must āidentifyā various elements that M considers dis-

tinct. This is just the sort of thing that equivalence relations and equivalence equivalence classes to

the rescue

classes (studied in Chapter 15) are designed to do, and is the reason we in-

cluded them in our discussion of sets.

Deļ¬ne a binary relation ā” on the domain of M (i.e. on the constants of

LH ) as follows:

c ā” d if and only if h(c = d) = true.

Lemma 11. The relation ā” is an equivalence relation.

Proof: This follows immediately from Exercise 19.20.

From this it follows that we can associate with each constant c its equiv-

alence class

[c] = {d | c ā” d}

This allows us to deļ¬ne our desired ļ¬rst-order structure Mh : deļ¬nition of Mh

ā—¦ The domain D of our desired ļ¬rst-order structure Mh is the set of all

such equivalence classes.

ā—¦ We let each constant c of LH name its own equivalence class [c].

Section 19.5

542 / Completeness and Incompleteness

ā—¦ We interpret relation symbols R as follows. For this deļ¬nition letā™s again

assume that R is binary, just to make the notation simpler. Then the

interpretation of R is the set

{ [c], [d] | h(R(c, d)) = true}

It you think about it a second, you will see that there is something not quite

clear about the deļ¬nition of R in the last item. We have to say which pairs

a, b of equivalence classes are in this relation. What happens if a = [c] = [c ]

and b = [d] = [d ]? If we had h(R(c, d)) = true but h(R(c , d )) = false

our deļ¬nition would not really make sense. Thus, we just make sure that this

cannot happen.

Lemma 12. If c ā” c , d ā” d and h(R(c, d)) = true then h(R(c , d )) = true.

Proof: By Exercise 19.8, the following is a tautological consequence

of the Henkin theory H:

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

Since h assigns everything in H true, and it assigns true to each

conjunct of R(c, d) ā§ c = c ā§ d = d , it must also assign true to

R(c , d ).

This lemma shows that our deļ¬nition of Mh does make sense after all.

The proof of the Henkin Construction Lemma will be completed by proving

the following result.

Lemma 13. For any sentence S of LH , Mh |= S if and only if h(S) = true.

the crucial lemma

Proof: The basic idea of this proof is to use induction. We have

explicitly deļ¬ned the structure Mh to make sure the claim is true

for atomic sentences. Further, truth assignments work the same way

on truth-functional connectives as the deļ¬nition of truth in a ļ¬rst-

order structure. So the only possible problems are the quantiļ¬ers and

these, we will see, are taken care of by the quantiļ¬er axioms in H.

The only mild complication to this outline is that the quantiļ¬er ā is

not handled directly, but indirectly through the deMorgan sentences

in H:

Ā¬āx P(x) ā” āx Ā¬P(x)

What makes this a complication is that the most obvious measures

of complexity, say by length or number of logical operations, would

Chapter 19

The Henkin Construction / 543

count āx P(x) as simpler than the sentence āx Ā¬P(x), whereas any

induction proof is going to need to make sure that the latter works

out right before it can be sure that the former does. We get around

this by deļ¬ning a diļ¬erent measure of complexity for wļ¬s. Namely,

we deļ¬ne the complexity of an atomic wļ¬ to be 0, the complexity

of Ā¬P and āx P to be one greater than the complexity of P, the

complexity of P ā§ Q, P āØ Q, and P ā’ Q to be one greater than the

maximum of that of P and Q, but the complexity of āx P to be three

greater than that of P. Here is a little table showing the complexity

of some wļ¬s in the blocks language:

wļ¬ complexity

Small(x) 0

(x = a) 0

Ā¬(x = a) 1

Small(x) ā’ Ā¬(x = a) 2

Ā¬(Small(x) ā’ Ā¬(x = a)) 3

āx Ā¬(Small(x) ā’ Ā¬(x = a)) 4

āx (Small(x) ā’ Ā¬(x = a)) 5

Notice that the complexity of a wļ¬ P(x) is the same as that of P(c).

(See, for example, Exercise 19.21.) With this deļ¬nition of complexity,

we can prove the lemma, by induction on the complexity of sentences.

As remarked above, the case where the complexity is 0 is true by the

way we deļ¬ned the structure Mh .

Assume that the lemma holds for all sentences of complexity ā¤ k and

let S have complexity ā¤ k + 1. There are several cases to consider,

depending on the main connective or quantiļ¬er of S. We treat one

of the truth-functional cases, as these are all similar, and then both

of the quantiļ¬er cases.

Case 1. Suppose S is P āØ Q. If Mh |= S, then at least one of P or Q is

true. Assume that P is true. Since the complexity of S is ā¤ k + 1, the

complexity of P is ā¤ k, so by induction hypothesis, h(P) = true. But

then h(P āØ Q) = true, as desired. The proof in the other direction

is similar.

Case 2. Suppose that S is āx P(x). We need to show that Mh |=

āx P(x) if and only if h assigns the sentence true. Assume ļ¬rst that

the sentence is true in Mh . Then since every object in the domain is

denoted by some constant, there is a constant c such that Mh |= P(c).

But since the complexity of this sentence is less than that of S, our

Section 19.5

544 / Completeness and Incompleteness

induction hypothesis shows us that h(P(c)) = true. But now recall

that our theory H contains the sentence

P(c) ā’ āx P(x)

so h assigns this sentence true. But then, by the truth table for ā’,

h assigns true to āx P(x), as desired.

The reverse direction of this case is very similar, but it uses the

Henkin witnessing axiom for P(x). Here is how it goes. Assume that

h assigns true to āx P(x). We need to show that Mh |= āx P(x). But

recall that h assigns true to the witnessing axiom

āx P(x) ā’ P(cP(x) )

Hence, by the truth table for ā’, h assigns true to P(cP(x) ). Hence,

by induction, this sentence is true in Mh . But then āx P(x) is true

as well.

Case 3. Finally, let us assume that S is āx P(x). We need to prove

that this sentence is true in Mh if and only if h assigns the sentence

true. Assume ļ¬rst that S is true in Mh . Then āx Ā¬P(x) is false in

Mh . But then, by induction, h assigns false to this sentence. But

recall that H contains the sentence

Ā¬āx P(x) ā” āx Ā¬P(x)

From this it follows that h assigns false to Ā¬āx P(x) and hence true

to āx P(x), as desired. The proof in the other direction is entirely

similar.

Function symbols If there are function symbols in the original

language, we have to explain how to interpret them in our struc-

ture. Suppose, for example, that our language contains a one-place

function symbol f. How should we deļ¬ne its interpretation f ? In par-

ticular, if d is some constant symbol, what equivalence class should

f ([d]) be? What comes to our rescue here is the witnessing constant

for the sentence

āx [f(d) = x]

We can deļ¬ne f ([d]) to be the equivalence class [cf(d)=x ] of the wit-

nessing constant cf (d)=x . Since

āx [f(d) = x] ā’ f(d) = cf(d)=x

Chapter 19

The Henkin Construction / 545

is in H, it is not hard to check that all the details of the proof then

work out pretty much without change.

This completes our ļ¬lling in of the outline of the proof of the Completeness

Theorem.

Exercises

19.19 Use Tarskiā™s World to open Henkin Construction. This ļ¬le lists eight sentences. Letā™s suppose

Ć‚| that the predicates used in these sentences (Cube, Dodec, and Small) exhaust the predicates of

L. (In particular, we banish = to avoid the complications it caused in the proof of the Henkin

Construction Lemma.) Let h be any truth assignment that assigns true to all these sentences.

Describe the ļ¬rst-order structure Mh . (How many objects will it have? What will they be

called? What shape and size predicates will hold of them?) Use Tarskiā™s World to build a world

that would be represented by this ļ¬rst-order structure. There will be many such. It should, of

ńņš. 98 |