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.

     

On the definable ideal generated by the plus cupping c.e. degrees

In this paper, we will prove that the plus cupping degrees generate a definable ideal on c.e. degrees different from other ones known so far, thus answering a question asked by Li and Yang (Proceedings of the 7th and the 8th Asian Logic Conferences. World Scientific Press, Singapore, 2003).     

The low<Subscript><Emphasis Type="Italic">n</Emphasis></Subscript> and low<Subscript><Emphasis Type="Italic">m</Emphasis></Subscript> r. e. degrees are not elementarily equivalent

Jockusch, Li and Yang showed that the Lown and Low1 r.e. degrees are not elementarily equivalent for n > 1. We answer a question they raise by using the results of Nies, Shore and Slaman to show that the Lown and Lowm r.e. degrees are not elementarily equivalent for n > m > 1.     

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.

     

A splitting theorem for degrees

We prove that, for any , and with _{T}A\oplus U$"> and r.e., in , there are pairs and such that ; ; and, for any and from and any set , if and , then . We then deduce that for any degrees , , and such that and are recursive in , , and is into , can be split over avoiding . This shows that the Main Theorem of Cooper (Bull. Amer. Math. Soc. 23 (1990), 151-158) is false.

     

Strong jump-traceability I: The computably enumerable case

Recent investigations in algorithmic randomness have lead to the discovery and analysis of the fundamental class K of reals called the K-trivial reals, defined as those whose initial segment complexity is identical with that of the sequence of all 1's. There remain many important open questions concerning this class, such as whether there is a combinatorial characterization of the class and whether it coincides with possibly smaller subclasses, such as the class of reals which are not sufficiently powerful as oracles to cup a Turing incomplete Martin-Löf random real to the halting problem. Hidden here is the question of whether there exist proper natural subclasses of K. We show that the combinatorial class of computably enumerable, strongly jump-traceable reals, defined via the jump operator by Figueira, Nies and Stephan [Santiago Figueira, André Nies, Frank Stephan, Lowness properties and approximations of the jump, Electr. Notes Theor. Comput. Sci. 143 (2006) 45-57], is such a class, and show that like K, it is an ideal in the computably enumerable degrees. This is the first example of a class of reals defined by a “cost function” construction which forms a proper subclass of K. Further, we show that every c.e., strongly jump-traceable set is not Martin-Löf cuppable, thus giving a combinatorial property which implies non-ML cuppability.     

A minimal pair joining to a plus cupping Turing degree

