König's Lemma and the Kleene Tree

• 25 April 2006
• Andrej Bauer
• Computation, Constructive math, Publications, Tutorial

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)

Comments

bou

03 May 2006 at 11:17

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).

Andrej Bauer

03 May 2006 at 15:38

Thank you, I incorporated your corrections and made a couple of other changes. The new version is online.