Uniformly defined descending sequences of degrees
Uniformly defined descending sequences of degrees
复制标题
统一定义的度数降序列
DOI：
10.1017/s0022481200051410
复制
发表时间：
1976
影响因子：
0.6
通讯作者：
H. Friedman
中科院分区：
文献类型：
--
作者：
H. Friedman
本文回答了Spector-Gandy证明π - 11自然数集正是由超算术集上的Σ1 1公式定义的自然数集这一定理中自然产生的一些问题。他们的证明使用了非良序的递归线性排序（h集）的层次结构。（在这方面，他们预测了对集合论的非标准模型的研究。）这个证明以下列事实为依据。设e是一个递归线性排序。那么e是一个有序的当且仅当e上存在一个超算术的h集。这在他们的证明中是隐含的，存在递归线性排序它们不是良序，它们上面有h集。关于这种非标准h集（通常称为伪层次）的进一步信息可以在Harrison[4]中找到。人们很自然地会问：在哪些递归线性排序上存在h集？在弗里德曼[1]表明,存在一个递归线性排序e没有hyperarithmetic降序序列,不能放在H-set e。在[1]也表明如果e是一个递归线性排序,每一个点的有一个直接后继和有限很多前辈或有限高于极限值(迄今为止称为足够),这样可以放在H-set e,然后e没有hyperarithmetic递减序列。在相关论文中，Friedman[2]证明了算术理解公理格式的ω-模型不存在编码的无穷序列xn，使得每个xn +1都是由xn编码的ω-模型中的集合，并且每个xn +1都是P（xn, xn +1）对某固定算术P的唯一解。
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 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? 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 some fixed arithmetic P.