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)
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).
Comment by bou — May 3, 2006 @ 11:17
Thank you, I incorporated your corrections and made a couple of other changes. The new version is online.
Comment by Andrej Bauer — May 3, 2006 @ 15:38