Hostname: page-component-7b7567c8c-8p88z Total loading time: 0 Render date: 2026-11-19T17:55:51.074Z Has data issue: false hasContentIssue false

Degrees of recursively enumerable sets which have no maximal supersets

Published online by Cambridge University Press:  12 March 2014

A. H. Lachlan*
Affiliation:
Simon Phaser University

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.

Information

Type
Research Article
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.)

Article purchase

Temporarily unavailable