Recursive theory and Dedekind cuts
Robert Irving Soare · Transactions of the American Mathematical Society · 1969
Considerable attention has been paid by mathematicians to the subject of recursive analysis, and in particular to the recursive real numbers, i.e. the class of Dedekind cuts which can be defined by an effective algorithm.From the point of view of recursion theory, however, it is more natural to consider certain nonrecursive Dedekind cuts, especially those which are recursively enumerable (r.e.) because most results in recursion theory are trivial at the level of recursive sets.In addition to generalizing well-known properties of recursive real numbers, the study of r.e.Dedekind cuts has applications to ordinary recursion theory.The dense linear ordering imposed by the rationals enables simplification of some ordinary proofs, and gives rise to several new order analogues of standard properties.Although our results were first derived for cuts, most are easily generalized to Jockusch's semirecursive sets [5], which may be viewed as generalized "cuts" in some recursive linear ordering of N.We begin by establishing the reducibility relationships between the standard definitions of a real number.We prove that there are no creative or quasicreative Dedekind cuts, although there is a Dedekind cut in every truth table degree.We use a priority argument to construct a r.e.Dedekind cut which is not a cylinder.This has as a corollary the result of P. R. Young [26] that there are pseudo-creative sets which are not splinters.We develop the cylinder properties of cuts, and disprove the order analogue of Myhill's theorem.Finally, we generalize a theorem of Yates [23] by constructing a semicreative Dedekind cut of every Turing degree, and as a corollary we generalize Jockusch's theorem [4] that in every Turing degree there is an w-degree consisting of a single 1 -degree.The dense linear ordering apparently prevents the classification of r.e.Dedekind cuts by the standard division of r.e.sets into categories such as creative sets or simple sets.However, some of our main results may be summarized as attempts to partially classify r.e. ( lower) Dedekind cuts by certain classes of fixed point free maps which preserve them.Let RL(RU) denote the class of real numbers in the Presented to the Society, October 25, 1966 under the title Nonrecursive real numbers.Part I: Cylinders and splinters; October 25, 1966 under the title Nonrecursive real numbers.Part II: Reducibility and productiveness and June 9, 1967 under the title Recursive theory and Dedekind cuts; received by the editors