Linear orderings under one-one reducibility

Publisher Website
Google Scholar
Abstract
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.

This publication has 8 references indexed in Scilit: