Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-18T02:47:04.042Z Has data issue: false hasContentIssue false

Uniformly defined descending sequences of degrees

Published online by Cambridge University Press:  12 March 2014

Harvey Friedman*
Affiliation:
Suny at Buffalo, Amherst, New York 14226

Extract

This paper answers some questions which naturally arise from the Spector-Gandy proof of their theorem that the π1 1 sets of natural numbers are precisely those which are defined by a Σ1 1 formula over the hyperarithmetic sets. Their proof used hierarchies on recursive linear orderings (H-sets) which are not well orderings. (In thisrespect 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?

In Friedman [1] it is shown that there exists a recursive linear ordering e that has no hyperarithmetic descending sequences such that no H-set can be placed on e. In [1] it is also shown that if e is a recursive linear ordering, every point of which has an immediate successor and either has finitely many predecessors or is finitely above a limit point (heretofore called adequate) such that an H-set can be placed on e, then e has no hyperarithmetic descending sequences. In a related paper, Friedman [2] shows that there is no infinite sequence xn of codes for ω-models of the arithmetic comprehension axiom scheme such that each x n+ 1 is a set in the ω-model coded by xn , and each x n+1 is the unique solution of P(xn , x n+1) for somefixed arithmetic P.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1976

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