RECURSIVE BAIRE CLASSIFICATION AND SPEEDABLE FUNCTIONS

Using recursive variants of Baire notions of nowhere dense and meagre sets we study the topological size of speedable and infinitely often speedable functions in a machine-independent framework. We show that the set of speedable functions is not “small” whereas the set of infinitely often speedable functions is “large”. In this way we offer partial answers to a question in [4].     

Difference Sets and Recursion Theory

There is a recursive set of natural numbers which is the difference set of some recursively enumerable set but which is not the difference set of any recursive set.     

The Isolated D. R. E. Degrees are Dense in the R. E. Degrees

In the present paper we prove that the isolated differences of r. e. degrees are dense in the r. e. degrees. Mathematics Subject Classification: 03D25.     

Infimum Properties Differ in the Weak Truth-table Degrees and the Turing Degrees

Abstract We prove that there are non-recursive r.e. sets A and C with A < _T C such that for every set . Both authors are supported by “863” and the National Science Foundation of China     

Graphs realised by r.e. equivalence relations

We investigate dependence of recursively enumerable graphs on the equality relation given by a specific r.e. equivalence relation on ω. In particular we compare r.e. equivalence relations in terms of graphs they permit to represent. This defines partially ordered sets that depend on classes of graphs under consideration. We investigate some algebraic properties of these partially ordered sets. For instance, we show that some of these partial ordered sets possess atoms, minimal and maximal elements. We also fully describe the isomorphism types of some of these partial orders.     

Automorphisms of Models of True Arithmetic: Subgroups which Extend to a Maximal Subgroup Uniquely

We show that if M is a countable recursively saturated model of True Arithmetic, then G = Aut(M) has nonmaximal open subgroups with unique extension to a maximal subgroup of Aut(M). Mathematics Subject Classification: 03C62, 03C50.     

Low sets without subsets of higher many‐one degree

Given a reducibility ?_r, we say that an infinite set A is r‐introimmune if A is not r‐reducible to any of its subsets B with |A\B| = ∞. We consider the many‐one reducibility ?_m and we prove the existence of a low₁ m‐introimmune set in Π⁰₁ and the existence of a low₁ bi‐m‐introimmune set.     

The Recursively Mahlo Property in Second Order Arithmetic

The paper characterizes the second order arithmetic theorems of a set theory that features a recursively Mahlo universe; thereby complementing prior proof-theoretic investigations on this notion. It is shown that the property of being recursively Mahlo corresponds to a certain kind of β-model reflection in second order arithmetic. Further, this leads to a characterization of the reals recursively computable in the superjump functional. Mathematics Subject Classification: 03F35, 03F15, 03E70.     

Resplendent models and $${\Sigma_1^1}$$ -definability with an oracle

In this article we find some sufficient and some necessary -conditions with oracles for a model to be resplendent or chronically resplendent. The main tool of our proofs is internal arguments, that is analogues of classical theorems and model-theoretic constructions conducted inside a model of first-order Peano Arithmetic: arithmetised back-and-forth constructions and versions of the arithmetised completeness theorem, namely constructions of recursively saturated and resplendent models from the point of view of a model of arithmetic. These internal arguments are used in conjunction with Pabion’s theorem that ensures that certain oracles are coded in a sufficiently saturated model of arithmetic. Examples of applications are provided for the theories of dense linear orders and of discrete linear orders. These results are then generalised to other ω-categorical theories and theories with a unique countable recursively saturated model.      

On a Class of Recursively Enumerable Sets

We define a class of so-called ∑(n)-sets as a natural closure of recursively enumerable sets W_n under the relation “∈” and study its properties.