On effective topological spaces

被引:29
作者
Spreen, D [1 ]
机构
[1] Univ Gesamthsch Siegen, Fachbereich Math Theoret Informat, D-57068 Siegen, Germany
关键词
D O I
10.2307/2586596
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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 Ceitin-Moschovakis, and a result by Ersov and Berger which says that the hereditarily effective operations coincide with the hereditarily effective total continuous Functionals on the natural numbers.
引用
收藏
页码:185 / 221
页数:37
相关论文
共 49 条
[1]   CHURCH THESIS, CONTINUITY, AND SET-THEORY [J].
BEESON, M ;
SCEDROV, A .
JOURNAL OF SYMBOLIC LOGIC, 1984, 49 (02) :630-643
[2]   UNPROVABILITY IN INTUITIONISTIC FORMAL SYSTEMS OF CONTINUITY OF EFFECTIVE OPERATIONS ON REALS [J].
BEESON, M .
JOURNAL OF SYMBOLIC LOGIC, 1976, 41 (01) :18-24
[3]   NONDERIVABILITY IN INTUITIONISTIC FORMAL SYSTEMS OF THEOREMS ON CONTINUITY OF EFFECTIVE OPERATIONS [J].
BEESON, MJ .
JOURNAL OF SYMBOLIC LOGIC, 1975, 40 (03) :321-346
[4]   CONTINUITY AND COMPREHENSION IN INTUITIONISTIC FORMAL SYSTEMS [J].
BEESON, MJ .
PACIFIC JOURNAL OF MATHEMATICS, 1977, 68 (01) :29-40
[5]  
BERGER U, 1993, ANN PURE APPL LOGIC, V60, P1
[6]  
Bourbaki N., 1966, ELEMENTS MATH GEN 1
[7]  
CEITIN GS, 1967, AM MATH SOC TRANSL, V64, P1
[8]   DISCONTINUITIES OF PROVABLY CORRECT OPERATORS ON THE PROVABLY RECURSIVE REAL NUMBERS [J].
COLLINS, WJ ;
YOUNG, P .
JOURNAL OF SYMBOLIC LOGIC, 1983, 48 (04) :913-920
[9]  
CZASZAR A, 1963, FDN GEN TOPOLOGY
[10]   PROCESSES AND THE DENOTATIONAL SEMANTICS OF CONCURRENCY [J].
DEBAKKER, JW ;
ZUCKER, JI .
INFORMATION AND CONTROL, 1982, 54 (1-2) :70-120