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

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.     

Isolation and the Jump Operator

We show the existence of a high d. c. e. degree d and a low₂ c.e. degree a such that d is isolated by a .     

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.     

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)     

The Isolated D. R. E. Degrees are Dense in the R. E. Degrees

In the present paper we prove that the isolated differences of r. e. degrees are dense in the r. e. degrees. Mathematics Subject Classification: 03D25.     

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)     

On Lachlan’s major sub-degree problem

The Major Sub-degree Problem of A. H. Lachlan (first posed in 1967) has become a long-standing open question concerning the structure of the computably enumerable (c.e.) degrees. Its solution has important implications for Turing definability and for the ongoing programme of fully characterising the theory of the c.e. Turing degrees. A c.e. degree a is a major subdegree of a c.e. degree b > a if for any c.e. degree x, if and only if . In this paper, we show that every c.e. degree b ≠ 0 or 0′ has a major sub-degree, answering Lachlan’s question affirmatively. Both authors were funded by EPSRC Research Grant no. GR/M 91419, “Turing Definability”, by INTAS-RFBR Research Grant no. 97-0139, “Computability and Models”, and by an NSFC Grand International Joint Project Grant no. 60310213, “New Directions in Theory and Applications of Models of Computation”. Both authors are grateful to Andrew Lewis for helpful suggestions regarding presentation, technical aspects of the proof, and verification. A. Li is partially supported by National Distinguished Young Investigator Award no. 60325206 (People’s Republic of China).     

On Genericity and Ershov's Hierarchy

It is natural to wish to study miniaturisations of Cohen forcing suitable to sets of low arithmetic complexity. We consider extensions of the work of Schaeffer [9] and Jockusch and Posner [6] by looking at genericity notions within the Δ₂ sets. Different equivalent characterisations of 1‐genericity suggest different ways in which the definition might be generalised. There are two natural ways of casting the notion of 1‐genericity: in terms of sets of strings and in terms of density functions, as we will see here. While these definitions coincide at the first level of the difference hierarchy, they turn out to differ at other levels. Furthermore, these differences remain when the remainder of the Δ⁰₂ sets are considered. While the string characterization of 1‐genericity collapses at the second level of the difference hierarchy to 2‐genericity, the density function definition gives a very interesting hierarchy at level w and above. Both of these results point towards the deep similarities exhibited by the n‐c.e. degrees for n ≥ 2.     

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.     

A Splitting with Infimum in the d‐c. e. Degrees

In this paper we prove that any c. e. degree is splittable with an c. e. infimum over any lesser c. e. degree in the class of d‐c. e. degrees.     

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)     

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.

     

Lower and upper orientable strong radius and strong diameter of complete k-partite graphs

For two vertices u and v in a strong digraph D, the strong distance sd(u,v) between u and v is the minimum size (the number of arcs) of a strong sub-digraph of D containing u and v. For a vertex v of D, the strong eccentricity se(v) is the strong distance between v and a vertex farthest from v. The strong radius srad(D) (resp. strong diameter sdiam(D)) is the minimum (resp. maximum) strong eccentricity among the vertices of D. The lower (resp. upper) orientable strong radius srad(G) (resp. SRAD(G)) of a graph G is the minimum (resp. maximum) strong radius over all strong orientations of G. The lower (resp. upper) orientable strong diameter sdiam(G) (resp. SDIAM(G)) of a graph G is the minimum (resp. maximum) strong diameter over all strong orientations of G. In this paper, we determine the lower orientable strong radius and diameter of complete k-partite graphs, and give the upper orientable strong diameter and the bounds on the upper orientable strong radius of complete k-partite graphs. We also find an error about the lower orientable strong diameter of complete bipartite graph K_m,n given in [Y.-L. Lai, F.-H. Chiang, C.-H. Lin, T.-C. Yu, Strong distance of complete bipartite graphs, The 19th Workshop on Combinatorial Mathematics and Computation Theory, 2002, pp. 12-16], and give a rigorous proof of a revised conclusion about sdiam(K_m,n).     

On the Universal Splitting Property

We prove that if an incomplete computably enumerable set has the the universal splitting property then it is low₂. This solves a question from Ambos-Spies and Fejer [1] and Downey and Stob [7]. Some technical improvements are discussed.     

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 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)