Theorem 2 (Completeness) Whenever then also
Proof: We prove the contrapositive. Assume that We will find an that extends and does not extend any
Towards this end, enumerate all finite strings as
Let We define a sequence by recursion as follows:
- Given with the property that let unless either, in which case, let
Now let and note that satisfies the following properties:
- by construction and compactness.
- For any iff
The left-to-right implication is clear from (1). The other direction holds by construction: If and then certainly and therefore
- In particular,
It is actually that interests us. In terms of property (3) says that
- is a tree.
To see this, suppose that where Then, by property (2), But then, certainly, so, by (2) again, This shows that is closed under initial segments.
- is actually a branch, i.e., is a singleton.
To see this, suppose that We need to show that there is a unique such that
Since then Suppose first that both and are in Then, by compression, and therefore a contradiction.
Suppose now that neither nor is in Then for both and It then follows, using Fact 3 from last lecture, that again a contradiction. This gives the result.
Finally, let be the unique element of Note that extends since Note also that extends no element of since no element of is in and the initial segments of are precisely the elements of This proves that
This is the reason why this formal system is called a tree system; both because of this argument, and because of the relation that it implies between this system and König’s lemma, as we will see below.
To illustrate the interplay resulting from the equivalence of the two relations and consider the following two proofs:
Corollary 3 is compact.
Proof: Given a covering of by open sets, let be the collection of strings such that the basic open set is completely contained in one of the open sets in the covering.
and it follows that Therefore for some finite subset of so and any finite collection of open sets in the covering that contain the sets for constitutes a finite subcovering of
It is not, of course, that the compactness of is a deep result. But the trivial argument just given helps explain some of the difficulties we found previously, since our results supersede this topological theorem.
Corollary 4 König’s lemma holds for infinite subtrees of .
Proof: Given a tree suppose that and let Then so, by completeness and Fact 5 from last lecture, there is a finite and an such that any of length or larger extends an element of
Note now that is closed under extensions, since is a tree. It follows that contains all strings of s and s, of length or larger. But then i.e., is finite.
Typeset using LaTeX2WP. Here is a printable version of this post.