A computably enumerable (c.e.) degree a is called nonbounding, if it bounds no minimal pair, and plus cupping, if every nonzero c.e. degree x below a is cuppable. Let NB and PC be the sets of all nonbounding and plus cupping c.e. degrees, respectively. Both NB and PC are well understood, but it has not been possible so far to distinguish between the two classes. In the present paper, we investigate the relationship between the classes NB and PC , and show that there exists a minimal pair which join to a plus cupping degree, so that PC ? NB . This gives a first known difference between NB and PC . (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

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.     

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$.     

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.     

Splitting in 2-computably enumerable degrees with avoiding cones

In this paper we show that for any pair of properly 2-c. e. degrees 0 < d < a such that there are no c. e. degrees between d and a, the degree a is splittable in the class of 2-c. e. degrees avoiding the upper cone of d. We also study the possibility to characterize such an isolation in terms of splitting.     

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.     

Restrictions on the degree spectra of algebraic structures

We construct the degree b ≤ 0″ admitting no algebraic structure with degree spectrum {x: x ? b}. Moreover, we solve Miller’s problem of distinguishing incomparable degrees by the spectra of linear orderings.     

There is no degree invariant half-jump

We prove that there is no degree invariant solution to Post's problem that always gives an intermediate degree. In fact, assuming definable determinacy, if is any definable operator on degrees such that on a cone then is low or high on a cone of degrees, i.e., there is a degree such that for every or for every .

     

Some reducibilities and splittings of recursively enumerable sets

The existence of a recursively enumerable (RE)T-degreea that does not contain an RE semirecursive setA ∈a with theQ-universal splitting property is proved. Each nonrecursive RE contiguous degree contains an RE setA with the universalT-Q-reduction property, butA is notT-Q-maximal. Each nonrecursive REW-degree contains an RE setA with the universalW-sQ-reduction property, butA is notW-sQ-maximal. Each creative set is partially semimaximal. Translated fromMatematicheskie Zametki, Vol. 66, No. 2, pp. 220–230, August, 1999.     

Isomorphism of lattices of recursively enumerable sets

Let , and for , let be the lattice of subsets of which are recursively enumerable relative to the ``oracle' . Let be , where is the ideal of finite subsets of . It is established that for any , is effectively isomorphic to if and only if , where is the Turing jump of . A consequence is that if , then . A second consequence is that can be effectively embedded into preserving least and greatest elements if and only if .

     

Non-Uniformity and Generalised Sacks Splitting

We show that there do not exist computable functions f ₁(e, i), f ₂(e, i), g ₁(e, i), g ₂(e, i) such that for all e, i ∈ ω, (1) $ {\left( {W_{{f_{1} {\left( {e,i} \right)}}} - W_{{f_{2} {\left( {e,i} \right)}}} } \right)} \leqslant _{{\rm T}} {\left( {W_{e} - W_{i} } \right)}; $ (2) $ {\left( {W_{{g_{1} {\left( {e,i} \right)}}} - W_{{g_{2} {\left( {e,i} \right)}}} } \right)} \leqslant _{{\rm T}} {\left( {W_{e} - W_{i} } \right)}; $ (3) $ {\left( {W_{e} - W_{i} } \right)} \not\leqslant _{{\rm T}} {\left( {W_{{f_{1} {\left( {e,i} \right)}}} - W_{{f_{2} {\left( {e,i} \right)}}} } \right)} \oplus {\left( {W_{{g_{1} {\left( {e,i} \right)}}} - W_{{g_{2} {\left( {e,i} \right)}}} } \right)}; $ (4) $ {\left( {W_{e} - W_{i} } \right)} \not\leqslant _{{\rm T}} {\left( {W_{{f_{1} {\left( {e,i} \right)}}} - W_{{f_{2} {\left( {e,i} \right)}}} } \right)}{\text{unless}}{\left( {W_{e} - W_{i} } \right)} \leqslant _{{\rm T}} {\emptyset};{\text{and}} $ (5) $ {\left( {W_{e} - W_{i} } \right)} \leqslant _{{\rm T}} {\left( {W_{{g_{1} {\left( {e,i} \right)}}} - W_{{g_{2} {\left( {e,i} \right)}}} } \right)}{\text{unless}}{\left( {W_{e} - W_{i} } \right)} \leqslant _{{\rm T}} {\emptyset}. $ It follows that the splitting theorems of Sacks and Cooper cannot be combined uniformly.     

Non‐isolated quasi‐degrees

We show that non‐isolated from below 2‐c.e. Q ‐degrees are dense in the structure of c.e. Q ‐degrees. We construct a 2‐c.e. Q ‐degree, which can't be isolated from below not only by c.e. Q ‐degrees, but by any Q ‐degree. We also prove that below any c.e. Q ‐degree there is a 2‐c.e. Q ‐degree, which is non‐isolated from below and from above (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Complexity properties of recursively enumerable sets andbsQ-completeness

The notions of boundedly strongly effectively speedable set and boundedly effectively speedable set are introduced. It is proved that the notions of boundedly strongly effectively speedable set, boundedly effectively speedable set, creative set, andbsQ-complete recursively enumerable set are equivalent. Translated fromMatematicheskie Zametki, Vol. 68, No. 4, pp. 554–559, October, 2000.     

On the bounded quasi‐degrees of c.e. sets

We study the degree structure of bQ‐reducibility and we prove that for any noncomputable c.e. incomplete bQ‐degree a, there exists a nonspeedable bQ‐degree incomparable with it. The structure $\mathcal {D}_{\mbox{bs}}$ of the $\mbox{bs}$‐degrees is not elementary equivalent neither to the structure of the $\mbox{be}$‐degrees nor to the structure of the $\mbox{e}$‐degrees. If c.e. degrees a and b form a minimal pair in the c.e. bQ‐degrees, then a and b form a minimal pair in the bQ‐degrees. Also, for every simple set S there is a noncomputable nonspeedable set A which is bQ‐incomparable with S and bQ‐degrees of S and A does not form a minimal pair.