Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
An addendum: What I meant by 'real life' would be such as the tiling problem example given by Richard Kaye in the opening chapter of the book "The mathematics of logic" and tiling problem and KL leads to Heesch's problem. However, I am unsure as to, if it would be to much of a wild leap of imagination to apply KL in Prof. Tao's Tomb Raider game. –  user18325 Nov 5 '11 at 3:19
    
Diestel's "Graph Theory" discusses the KL and some applications. –  Austin Mohr Nov 5 '11 at 4:39

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
    
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. –  Brian M. Scott Nov 15 '11 at 10:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.