Given two (positive) equivalence relations ∼ 1 , ∼ 2 on the set ω of natural numbers, we say that ∼ 1 is m-reducible to ∼ 2 if there exists a total recursive function h such that for every x, y ∈ ω, we have $x \sim_1 y \operatorname{iff} hx \sim_2 hy$ . We prove that the equivalence relation induced in ω by a positive precomplete numeration is complete with respect to this reducibility (and, moreover, a "uniformity property" holds). This (...) result allows us to state a classification theorem for positive equivalence relations (Theorem 2). We show that there exist nonisomorphic positive equivalence relations which are complete with respect to the above reducibility; in particular, we discuss the provable equivalence of a strong enough theory: this relation is complete with respect to reducibility but it does not correspond to a precomplete numeration. From this fact we deduce that an equivalence relation on ω can be strongly represented by a formula (see Definition 8) iff it is positive. At last, we interpret the situation from a topological point of view. Among other things, we generalize a result of Visser by showing that the topological space corresponding to a partition in e.i. sets is irreducible and we prove that the set of equivalence classes of true sentences is dense in the Lindenbaum algebra of the theory. (shrink)

We analyse the connection between the computability and continuity of functions in the case of homomorphisms between topological algebraic structures. Inspired by the Pour-El and Richards equivalence theorem between computability and boundedness for closed linear operators on Banach spaces, we study the rather general situation of partial homomorphisms between metric partial universal algebras. First, we develop a set of basic notions and results that reveal some of the delicate algebraic, topological and effective properties of partial algebras. Our main computability concepts (...) are based on numerations and include those of effective metric partial algebras and effective partial homomorphisms. We prove a general equivalence theorem that includes a version of the Pour-El and Richards Theorem, and has other applications. Finally, the Pour-El and Richards axioms for computable sequence structures on Banach spaces are generalised to computable partial sequence structures on metric algebras, and we prove their equivalence with our computability model based on numerations. (shrink)

Khutoretskii's Theorem states that the Rogers semilattice of any family of c.e. sets has either at most one or infinitely many elements. A lemma in the inductive step of the proof shows that no Rogers semilattice can be partitioned into a principal ideal and a principal filter. We show that such a partitioning is possible for some family of d.c.e. sets. In fact, we construct a family of c.e. sets which, when viewed as a family of d.c.e. sets, has (up (...) to equivalence) exactly two computable Friedberg numberings ¼ and ν, and ¼ reduces to any computable numbering not equivalent to ν. The question of whether the full statement of Khutoretskii's Theorem fails for families of d.c.e. sets remains open. (shrink)

In the context of his theory of numberings, Ershov showed that Kleene's recursion theorem holds for any precomplete numbering. We discuss various generalizations of this result. Among other things, we show that Arslanov's completeness criterion also holds for every precomplete numbering, and we discuss the relation with Visser's ADN theorem, as well as the uniformity or nonuniformity of the various fixed point theorems. Finally, we base numberings on partial combinatory algebras and prove a generalization of Ershov's theorem in this context.

A strong reducibility relation between partial numberings is introduced which is such that the reduction function transfers exactly the numbers which are indices under the numbering to be reduced into corresponding indices of the other numbering. The degrees of partial numberings of a given set with respect to this relation form an upper semilattice.In addition, Ershov’s completion construction for total numberings is extended to the partial case: every partially numbered set can be embedded in a set which results from the (...) given set by adding one point and which is enumerated by a total and complete numbering. As is shown, the degrees of complete numberings of the extended set also form an upper semilattice. Moreover, both semilattices are isomorphic.This is not so in the case of the usual, weaker reducibility relation for partial numberings which allows the reduction function to transfer arbitrary numbers into indices. (shrink)

Berger, U., Total sets and objects in domain theory, Annals of Pure and Applied Logic 60 91-117. Total sets and objects generalizing total functions are introduced into the theory of effective domains of Scott and Ersov. Using these notions Kreisel's Density Theorem and the Theorem of Kreisel-Lacombe-Shoenfield are generalized. As an immediate consequence we obtain the well-known continuity of computable functions on the constructive reals as well as a domain-theoretic characterization of the Heriditarily Effective Operations.

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

In examples like the total recursive functions or the computable real numbers the canonical indexings are only partial maps. It is even impossible in these cases to find an equivalent total numbering. We consider effectively given topological T 0 -spaces and study the problem in which cases the canonical numberings of such spaces can be totalized, i.e., have an equivalent total indexing. Moreover, we show under very natural assumptions that such spaces can effectively and effectively homeomorphically be embedded into a (...) totally indexed algebraic partial order that is closed under the operation of taking least upper bounds of enumerable directed subsets. (shrink)

