6
$\begingroup$

König's lemma states that given an infinite tree, an infinite path exists, where of course by tree we mean a full binary tree. I found some examples in Logical Labyrinths by Smullyan where he discusses about immortal people having infinite descending chain of children ancestrally.

My question, what are some applications or examples of KL in real life? Also being a contrapositive of Brouwer's fan theorem, the weakened form has applications in logic especially in Heine-Borel theorem.

I just want to get a further intuitive understanding of the lemma when fleshed out in concrete examples.

Thank you. Please note I have already went over this site which gives an excellent account of it but I was looking for similar but different examples.

  • 0
    Diestel's "Graph Theory" discusses the KL and some applications.2011-11-05

1 Answers 1

6

The theorem is often used in combinatorial applications to show that a large enough collection of finite approximations can be used to make an infinite set. Examples include:

  • The proof of Gödel's completeness theorem due to Henkin proceeds by making an infinite subtree of $\{0,1\}$ such that any path through the tree gives a model of the theory in question.

  • The proof that the infinite form of Ramsey's theorem implies the finite form. If the finite form is not true, there are "bad" colorings of arbitrarily long initial segments of $\mathbb{N}$. These form a tree, and a path through the tree gives a "bad" coloring for the infinite form of Ramsey's theorem.

  • The proof that a metric space is completely metrizable if and only if it is a $G_\delta$ subset of its completion (Theorem 8.17 of Kechris' Classical Descriptive Set Theory) includes a slick use of König's lemma.

Of course there are others, which I am sure other people will point out in separate answers.

  • 0
    You can’t really speak of *the* proof of the last two results. In both cases the proof with which I’m most familiar doesn’t use König’s lemma.2011-11-15