König’s Lemma and the Kleene Tree

For the benefit of the topology seminar audience at the math department of University of Ljubljana, I have written a self-contained explanation of the Kleene tree, which is an interesting object in computability theory. For the benefit of the rest of the planet, I am publishing it here.

Abstract: I present a basic result about Cantor space in the context of computability theory: the computable Cantor space is computably non-compact. This is in sharp contrast with the classical theorem that Cantor space is compact. The note is written for mathematicians with classical training in topology and analysis. I assume nothing from computability theory, except the basic intuition about how computers work by executing instructions given by a finite program.

Download: kleene-tree.pdf (updated May 3rd, 2006)

2 thoughts on “König’s Lemma and the Kleene Tree

  1. Congratulations for this short summary. I have enjoyed its reading.

    Let me write some misprints (at least in my opinion) I have found in the last page.

    1. The equality stated in Theorem 3.6 si simply an inclusion \subseteq (by cardinality reasons it is obvious they are different)

    2. In the first case of the definition of f(n) you must use p(n+1) and not p(n).

Leave a Reply

Your email address will not be published. Required fields are marked *

5 + 1 =

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>