Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-26T10:29:26.706Z Has data issue: false hasContentIssue false
  • English
  • Français

On effective topological spaces

Published online by Cambridge University Press:  12 March 2014

Dieter Spreen
Dieter Spreen*
Affiliation:
Fachbereich Mathematik, Theoretische Informatik, Universität-Gh Siegen, D-57068 Siegen, Germany, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Starting with D. Scott's work on the mathematical foundations of programming language semantics, interest in topology has grown up in theoretical computer science, under the slogan ‘open sets are semidecidable properties’. But whereas on effectively given Scott domains all such properties are also open, this is no longer true in general. In this paper a characterization of effectively given topological spaces is presented that says which semidecidable sets are open.

This result has important consequences. Not only follows the classical Rice-Shapiro Theorem and its generalization to effectively given Scott domains, but also a recursion theoretic characterization of the canonical topology of effectively given metric spaces. Moreover, it implies some well known theorems on the effective continuity of effective operators such as P. Young and the author's general result which in its turn entails the theorems by Myhill-Shepherdson, Kreisel-Lacombe-Shoenfield and Ceĭtin-Moschovakis, and a result by Eršov and Berger which says that the hereditarily effective operations coincide with the hereditarily effective total continuous functionals on the natural numbers.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 63 , Issue 1 , March 1998 , pp. 185 - 221
Copyright
Copyright © Association for Symbolic Logic 1998

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

REFERENCES

