Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-17T07:48:05.584Z Has data issue: false hasContentIssue false

On many-one degrees1

Published online by Cambridge University Press:  12 March 2014

Shih-Chao Liu*
Affiliation:
Institute of Mathematics, Academia Sinica, Taiwan (Formosa), China

Extract

Two questions were left open in [1]. 1) Do W(σ) and W(r) have the same many-one degree for any σ, τ such that ωη+1.2 ≤ σ < τ < ωη+2? 2) Is W(σ) many-one reducible to W(r) for any σ, τ such that ωη+1.2 ≤ σ < τ < ωη+2? We answered the second question affirmatively in [2]. In this paper we answer the first question in the negative. From the results of [1] [2] and this paper we have a complete picture of the many-one degrees of the predicates e ∈ W(σ)

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1964

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable