Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-18T06:37:58.620Z Has data issue: false hasContentIssue false
  • English
  • Français

Some results related to the continuity problem

Published online by Cambridge University Press:  13 June 2016

DIETER SPREEN
DIETER SPREEN*
Affiliation:
Department of Mathematics, University of Siegen, 57068 Siegen, Germany. Email: [email protected] Department of Decision Sciences, University of South Africa, PO Box 392, Pretoria 0003, South Africa
Get access Rights & Permissions [Opens in a new window]

Abstract

The continuity problem, i.e., the question whether effective maps between effectively given topological spaces are effectively continuous, is reconsidered. In earlier work, it was shown that this is always the case, if the effective map also has a witness for non-inclusion. The extra condition does not have an obvious topological interpretation. As is shown in the present paper, it appears naturally where in the classical proof that sequentially continuous maps are continuous, the Axiom of Choice is used. The question is therefore whether the witness condition appears in the general continuity theorem only for this reason, i.e., whether effective operators are effectively sequentially continuous. For two large classes of spaces covering all important applications, it is shown that this is indeed the case. The general question, however, remains open.

Spaces in this investigation are in general not required to be Hausdorff. They only need to satisfy the weaker T0 separation condition

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 27 , Special Issue 8: Continuity, Computability, Constructivity: From Logic to Algorithms 2013 , December 2017 , pp. 1601 - 1624
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Amadio, R.M. and Curien, P.-L. (1998). Domains and Lambda-Calculi, Cambridge University Press, Cambridge.CrossRefGoogle Scholar
Blanck, J. (1997). Domain representability of metric spaces. Annals of Pure and Applied Logic 83 (3) 225–247.Google Scholar
Ceĭtin, G.S. (1962). Algorithmic operators in constructive metric spaces. Trudy Mat. Inst. Steklov 67 295–361; English transl., Amer. Math. Soc. Transl., ser. 2, 64 1–80.Google Scholar
Edalat, A. (1997). Domains for computation in mathematics, physics and exact real arithmetic. Bulletin of Symbolic Logic 3 (4) 401–452.CrossRefGoogle Scholar
Egli, H. and Constable, R.L. (1976). Computability concepts for programming language semantics. Theoretical Computer Science 2 (2) 133–145.Google Scholar
Eršov, Ju. L. (1972) Computable functionals of finite type. Algebra i Logika 11 (4) 367–437; English transl., Algebra and Logic 11 (4) 203–242.Google Scholar
Eršov, Ju. L. (1973). The theory of A-spaces. Algebra i Logika 12 (4) 369–416; English transl., Algebra and Logic 12 (4) 209–232.Google Scholar
Eršov, Ju. L. (1975). Theorie der Numerierungen II. Zeitschrift für mathematische Logik Grundlagen der Mathematik 21 (1) 473–584.Google Scholar
Eršov, Ju. L. (1977). Model ℂ of partial continuous functionals. In: Gandy, R. et al. (eds.) Logic Colloquium 76, North-Holland, Amsterdam, 455–467.Google Scholar
Friedberg, R. (1958). Un contre-exemple relatif aux fonctionelles récursives. Comptes rendus hebdomadaires des séances de l'Académie des Sciences (Paris) 247 (1) 852–854.Google Scholar
Gierz, G., Hofman, K.H., Keimel, K., Lawson, J.D., Mislove, M.W. and Scott, D. (2003). Continuous Lattices and Domains, Cambridge University Press, Cambridge.Google Scholar
Gunter, C.A. (1992). Semantics of Programming Languages, MIT Press, Cambridge, Mass. Google Scholar
Hoyrup, M. (2015) personal communication.Google Scholar
Kreisel, G., Lacombe, D. and Shoenfield, J. (1959). Partial recursive functionals and effective operations. In: Heyting, A. (ed.) Constructivity in Mathematics, North-Holland, Amsterdam, 290–297.Google Scholar
Moschovakis, Y.N. (1964). Recursive metric spaces. Fundamenta Math. 55 (3) 215–238.CrossRefGoogle Scholar
Moschovakis, Y.N. (1965). Notation systems and recursive ordered fields. Compositio Math. 17 40–71.Google Scholar
Myhill, J. and Shepherdson, J.C. (1955). Effective operators on partial recursive functions. Zeitschrift für mathematische Logik Grundlagen der Mathematik 1 (4) 310–317.Google Scholar
Pour-El, M.B. and Richards, J.I. (1989). Computability in Analysis and Physics, Springer-Verlag, Berlin.Google Scholar
Rogers, H. Jr., (1967). Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York.Google Scholar
Sciore, E. and Tang, A. (1978). Computability theory in admissible domains. In: 10th Annual ACM Symposium on Theory of Computing 95–104. Association for Computing Machinery, New York.Google Scholar
Specker, E. (1949). Nicht konstruktiv beweisbare Sätze der Analysis. The Journal of Symbolic Logic 14 (3) 145–158.Google Scholar
Spreen, D. (1995). On some decision problems in programming. Information and Computation 122 (1) 120–139; Corrigendum (1999) 148 (2) 241–244.Google Scholar
Spreen, D. (1996). Effective inseparability in a topological setting. Annals of Pure and Applied Logic 80 (3) 257–275.Google Scholar
Spreen, D. (1998). Effective topological spaces. The Journal of Symbolic Logic 63 (1) 185–221.Google Scholar
Spreen, D. (2000). Corrigendum. The Journal of Symbolic Logic 65 (4) 1917–1918.CrossRefGoogle Scholar
Spreen, D. (2001a). Can partial indexings be totalized? The Journal of Symbolic Logic 66 (3) 1157–1185.Google Scholar
Spreen, D. (2001b). Representations versus numberings: On two computability notions. Theoretical Computer Science 26 (1–2) 473–499.CrossRefGoogle Scholar
Spreen, D. (2008). On some problems in computable topology. In: Dimitracopoulos, C. et al. (eds.) Logic Colloquium'05, Cambridge University Press, Cambridge, 221–254.Google Scholar
Spreen, D. (2010). Effectivity and effective continuity of multifunctions. The Journal of Symbolic Logic 75 (2) 602–640.CrossRefGoogle Scholar
Spreen, D. (2014). An isomorphism theorem for partial numberings. In: Brattka, V., Diener, H. & Spreen, D. (eds.) Logic, Computation, Hierarchies, Ontos Mathematical Logic 4, De Gruyter, Boston/Berlin, 341–381.Google Scholar
Spreen, D. and Young, P. (1984). Effective operators in a topological setting. In: Richter, M.M., Börger, E., Oberschelp, W., Schinzel, B. & Thomas, W. (eds.) Computation and Proof Theory, Proceedings of the Logic Colloquium held in Aachen 1983, Part II. Lecture Notes in Mathematics 1104, Springer, Berlin, 437–451.Google Scholar
Sturm, C.F. (1835). Mémoire sur la résolution des équations numeriques. Annales de mathématiques pures et appliquées 6 271–318.Google Scholar
Weihrauch, K. and Deil, T. (1980). Berechenbarkeit auf cpo's. Schriften zur Angewandten Mathematik und Informatik, 63 Rheinisch-Westfälische Technische Hochschule Aachen.Google Scholar