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: 33,066
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

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 Ce 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. Hermann - 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 downloads
14 ( #386,466 of 2,241,585 )

Recent downloads (6 months)
4 ( #113,097 of 2,241,585 )

How can I increase my downloads?

Monthly downloads

My notes

Sign in to use this feature