A theorem on minimal degrees
- 1 December 1966
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 31 (4) , 539-544
- https://doi.org/10.2307/2269688
Abstract
In their original paper on degrees [3], Kleene and Post showed that there is a degree between 0 and 0′. Later, Friedberg [1] and Muchnik [4] showed that there is a recursively enumerable degree between 0 and 0′. Since then, this phenomenon has been repeated several times: a result has been proved for degrees, and then, after considerable additional effort, it has been proved for recursively enumerable degrees.There are some obvious respects in which that set of all degrees differs from the set of recursively enumerable degrees; e.g., the former is uncountable and has no largest member.Keywords
This publication has 2 references indexed in Scilit:
- TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)Proceedings of the National Academy of Sciences, 1957
- The Upper Semi-Lattice of Degrees of Recursive UnsolvabilityAnnals of Mathematics, 1954