Pi-0-1 classes in computable analysis and topology
Anil Nerode, Joseph S. Miller · 2002
We explore aspects of 1 0 classes in Rn . These are the effective closed sets of computable analysis and natural analogs of the 1 0 classes in 2ω, widely studied by computability theorists. In Chapter II, we characterize the fixable classes—the sets of fixed point of computable maps from the unit cube [0,1] n to itself—as the 1 0 , classes which contain a nonempty, connected 1 0 subclass. This settles a question asked in [CJ00]. To prove that Brouwer's theorem is inconsistent with Russian constructivism, Orevkov gave a fixable class with no computable points [Ore63]. Our proof employs a generalization of Orevkov's construction, as well as the notion of topological degree . Homology theory is used in the definition and computation of the topological degree. Homology returns in Chapter III, where chains are used to take algorithmic advantage of the topological structure of a 1 0 , class. We show that a 1 0 class homeomorphic to a sphere is located: the distance to the class is computable. Closed balls embedded as 1 0 classes are also studied. Chapter IV studies members of 1 0 classes which contain no computable points. These avoidable points were introduced by Kalantari and Welch [KW]. Avoidability is a type of effective non-computability; we introduce hyperavoidability , a stronger notion, and initiate the computability theoretic study of both classes, including their behavior in the Turing and weak truth-table degrees.