Mathematics and Computation

A blog about mathematics for computers

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

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

How to comment on this blog: At present comments are disabled because the relevant script died. If you comment on this post on Mastodon and mention, I will gladly respond. You are also welcome to contact me directly.