# 15.5: Compactness, Identity, and Functions

In this section I am going to get started in cleaning up some details. But I am going to let you do most of the work. Students of truth trees and of derivations will be able to apply the material of this section appropriately to what they have learned.

My completeness proofs for predicate logic assumed a finite set of sentences, Z. To get a full statement of completeness, where Z can be infinite, we need to show that the compactness result, T8, which we proved in chapter 14, also holds for predicate logic. To accomplish this we need to modify the idea of a tree of truth value assignments.

Here's what we do. We can consider all possible closed atomic sentences written out in some definite order: the first atomic sentence letter, the second, the first one place predicate with the first name, the second . . . : 'A', 'B', 'Pa', 'Pb', 'Raa'. . . . To make sure that this is possible, again consider that we could write each such description of the atomic sentences in English and order them as in a dictionary.

Say the closed atomic sentences are XI, X2, XS, . . . Then we can diagram all possible truth value assignments to these atomic sentences in the form of a tree:

The third line will catalogue the alternative truth values for X; underneath all the possibilities covered in lines 1 and 2, and so on.

Note that each path through this tree represents an interpretation, indeed, just the sort of interpretations represented by open paths on a truth tree or semantic tableau derivation. We have seen. in the com~leteness proofs, how there must be at least one such interpretation for each consistent finite set of sentences. We now proceed very much as we did in predicate logic. Let Z be an infinite set of sentences all of the finite subsets of which are consistent. We list the sentences in some definite order, and consider the initial finite segments of this ordering: Z,, Zp, 5, . . . As we work down the lines of the tree, we close branches which conflict with some sentences in one of the 2;. Since all of the Z; are consistent. for each line of the tree, there will be an open branch reaching down to that line. Koenig's lemma tells us that there is then an infinite path through the tree. But (if you make the right sort of arrangement of when paths get closed) you will see that this infinite path represents an interpretation which makes true all the sentences in all the Zi. That is, this interpretation is a model of Z.

Exercise \(\PageIndex{1}\)

EXERCISE 15-25. Following the suggestions. of the argument sketch given in the last paragraph, give a detailed proof of compactness for predicate logic.

Actually, we have done the work to prove the L**owenheim**** Skolem Theorem**, a much stronger result, of fundamental importance in logic and set theory. In all my discussion of infinite interpretations, I have not mentioned the fact that there are different kinds of infinities. The infinity of the integers is the smallest, called, for obvious reasons, a Countable Infinity. However, other infinities are, in a certain sense, "larger." Consider, for example, the infinity of the real numbers (numbers representable by a finite or an infinite decimal fraction, such as 27.75283 . . .). The infinity of the real numbers is larger, or Uncountable, in the sense that there is no one-to-one correspondence between the integers and the real numbers. We cannot list the real numbers with the integers the way we can an infinite set of sentences.

The Lowenheim Skolem theorem says that if a set of sentences has a model with a finite, countable, or uncountable domain, then it has a finite or a countable model. For finite sets of sentences, these models are generated by open paths on a truth tree or semantic tableau derivation. If a finite set has a model (finite, countable, or uncountable) then there is an open path. But then the open path represents a finite or countably infinite model. The compactness theorem then shows how the same is true of infinite consistent sets of sentences. (If our object language does not include identity, then there is always a countable model. But '=' allows us to write a sentence which, for example, is only true in an interpretation with exactly one object. Can you produce such a sentence?)

My soundness and consistency proofs assumed that our object language contained neither identity nor function symbols. For the moment, let's consider just identity. To begin with, we must refine the characterization of an interpretation with requirements which should seem natural if '=' really means 'identity':

D20' (Interpretations for languages with identity): An interpretation is as described in D20 with the following two additional requirements:

a) A sentence of the form s=t is true in an interpretation iff s and t name the same object.

b) For all atomic sentences of the form R(s,t), if s=t is true in an interpretation, then R(s,t) and R1(s,t) have the same truth value in the interpretation, where R1(s,t) arises from R(s,t) by replacing any number of occurrences of s with t or oft with s.

Clause b) covers sentences such as 'Qab': If 'a=c' is true in an interpretation, then 'Qab' and 'Qcb' have the same truth value in the interpretation.

