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)

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)

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)

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 topologicalT0-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)

We carry out a study of definability issues in the standard models of Presburger and Skolem arithmetics (henceforth referred to simply as Presburger and Skolem arithmetics, for short, because we only deal with these models, not the theories, thus there is no risk of confusion) supplied with free unary predicates—which are strongly related to definability in the monadic SOA (second-order arithmetic) without × or + , respectively. As a consequence, we obtain a very direct proof for ${\Pi^1_1}$ -completeness of Presburger, (...) and also Skolem, arithmetic with a free unary predicate, generalize it to all ${\Pi^1_n}$ -levels, and give an alternative description of the analytical hierarchy without × or + . Here ‘direct’ means that one explicitly m-reduces the truth of ${\Pi^1_1}$ -formulae in SOA to the truth in the extended structures. Notice that for the case of Presburger arithmetic, the ${\Pi^1_1}$ -completeness was already known, but the proof was indirect and exploited some special ${\Pi^1_1}$ -completeness results on so-called recurrent nondeterministic Turing machines—for these reasons, it was hardly able to shed any light on definability issues or possible generalizations. (shrink)

In the paper we introduce and study regular enumerations for arbitrary recursive ordinals. Several applications of the technique are presented.

The main result proved in the paper is that on every recursive structure the intrinsically hyperarithmetical sets coincide with the relatively intrinsically hyperarithmetical sets. As a side effect of the proof an effective version of the Kueker's theorem on definability by means of infinitary formulas is obtained.

An external characterization of the inductive sets on countable abstract structures is presented. The main result is an abstract version of the classical Suslin-Kleene characterization of the hyperarithmetical sets.

This paper investigates the algebraic structure of the Medvedev lattice M. We prove that M is not a Heyting algebra. We point out some relations between M and the Dyment lattice and the Mucnik lattice. Some properties of the degrees of enumerability are considered. We give also a result on embedding countable distributive lattices in the Medvedev lattice.

We study the measure independent character of Godel speed-up theorems. In particular, we strengthen Arbib's necessary condition for the occurrence of a Godel speed-up [2, p. 13] to an equivalence result and generalize Di Paola's speed-up theorem [4]. We also characterize undecidable theories as precisely those theories which possess consistent measure independent Godel speed-ups and show that a theory τ 2 is a measure independent Godel speed-up of a theory τ 1 if and only if the set of undecidable sentences (...) of τ 1 which are provable in τ 2 is not recursively enumerable. (shrink)

We carry out a systematic study of decidability for theories of real vector spaces, inner product spaces, and Hilbert spaces and of normed spaces, Banach spaces and metric spaces, all formalized using a 2-sorted first-order language. The theories for list turn out to be decidable while the theories for list are not even arithmetical: the theory of 2-dimensional Banach spaces, for example, has the same many-one degree as the set of truths of second-order arithmetic.We find that the purely universal and (...) purely existential fragments of the theory of normed spaces are decidable, as is the ∀∃ fragment of the theory of metric spaces. These results are sharp of their type: reductions of Hilbertʼs 10th problem show that the ∃∀ fragments for metric and normed spaces and the ∀∃ fragment for normed spaces are all undecidable. (shrink)

We provide and interpret a new measure independent characterization of the Gödel speed-up phenomenon. In particular, we prove a theorem that demonstrates the indifference of the concept of a measure independent Gödel speed-up to an apparent weakening of its definition that is obtained by requiring only those measures appearing in some fixed Blum complexity measure to participate in the speed-up, and by deleting the “for all r” condition from the definition so as to relax the required amount of speed-up. We (...) interpret our results as correlating the relative difficulty of mechanically recognizing theories with the relative power and the relative abstractness of the theories. We conclude by providing two open problems concerning possible similarities and relationships between the Blum speedability and Gödel speed-up phenomena. MSC: 03D15, 03F20. (shrink)

