Annals of Pure and Applied Logic 80 (3):257-275 (1996)

Effective inseparability of pairs of sets is an important notion in logic and computer science. We study the effective inseparability of sets which appear as index sets of subsets of an effectively given topological T0-space and discuss its consequences. It is shown that for two disjoint subsets X and Y of the space one can effectively find a witness that the index set of X cannot be separated from the index set of Y by a recursively enumerable set, if X intersects the topological closure of an effectively enumerable subset of Y. As a consequence of a more general parametric inseparability result a theorem of Rice-Shapiro type is obtained. Moreover, under some additional requirements it follows that nonopen subsets have productive index sets. This implies a generalized Rice theorem: Connected spaces have only trivial completely recursive subsets. As application some decision problems in computable analysis and domain theory are studied. It follows that the complement of the halting problem can be reduced to the problem to decide of a number whether it is a computable irrational. The same is true for the problems to decide whether two numbers are equal, whether one is not greater than the other, and whether a number is equal to a given number. In the case of an effectively given continuous complete partial order the complexity of the last problem depends on whether the given element is the smallest element, in which case the complement of the halting problem is reducible to it, whether it is a base element and maximal, then the decision problem is recursively isomorphic to the halting problem, or whether it is none of these. In this case, both the halting problem and its complement are reducible to the problem. The same is true in nontrivial cases for the problems whether an element belongs to the basis, whether two elements of the partial order are equal, or whether one approximates the other. In general, for any nonempty proper subset of the partial order either the halting problem or its complement can be reduced to the membership problem of the subset
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/0168-0072(95)00067-4
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 71,410
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Theorie der Numerierungen I.Ju L. Eršov - 1973 - Mathematical Logic Quarterly 19 (19‐25):289-388.
Theorie der Numerierungen II.J. U. L. Eršov - 1975 - Mathematical Logic Quarterly 21 (1):473-584.
Simplicity in Effective Topology.Iraj Kalantari & Anne Leggett - 1982 - Journal of Symbolic Logic 47 (1):169-183.

View all 19 references / Add more references

Citations of this work BETA

On Effective Topological Spaces.Dieter Spreen - 1998 - Journal of Symbolic Logic 63 (1):185-221.
Can Partial Indexings Be Totalized?Dieter Spreen - 2001 - Journal of Symbolic Logic 66 (3):1157-1185.
A Note on Partial Numberings.Serikzhan Badaev & Dieter Spreen - 2005 - Mathematical Logic Quarterly 51 (2):129-136.

Add more citations

Similar books and articles

Corrigendum: On Effective Topological Spaces.Dieter Spreen - 2000 - Journal of Symbolic Logic 65 (4):1917-1918.
On Effective Topological Spaces.Dieter Spreen - 1998 - Journal of Symbolic Logic 63 (1):185-221.
A Note on Partial Numberings.Serikzhan Badaev & Dieter Spreen - 2005 - Mathematical Logic Quarterly 51 (2):129-136.
Topological Dynamics of Definable Group Actions.Ludomir Newelski - 2009 - Journal of Symbolic Logic 74 (1):50-72.
Effectivity and Effective Continuity of Multifunctions.Dieter Spreen - 2010 - Journal of Symbolic Logic 75 (2):602-640.
Thought Insertion and the Inseparability Thesis.Paul J. Gibbs - 2000 - Philosophy, Psychiatry, and Psychology 7 (3):195-202.
Priority Setting and Evidence Based Purchasing.Lucy Frith - 1999 - Health Care Analysis 7 (2):139-151.


Added to PP index

Total views
6 ( #1,137,556 of 2,519,701 )

Recent downloads (6 months)
1 ( #406,314 of 2,519,701 )

How can I increase my downloads?


My notes