The Degree of a Sigman Cut
The Degree of a Sigman Cut
复制标题
西格曼削减的程度
DOI：
10.1016/0168-0072(90)90021-s
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
K. Mourad
中科院分区：
文献类型：
--
作者：
C. Chong;K. Mourad
让 P-表示皮亚诺公理减去归纳方案。对于n 3 1，设ZE, 和Bz,, 分别表示En 归纳方案和E,, 集合方案。 Paris 和 Kirby [lo] 研究了 P-+ I& 和 P-+ B& 的相对证明理论强度。一般定理指出，P-+ ZX,, 蕴含 P-+ BE,, 蕴含 P-+ ZEn_-l，但反之则不然。这证明了从递归理论的角度研究皮亚诺算术片段模型的合理性。 Mytilinaios 和 Slaman [9] 发表了这个方向的第一个结果。他们表明，归纳对于证明不完全高重置的存在是必要的（我们注意到辛普森早些时候注意到波斯特的问题可以在 P-+ ZE 中解决）。此后出现了一些研究重置和度以及基本定理的著作（参见[l, 2, 5-9, 111）。在许多这样的著作中，对有限和无限伤害优先权论证进行了研究和分析。在某些情况下，a-递归理论的思想被用来在弱算术模型中进行优先级论证。在其他情况下，如果这是不可能的，则给出反例来表明这些模型中不存在某些重置。 Slaman 和 Woodin [ll] 的论文中提出了与我们的工作特别相关的方法，他们在其中解决了某些 P-+ BE 模型的 Post 问题，而不使用有限伤害优先权参数。事实上，他们挑选出了模型中的某个切口，并表明它具有中等程度的重新度。这促使我们更仔细地研究 P-+ B& 模型中的削减程度，以及它们与程度结构的关系。我们对度的存在性问题特别感兴趣，其原始证明（如文献中提出的）至少依赖于 ZE, 的假设。最小次数和最小配对问题是两个突出的例子。令Ju 为P-+ BE, 的模型，但不是Zz,,(n 2 2) 的模型。已知 _44 和 I 上定义的 az,, 共尾函数有一个割 Z。本文的主要结果之一指出 Z 和 o”-’ 形成最小对。如果我们将 _& 特化为 [9 和 111 中考虑的模型之一，其中每个实数都被编码（这里我们也允许 n= 1），那么 Z 是最小度的。因此，理论上证明，所引用的结果的陈述是严格的弱于 Z&，高于基数
Let P-denote the Peano axioms minus the induction scheme. For n 3 1, let ZE,, and Bz,, denote respectively the En induction scheme and the E,, collection scheme. Paris and Kirby [lo] studied the relative proof-theoretic strengths of P-+ I& and P-+ B& Th e general theorem states that P-+ ZX,, implies P-+ BE,, implies P-+ ZEn_-l, but not conversely. This justifies investigations into models of fragments of Peano arithmetic from the recursion-theoretic point of view. Mytilinaios and Slaman [9] published the first result in this direction. They showed that & induction was necessary to prove the existence of an incomplete high re set (we note that Simpson had noticed earlier that Post’s problem could be solved in P-+ ZE,). Several works have since emerged, studying re sets and degrees, and basis theorems (cf.[l, 2, 5-9, 111). In many of these works, finite and infinite injury priority arguments were studied and analyzed. In some cases ideas from a-recursion theory were used to carry out priority arguments in weak models of arithmetic. In other cases, where this was not possible, counterexamples were given to show the nonexistence of certain re sets in these models.An approach of special relevance to our work here is in the paper of Slaman and Woodin [ll] where they solved Post’s problem for some models of P-+ BE, without the use of a finite injury priority argument. Indeed they singled out a certain cut in the model and showed that it had intermediate re degree. This prompted us to study more closely the degree of cuts in models of P-+ B&, and how they relate to the structure of degrees. We are in particular interested in problems on the existence of degrees whose original proofs (as presented in the literature) depend on the assumption of at least ZE,. The minimal degree and minimal pair problems are two prominent examples. Let Ju be a model of P-+ BE,, but not Zz,,(n 2 2). It is known that there is a cut Z in _44 and az,, cofinal function defined on I. One of the main results of this paper states that Z and o”-’form a minimal pair. If we specialize _& to be one of the models considered in [9 and 111, in which every real is coded (here we allow n= 1 as well), then Z is of minimal degree. It follows that, proof-theoretically speaking, the statements of the results quoted are strictly weaker than Z&, over the base