An ω-language is a set of infinite sequences on a countable language, and corresponds to a set of real numbers in a natural way. Languages may be described by logical formulas in the arithmetical hierarchy and also may be described as the set of words accepted by some type of automata or Turing machine. Certain families of languages, such as the equation image languages, may enumerated as P0, P1, … and then an index set associated to a given property R (...) of languages is just the set of e such that Pe has the property. The complexity of index sets for 7 types of languages is determined for various properties related to the size of the language. (shrink)

In this paper we develop a point-free approach to the study of topological spaces and functions on them, establish platforms for both and present some findings on recursive points. In the first sections of the paper, we obtain conditions under which our approach leads to the generation of ideal objects with which mathematicians work. Next, we apply the effective version of our approach to the real numbers, and make exact connections to the classical approach to recursive reals. In the succeeding (...) sections of the paper, we introduce machinery to produce functions on topological spaces and find succinct conditions which will be effectivized in our sequel. (shrink)

The first-order theory of the lattice of recursively enumerable closed subsets of an effective topological space is proved undecidable using the undecidability of the first-order theory of the lattice of recursively enumerable sets. In particular, the first-order theory of the lattice of recursively enumerable closed subsets of Euclidean n -space, for all n , is undecidable. A more direct proof of the undecidability of the lattice of recursively enumerable closed subsets of Euclidean n -space, n ⩾ 2, is provided using (...) the method of reduction and the recursive inseparability of the set of all formulae satisfiable in every model of the theory of SIBs and the set of all formulae refutable in some finite model of the theory of SIBs. (shrink)

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. (shrink)

The first-order theory of the lattice of recursively enumerable closed subsets of an effective topological space is proved undecidable using the undecidability of the first-order theory of the lattice of recursively enumerable sets. In particular, the first-order theory of the lattice of recursively enumerable closed subsets of Euclidean n -space, for all n, is undecidable. A more direct proof of the undecidability of the lattice of recursively enumerable closed subsets of Euclidean n -space, n ⩾ 2, is provided using the (...) method of reduction and the recursive inseparability of the set of all formulae satisfiable in every model of the theory of SIBs and the set of all formulae refutable in some finite model of the theory of SIBs. (shrink)

This paper is an investigation of definability hierarchies on effective topological spaces. An open subset U of an effective space X is definable iff there is a parameter free definition φ of U so that the atomic predicate symbols of φ are recursively open relations on X . The complexity of a definable open set may be identified with the quantifier complexity of its definition. For example, a set U is an ∃∃∀∃-set if it has an ∃∃∀∃ parameter free definition (...) using only recursively open predicate symbols. Since X is not equipped with a natural pairing apparatus such a U need not be an ∃∀∃-set. Let Σ denote the class of all ∃-sets, ∃∃-sets, ∃∃∃-sets etc. We show that an open set is in Σ iff it is equivalent modulo a nowhere dense set to a recursively enumerable open set . Thus Σ = e.r.e. Indeed we show the existence of a universal Σ -set as well as the existence of universal sets for higher levels of the definability hierarchy. (shrink)