On the Cantor–Bendixson rank of a set that is searchable in Gödel’s T

Article type: Research Article

Authors: Normann, Dag

Affiliations: Department of Mathematics, The University of Oslo, P.O. Box 1053, Blindern, Oslo, Norway. dnormann@math.uio.no. http://folk.uio.no/dnormann/

Abstract: We prove that if a closed subset X of the Baire space is searchable in the sense of Escardó [Logical Methods in Computer Science 4(3) (2008), 3], and by a functional definable in Gödel’s T, then X is countable, and the Cantor–Bendixson rank of X is bounded by the ordinal ε0. To this end we introduce evaluation trees, well founded decorated trees that induce operators from the full set-theoretical class NN→N to NN. We prove that when a search operator for a set X is induced from an evaluation tree T, then the Cantor–Bendixson rank of X is bounded by the Kleene–Brouwer order type of T. Further we use a theorem due to Howard [Journal of Symbolic Logic 45(3) (1980), 493–504], estimating the ordinal complexity of the reduction tree of a term in system T, to show that all functionals of type (NN→N)→NN definable in T can be computed using an evaluation tree of ordinal rank below ε0.

Keywords: Searchable, Gödel’s T, Cantor–Bendixson rank

DOI: 10.3233/COM-150043

Journal: Computability, vol. 5, no. 1, pp. 61-74, 2016