Recursive Pseudo-Well-Orderings

Joseph Harrison

Transactions of the American Mathematical Society · 1968 · 15 citations · 5 references

Concepts

Abstract

Introduction.This paper is devoted to a study of recursive linear orderings which have no hyperarithmetic descending sequences and hierarchies on these orderings.In the first section we discuss a method for generalizing certain results on recursive-well-orderings to such recursive pseudo-well-orderings.We prove that if < s is any such ordering, then transfinite induction holds on <B for Si formulae.This permits one to extend several other results for recursive wellorderings to such < B. The possible order types of such relations is completely characterized by the result that, for some a<wx, <R has order type a>x(l+r¡) + a where 17 is the order type of the rationals in the open interval (0, 1).In the second section we define a hierarchy on a recursive pseudo-well-ordering to be essentially a sequence of functions associated with each element of the field of < R and satisfying the same inductive conditions at successors and limits as the functions of the hyperarithmetic hierarchy.We obtain various results which show how the relation < R induces certain structures on the relations of recursive and hyperarithmetic reducibility between functions of the hierarchy.The most important of these is that if aa and ab are the functions associated with a and b in some hierarchy on < R ; and if a < R b, and the segment between a and b is not well ordered, then everything hyperarithmetic in aa is recursive ab.These facts can be applied to obtain a number of new results of interest in the study of hyperdegrees.These include the existence of pairs of hyperdegrees without a greatest lower bound ; the existence, for a given hyperdegree, of an infinite descending sequence of hyperdegrees having the given one as a greatest lower bound ; the existence of maximal densely ordered sets of hyperdegrees ; the existence, for a given Y,{ set 5 containing a nonhyperarithmetic function, of a subset of the hyperdegrees of 5 having the cardinality of the continuum and consisting of mutually incomparable hyperdegrees; the existence of a pair of hyperdegrees [a], [ß] such that 0< [ce], [ß]<0' (the hyperdegree of Kleene's 0), with [a] n [ß] = 0 and [a] u [ß]=0'.In addition, our methods also yield the basic results on the existence of incomparable hyperdegree obtained in recent years via the methods of forcing and measure theory (see for example, Feferman [4], Spector [16], and Thomason [18]).In the text much use is made of O*, the set of notations for recursive linear orderings with no hyperarithmetic descending sequences which was introduced in

References

5