Movatterモバイル変換

Anderson and Csima :245–264, 2014) defined a jump operator, the bounded jump, with respect to bounded Turing reducibility. They showed that the bounded jump is closely related to the Ershov hierarchy and that it satisfies an analogue of Shoenfield jump inversion. We show that there are high bounded low sets and low bounded high sets. Thus, the information coded in the bounded jump is quite different from that of the standard jump. We also consider whether the analogue of the Jump (...) Theorem holds for the bounded jump: do we have A≤bTB\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A \le _{bT}B$$\end{document} if and only if Ab≤1Bb\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A^b \le _1 B^b$$\end{document}? We show the forward direction holds but not the reverse. (shrink)

No categories

Direct download(2 more)   Export citation   Bookmark   2 citations  

We show that if H is an effectively completely decomposable computable torsion-free abelian group, then there is a computable copy G of H such that G has computable orders but not orders of every degree.

Direct download(5 more)   Export citation   Bookmark   2 citations  

We say a countable model ������ has a 0-basis if the types realized in ������ are uniformly computable. We say ������ has a (d-)decidable copy if there exists a model ������ ≅ ������ such that the elementary diagram of ������ is (d-)computable. Goncharov, Millar, and Peretyat'kin independently showed there exists a homogeneous model ������ with a 0-basis but no decidable copy. We extend this result here. Let d ≤ 0' be any low₂ degree. We show that there exists a homogeneous (...) model ������ with a 0-basis but no d-decidable copy. A degree d is 0-basis homogeneous bounding if any homogenous ������ with a 0-basis has a d-decidable copy. In previous work, we showed that the nonlow₂ $\Delta _{2}^{0}$ degrees are 0-basis homogeneous bounding. The result of this paper shows that this is an exact characterization of the 0-basis homogeneous bounding $\Delta _{2}^{0}$ degrees. (shrink)

Direct download(7 more)   Export citation   Bookmark   3 citations  

Much previous study has been done on the degree spectra of prime models of a complete atomic decidable theory. Here we study the analogous questions for homogeneous models. We say a countable model A has a d-basis if the types realized in A are all computable and the Turing degree d can list $\Delta _{0}^{0}$ -indices for all types realized in A. We say A has a d-decidable copy if there exists a model B ≅ A such that the elementary (...) diagram of B is d-computable. Goncharov, Millar, and Peretyat'kin independently showed there exists a homogeneous A with a 0-basis but no decidable copy. We prove that any homogeneous A with a 0'-basis has a low decidable copy. This implies Csima's analogous result for prime models. In the case where all types of the theory T are computable and A is a homogeneous model with a 0-basis, we show A has copies decidable in every nonzero degree. A degree d is 0-homogeneous bounding if any automorphically nontrivial homogeneous A with a 0-basis has a d-decidable copy. We show that the nonlow₂ $\Delta _{2}^{0}$ degrees are 0-homogeneous bounding. (shrink)

Direct download(6 more)   Export citation   Bookmark   3 citations  

In the last five years there have been a number of results about the computable content of the prime, saturated, or homogeneous models of a complete decidable theory T in the spirit of Vaught's "Denumerable models of complete theories" combined with computability methods for degrees d ≤ 0′. First we recast older results by Goncharov, Peretyat'kin, and Millar in a more modern framework which we then apply. Then we survey recent results by Lange, "The degree spectra of homogeneous models," which (...) generalize the older results and which include positive results on when a certain homogeneous model of T has an isomorphic copy of a given Turing degree. We then survey Lange's "A characterization of the 0-basis homogeneous bounding degrees" for negative results about when does not have such copies, generalizing negative results by Goncharov, Peretyat'kin, and Millar. Finally, we explain recent results by Csima, Harizanov, Hirschfeldt, and Soare, "Bounding homogeneous models," about degrees d that are homogeneous bounding and explain their relation to the PA degrees. (shrink)

Direct download(3 more)   Export citation   Bookmark   3 citations  

