2011/05/16 by Arno Pauly, Martin Ziegler, Pauly, Arno +1
Mathematics · #03D78 #03F60 #54C08 #FOS: Mathematics #General Topology (math.GN) #Logic (math.LO) #math.GN #math.LO #msc:03D78 #msc:03F60 #msc:54C08
paper · pdf · doi:10.48550/arxiv.1105.3050
23 pages, 5 figures
arxiv created 2011/09/08 · arxiv updated 2015/03/18
A type-2 computable real function is necessarily continuous; and this remains true for relative, i.e. oracle-based computations. Conversely, by the Weierstrass Approximation Theorem, every continuous f:[0,1]->R is computable relative to some oracle. In their search for a similar topological characterization of relatively computable multivalued functions f:[0,1]=>R (aka relations), Brattka and Hertling (1994) have considered two notions: weak continuity (which is weaker than relative computability) and strong continuity (which is stronger than relative computability). Observing that uniform continuity plays a crucial role in the Weierstrass Theorem, we propose and compare several notions of uniform continuity for relations. Here, due to the additional quantification over values y in f(x), new ways of (linearly) ordering quantifiers arise, yet none of them turn out as satisfactory. We are thus led to a notion of uniform continuity based on the Henkin Quantifier; and prove it necessary for relative computability. In fact iterating this condition yields a strict hierarchy of notions each necessary, and the omega-th level also sufficient, for relative computability.