# 14.1: Koenig's Lemma

- Page ID
- 1891

My proofs of completeness, both for trees and for derivations, assumed finiteness of the set Z in the statement ~k-X. Eliminating this restriction involves something called 'compactness', which in turn is a special case of a general mathematical fact known as 'Koenig's lemma'. Since we will need Koenig's lemma again in the next chapter, we will state and prove it in a form general enough for our purposes.

Suppose we have a branching system of points, or Nodes, such as the following:

The nodes are connected by branching lines running downward; these 212 are called Paths, or Branches. I have numbered the horizontal lines to help in referring to parts of the tree. We will consider only tree structures which have Finite Branching-that is, from any one node, only finitely many branches can emerge. To keep things simple, I will always illustrate with double branching, that is, with at most two branches emerging from a node. The restriction to two branches won't make an important difference.

Truth trees are one example of such a tree structure. Semantic tableau derivations are another, with each branch representing the formation of a new subderivation and each node representing all the tableaux on a subderivation before starting new subderivations. Some of the paths end with a 'x ', as when we close a path in a truth tree or close a tableau in a tableau derivation. We say that such a path is Closed. A tree might have only finitely many horizontal lines, That is, there might be a line number, n, by which all paths have ended, or closed. Or such a tree might have infinitely many lines. What we want to prove is that if such a tree is infinite (has infinitely many horizontal lines with at least one open path extending to each line), then there is an infinite path through the tree.

Perhaps this claim will seem obvious to you (and perhaps when all is said and done it is obvious). But you should appreciate that the claim is not just a trivial logical truth, so it really does call for demonstration. The claim is a conditional: If for every line there is an open path extending to that line, th there is an open path which extends to every line. The antecedent of the conditional is a doubly quantified sentence of the form (Vu)(3v)R(u,v). The consequent is the same, except that the order of the quantifiers has been reversed: (3v)(Vu)R(u,v). Conditionals of this form are not always true. From the assumption that everyone is loved by someone, it does not follow that there is someone who loves everyone. The correctness of such conditionals or their corresponding arguments requires special facts about the relation R.

The tree structure provides the special facts we need in this case. Let's assume that we have an infinite tree, that is, a tree with infinitely many horizontal lines and at least one open path extending to each line. The key is to look at infinite subtrees. For example, look at line 3. The first, third, and fourth nodes can each be viewed as the first node in its own subtree, that is, the system of paths which starts with the node in question. The first node of line 3 heads a subtree which does not end, at least not as far as we can tell by as much of the tree as I have drawn. The same is true for the third node of line 3. But the fourth node heads a subtree that we can see is finite: All paths starting from that node close.

Now consider all of the nodes of line 3 again. Suppose that all of the subtrees headed by these nodes are finite. Then the whole tree would be finite. Line 3 has only four nodes, and if each has below it only finitely many nodes, then there are only finitely many nodes in the whole tree. 414 Koenig'r Lemma, Compactness, and Generalization to Infinite Sets of Premises 14-2. Compactness and Infinite Sets of Premises 415 In such cases there are no more than four times the maximum number of nodes in the subtrees headed by line 3 nodes, plus the three nodes in lines 1 and 2. Conversely, if the whole tree is infinite, at least one node of line 3 must head an infinite subtree.

We can use induction to prove that the same will be true of any line of an infinite tree:

L22: In any infinite tree, every line has at least one node which heads an infinite subtree.

Suppose we have an infinite tree. Our inductive property will be: The nth line has at least one node which heads an infinite tree. Line 1 has this property, by assumption of the argument. This gives the basis step of the induction. For the inductive step, assume the inductive hypothesis that line n has the inductive property. That is, line n has at least one node which heads an infinite tree. Let N be the leftmost such node. Consider the nodes on line n + 1 below node N. If both of these nodes were to head only finite subtrees, then N would also head only a finite subtree, contrary to the inductive hypothesis. So at least one of these nodes of line n + 1 must also head an infinite subtree. In sum, if line n has the inductive property, so does line n + 1, completing the inductive proof of L22. It is now easy to establish

L23 (Koenig's lemma): In any infinite tree there is an infinite path.

Proof: Given an infinite tree, start with the top node and extend a path from each line to the next by choosing the leftmost node in the next line which heads an infinite tree. L22 guarantees that there will always be such a node. Since at each stage we again pick a node which heads an infinite tree, the process can never end. (See Exercise 14-1.)

### 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.