Singular Coverings and Non-Uniform Notions for Closed Set Computability
Stéphane Le Roux, Martin Ziegler · arXiv (Cornell University) · 2006
Abstract. The empty set of course contains no computable point. On the other hand, surprising results due to Zaslavskiĭ, Tseĭtin, Kreisel, and Lacombe assert the existence of non-empty co-r.e. closed sets devoid of computable points: sets which are even ‘large ’ in the sense of positive Lebesgue measure. We observe that a certain size is in fact necessary: every non-empty co-r.e. closed real set without computable points has continuum cardinality. This initiates a comparison of different notions of computability for closed real subsets non-uniformly like, e.g., for sets of fixed cardinality or sets containing a (not necessarily effectively findable) computable point. By relativization we obtain a bounded recursive rational sequence of which every accumulation point is not even computable with support of a Halting oracle. Finally the question is treated whether compact sets have co-r.e. closed connected components; and every star-shaped co-r.e. closed set is asserted to contain a computable point. 1