Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-26T18:02:08.710Z Has data issue: false hasContentIssue false
  • English
  • Français

Initial Segments of Many-One Degrees

Published online by Cambridge University Press:  20 November 2018

A. H. Lachlan
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.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 22 , Issue 1 , 01 February 1970 , pp. 75 - 85
Copyright
Copyright © Canadian Mathematical Society 1970

References

1. Lachlan, A. H., Distributive initial segments of the degrees of unsolvability, Z. Math. Logik Grundlagen Math. 14 (1968), 457–472.Google Scholar
2. Rogers, H. Jr., Theory of recursive functions and effective computability (McGraw-Hill, New York, 1967).Google Scholar