Hostname: page-component-7b7567c8c-9cwtv Total loading time: 0 Render date: 2026-11-19T20:54:18.370Z Has data issue: false hasContentIssue false

Initial Segments of Many-One Degrees

Published online by Cambridge University Press:  20 November 2018

A. H. Lachlan*
Affiliation:
Simon Fraser University, Burnaby, British Columbia
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 ≦mN 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.

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1970