We give a valuation theoretic characterization for a real closed field to be recursively saturated. This builds on work in [9], where the authors gave such a characterization forκ-saturation, for a cardinal$\kappa \ge \aleph _0 $. Our result extends the characterization of Harnik and Ressayre [7] for a divisible ordered abelian group to be recursively saturated.

Direct download(8 more)   Export citation   Bookmark   1 citation  

Soare [20] proved that the maximal sets form an orbit in${\cal E}$. We consider here${\cal D}$-maximal sets, generalizations of maximal sets introduced by Herrmann and Kummer [12]. Some orbits of${\cal D}$-maximal sets are well understood, e.g., hemimaximal sets [8], but many are not. The goal of this paper is to define new invariants on computably enumerable sets and to use them to give a complete nontrivial classification of the${\cal D}$-maximal sets. Although these invariants help us to better understand the${\cal D}$-maximal (...) sets, we use them to show that several classes of${\cal D}$-maximal sets break into infinitely many orbits. (shrink)

Direct download(2 more)   Export citation   Bookmark  

Direct download(5 more)   Export citation   Bookmark  

Direct download(3 more)   Export citation   Bookmark  

Let R be a real closed field. An integer part I for R is a discretely ordered subring such that for every \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${r \in R}$$\end{document}, there exists an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${i \in I}$$\end{document} so that i ≤ r< i + 1. Mourgues and Ressayre (J Symb Logic 58:641–647, 1993) showed that every real closed field has an integer part. The procedure of Mourgues and (...) Ressayre appears to be quite complicated. We would like to know whether there is a simple procedure, yielding an integer part that is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta^0_2(R)}$$\end{document} —limit computable relative to R. We show that there is a maximal Z-ring \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${I \subseteq R}$$\end{document} which is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta^0_2(R)}$$\end{document}. However, this I may not be an integer part for R. By a result of Wilkie (Logic Colloquium ’77), any Z-ring can be extended to an integer part for some real closed field. Using Wilkie’s ideas, we produce a real closed field R with a Z-ring \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${I \subseteq R}$$\end{document} such that I does not extend to an integer part for R. For a computable real closed field, we do not know whether there must be an integer part in the class \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta^0_2}$$\end{document}. We know that certain subclasses of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta^0_2}$$\end{document} are not sufficient. We show that for each \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${n \in \omega}$$\end{document}, there is a computable real closed field with no n-c.e. integer part. In fact, there is a computable real closed field with no n-c.e. integer part for any n. (shrink)

Direct download(4 more)   Export citation   Bookmark   1 citation  

We prove that for every Scott set S there are S-saturated real closed fields and S-saturated models of Presburger arithmetic.

Direct download(4 more)   Export citation   Bookmark  

We introduce agreement reducibility and highlight its major features. Given subsets A and B of, we write if there is a total computable function satisfying for all,.We shall discuss the central role plays in this reducibility and its connection to strong‐hyper‐hyper‐immunity. We shall also compare agreement reducibility to other well‐known reducibilities, in particular s1‐ and s‐reducibility. We came upon this reducibility while studying the computable reducibility of a class of equivalence relations on based on set‐agreement. We end by describing the (...) origin of agreement reducibility and presenting some results in that context. (shrink)

No categories

Direct download(2 more)   Export citation   Bookmark  

Let K be a family of structures, closed under isomorphism, in a fixed computable language. We consider effective lists of structures from K such that every structure in K is isomorphic to exactly one structure on the list. Such a list is called a computable classification of K, up to isomorphism. Using the technique of Friedberg enumeration, we show that there is a computable classification of the family of computable algebraic fields and that with a 0'-oracle, we can obtain similar (...) classifications of the families of computable equivalence structures and of computable finite-branching trees. However, there is no computable classification of the latter, nor of the family of computable torsion-free abelian groups of rank 1, even though these families are both closely allied with computable algebraic fields. (shrink)

Direct download(4 more)   Export citation   Bookmark