Non-Uniform Comparison of Notions for Closed Set Computability of Fixed Cardinality with Applications to Singular Coverings
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 ‘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 of cardinality less than the continuum does contain a computable point. More generally, the present note exhibits a comparison of different notions of computability for closed real subsets non-uniformly, that is, once their cardinality is fixed. 1