[1]Beeson, M. J., The unprovability in intuitionistic formal systems of theorems on the continuity of effective operations, this Journal, vol. 40 (1975), pp. 321–346.Google Scholar
[2]Beeson, M. J., The nonderivability in intuitionistic formal systems of the continuity of effective operations on the reals, this Journal, vol. 41 (1976), pp. 18–24.Google Scholar
[3]Beeson, M. J., Continuity and comprehension in intuitionistic formal systems, Pacific Journal of Mathematics, vol. 68 (1977), pp. 29–40.CrossRefGoogle Scholar
[4]Beeson, M. J. and Ščedrov, A., Church's thesis, continuity, and set theory, this Journal, vol. 49 (1984), pp. 630–643.Google Scholar
[5]Berger, U., Total sets and objects in domain theory, Annals of Pure and Applied Logic, vol. 60 (1993), pp. 91–117.CrossRefGoogle Scholar
[6]Bourbaki, N., Elements of mathematics, General topology, Part 1, Hermann, Paris, 1966.Google Scholar
[7]Ceĭtin, G. S., Algorithmic operators in constructive metric spaces, Trudy Matematiki Instituta Steklov, vol. 67 (1962), pp. 295–361, English translation: American Mathematical Society Translations, series 2, vol. 64, 1967, pp. 1–80.Google Scholar
[8]Czászár, A., Foundations of general topology, Pergamon, New York, 1963.Google Scholar
[9]de Barker, J. W. and Zucker, J. I., Processes and the denotational semantics of concurrency, Information and Control, vol. 54 (1982), pp. 70–120.CrossRefGoogle Scholar
[10]Egli, H. and Constable, R. L., Computability concepts for programming language semantics, Theoretical Computer Science, vol. 2 (1976), pp. 133–145.CrossRefGoogle Scholar
[11]Eršov, Ju. L., Computable functionals of finite type, Algebra i Logika, vol. 11 (1972), pp. 367–437, English translation: Algebra and Logic, vol. 11, 1972, pp. 203–242.Google Scholar
[12]Eršov, Ju. L., Theorie der Numerierungen I, Zeitschrift für mathematische Logik Grundlagen der Mathematik, vol. 19 (1973), pp. 289–388.CrossRefGoogle Scholar
[13]Eršov, Ju. L., The theory of A-spaces, Algebra i Logika, vol. 12 (1973), pp. 369–416, English translation: Algebra and Logic, vol. 12, 1973, pp. 209–232.Google Scholar
[14]Eršov, Ju. L., Theorie der Numerierungen II, Zeitschrift für mathematische Logik Grundlagen der Mathematik, vol. 21 (1975), pp. 473–584.CrossRefGoogle Scholar
[15]Eršov, Ju. L., Heriditarily effective operations, Algebra i Logika, vol. 15 (1976), pp. 642–654, English translation: Algebra and Logic, vol. 15 (1976), pp. 400–409.Google Scholar
[16]Eršov, Ju. L., Model ℂ of partial continuous functionals, Logic colloquium 76 (Gandy, R.et al., editors), North-Holland, Amsterdam, 1977, pp. 455–467.Google Scholar
[17]Fletcher, P. and Lindgren, W. F., Quasi-uniform spaces, Dekker, New York, 1982.Google Scholar
[18]Friedberg, R., Un contre-exemple relatif aux fonctionelles récursives, Comptes Rendus de l'Académie des Sciences, vol. 247 (1958), pp. 852–854.Google Scholar
[19]Giannini, P. and Longo, G., Effectively given domains and lambda-calculus models, Information and Control, vol. 62 (1984), pp. 36–63.CrossRefGoogle Scholar
[20]Gierz, G., Hofmann, K. H., Keimel, K., Lawson, D. J., Mislove, M., and Scott, D. S., A compendium on continuous lattices, Springer-Verlag, Berlin, 1980.CrossRefGoogle Scholar
[21]Helm, J., On effectively computable operators, Zeitschrift für mathematische Logik Grundlagen der Mathematik, vol. 17 (1971), pp. 231–244.CrossRefGoogle Scholar
[22]Kreisel, G., Lacombe, D., and Shoenfield, J., Partial recursive functionals and effective operations, Constructivity in mathematics (Heyting, A., editor), North-Holland, Amsterdam, 1959, pp. 290–297.Google Scholar
[23]Lachlan, A., Effective operators in a general setting, this Journal, vol. 29 (1964), pp. 163–178.Google Scholar
[24]Mal'cev, A. I., The metamathematics of algebraic systems, Collected papers: 1936–1967, (Wells, B. F. III, editor), North-Holland, Amsterdam, 1971.Google Scholar
[25]Melton, A., Topological spaces for cpos, Categorical methods in computer science (Ehrig, H.et al., editors), Lecture Notes in Computer Science, no. 393, Springer-Verlag, Berlin, 1989, pp. 302–314.Google Scholar
[26]Moschovakis, Y. N., Recursive analysis, Ph. D. thesis, University of Wisconsin, Madison, Wisconsin, 1963.Google Scholar
[27]Moschovakis, Y. N., Recursive metric spaces, Fundamenta Mathematicae, vol. 55 (1964), pp. 215–238.CrossRefGoogle Scholar
[28]Myhill, J. and Shepherdson, J. C., Effective operators on partial recursive functions, Zeitschrift für mathematische Logik Grundlagen der Mathematik, vol. 1 (1955), pp. 310–317.CrossRefGoogle Scholar
[29]Nivat, M., Infinite words, infinite trees, infinite computations, Foundations of computer science III, Part 2 (de Bakker, J. W.et al., editors), Mathematical Centre Tracts, no. 109, 1979, pp. 1–52.Google Scholar
[30]Nogina, E. Ju., Relations between certain classes of effectively topological spaces, Matematicheskie Zametki, vol. 5 (1969), pp. 483–495, English translation: Mathematical Notes, vol. 5, 1969, pp. 288–294.Google Scholar
[31]Pour-El, M. B., A comparison of five ‘computable' operators, Zeitschrift für mathematische Logik Grundlagen der Mathematik, vol. 6 (1960), pp. 325–340.CrossRefGoogle Scholar
[32]Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[33]Sciore, E. and Tang, A., Computability theory in admissible domains, 10th annual ACM symposium on theory of computing, Association of Computing Machinery, New York, 1978, pp. 95–104.Google Scholar
[34]Scott, D., Outline of a mathematical theory of computation, Technical monograph PRG-2, Oxford University Computing Laboratory, 1970.Google Scholar
[35]Scott, D., Continuous lattices, Toposes, algebraic geometry and logic (Bucur, I.et al., editors), Lecture Notes in Mathematics, no. 274, Springer-Verlag, Berlin, 1971, pp. 97–136.Google Scholar
[36]Scott, D., Domains for denotational semantics, Automata, languages and programming (Nielsen, M.et al., editors), Lecture Notes in Computer Science, no. 140, Springer-Verlag, Berlin, 1982, pp. 577–613.CrossRefGoogle Scholar
[37]Smyth, M. B., Power domains and predicate transformers, Automata, languages and programming (Diaz, J., editor), Lecture Notes in Computer Science, no. 154, Springer-Verlag, Berlin, 1983, pp. 662–675.CrossRefGoogle Scholar
[38]Smyth, M. B., Finite approximation of spaces, Category theory and computer programming (Pittet, D.et al., editors), Lecture Notes in Computer Science, no. 240, Springer-Verlag, Berlin, 1986, pp. 225–241.CrossRefGoogle Scholar
[39]Smyth, M. B., Quasi-uniformities: reconciling domains with metric spaces, Mathematical foundations of programming language semantics, 3rd workshop (Main, M.et al., editors), Lecture Notes in Computer Science, no. 298, Springer-Verlag, Berlin, 1988, pp. 236–253.CrossRefGoogle Scholar
[40]Smyth, M. B., Completeness of quasi-uniform spaces and syntopological spaces, Journal of the London Mathematical Society, vol. 49 (1994), pp. 385–400.CrossRefGoogle Scholar
[41]Spreen, D., On domains witnessing increase in information, in preparation, 199?Google Scholar
[42]Spreen, D., On some decision problems in programming, Information and Computation, vol. 122 (1995), pp. 120–139.CrossRefGoogle Scholar
[43]Spreen, D., Effective inseparability in a topological setting, Annals of Pure and Applied Logic, vol. 80 (1996), pp. 257–275.CrossRefGoogle Scholar
[44]Spreen, D. and Young, P., Effective operators in a topological setting, Computation and proof theory, Part II (Richter, M. M.et al., editors), Lecture Notes in Mathematics, no. 1104, Springer-Verlag, Berlin, 1984, Proceedings of Logic Colloquium Aachen 1983, pp. 437–451.CrossRefGoogle Scholar
[45]Stoltenberg-Hansen, V., Lindström, I., and Griffor, E. R., Mathematical theory of domains, Cambridge University Press, Cambridge, 1994.CrossRefGoogle Scholar
[46]Weihrauch, K., Computability, Springer-Verlag, Berlin, 1987.CrossRefGoogle Scholar
[47]Weihrauch, K. and Deil, T., Berechenbarkeit auf cpo's, Schriften zur Angewandten Mathematik und Informatik, no. 63, Rheinisch-Westfälische Technische Hochschule Aachen, 1980.Google Scholar
[48]Young, P., An effective operator, continuous but not partial recursive, Proceedings of the American Mathematical Society, vol. 19 (1968), pp. 103–108.CrossRefGoogle Scholar
[49]Young, P. and Collins, W., Discontinuities of provably correct operators on the provably recursive real numbers, this Journal, vol. 48 (1983), pp. 913–920.Google Scholar