Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-16T13:43:25.402Z Has data issue: false hasContentIssue false

Linear orderings under one-one reducibility

Published online by Cambridge University Press:  12 March 2014

Paul R. Young*
Affiliation:
Reed College and Stanford university

Extract

In [2], Fischer has shown the existence of a bounded-truth-table degree of unsolvability which contains a collection of many-one degrees which has, under many-one reducibility, the order type, ω, of the positive integers. In [1; pg. 124], Dekker and Myhill give a construction which shows that the many-one degree of any simple set contains a collection of one-one degrees of simple sets which has, under one-one reducibility, the order type (ω + ω*) ·ω. A basic result of recursive function theory (due to Myhill) is that the creative sets form a many-one degree which consists of a single one-one degree (i.e. a single recursive isomorphism type).

It is well known that the recursive sets form three many-one degrees. Two of these, the degrees of the empty set and of the set of all integers, consist of single one-one degrees.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1996

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