Π⁰₁ classes in computable analysis and topology

by Joseph S. Miller

Ph.D. dissertation, Cornell University, 2002.

Available upon request.

Abstract. We explore aspects of Π⁰₁ in Rⁿ. These are the effective closed sets of computable analysis and natural analogs of the Π⁰₁ 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]ⁿ to itself—as the Π⁰₁ classes which contain a nonempty, connected Π⁰₁ subclass. This settles a question asked in Cenzer and Jockusch (2000). To prove that Brouwer's theorem is inconsistent with Russian constructivism, Orevkov gave a fixable class with no computable points (1963). 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 Π⁰₁ class. We show that a Π⁰₁ class homeomorphic to a sphere is located: the distance to the class is computable. Closed balls embedded as Π⁰₁ classes are also studied. Chapter IV studies members of Π⁰₁ classes which contain no computable points. These avoidable points were introduced by Kalantari and Welch. 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.