Truth tabular degrees of recursively enumerable sets

The upper semilattice of truth tabular degrees of recursively enumerable (r.e.) sets is studied. It is shown that there exists an infinite set of pairwise tabularly incomparable truth tabular degrees higher than any tabularly incomplete r.e. truth tabular degree. A similar assertion holds also for r.e. m-degrees. Hence follows that a complete truth tabular degree contains an infinite antichain of r.e. m-degrees.Translated from Matematicheskie Zametki, Vol. 14, No. 5, pp. 697–702, November, 1973.     

The distribution of the generic recursively enumerable degrees

Summary In this paper we investigate problems about densities ofe-generic,s-generic andp-generic degrees. We, in particular, show that allp-generic degrees are non-branching, which answers an open question by Jockusch who asked: whether alls-generic degrees are non-branching and refutes a conjecture of Ingrassia; the set of degrees containing r.e.p-generic sets is the same as the set of r.e. degrees containing an r.e. non-autoreducible set.This research was supported by a grant of the Stiftung Volkswagenwerk     

Cappable recursively enumerable degrees and Post's program

We give a simple structural property which characterizes the r.e. sets whose (Turing) degrees are cappable. Since cappable degrees are incomplete, this may be viewed as a solution of Post's program, which asks for a simple structural property of nonrecursive r.e. sets which ensures incompleteness.Part of this research was done while the authors visited the Mathematical Sciences research Institute, Berkeley     

The discontinuity of splitting in the recursively enumerable degrees

In this paper we examine a class of pairs of recursively enumerable degrees, which is related to the Slaman-Soare Phenomenon.Preparation of this paper supported by S.E.R.C. (UK) Research Grant no. GR/H 02165, and by European network Complexity, Logic and Recursion Theory (EC Contract No. ERBCHRXCT930415). The second author wishes to thank Alistair H. Lachlan and the University of Leeds     

Minimal pairs in initial segments of the recursively enumerable degrees

We show that for every r.e. Turing degreea>0, there is an r.e. degreeb<a which is not half of a minimal pair in the initial segment [0, a]. This work was partially supported by National Science Foundation Grant DMS88-00030 to Stob, the New Zealand Marsden Fund for Basic Research in Science Grant VIC-509 to Downey, and New Zealand-United States Cooperative Science Program Grant INT90-20558 from the National Science Foundation to both authors. The authors thank the referee for several helpful comments.     

Not every finite lattice is embeddable in the recursively enumerable degrees

A certain lattice with eight elements is shown to be not embeddable as a lattice in the recursively enumerable degrees. This refutes the well-known Embedding Conjecture which asserted that every finite lattice could be so embedded.     

The existence of minimal honest polynomial degree below and recursively enumerable degrees

In [1] Homer introduced the honest polynomial reducibility and proved that under this new reducibility a set of minimal degree below O″ is constructed under the assumption thatP=NP. In this paper we will prove that under the same assumption a set of minimal degree can be constructed below any recursively enumerable degrees. So under the honest polynomial reducibility a set of low minimal degree does exist.