Premium
Some New Lattice Constructions in High R. E. Degrees
Author(s) -
Rolletschek Heinrich
Publication year - 1995
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19950410311
Subject(s) - mathematics , mathematical proof , recursively enumerable language , simple (philosophy) , simplicity , maximal set , degree (music) , combinatorics , set (abstract data type) , lattice (music) , discrete mathematics , recursively enumerable set , maximal element , extensibility , type (biology) , computer science , geometry , philosophy , physics , epistemology , acoustics , programming language , ecology , biology , operating system
A well‐known theorem by Martin asserts that the degrees of maximal sets are precisely the high recursively enumerable (r. e.) 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 (Lerman, Lachlan). 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 (i) A has no dense simple superset, (ii) the transformation preserves simplicity‐ or non‐extensibility properties as far as this is consistent with (i), and (iii) A T B if B is high, and A ≥ T B otherwise. Several proofs involve refinements of known constructions; relationships to earlier results are discussed in detail.