Vol. 24, No. 1, 1968

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 331: 1  2
Vol. 330: 1  2
Vol. 329: 1  2
Vol. 328: 1  2
Vol. 327: 1  2
Vol. 326: 1  2
Vol. 325: 1  2
Vol. 324: 1  2
Online Archive
Volume:
Issue:
     
The Journal
About the journal
Ethics and policies
Peer-review process
 
Submission guidelines
Submission form
Editorial board
Officers
 
Subscriptions
 
ISSN 1945-5844 (electronic)
ISSN 0030-8730 (print)
 
Special Issues
Author index
To appear
 
Other MSP journals
Initial segments of degrees

Joseph Goeffrey Rosenstein

Vol. 24 (1968), No. 1, 163–172
Abstract

Spector first constructed a function h whose degree of recursive unsolvability is minimal—that is to say that any function recursive in h is either recursive or of the same degree as h. Define a set Q of degrees to be an initial segment of the upper semi-lattice of degrees of unsolvability if

a ∈ Q ∧b < a.→ .b ∈ Q.

Spector’s result can then be interpreted as saying that a certain partially ordered set occurs as an initial segment of the degrees; it was conjectured that the same is true for every finite partially ordered set which has a least member. Sacks then constructed two minimal degrees a and b such that a b has a,b,0 as its only predecessors.

In this paper their methods are extended to obtain the following result. Let T be the upper semi-lattice of all finite subsets of N. Then T can be embedded as an initial segment of the degrees. From this it follows that any finite partial ordering which can be embedded as an initial segment of P(B) (the power set of B), with B finite, can also be embedded as an initial segment of the degrees.

Mathematical Subject Classification
Primary: 02.70
Milestones
Received: 19 April 1966
Published: 1 January 1968
Authors
Joseph Goeffrey Rosenstein