Joseph Miller

VIGRE postdoctoral position at Indiana University at Bloomington

Pi-0-1 Classes in Computable Analysis and Topology

Anil Nerode

Mathemtical logic, computability theory

Abstract: We explore aspects of \Pi^0_1 classes in R^n. These are the effective closed sets of computable analysis and natural analogs of the \Pi^0_1 classes in 2^\omega, 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 \Pi^0_1 classes which contain a nonempty, connected \Pi^0_1 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 \Pi^0_1 class. We show that a \Pi^0_1 class homeomorphic to a sphere is located: the distance to the class is computable. Closed balls embedded as \Pi^0_1 classes are also studied. Chapter IV studies members of \Pi^0_1 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.

PhD

PhD