Degrees of recursively enumerable sets which have no maximal supersets
- 10 October 1968
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 33 (3) , 431-443
- https://doi.org/10.2307/2270328
Abstract
The purpose of this paper is to present two new theorems concerning the degrees of coinfinite recursively enumerable (r.e.) sets which have no maximal supersets Let the class of all such degrees be denoted by A. Martin in [2] conjectured that there was some equality or inequality involving a′ or a″ characterizing the degrees a in A. Martin himself proved ([2, Corollary 4.1]) that a′ = 0″ is sufficient for ar r.e. degree a to be in A, and Robinson [3] announced that a′ ≥ 0″ is necessary. In this paper we improve both of these theorems by a factor of the jump, i.e., we shall show that a″ = 0″ is sufficient for an r.e. degree a to be in A, and that a″ ≥ 0″ is necessary.Keywords
This publication has 2 references indexed in Scilit:
- On the lattice of recursively enumerable setsTransactions of the American Mathematical Society, 1968
- Classes of Recursively Enumerable Sets and Degrees of UnsolvabilityMathematical Logic Quarterly, 1966