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.     

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.

     

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.     

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.     

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.

     

Minimal degrees which are but not

We give a short proof of the existence of minimal Turing degrees which are but not .

     

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.     

A nonlow2 R. E. Degree with the Extension of Embeddings Properties of a low2 Degree

We construct a nonlow₂ r.e. degree d such that every positive extension of embeddings property that holds below every low₂ degree holds below d . Indeed, we can also guarantee the converse so that there is a low r.e. degree c such that that the extension of embeddings properties true below c are exactly the ones true belowd.Moreover, we can also guarantee that no b ≤ d is the base of a nonsplitting pair.     

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 .

     

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

A proof of a partition theorem for

In this note we give a proof of Devlin's theorem via Milliken's theorem about weakly embedded subtrees of the complete binary tree . Unlike the original proof which is (still unpublished) long and uses the language of category theory, our proof is short and uses direct combinatorial reasoning.

     

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)     

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.     

A splitting theorem for manifolds of almost nonnegative Ricci curvature

Cheeger and Gromoll proved that a closed Riemannian manifold of nonnegative Ricci curvature is, up to a finite cover, diffeomorphic to a direct product of a simply connected manifold and a torus. In this paper, we extend this theorem to manifolds of almost nonnegative Ricci curvature.     

Recursively compressible sets

Classes of recursively compressible and incompressible sets as well as some other classes emerging in connection with a simple recursive-theory model of data array packing are studied. Some new completeness criteria for sets are obtained.Translated fromMatematicheskie Zametki, Vol. 64, No. 1, pp. 9–16, July, 1998.     

A fixed-point theorem for usco maps

The familiar fixed-point theorem of Kakutani is strengthened by weakening the hypotheses on the set-valued mapping. Applications are made for and decompositions of compact metric spaces.

     

A note on mixed graphs and directed splitting off

We give counterexamples to two conjectures of Bill Jackson in Some remarks on arc-connectivity, vertex splitting, and orientation in graphs and digraphs (Journal of Graph Theory 12 (3):429–436, 1988) concerning orientations of mixed graphs and splitting off in digraphs, and prove the first conjecture in the (di-) Eulerian case(s). Beside that we solve a degree constrained non-uniform directed augmentation problem for di-Eulerian mixed graphs. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 213–221, 1998     

Cotlar-Stein lemma and the theorem

In this note we give a generalization of the Cotlar-Stein lemma and using this lemma we give a new proof of a special case of the theorem which, in general, was proved by David, Journé and Semmes.

     

A splitting theorem for the Medvedev and Muchnik lattices

This is a contribution to the study of the Muchnik and Medvedev lattices of non‐empty Π⁰₁ subsets of 2^ω. In both these lattices, any non‐minimum element can be split, i. e. it is the non‐trivial join of two other elements. In fact, in the Medvedev case, ifP > _M Q, then P can be split above Q. Both of these facts are then generalised to the embedding of arbitrary finite distributive lattices. A consequence of this is that both lattices have decidible ?‐theories.