Uniformly defined descending sequences of degrees

E-ISSN： 1943-5886|41|2|363-367

ISSN： 0022-4812

Source： The Journal of Symbolic Logic, Vol.41, Iss.2, 1976-06, pp. : 363-367

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

This paper answers some questions which naturally arise from the Spector-Gandy proof of their theorem that the π₁ ¹ sets of natural numbers are precisely those which are defined by a Σ₁ ¹ formula over the hyperarithmetic sets. Their proof used hierarchies on recursive linear orderings (H-sets) which are not well orderings. (In this respect they anticipated the study of nonstandard models of set theory.) The proof hinged on the following fact. Let e be a recursive linear ordering. Then e is a well ordering if and only if there is an H-set on e which is hyperarithmetic. It was implicit in their proof that there are recursive linear orderings which are not well orderings, on which there are H-sets. Further information on such nonstandard H-sets (often called pseudohierarchies) can be found in Harrison [4]. It is natural to ask: on which recursive linear orderings are there H-sets?