Initial Segments of Many-One Degrees

Abstract

Our aim in this paper is to give a characterization of the order types of the countable initial segments of many-one degrees (m-degrees). The basic definitions and background information can be found in [ 2 ] from where we draw most of our notation and terminology. We expand the usual notion of m-reducibility by adopting the convention that R ≦ m ∅ and R ≦ m N for every recursive set R . This has the effect of giving all recursive sets the same m-degree; that m-degree will be denoted by 0 . We shall denote by ≦ the partial ordering of m-degrees induced by ≦ m , and shall denote by a ∪ b the least upper bound of the m-degrees a, b. We call a ∪ b the union of a and b .