# 14.2: Compactness and Infinite Sets of Premises

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

In my proofs of completeness, the statement that if ZkX, then ZtX, I assumed that Z is finite. But in my original definition of z~X and ZtX, I allowed Z to be infinite. Can we lift the restriction to finite Z in the proofs of completeness?

There is no problem with t. By ZtX, for infinite Z, we just mean that there is a proof which uses some finite subset of Z as premises. Counting Z as a subset of itself, this means that (whether Z is finite or infinite) X can be derived from Z iff X can be derived from some finite subset of Z. That is (using 'Z'CZ' to mean that Z' is a subset of Z)

(1) ZkX iff (3Z1)(Z'CZ and Z' is finite and Z'kX).

EXERCISE 14-1. Consider a tree that looks like this:

This tree differs from the ones we have been considering because it allows Infinite Branching-that is, from one node (here, the first node) infinitely many new branches emerge. These branches also extend farther and farther down as you move from left to right, so that the tree extends infinitely downward as well as to the right. For each integer, n, there is an open path that extends to the nth line. But there is no infinite path through the tree!

This example helps to show that Koenig's lemma is not just a trivial truth. Thinking about this example will also help to make sure you understand the proof of Koenig's lemma.

Explain why the proof of Koenig's lemma breaks down for trees with infinite branching. My proof actually assumed at most double branching. Rewrite the proof to show that Koenig's lemma works when the tree structure allows any amount of finite branching.

What we need is a similar statement for 1:

(2) Z~X iff (3Z1)(Z'C Z and Z' is finite and ~'kx).

(1) and (2) will enable us quickly to connect completeness for finite Z' with completeness for infinite Z. Using L1 we see that (2) is equivalent to

(3) ZU{-X) is inconsistent iff (3Zr)(Z'CZ and Z' is finite and Z'U{-X) is inconsistent).

Compactness is just (3), but stated slightly more generally, without the supposition that the inconsistent set has to include the negation of some sentence:

T8 (Compactness): Z is inconsistent iff Z has an inconsistent finite subset. Equivalently, Z is consistent iff all its finite subsets are consistent.

Compactness with the help of L1 will immediately give us

T9 (Completeness): If Z~X, then ZtX, where Z now may be infinite.

t may be derivability by trees or derivations (or, indeed many other systems of proof). All that we require here is (l), compactness, and completeness for finite sets Z in the system of proof at hand.

EXERCISES

14-2. Prove the equivalence of the two statements of compactness in T8.

14-3. Prove completeness for arbitrary sets of sentences. That is, prove that if Z~X, then ZtX, where Z may be infinite. Do this by using compactness and L1 to prove (2). Then use (2) and (I), together with the restricted form of completeness we have already proved (with Z restricted to being a finite set) to lift the restriction to finite Z.

The key here is compactness, and the key to compactness is Koenig's lemma. In outline, we will create a tree the paths of which will represent lines of a truth table. Finite subsets of an infinite set of sentences, Z, will be made true by paths (truth table lines) reaching down some finite number of lines in our tree. Koenig's lemma will then tell us that there is an 14-2. Compactness and Infinite Sets ofPremires 2 17 infinite path, which will provide the interpretation making everything in Z true, showing Z to be consistent.

Here goes. Since our language has infinitely many sentence letters, let's call the sentence letters 'A,', 'A2', . . . , 'A,'. . . . Consider the tree which starts like this:

Each branch through the third line represents one of the eight possible truth value assignments to 'A,', 'A2', and 'As'. Branch (1) represents 'A,', 'A;, and 'A3' all true. Branch (2) represents 'A,' and 'A2' true and 'A3' false. Branch (3) represents 'Al' true, 'A2' false, and 'A3' true. And so on. Line 4 will extend all branches with the two possible truth value assignments to 'A;, with 'A; true on one extension and 'A; false on the other. Continuing in this way, each initial segment of a branch reaching to line n represents one of the truth value assignments to 'A,' through 'A,', and every possible truth value assignment is represented by one of the branches.

Now let us suppose that the set, Z, is composed of the sentence logic sentences X1, Xp, . . . , X, . . . , all written with the sentence letters 'A,', 'A,', . . . , 'A,'. . . . Let Z, = {XI, Xp, . . . XJ. That is, for each n, Z, is the finite set composed of the first n sentences in the list XI, XI. . . . Finally, let us suppose that each Z, is consistent, that is, that Z, has a model, an interpretation, I, which assigns truth values to all sentence letters appearing in the sentences in Z, and which makes all the sentences in Z, true.

Our tree of truth value assignments will have initial path segments which represent the models which make the 2,'s consistent. Koenig's lemma will then tell us that there will be an infinite path which makes all the XI, Xp, . . . . true. To show this carefully, let us prune the truth value tree. For each Z,, starting with ZI, let in be the first integer such that all the sentence letters in the sentence in Z, occur in the list 'A,', 'A2', . . . , 'Ai,'. Then the initial paths through line in will give all the possible interpretations to the sentences in 2,. Mark as closed any path which does not 418 Koenig'r Lemma, Compactness, and Generalwtion to Injnite Sets of Premises 14-2. Compactness and lnjnite Sets of Premises 2 19 represent a model of Z,, that is, which makes any sentence in Z, false. Since each Z, is consistent, there will be at least one open path reaching to line in.

I have provided an outline of a proof of lemma 24:

L24: Let XI, X, . . . 2C,, be an infinite sequence of sentences, each initial subsequence of which is consistent. Let T be a tree the paths which represent all the truth value assignments to the sentence letters occurring in XI, X,. . . . Let each path be closed at line in if the path's initial segment to line in makes any sentence XI through X. false, where line in is the first line paths to which assign truth values to all sentence letters in XI through %. Then, for every line in T, there is an open path that reaches to that line.

EXERCISE 14-4. Prove lemma L24. Wait a minute! What remains to be done to prove L24? That depends on how thorough you want to be. There are details I didn't discuss. What if the vocabulary used is finite? What if the vocabulary of some Z, already includes the vocabulary of Z,+,? More interestingly, perhaps you can find a simpler proof of L24 than the one I suggested. Or better still, you may be able to reformulate L24 so that your L24 is less complicated to prove but still functions to make the proof of compactness easy, in something like the way I will describe in the following paragraphs.

Proving compactness is now easy. Suppose that all of 2's finite subsets are consistent. If Z itself is finite, then, because any set counts as one of its own subsets, Z is consistent. If Z is infinite, we can order its sentences in some definite order. For example, write out each connective and parenthesis with its English name ('disjunction', 'negation', 'right parenthesis', etc.) and think of each sentence logic sentence thus written out as a very long word. Then order the sentences (as words) as one does in a dictionary. (This is called a Lexicographical Ordering.) Since all finite subsets of Z are consistent, each initial segment of the ordered list of sentences is a consistent set. L24 applies to tell us that there is a tree, the initial finite open paths of which represent models of the initial segments of the list of sentences. L24 further tells us that for each line of the tree, there will be at least one open path that reaches that line. Koenig's lemma then tells us that there will be at least one path through the whole tree (an infinite path if the tree is infinite). This path will represent a model for all the sentences in the set, establishing the consistency of Z.

EXERCISES 14-5. Complete the proof of compactness by showing that if Z is consistent, then so are all of its finite subsets. 14-6. In my proof of soundness for trees I also limited Z in the statement ZkX to be a finite set. There was no reason for doing so other than the fact that for trees it was convenient to treat soundness and completeness together, and I needed the restriction to finite Z in the proof of completeness.

Assume soundness for finite Z, that is, assume that for all finite Z, if ZkX, then ZkX. Prove the same statement for infinite Z. Your proof will be perfectly general; it will not depend on which system of proof is in question. You will not need to use compactness, but you will need to use the result of exercise 10-9. I

CHAPTER CONCEPTS

Here are this chapter's principal concepts. In reviewing the chapter, be sure you understand them.

1. Tree Structure
2. Node of a Tree
3. Path (or Branch) in a Tree
4. Koenig's Lemma
5. Compactness
6. Finite Branching
7. Infinite Branching
8. Tree of Truth Value Assignments
9. Lexicographical Ordering