Some New Lattice Constructions in High R. E. Degrees

Mathematical Logic Quarterly 41 (3):395-430 (1995)

A well-known theorem by Martin asserts that the degrees of maximal sets are precisely the high recursively enumerable degrees, and the same is true with ‘maximal’ replaced by ‘dense simple’, ‘r-maximal’, ‘strongly hypersimple’ or ‘finitely strongly hypersimple’. Many other constructions can also be carried out in any given high r. e. degree, for instance r-maximal or hyperhypersimple sets without maximal supersets . In this paper questions of this type are considered systematically. Ultimately it is shown that every conjunction of simplicity- and non-extensibility properties can be accomplished, unless it is ruled out by well-known, elementary results. Moreover, each construction can be carried out in any given high r. e. degree, as might be expected. For instance, every high r. e. degree contains a dense simple, strongly hypersimple set A which is contained neither in a hyperhypersimple nor in an r-maximal set. The paper also contains some auxiliary results, for instance: every r. e. set B can be transformed into an r. e. set A such that A has no dense simple superset, the transformation preserves simplicity- or non-extensibility properties as far as this is consistent with , and A [TRIPLE BOND]TB if B is high, and A ≥TB otherwise. Several proofs involve refinements of known constructions; relationships to earlier results are discussed in detail
Keywords Hypersimple set  Simple set  Hyperhypersimple set  High r. e. degree  Maximal set  Turing degree
Categories (categorize this paper)
DOI 10.1002/malq.19950410311
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 48,784
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Hypersimplicity and Semicomputability in the Weak Truth Table Degrees.George Barmpalias - 2005 - Archive for Mathematical Logic 44 (8):1045-1065.
A Jump Operator on Honest Subrecursive Degrees.Lars Kristiansen - 1998 - Archive for Mathematical Logic 37 (2):105-125.
Maximal Contiguous Degrees.Peter Cholak, Rod Downey & Stephen Walk - 2002 - Journal of Symbolic Logic 67 (1):409-437.
Q 1-Degrees of C.E. Sets.R. Sh Omanadze & Irakli O. Chitaia - 2012 - Archive for Mathematical Logic 51 (5-6):503-515.
Joining to High Degrees Via Noncuppables.Jiang Liu & Guohua Wu - 2010 - Archive for Mathematical Logic 49 (2):195-211.
On Lachlan’s Major Sub-Degree Problem.S. Barry Cooper & Angsheng Li - 2008 - Archive for Mathematical Logic 47 (4):341-434.
1-Reducibility Inside an M-Degree with Maximal Set.E. Herrmann - 1992 - Journal of Symbolic Logic 57 (3):1046-1056.
On Relative Enumerability of Turing Degrees.Shamil Ishmukhametov - 2000 - Archive for Mathematical Logic 39 (3):145-154.
Wtt-Degrees and T-Degrees of R.E. Sets.Michael Stob - 1983 - Journal of Symbolic Logic 48 (4):921-930.
On the Jump Classes of Noncuppable Enumeration Degrees.Charles M. Harris - 2011 - Journal of Symbolic Logic 76 (1):177 - 197.
Isolation in the CEA Hierarchy.Geoffrey LaForte - 2004 - Archive for Mathematical Logic 44 (2):227-244.
On Very High Degrees.Keng Meng Ng - 2008 - Journal of Symbolic Logic 73 (1):309-342.


Added to PP index

Total views
37 ( #252,045 of 2,309,284 )

Recent downloads (6 months)
7 ( #128,759 of 2,309,284 )

How can I increase my downloads?


My notes

Sign in to use this feature