The different behaviour of total and partial numberings with respect to the reducibility preorder is investigated. Partial numberings appear quite naturally in computability studies for topological spaces. The degrees of partial numberings form a distributive lattice which in the case of an infinite numbered set is neither complete nor contains a least element. Friedberg numberings are no longer minimal in this situation. Indeed, there is an infinite descending chain of non-equivalent Friedberg numberings below every given numbering, as well as an (...) uncountable antichain. (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)

In this paper we study the reducibility order m (defined in a natural way) over n 0 -equivalence relations. In particular, for every n> 0 we exhibit n 0 -equivalence relations which are complete with respect to m and investigate some consequences of this fact (see Introduction).

We prove a number of elementary facts about computability in partial combinatory algebras. We disprove a suggestion made by Kreisel about using Friedberg numberings to construct extensional pca’s. We then discuss separability and elements without total extensions. We relate this to Ershov’s notion of precompleteness, and we show that precomplete numberings are not 1–1 in general.

We investigate properties of universal numberings of finite families of d.c.e. sets. We show different cases of finite families of d.c.e. sets for which there is a universal numbering and for which there is not.

We present a model of computation for string functions over single-sorted, total algebraic structures and study some basic features of a general theory of computability within this framework. Our concept generalizes the Blum-Shub-Smale setting of computability over the reals and other rings. By dealing with strings of arbitrary length instead of tuples of fixed length, some suppositions of deeper results within former approaches to generalized recursion theory become superfluous. Moreover, this gives the basis for introducing computational complexity in a BSS-like (...) manner. Relationships both to classical computability and to Friedman's concept of eds computability are established. Two kinds of nondeterminism as well as several variants of recognizability are investigated with respect to interdependencies on each other and on properties of the underlying structures. For structures of finite signatures, there are universal programs with the usual characteristics. For the general case of not necessarily finite signature, this subject will be studied in a separate, forthcoming paper. (shrink)

A metric space is said to be locally non-compact if every neighborhood contains a sequence that is eventually bounded away from every element of the space, hence contains no accumulation point. We show within recursive mathematics that a nonvoid complete metric space is locally non-compact iff it is without isolated points.The result has an interesting consequence in computable analysis: If a complete metric space has a computable witness that it is without isolated points, then every neighborhood contains a computable sequence (...) that is eventually computably bounded away from every computable element of the space. (shrink)

If one wants to compute with infinite objects like real numbers or data streams, continuity is a necessary requirement: better and better (finite) approximations of the input are transformed into better and better (finite) approximations of the output. In case the objects are constructively generated, they can be represented by a finite description of the generating procedure. By effectively transforming such descriptions for the generation of the input (respectively, their codes) into (the code of) a description for the generation of (...) the output another type of computable operation is obtained. Such operations are also called effective. The relationship of both classes of operations has always been a question of great interest. In this paper the setting is extended to the case of multifunctions. Various ways of coding (indexing) sets are discussed and their relationship is investigated. Moreover, effective versions of several continuity notions for multifunctions are introduced. For each of these notions an indexing system for sets is exhibited so that the multifunctions that are effective with respect to this indexing system are exactly the multifunction which are effectively continuous with respect to the continuity notion under consideration. Mostly, in addition to being effective the multifunctions need also possess certain witnessing functions. Important special cases are discussed where such witnessing functions always exist. (shrink)

Limitwise monotonic sets and functions constitute an important tool in computable structure theory. We investigate limitwise monotonic numberings. A numbering ν of a family is limitwise monotonic (l.m.) if every set is the range of a limitwise monotonic function, uniformly in k. The set of all l.m. numberings of S induces the Rogers semilattice. The semilattices exhibit a peculiar behavior, which puts them in‐between the classical Rogers semilattices (for computable families) and Rogers semilattices of ‐computable families. We show that every (...) Rogers semilattice of a ‐computable family is isomorphic to some semilattice. On the other hand, there are infinitely many isomorphism types of classical Rogers semilattices which can be realized as semilattices. In particular, there is an l.m. family S such that is isomorphic to the upper semilattice of c.e. m‐degrees. We prove that if an l.m. family S contains more than one element, then the poset is infinite, and it is not a lattice. The l.m. numberings form an ideal (w.r.t. reducibility between numberings) inside the class of all ‐computable numberings. We prove that inside this class, the index set of l.m. numberings is ‐complete. (shrink)

The paper contains some observations on e-complete, precomplete, and uniformly finitely precomplete r. e. equivalence relations. Among these are a construction of a uniformly finitely precomplete r. e. equivalence which is neither e- nor precomplete, an extension of Lachlan's theorem that all precomplete r. e. equivalences are isomorphic, and a characterization of sets of fixed points of endomorphisms of uniformly finitely precomplete r. e. equivalences.