Every incomplete computably enumerable truth-table degree is branching

If r is a reducibility between sets of numbers, a natural question to ask about the structure ? _r of the r-degrees containing computably enumerable sets is whether every element not equal to the greatest one is branching (i.e., the meet of two elements strictly above it). For the commonly studied reducibilities, the answer to this question is known except for the case of truth-table (tt) reducibility. In this paper, we answer the question in the tt case by showing that every tt-incomplete computably enumerable truth-table degree a is branching in ? _tt . The fact that every Turing-incomplete computably enumerable truth-table degree is branching has been known for some time. This fact can be shown using a technique of Ambos-Spies and, as noticed by Nies, also follows from a relativization of a result of Degtev. We give a proof here using the Ambos-Spies technique because it has not yet appeared in the literature. The proof uses an infinite injury argument. Our main result is the proof when a is Turing-complete but tt-incomplete. Here we are able to exploit the Turing-completeness of a in a novel way to give a finite injury proof. Received: 22 January 1999 / Revised version: 12 July 1999 / Published online: 21 December 2000     

Lowness properties and randomness

The set A is low for (Martin-Löf) randomness if each random set is already random relative to A. A is K-trivial if the prefix complexity K of each initial segment of A is minimal, namely . We show that these classes coincide. This answers a question of Ambos-Spies and Ku?era in: P. Cholak, S. Lempp, M. Lerman, R. Shore, (Eds.), Computability Theory and Its Applications: Current Trends and Open Problems, American Mathematical Society, Providence, RI, 2000: each low for Martin-Löf random set is . Our class induces a natural intermediate ideal in the r.e. Turing degrees, which generates the whole class under downward closure.Answering a further question in P. Cholak, S. Lempp, M. Lerman, R. Shore, (Eds.), Computability Theory and Its Applications: Current Trends and Open Problems, American Mathematical Society, Providence, RI, 2000, we prove that each low for computably random set is computable.     

Presentations of the successor relation of computable linear ordering

We prove that a nontrivial degree spectrum of the successor relation of either strongly η-like or non-η-like computable linear orderings is closed upwards in the class of all computably enumerable degrees. We also show that the degree spectrum contains 0 if and only if either it is trivial or it contains all computably enumerable degrees.     

Strong jump-traceability II: <Emphasis Type="Italic">K</Emphasis>-triviality

We show that every strongly jump-traceable set is K-trivial. Unlike other results, we do not assume that the sets in question are computably enumerable.     

Torsion-free constructive nilpotent <Emphasis Type="Italic">R</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>-groups

We consider a torsion-free nilpotent R _p -group, the p-rank of whose quotient by the commutant is equal to 1 and either the rank of the center by the commutant is infinite or the rank of the group by the commutant is finite. We prove that the group is constructivizable if and only if it is isomorphic to the central extension of some divisible torsion-free constructive abelian group by some torsion-free constructive abelian R _p -group with a computably enumerable basis and a computable system of commutators. We obtain similar criteria for groups of that type as well as divisible groups to be positively defined. We also obtain sufficient conditions for the constructivizability of positively defined groups.     

Every Set has a Least Jump Enumeration

Given a computably enumerable set W, there is a Turing degreewhich is the least jump of any set in which W is computablyenumerable, namely 0'. Remarkably, this is not a phenomenonof computably enumerable sets. It is shown that for every subsetA of N, there is a Turing degree, c'_µ(A), which is theleast degree of the jumps of all sets X for which A is . In addition this result providesan isomorphism invariant method for assigning Turing degreesto certain torsion-free abelian groups.     

Isolated 2-computably enumerable <Emphasis Type="Italic">Q</Emphasis>-degrees

In this work we prove that for every pair of computably enumerable degrees a<Q b there exists a properly 2-computably enumerable degree d such that a <Q d <Q b, a isolates d from below, and b isolates d from above. Two corollaries follow from this result. First, there exists a 2-computably enumerable degree which is Q-incomparable with any nontrivial (different from 0 and 0′) computably enumerable degree. Second, every nontrivial computably enumerable degree isolates some 2-computably enumerable degree from below and some 2-computably enumerable degree from above.     

Degrees of Autostability Relative to Strong Constructivizations of Graphs

We show that each computably enumerable Turing degree is a degree of autostability relative to strong constructivizations for a decidable directed graph. We construct a decidable undirected graph whose autostability spectrum relative to strong constructivizations is equal to the set of all PA-degrees.     

The computably enumerable degrees are locally non-cappable

We prove that every non-computable incomplete computably enumerable degree is locally non-cappable, and use this result to show that there is no maximal non-bounding computably enumerable degree. The author was supported by an EPSRC Research Studentship. Mathematics Subject Classification (2000):03D25 Keywords or phrases:Computably enumerable – Degree     

An Interval of Computably Enumerable Isolating Degrees

We construct computably enumerable degrees a < b such that all computably enumerable degrees c with a < c < b isolate some d. c. e. degree d.     

Regular reals

