Vol. 40, No. 3, 1972

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 294: 1
Vol. 293: 1  2
Vol. 292: 1  2
Vol. 291: 1  2
Vol. 290: 1  2
Vol. 289: 1  2
Vol. 288: 1  2
Vol. 287: 1  2
Online Archive
Volume:
Issue:
     
The Journal
Subscriptions
Editorial Board
Officers
Special Issues
Submission Guidelines
Submission Form
Contacts
Author Index
To Appear
 
ISSN: 0030-8730
Degrees of members of Π10 classes

Carl Groos Jockusch, Jr. and Robert Irving Soare

Vol. 40 (1972), No. 3, 605–616
Abstract

This paper deals with the degrees of members of Π10 classes of sets or function which lack recursive members. For instance, it is shown that if a is a degree and 0 < a 0, then there exists a Π10 class of sets which has a member of degree a but none of degree 0. By way of contrast there is no Π10 class of functions which has members of all nonzero r.e. degrees but no recursive members. Furthermore, each nonempty Π10 class of sets has a member of r.e. degree but not necessarily of r.e. degree less than 0. As corollaries results are derived about degrees of theories and degrees of models such as: (1) There is an axiomatizable, essentially undecidable theory with a complete extension of minimal degree; (2) (ScottTennenbaum): There is a complete extension of Peano arithmetic of degree 0but none of r.e. degree < 0;(3) There is no nonstandard model of Peano arithmetic of r.e. degree < 0. The recursion theorem is applied to yield new information about standard constructions such as Yates’ simple nonhypersimple set of given nonzero r.e. degree.

Mathematical Subject Classification
Primary: 02F40
Milestones
Received: 27 October 1970
Published: 1 March 1972
Authors
Carl Groos Jockusch, Jr.
Robert Irving Soare