Effective Borel degrees of some topological functions
Guido Gherardi · Mathematical logic quarterly · 2006
Abstract The focus of this paper is the incomputability of some topological functions (with respect to certain representations) using the tools of Borel computability theory, as introduced by V. Brattka in [3] and [4]. First, we analyze some basic topological functions on closed subsets of ℝn , like closure, border, intersection, and derivative, and we prove for such functions results of Σ02‐completeness and Σ03‐completeness in the effective Borel hierarchy. Then, following [13], we re‐consider two well‐known topological results: the lemmas of Urysohn and Urysohn‐Tietze for generic metric spaces (for the latter we refer to the proof given by Dieudonné). Both lemmas define Σ02‐computable functions which in some cases are even Σ02‐complete. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)