We prove that there exists a noncappable enumeration degree strictly below 0' e.

We introduce a new hierarchy of computably enumerable degrees. This hierarchy is based on computable ordinal notations measuring complexity of approximation of${\rm{\Delta }}_2^0$functions. The hierarchy unifies and classifies the combinatorics of a number of diverse constructions in computability theory. It does so along the lines of the high degrees (Martin) and the array noncomputable degrees (Downey, Jockusch, and Stob). The hierarchy also gives a number of natural definability results in the c.e. degrees, including a definable antichain.

We show that every nonzero $\Sigma _{2}^{0}$ enumeration degree bounds a nonsplitting nonzero enumeration degree.

Using properties of${\cal K}$-pairs of sets, we show that every nonzero enumeration degreeabounds a nontrivial initial segment of enumeration degrees whose nonzero elements have all the same jump asa. Some consequences of this fact are derived, that hold in the local structure of the enumeration degrees, including: There is an initial segment of enumeration degrees, whose nonzero elements are all high; there is a nonsplitting high enumeration degree; every noncappable enumeration degree (...) is high; every nonzero low enumeration degree can be capped by degrees of any possible local jump ; every enumeration degree that bounds a nonzero element of strictly smaller jump, is bounding; every low enumeration degree below a non low enumeration degreeacan be capped belowa. (shrink)

A set A is symmetric enumeration (se-) reducible to a set B (A ≤\sb se B) if A is enumeration reducible to B and \barA is enumeration reducible to \barB. This reducibility gives rise to a degree structure (D\sb se) whose least element is the class of computable sets. We give a classification of ≤\sb se in terms of other standard reducibilities and we show that the natural embedding of the Turing degrees (D\sb T) into the (...) enumeration degrees (D\sb e) translates to an embedding (ι\sb se) into D\sb se that preserves least element, suprema, and infima. We define a weak and a strong jump and we observe that ι\sb se preserves the jump operator relative to the latter definition. We prove various (global) results concerning branching, exact pairs, minimal covers, and diamond embeddings in D\sb se. We show that certain classes of se-degrees are first-order definable, in particular, the classes of semirecursive, Σ\sb n ⋃ Π\sb n, Δ\sb n (for any n \in ω), and embedded Turing degrees. This last result allows us to conclude that the theory of D\sb se has the same 1-degree as the theory of Second-Order Arithmetic. (shrink)

We prove that every countable relation on the enumeration degrees, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} ${\frak E}$\end{document}, is uniformly definable from parameters in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} ${\frak E}$\end{document}. Consequently, the first order theory of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} ${\frak E}$\end{document} is recursively isomorphic to the second order theory of arithmetic. By an effective version of coding lemma, we show that the (...) first order theory of the enumeration degrees of the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\Sigma^0_2$\end{document} sets is not decidable. (shrink)

§1. Introduction. Natural sets that can be enumerated by a computable function always seem to be either actually computable or of the same complexity as the Halting Problem, the complete r.e. set K. The obvious question, first posed in Post [1944] and since then called Post's Problem is then just whether there are r.e. sets which are neither computable nor complete, i.e., neither recursive nor of the same Turing degree as K?Let be the r.e. degrees, i.e., the r.e. sets (...) modulo the equivalence relation of equicomputable with the partial order induced by Turing computability. This structure is a partial order with least element 0, the degree of the computable sets, and greatest element 1 or 0′, the degree of K. Post's problem then asks if there are any other elements of.The solution of Post's problem by Friedberg [1957] and Muchnik [1956] was followed by various algebraic or order theoretic results that were interpreted as saying that the structure was in some way well behaved:Theorem 1.1. Every countable partial ordering or even uppersemilattice can be embedded into.Theorem 1.2. For every nonrecursive r.e. degreeathere are r.e. degreesb, c < asuch thatb ∨ c = a.Theorem 1.3. For every pair of nonrecursive r.e. degreesa < bthere is an r.e. degreecsuch thata < c < b. (shrink)

We show that the Π 0 2 enumeration degrees are not dense. This answers a question posed by Cooper.

We characterize the class of c.e. degrees that bound a critical triple as those degrees that compute a function that has no ω-c.e. approximation.

We show that every nonzero $${\Delta^{0}_{2}}$$ enumeration degree bounds the enumeration degree of a 1-generic set. We also point out that the enumeration degrees of 1-generic sets, below the first jump, are not downwards closed, thus answering a question of Cooper.

This paper continues the investigation into the relationship between good approximations and jump inversion initiated by Griffith. Firstly it is shown that there is a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi^{0}_{2}}$$\end{document} set A whose enumeration degree a is bad—i.e. such that no set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${X \in a}$$\end{document} is good approximable—and whose complement \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\overline{A}}$$\end{document} has lowest possible jump, in other (...) words is low2. This also ensures that the degrees y ≤ a only contain \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta^{0}_{3}}$$\end{document} sets and thus yields a tight lower bound for the complexity of both a set of bad enumeration degree, and of its complement, in terms of the high/low jump hierarchy. Extending the author’s previous characterisation of the double jump of good approximable sets, the triple jump of a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma^{0}_{2}}$$\end{document} set A is characterised in terms of the index set of coinfinite sets enumeration reducible to A. The paper concludes by using Griffith’s jump interpolation technique to show that there exists a high quasiminimal \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} enumeration degree. (shrink)

