The computable Lipschitz degrees of computably enumerable sets are not dense

The computable Lipschitz reducibility was introduced by Downey, Hirschfeldt and LaForte under the name of strong weak truth-table reducibility (Downey et al. (2004) [6]). This reducibility measures both the relative randomness and the relative computational power of real numbers. This paper proves that the computable Lipschitz degrees of computably enumerable sets are not dense. An immediate corollary is that the Solovay degrees of strongly c.e. reals are not dense. There are similarities to Barmpalias and Lewis’ proof that the identity bounded Turing degrees of c.e. sets are not dense (George Barmpalias, Andrew E.M. Lewis (2006) [2]), however the problem for the computable Lipschitz degrees is more complex.     

A computably enumerable vector space with the strong antibasis property

Downey and Remmel have completely characterized the degrees of c.e. bases for c.e. vector spaces (and c.e. fields) in terms of weak truth table degrees. In this paper we obtain a structural result concerning the interaction between the c.e. Turing degrees and the c.e. weak truth table degrees, which by Downey and Remmel's classification, establishes the existence of c.e. vector spaces (and fields) with the strong antibasis property (a question which they raised). Namely, we construct c.e. sets such that the c.e. W-degrees below that of A are disjoint from the nonzero c.e. T-degrees below that of A and comparable to that of B. Received: 2 December 1998     

Jumps of computably enumerable equivalence relations

We study computably enumerable equivalence relations (or, ceers), under computable reducibility ≤, and the halting jump operation on ceers. We show that every jump is uniform join-irreducible, and thus join-irreducible. Therefore, the uniform join of two incomparable ceers is not equivalent to any jump. On the other hand there exist ceers that are not equivalent to jumps, but are uniform join-irreducible: in fact above any non-universal ceer there is a ceer which is not equivalent to a jump, and is uniform join-irreducible. We also study transfinite iterations of the jump operation. If a is an ordinal notation, and E is a ceer, then let $E^{(a)}$ denote the ceer obtained by transfinitely iterating the jump on E along the path of ordinal notations up to a. In contrast with what happens for the Turing jump and Turing reducibility, where if a set X is an upper bound for the A-arithmetical sets then $X^{(2)}$ computes $A^{(\omega )}$, we show that there is a ceer R such that $R\ge {\mathrm{Id}}^{(n)}$, for every finite ordinal n, but, for all k, $R^{(k)}?{\mathrm{Id}}^{(\omega )}$ (here Id is the identity equivalence relation). We show that if $a,b$ are notations of the same ordinal less than ${\omega }^2$, then $E^{(a)}\equiv E^{(b)}$, but there are notations $a,b$ of ${\omega }^2$ such that ${\mathrm{Id}}^{(a)}$ and ${\mathrm{Id}}^{(b)}$ are incomparable. Moreover, there is no non-universal ceer which is an upper bound for all the ceers of the form ${\mathrm{Id}}^{(a)}$ where a is a notation for ${\omega }^2$.     

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     

Kolmogorov complexity and computably enumerable sets

We study the computably enumerable sets in terms of the:     

On the filter of computably enumerable supersets of an r-maximal set

We study the filter ℒ^*(A) of computably enumerable supersets (modulo finite sets) of an r-maximal set A and show that, for some such set A, the property of being cofinite in ℒ^*(A) is still Σ⁰ ₃-complete. This implies that for this A, there is no uniformly computably enumerable “tower” of sets exhausting exactly the coinfinite sets in ℒ^*(A). Received: 6 November 1999 / Revised version: 10 March 2000 /?Published online: 18 May 2001     

Low upper bounds in the LR degrees

We say that A≤_LRB if every B-random real is A-random—in other words, if B has at least as much derandomization power as A. The LR reducibility is a natural weak reducibility in the context of randomness, and generalizes lowness for randomness. We study the existence and properties of upper bounds in the context of the LR degrees. In particular, we show that given two (or even finitely many) low sets, there is a low c.e. set which lies LR above both. This is very different from the situation in the Turing degrees, where Sacks’ splitting theorem shows that two low sets can join to 0^′.     

The -theory of the computably enumerable Turing degrees is undecidable

We show the undecidability of the -theory of the partial order of computably enumerable Turing degrees.

     

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.     

A join theorem for the computably enumerable degrees

It is shown that for any computably enumerable (c.e.) degree , if , then there is a c.e. degree such that (so is lowand is high). It follows from this and previous work of P. Cholak, M. Groszek and T. Slaman that the low and low c.e. degrees are not elementarily equivalent as partial orderings.

     

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     

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.     

A semilattice generated by superlow computably enumerable degrees

We prove that a partially ordered set of all computably enumerable (c. e.) degrees that are the least upper bounds of two superlow c. e. degrees is an upper semilattice not elementary equivalent to the semilattice of all c. e. degrees.     

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.     

Martin’s Axiom and embeddings of upper semi-lattices into the Turing degrees

It is shown that every locally countable upper semi-lattice of cardinality the continuum can be embedded into the Turing degrees, assuming Martin’s Axiom.     

An extension of the recursively enumerable Turing degrees

Consider the countable semilattice _T consisting of the recursivelyenumerable Turing degrees. Although _T is known to be structurallyrich, a major source of frustration is that no specific, naturaldegrees in _T have been discovered, except the bottom and topdegrees, 0 and 0'. In order to overcome this difficulty, weembed _T into a larger degree structure which is better behaved.Namely, consider the countable distributive lattice _w consistingof the weak degrees (also known as Muchnik degrees) of massproblems associated with non-empty ₀¹ subsets of 2. It is knownthat _w contains a bottom degree 0 and a top degree 1 and isstructurally rich. Moreover, _w contains many specific, naturaldegrees other than 0 and 1. In particular, we show that in _wone has 0 < d < r₁ < f(r₂, 1) < 1. Here, d is theweak degree of the diagonally non-recursive functions, and r_nis the weak degree of the n-random reals. It is known that r₁can be characterized as the maximum weak degree of a ₀¹ subsetof 2 of positive measure. We now show thatf(r₂, 1) can be characterizedas the maximum weak degree of a ₀¹ subset of 2, the Turing upwardclosure of which is of positive measure. We exhibit a naturalembedding of _T into _w which is one-to-one, preserves the semilatticestructure of _T, carries 0 to 0, and carries 0' to 1. Identifying_T with its image in _w, we show that all of the degrees in _Texcept 0 and 1 are incomparable with the specific degrees d,r₁, andf(r₂, 1) in _w.