Concerning partial recursive similarity transformations of linearly ordered sets

Louise Hay, Alfred Berry Manaster and Joseph Goeffrey Rosenstein

Vol. 71 (1977), No. 1, 57–70

DOI: 10.2140/pjm.1977.71.57

Abstract

Interesting contrasts between uncountable suborderings of the continuum and denumerable linear orderings are provided by results of Dushnik and Miller and Sierpiński on the one hand and Laver on other. We investigate analogues of these results in a recursive setting where the only similarity maps are restrictions of partial recursive functions. Complements of recursively enumerable bi-dense subsets of the rationals of arbitrary nonzero degree of unsolvability are shown to bear a strong resemblance to uncountable suborderings of the continuum.

Mathematical Subject Classification 2000

Primary: 02F25, 02F25

Secondary: 06A05

Milestones

Received: 8 June 1976

Published: 1 July 1977