Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2025-01-03T11:53:27.904Z Has data issue: false hasContentIssue false
  • English
  • Français

Degrees of recursively enumerable sets which have no maximal supersets

Published online by Cambridge University Press:  12 March 2014

A. H. Lachlan
A. H. Lachlan*
Affiliation:
Simon Phaser University
Get access Rights & Permissions [Opens in a new window]

Extract

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.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 33 , Issue 3 , 10 October 1968 , pp. 431 - 443
Copyright
Copyright © Association for Symbolic Logic 1968

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Lachlan, A. H., On the lattice of recursively enumerable sets, Transactions of the American Mathematical Society, vol. 130 (1968), pp. 1–37.CrossRefGoogle Scholar
[2]Martin, D. A., Classes of recursively enumerable sets and degrees of unsolvability, Zetischrift fur Mathematische Logik und Grundlagen der Mathematik, vol. 12 (1966), pp. 295–310.CrossRefGoogle Scholar
[3]Robinson, R. W., Recursively enumerable sets not contained in any maximal set, Abstract 632–4, Notices of the American Mathematical Society, vol. 13 (1966), p. 325.Google Scholar