2005/01/31 by Martin Ziegler
Computer Science · #Algorithms and Data Compression #Computability, Logic, AI Algorithms #cs.LO #semigroups and automata theory
paper · pdf · doi:10.1016/j.jco.2006.05.002
published as pp.827-849 in Journal of Complexity vol.22 (2006) · added section on semi-algebraic functions; to appear in Proc. http://cca-net.de/cca2005
arxiv created 2005/06/17 · openalex publication_date 2006/07/27 · arxiv updated 2010/05/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
A function f is continuous iff the PRE-image f-1[V] of any open set V is open again. Dual to this topological property, f is called OPEN iff the IMAGE f[U] of any open set U is open again. Several classical Open Mapping Theorems in Analysis provide a variety of sufficient conditions for openness. By the Main Theorem of Recursive Analysis, computable real functions are necessarily continuous. In fact they admit a well-known characterization in terms of the mapping V+->f-1[V] being EFFECTIVE: Given a list of open rational balls exhausting V, a Turing Machine can generate a corresponding list for f-1[V]. Analogously, EFFECTIVE OPENNESS requires the mapping U+->f[U] on open real subsets to be effective. By effectivizing classical Open Mapping Theorems as well as from application of Tarski's Quantifier Elimination, the present work reveals several rich classes of functions to be effectively open.