If A and B are subsets of natural numbers we say that A is recursively equivalent to B (denoted A ≃ B) if there is a one-one partial recursive function which maps A onto B, and that A is recursively isomorphic to B (denoted A ≅ B) if there is a one-one total recursive function which maps A onto B and Ā (the complement of A) onto B#x00AF;.

In [2] we constructed an infinite set of natural numbers containing no subset of higher (Turing) degree. Since it is well known that there are nonrecursive sets (e.g. sets of minimal degree) containing no nonrecursive subset of lower degree, it is natural to suppose that these arguments may be combined, but this is false. We prove that every infinite set must contain a nonrecursive subset of either higher or lower degree.

Many of our concepts are introduced to us via, and seem only to be constrained by, roughand-ready explanations and some sample paradigm positive and negative applications. This happens even in informal logic and mathematics. Yet in some cases, the concepts in question – although only informally and vaguely characterized – in fact have, or appear to have, entirely determinate extensions. Here’s one familiar example. When we start learning computability theory, we are introduced to the idea of an algorithmically computable function (...) (from numbers to numbers) – i.e. one whose value for any given input can be determined by a step-by-step calculating procedure, where each step is fully determined by some antecedently given finite set of calculating rules. We are told that we are to abstract from practical considerations of how many steps will be needed and how much ink will be spilt in the process, so long as everything remains finite. We are also told that each step is to be ‘small’ and the rules governing it must be ‘simple’, available to a cognitively limited calculating agent: for we want an algorithmic procedure, step-by-minimal-step, to be idiot-proof. For a classic elucidation of this kind, see e.g. Rogers (1967, pp. 1–5). Church’s Thesis, in one form, then claims this informally explicated concept in fact has a perfectly precise extension, the set of recursive functions. Church’s Thesis can be supported in a quasi-empirical way, by the failure of our searches for counterexamples. It can be supported too in a more principled way, by the observation that different appealing ways of sharpening up the informal chararacterization of algorithmic computability end up specifying the same set of recursive functions. But such considerations fall short of a demonstration of the Thesis. So is there a different argumentative strategy we could use, one that could lead to a proof? Sometimes it is claimed that there just can’t be, because you can never really prove results involving an informal concept like algorithmic computability.. (shrink)

Profinite groups are Galois groups. The effective study of infinite Galois groups was initiated by Metakides and Nerode [8] and further developed by LaRoche [5]. In this paper we study profinite groups without considering Galois extensions of fields. The Artin method of representing a finite group as a Galois group has been generalized by Waterhouse [14] to profinite groups. Thus, there is no loss of relevance in our approach.The fundamental notions of a co-r.e. profinite group, recursively profinite group, and the (...) degree of a co-r.e. profinite group are defined in §1. In this section we prove that every co-r.e. profinite group can be effectively represented as an inverse limit of finite groups. The degree invariant is shown to behave very well with respect to open subgroups and quotients. The work done in this section is basic to the rest of the paper.The commutator subgroup, the Frattini subgroup, thep-Sylow subgroups, and the center of a profinite group are essential in the study of profinite groups. It is only natural to ask if these subgroups are effective. The following question exemplifies our approach to this problem: Is the center a co-r.e. profinite group? Theorem 2 provides a general method for answering this type of question negatively. Examples 3,4 and 5 are all applications of this theorem. (shrink)

Let CKDT be the assertion that for every countably infinite bipartite graph G, there exist a vertex covering C of G and a matching M in G such that C consists of exactly one vertex from each edge in M. (This is a theorem of Podewski and Steffens [12].) Let ATR0 be the subsystem of second-order arithmetic with arithmetical transfinite recursion and restricted induction. Let RCA0 be the subsystem of second-order arithmetic with recursive comprehension and restricted induction. We show that (...) CKDT is provable in ART0. Combining this with a result of Aharoni, Magidor, and Shore [2], we see that CKDT is logically equivalent to the axioms of ATR0, the equivalence being provable in RCA0. (shrink)