A good many of the semantical facts surrounding identity turn on the following lemma, which simply generalizes clause b) to the case of any closed sentence:

L40: Let I be an interpretation for predicate logic with identity. Then, for all sentences of the form R(s,t), if s=t is true in I, R(s,t) and R1(s,t) have the same truth value in I, where R1(s,t) arises from R(s,t) by replacing any number of occurrences of s with t or oft with s. / I 1 1

15-26. Prove LAO.

You are now in a position to examine how our soundness proofs need to be modified if our language includes identity. Identity involves new rules, the roles of which need to be checked in the proofs.

15-27. (Trees) Show that the truth tree = rule is downwardly correct. To treat the f rule, note that we can reconstrue it in the following way: Whenever a sentence of the form sf s appears on a branch, also write the sentence s= s on that branch. Explain why this rule comes to the same as the # rule as stated in chapter 9. Prove that the rule in this form is downwardly correct.

15-28. (Derivations) State and prove rule soundness for the two derivation rules for identity. Comment on whether and, if so, how these rules require any changes in the inductive proof of soundness for derivations.

We can turn now to completeness. For semantic tableau derivations we must add two new parts to the rules for sequential generation, corresponding exactly to the =I and = E rules: Whenever a name s occurs on a tableau, include the sentence s = s on the sequentially generated tableau. And if two sentences of the form s=t and R(s,t) appear on a tableau, include the sentences Rt(s,t) on the sequentially generated tableau. Then, for both trees and semantic tableau derivations, we change how we read an interpretation off an open branch. Before, every name was assigned a distinct object. Now each name will be assigned a distinct object unless a sentence of the form s=t appears on the branch. Then s and t are assigned the same object. This corresponds to clause a) in D20'. Clause b) in D20' is already ensured by the identity rules for trees and for tableau generation.

Exercise \(\PageIndex{1}\): Trees

EXERCISES 15-29. Show that clause b) of D20' will be satisfied in the interpretation represented by an open branch. Comment on the status of lemma L40 in describing an open branch. That is, note the way in which, in effect, proof of upward adequacy automatically covers the work done by lemma L40. Then check that the tree method with identity is upwardly adequate. Though intuitively quite clear, a formal proof requires care, since the input and output sentences for the = rule all have the same predicates and connectives, so that none of our prior methods of attributing lengths to sentences will apply here.

Exercise \(\PageIndex{1}\): Derivations

15-30. Show that clause b) of D20' will be satisfied in the interpretation represented by an open branch. Comment on the status of lemma L40 in describing an open branch. That is, note the way in which, in effect, proof of lemma L37 automatically covers the work done by lemma L40. Then check that lemma L37 is still correct. Just as with the case for trees, proof requires care, since none of our prior means of assigning lengths to sentences will work here.

Finally, let's take a brief look at function symbols. Again, we must extend the definition of an interpretation:

D20" (Interpretations for languages with function symbols): An interpretation is as described in D20 or D201, with the following addition: For each function symbol, f, and each object, o, in the domain of the interpretation, the interpretation assigns a unique object o' = f(o), as the value off applied to o. If s is a closed term referring to object o*, then f(s) is a term referring to f(o*).

The last sentence in D20" constitutes a recursive definition. If s is a name, referring to o, then f(s) refers to f(o), ff(s) refers to ff(o), and so on.

As with identity, once we have made this extension of the notion of an interpretation, mbst of the work is done.

EXERCISES 15-31. (Trees) Check the downward correctness of the quantifier rules when the language includes function symbols.

15-32. (Derivations) Check the proof of rule soundness for the quantifier rules when the language includes function symbols.

15-33. (Trees) Check that the proof of upward adequacy works when interpretations are read off open branches in accord with definition D20".

15-34. (Derivations) Check lemma L37 when interpretations are read off open branches in accord with definition D20".

### Contributors

Paul Teller (UC Davis). The Primer was published in 1989 by Prentice Hall, since acquired by Pearson Education. Pearson Education has allowed the Primer to go out of print and returned the copyright to Professor Teller who is happy to make it available without charge for instructional and educational use.