Say that α is an n‐strongly c. e. (n‐strongly computably enumerable) real if α is a sum of n many strongly c. e. reals, and that α is regular if α is n‐strongly c. e. for some n. Let Sⁿ be the set of all n‐strongly c. e. reals, Reg be the set of regular reals and CE be the set of c. e. reals. Then we have: S¹ ? S² ? · · · ? Sⁿ ? · · · ? ? Reg ? CE . This gives a hierarchy of the c. e. reals. We also study the regularity of the d. c. e. reals. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Atomlessr-maximal sets

We focus on % MathType!End!2!1!(A), the filter of supersets ofA in the structure of the computably enumerable sets under the inclusion relation, whereA is an atomlessr-maximal set. We answer a long-standing question by showing that there are infinitely many pairwise non-isomorphic filters of this type. Research partially supported NSF Grants DMS-96-3465 (Cholak) and DMS-95-00983 (Nies). The authors would like to thank Mike Stob for his help and interest.     

Strong noncuppability in low computably enumerable degrees

We prove the existence of noncomputable low computably enumerable degrees b < a such that b is strongly noncuppable to a in the class R.     

On a Conjecture of Kleene and Post

A proof is given that 0 ′ (the argest Turing degree containing a computably enumerable set) is definable in the structure of the degrees of unsolvability. This answers a long‐standing question of Kleene and Post, and has a number of corollaries including the definability of the jump operator.     

Schnorr trivial reals: a construction

A real is Martin-Löf (Schnorr) random if it does not belong to any effectively presented null ${\Sigma^0_1}A real is Martin-L?f (Schnorr) random if it does not belong to any effectively presented null (recursive) class of reals. Although these randomness notions are very closely related, the set of Turing degrees containing reals that are K-trivial has very different properties from the set of Turing degrees that are Schnorr trivial. Nies proved in (Adv Math 197(1):274–305, 2005) that all K-trivial reals are low. In this paper, we prove that if , then h contains a Schnorr trivial real. Since this concept appears to separate computational complexity from computational strength, it suggests that Schnorr trivial reals should be considered in a structure other than the Turing degrees. This material is based upon work supported under a National Science Foundation Graduate Research Fellowship and appears in the author’s Ph.D. thesis. A preliminary version of this paper appeared in Electronic Notes in Theoretical Computer Science     

Elementary differences between the degrees of unsolvability and degrees of compressibility

Given two infinite binary sequences A,B we say that B can compress at least as well as A if the prefix-free Kolmogorov complexity relative to B of any binary string is at most as much as the prefix-free Kolmogorov complexity relative to A, modulo a constant. This relation, introduced in Nies (2005) [14] and denoted by A≤_LKB, is a measure of relative compressing power of oracles, in the same way that Turing reducibility is a measure of relative information. The equivalence classes induced by ≤_LK are called LK degrees (or degrees of compressibility) and there is a least degree containing the oracles which can only compress as much as a computable oracle, also called the ‘low for K’ sets. A well-known result from Nies (2005) [14] states that these coincide with the K-trivial sets, which are the ones whose initial segments have minimal prefix-free Kolmogorov complexity.We show that with respect to ≤_LK, given any non-trivial sets X,Y there is a computably enumerable set A which is not K-trivial and it is below X,Y. This shows that the local structures of and Turing degrees are not elementarily equivalent to the corresponding local structures in the LK degrees. It also shows that there is no pair of sets computable from the halting problem which forms a minimal pair in the LK degrees; this is sharp in terms of the jump, as it is known that there are sets computable from which form a minimal pair in the LK degrees. We also show that the structure of LK degrees below the LK degree of the halting problem is not elementarily equivalent to the or structures of LK degrees. The proofs introduce a new technique of permitting below a set that is not K-trivial, which is likely to have wider applications.     

Lattice embeddings and array noncomputable degrees

We focus on a particular class of computably enumerable (c. e.) degrees, the array noncomputable degrees defined by Downey, Jockusch, and Stob, to answer questions related to lattice embeddings and definability in the partial ordering (??, ≤) of c. e. degrees under Turing reducibility. We demonstrate that the latticeM₅ cannot be embedded into the c. e. degrees below every array noncomputable degree, or even below every nonlow array noncomputable degree. As Downey and Shore have proved that M₅ can be embedded below every nonlow₂ degree, our result is the best possible in terms of array noncomputable degrees and jump classes. Further, this result shows that the array noncomputable degrees are definably different from the nonlow₂ degrees. We note also that there are embeddings of M₅ in which all five degrees are array noncomputable, and in which the bottom degree is the computable degree 0 but the other four are array noncomputable. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Modulo computably enumerable degrees by cupping partners

Cupping partners of an element in an upper semilattice with a greatest element 1 are those joining the element to 1. We define a congruence relation on such an upper semilattice by considering the elements having the same cupping partners as equivalent. It is interesting that this congruence relation induces a non-dense quotient structure of computably enumerable Turing degrees. Another main interesting phenomenon in this article is that on the computably enumerable degrees, this relation is different from that modulo the noncuppable ideal, though they define a same equivalent class for the computable Turing degree.