We prove that each Σ 0 2 set which is hypersimple relative to $\emptyset$ ' is noncuppable in the structure of the Σ 0 2 enumeration degrees. This gives a connection between properties of Σ 0 2 sets under inclusion and and the Σ 0 2 enumeration degrees. We also prove that some low non-computably enumerable enumeration degree contains no set which is simple relative to $\emptyset$ '.

We prove that a sequence of sets containing representatives of cupping partners for every nonzero ${\Delta^0_2}$ enumeration degree cannot have a ${\Delta^0_2}$ enumeration. We also prove that no subclass of the ${\Sigma^0_2}$ enumeration degrees containing the nonzero 3-c.e. enumeration degrees can be cupped to ${\mathbf{0}_e'}$ by a single incomplete ${\Sigma^0_2}$ enumeration degree.

Lachlan [9] proved that there exists a non-recursive recursively enumerable degree such that every non-recursive r. e. degree below it bounds a minimal pair. In this paper we first prove the dual of this fact. Second, we answer a question of Jockusch by showing that there exists a pair of incomplete r. e. degrees a0, a1 such that for every non-recursive r. e. degree w, there is a pair of incomparable r. e. degrees b0, b2 such that w (...) = b0 V b1 and bi for i = 0, 1. (shrink)

We examine the computably enumerable (c.e.) degrees of prime models of complete atomic decidable (CAD) theories. A structure has degree d if d is the degree of its elementary diagram. We show that if a CAD theory T has a prime model of c.e. degree c, then T has a prime model of strictly lower c.e. degree b, where, in addition, b is low (b' = 0'). This extends Csima's result that every CAD theory has a low prime model. (...) We also prove a density result for c.e. degrees of prime models. In particular, if c and d are c.e. degrees with d < c and c not low₂ (c" > 0"), then for any CAD theory T, there exists a c.e. degree b with d < b < c such that T has a prime model of degree b, where b can be chosen so that b' is any degree c.e. in c with d' ≤ b'. As a corollary, we show that for any degree c with 0 < c < 0', every CAD theory has a prime model of low c.e. degree incomparable with c. We show also that every CAD theory has prime models of low c.e. degree that form a minimal pair, extending another result of Csima. We then discuss how these results apply to homogeneous models. (shrink)

Lachlan observed that any nonzero d.c.e. degree bounds a nonzero c.e. degree. In this paper, we study the c.e. predecessors of d.c.e. degrees, and prove that given a nonzero d.c.e. degree , there is a c.e. degree below and a high d.c.e. degree such that bounds all the c.e. degrees below . This result gives a unified approach to some seemingly unrelated results. In particular, it has the following two known theorems as corollaries: there is a low c.e. (...) degree isolating a high d.c.e. degree [S. Ishmukhametov, G. Wu, Isolation and the high/low hierarchy, Arch. Math. Logic 41 259–266]; there is a high d.c.e. degree bounding no minimal pairs [C.T. Chong, A. Li, Y. Yang, The existence of high nonbounding degrees in the difference hierarchy, Ann. Pure Appl. Logic 138 31–51]. (shrink)

We show that there exist downwards properly $\Sigma _{2}^{0}$ (in fact noncuppable) e-degrees that are not high. We also show that every high e-degree bounds a noncuppable e-degree.

We give several new characterizations of the continuous enumeration degrees. The main one proves that an enumeration degree is continuous if and only if it is not half a nontrivial relativized K-pair. This leads to a structural dichotomy in the enumeration degrees.

The jump operator on the ω-enumeration degrees was introduced in [I.N. Soskov, The ω-enumeration degrees, J. Logic Computat. 17 1193–1214]. In the present paper we prove a jump inversion theorem which allows us to show that the enumeration degrees are first order definable in the structure of the ω-enumeration degrees augmented by the jump operator. Further on we show that the groups of the automorphisms of and of the enumeration degrees (...) are isomorphic. In the second part of the paper we study the jumps of the ω-enumeration degrees below . We define the ideal of the almost zero degrees and obtain a natural characterization of the class H of the ω-enumeration degrees below which are high n for some n and of the class L of the ω-enumeration degrees below which are low n for some n. (shrink)

We give a simple structural property which characterizes the r.e. sets whose (Turing) degrees are cappable. Since cappable degrees are incomplete, this may be viewed as a solution of Post's program, which asks for a simple structural property of nonrecursive r.e. sets which ensures incompleteness.

We show that there is a limit lemma for enumeration reducibility to 0 e ', analogous to the Shoenfield Limit Lemma in the Turing degrees, which relativises for total enumeration degrees. Using this and `good approximations' we prove a jump inversion result: for any set W with a good approximation and any set X< e W such that W≤ e X' there is a set A such that X≤ e A< e W and A'=W'. (All jumps (...) are enumeration degree jumps.) The degrees of sets with good approximations include the Σ0 2 degrees and the n-CEA degrees. (shrink)

We give an algorithm for deciding whether an embedding of a finite partial order [Formula: see text] into the enumeration degrees of the [Formula: see text]-sets can always be extended to an embedding of a finite partial order [Formula: see text].

We show that every nontrivial interval in the recursively enumerable degrees contains an incomparable pair which have an infimum in the recursively enumerable degrees.

We define a class of finite partial lattices which admit a notion of rank compatible with embedding constructions, and present a necessary and sufficient condition for the embeddability of a finite ranked partial lattice into the computably enumerable degrees.

We show that in the language of {≤}, the Π₃-fragment of the first order theory of the $\Sigma _{2}^{0}$-enumeration degrees is undecidable. We then extend this result to show that the Π₃-theory of any substructure of the enumeration degrees which contains the $\Delta _{2}^{0}$-degrees is undecidable.

Ambos-Spies, K. and R.A. Shore, Undecidability and 1-types in the recursively enumerable degrees, Annals of Pure and Applied Logic 63 3–37. We show that the theory of the partial ordering of recursively enumerable Turing degrees is undecidable and has uncountably many 1-types. In contrast to the original proof of the former which used a very complicated O''' argument our proof proceeds by a much simpler infinite injury argument. Moreover, it combines with the permitting technique to get similar results (...) for any ideal of the r.e. degrees. (shrink)

This paper is dedicated to the study of properties of the operations ∪ and ∩ in the upper semilattice of the e-degrees as well as in the interval (c,c') e for any e-degree c.

We show that the theory of the local structure of the enumeration degrees is computably isomorphic to the theory of first order arithmetic. We introduce a novel coding method, using the notion of a K-pair, to code a large class of countable relations.

Say a set Gω is 1-generic if for any eω, there is a string σG such that {e}σ↓ or τσ↑). It is known that can be split into two 1-generic degrees. In this paper, we generalize this and prove that any nonzero computably enumerable degree can be split into two 1-generic degrees. As a corollary, no two computably enumerable degrees bound the same class of 1-generic degrees.

We show that the theory of the partial ordering of the computably enumerable degrees in any given nontrivial interval is undecidable and has uncountably many 1-types.

We prove that there exists a nonzero recursively enumerable Turing degree possessing a strong minimal cover.

We show that every splitting of ${0}_{\mathrm{e}}^{\prime }$ in the local structure of the enumeration degrees, $$\mathcal{G}_{e} , contains at least one low-cuppable member. We apply this new structural property to show that the classes of all $\mathcal{K}$ -pairs in $\mathcal{G}_{e}$ , all downwards properly ${\mathrm{\Sigma }}_{2}^{0}$ enumeration degrees and all upwards properly ${\mathrm{\Sigma }}_{2}^{0}$ enumeration degrees are first order definable in $\mathcal{G}_{e}$.

We show that every finite lattice is embeddable into the Σ 0 2 enumeration degrees via a lattice-theoretic embedding which preserves 0 and 1.

In this paper, we prove that there exist computably enumerable degrees a and b such that $\mathbf{a} > \mathbf{b}$ and for any degree x, if x ≤ a and x is a minimal degree, then $\mathbf{x}.

We consider the set of jumps below a Turing degree, given by JB={x':x≤a}, with a focus on the problem: Which recursively enumerable degrees a are uniquely determined by JB? Initially, this is motivated as a strategy to solve the rigidity problem for the partial order R of r.e. degrees. Namely, we show that if every high2 r.e. degree a is determined by JB, then R cannot have a nontrivial automorphism. We then defeat the strategy—at least in the form (...) presented—by constructing pairs a0, a1 of distinct r.e. degrees such that JB=JB within any possible jump class {x:x'=c}. We give some extensions of the construction and suggest ways to salvage the attack on rigidity. (shrink)

Sacks [23] asks if the metarecursively enumerable degrees are elementarily equivalent to the r.e. degrees. In unpublished work, Slaman and Shore proved that they are not. This paper provides a simpler proof of that result and characterizes the degree of the theory as [Formula: see text] or, equivalently, that of the truth set of [Formula: see text].

This book presents new results in computability theory, a branch of mathematical logic and computer science that has become increasingly relevant in recent years. The field's connections with disparate areas of mathematical logic and mathematics more generally have grown deeper, and now have a variety of applications in topology, group theory, and other subfields. This monograph establishes new directions in the field, blending classic results with modern research areas such as algorithmic randomness. The significance of the book lies not only (...) in the depth of the results contained therein, but also in the fact that the notions the authors introduce allow them to unify results from several subfields of computability theory. (shrink)

We present a necessary and sufficient condition for the embeddability of a principally decomposable finite lattice into the computably enumerable degrees. This improves a previous result which required that, in addition, the lattice be ranked. The same condition is also necessary and sufficient for a finite lattice to be embeddable below every non-zero computably enumerable degree.