2013/12/03 by Matthew de Brecht, de Brecht, Matthew
Computer Science · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO) #cs.LO #math.LO
paper · pdf · doi:10.48550/arxiv.1312.0697
arxiv created 2013/12/03 · arxiv updated 2013/12/04
We develop a general theory of jump operators, which is intended to provide an abstraction of the notion of "limit-computability" on represented spaces. Jump operators also provide a framework with a strong categorical flavor for investigating degrees of discontinuity of functions and hierarchies of sets on represented spaces. We will provide a thorough investigation within this framework of a hierarchy of Δ02-measurable functions between arbitrary countably based T0-spaces, which captures the notion of computing with ordinal mind-change bounds. Our abstract approach not only raises new questions but also sheds new light on previous results. For example, we introduce a notion of "higher order" descriptive set theoretical objects, we generalize a recent characterization of the computability theoretic notion of "lowness" in terms of adjoint functors, and we show that our framework encompasses ordinal quantifications of the non-constructiveness of Hilbert's finite basis theorem.