A well known fact is that every Lebesgue measurable set is regular, i.e., it includes an F$_{\sigma}$ set of the same measure. We analyze this fact from a metamathematical or foundational standpoint. We study a family of Muchnik degrees corresponding to measure-theoretic regularity at all levels of the effective Borel hierarchy. We prove some new results concerning Nies's notion of LR-reducibility. We build some $\omega$-models of RCA$_0$which are relevant for the reverse mathematics of measure-theoretic regularity.

A mass problem is a set of Turing oracles. If P and Q are mass problems, we say that P is weakly reducible to Q if every member of Q Turing computes a member of P. We say that P is strongly reducible to Q if every member of Q Turing computes a member of P via a fixed Turing functional. The weak degrees and strong degrees are the equivalence classes of mass problems under weak and strong reducibility, respectively. We (...) focus on the countable distributive lattices P w and P s of weak and strong degrees of mass problems given by nonempty Π 1 0 subsets of 2 ω . Using an abstract Gödel/Rosser incompleteness property, we characterize the Π 1 0 subsets of 2 ω whose associated mass problems are of top degree in P w and P s , respectively. Let R be the set of Turing oracles which are random in the sense of Martin-Löf, and let r be the weak degree of R. We show that r is a natural intermediate degree within P w . Namely, we characterize r as the unique largest weak degree of a Π 1 0 subset of 2 ω of positive measure. Within P w we show that r is meet irreducible, does not join to 1, and is incomparable with all weak degrees of nonempty thin perfect Π 1 0 subsets of 2 ω . In addition, we present other natural examples of intermediate degrees in P w . We relate these examples to reverse mathematics, computational complexity, and Gentzen-style proof theory. (shrink)

This paper is essentially the author's Gödel Lecture at the ASL Logic Colloquium '09 in Sofia extended and supplemented by material from some other papers. After a brief description of traditional reverse mathematics, a computational approach to is presented. There are then discussions of some interactions between reverse mathematics and the major branches of mathematical logic in terms of the techniques they supply as well as theorems for analysis. The emphasis here is on ones that lie outside the usual main (...) systems of reverse mathematics. While retaining the usual base theory and working still within second order arithmetic, theorems are described that range from those far below the usual systems to ones far above. (shrink)

We describe the important role that the conjectures and questions posed at the end of the two editions of Gerald Sacks's Degrees of Unsolvability have had in the development of recursion theory over the past thirty years.

This paper surveys the recent developments in the area that grew out of attempts to solve an analog of Hilbert's Tenth Problem for the field of rational numbers and the rings of integers of number fields. It is based on a plenary talk the author gave at the annual North American meeting of ASL at the University of Notre Dame in May of 2009.

We show that Diophantine equivalence of two suitably presented countable rings implies that the existential polynomial languages of the two rings have the same "expressive power" and that their Diophantine sets are in some sense the same. We also show that a Diophantine class of countable rings is contained completely within a relative enumeration class and demonstrate that one consequence of this fact is the existence of infinitely many Diophantine classes containing holomophy rings of Q.

§1. Overview. Philosophers and mathematicians have drawn lots of conclusions from Gödel's incompleteness theorems, and related results from mathematical logic. Languages, minds, and machines figure prominently in the discussion. Gödel's theorems surely tell us something about these important matters. But what?A descriptive title for this paper would be “Gödel, Lucas, Penrose, Turing, Feferman, Dummett, mechanism, optimism, reflection, and indefinite extensibility”. Adding “God and the Devil” would probably be redundant. Despite the breath-taking, whirlwind tour, I have the modest aim of forging (...) connections between different parts of this literature and clearing up some confusions, together with the less modest aim of not introducing any more confusions.I propose to focus on three spheres within the literature on incompleteness. The first, and primary, one concerns arguments that Gödel's theorem refutes the mechanistic thesis that the human mind is, or can be accurately modeled as, a digital computer or a Turing machine. The most famous instance is the much reprinted J. R. Lucas [18]. To summarize, suppose that a mechanist provides plans for a machine,M, and claims that the output ofMconsists of all and only the arithmetic truths that a human, or the totality of human mathematicians, will ever or can ever know. We assume that the output ofMis consistent. (shrink)