We investigate and extend the notion of a good approximation with respect to the enumeration ${({\mathcal D}_{\rm e})}$ and singleton ${({\mathcal D}_{\rm s})}$ degrees. We refine two results by Griffith, on the inversion of the jump of sets with a good approximation, and we consider the relation between the double jump and index sets, in the context of enumeration reducibility. We study partial order embeddings ${\iota_s}$ and ${\hat{\iota}_s}$ of, respectively, ${{\mathcal D}_{\rm e}}$ and ${{\mathcal D}_{\rm T}}$ (the Turing degrees) into (...) ${{\mathcal D}_{\rm s}}$ , and we show that the image of ${{\mathcal D}_{\rm T}}$ under ${\hat{\iota}_s}$ is precisely the class of retraceable singleton degrees. We define the notion of a good enumeration, or singleton, degree to be the property of containing the set of good stages of some good approximation, and we show that ${\iota_s}$ preserves the latter, as also other naturally arising properties such as that of totality or of being ${\Gamma^0_n}$ , for ${\Gamma \in \{\Sigma,\Pi,\Delta\}}$ and n > 0. We prove that the good enumeration and singleton degrees are immune and that the good ${\Sigma^0_2}$ singleton degrees are hyperimmune. Finally we show that, for singleton degrees a s < b s such that b s is good, any countable partial order can be embedded in the interval (a s, b s). (shrink)

Defining a class of sets to be uniform Δ02 if it is derived from a binary {0,1}{0,1}-valued function f≤TKf≤TK, we show that, for any C⊆DeC⊆De induced by such a class, there exists a high Δ02 degree c which is incomparable with every degree b ϵ Ce \ {0e, 0'e}. We show how this result can be applied to quite general subclasses of the Ershov Hierarchy and we also prove, as a direct corollary, that every nonzero low degree caps with both (...) a high and a nonzero low Δ02 degree. (shrink)

We prove that for every ${\mathrm{\Sigma }}_{2}^{0}$ enumeration degree b there exists a noncuppable ${\mathrm{\Sigma }}_{2}^{0}$ degree a > 0 e such that b′ ≤ e a′ and a″ ≤ e b″. This allows us to deduce, from results on the high/low jump hierarchy in the local Turing degrees and the jump preserving properties of the standard embedding l: D T → D e , that there exist ${\mathrm{\Sigma }}_{2}^{0}$ noncuppable enumeration degrees at every possible—i.e., above low₁—level of the high/low (...) jump hierarchy in the context of D e. (shrink)

We develop an approach to the longstanding conjecture of Kierstead concerning the character of strongly nontrivial automorphisms of computable linear orderings. Our main result is that for any η-like computable linear ordering, such that has no interval of order type η, and such that the order type of is determined by a -limitwise monotonic maximal block function, there exists computable such that has no nontrivial automorphism.

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)

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 discuss a notion of forcing that characterizes enumeration 1-genericity, and we investigate the immunity, lowness, and quasiminimality properties of enumeration 1-generic sets and their degrees. We construct an enumeration operator Δ such that, for any A, the set ΔA is enumeration 1-generic and has the same jump complexity as A. We deduce from this and other recent results from the literature that not only does every degree a bound an enumeration 1-generic degree b such that a'=b', but also that, (...) if a is nonzero, then we can find such b satisfying 0eshrink)