Subsystems of true arithmetic and hierarchies of functions
type: Item
instance of: scholarly article
title: Subsystems of true arithmetic and hierarchies of functions
zbMATH Open document ID: 0802.03036
DOI: 10.1016/0168-0072(93)90031-8
published in: Annals of Pure and Applied Logic
publication date: 1994-12-12T00:00:00Z
review text: The author generalizes, from Peano Arithmetic (PA) to systems with transfinite induction \(( \text{TI}(\alpha))\), results of Paris-Harrington on the independence of the finite Ramsey theorem (PH) and those of Wainer on the provably total recursive functions in connection with the Hardy hierarchy. [Cf. \textit{J. Paris} and \textit{L. Harrington}, Handbook of mathematical logic, 1133-1142 (1977; Zbl 0443.03001) and \textit{W. Buchholz} and \textit{S. Wainer}, Contemp. Math. 65, 179-198 (1987; Zbl 0635.03056), respectively.] He puts a combinatorial concept, skeleton, to the fore, and does without the usual proof-theoretic means like cut- elimination. Starting from PH, Paris and Harrington constructed a large finite set, \(A\), that is scattered (i.e. \(a,b\in A\), \(a<b\) then \(a^ 2<b\)) and gives indiscernible bounds to the quantifiers of formulas of interest, on the way to finding an appropriate initial segment of a model. Such a set \(A\) is the proto-type of a skeleton. In the first half of the paper, the author expands and elaborates this notion, particularly in relation to the transfinite situation, and also presents combinatorial reflexion principles, CR (the existence of skeletons that are arbitrarily large and as scattered as desired). This principle is compared to Kreisel-Levy's reflexion principle [cf. \textit{G. Kreisel} and \textit{A. Lévy}, Z. Math. Logik Grundlagen Math. 14, 97-142 (1968; Zbl 0167.013)], and a new proof is given of their result about the equal power of \(TI(\varepsilon_ \alpha)\) and \(R_ \alpha( \text{PA})\), the reflexion principle iterated \(\alpha\) times. The \(\alpha\)-th iterate of PH is shown to be equivalent to \(R( \text{TI}(< \varepsilon_ \alpha)\), \(\Sigma_ 1)\), and is compared to a similar sentence constructed by \textit{K. McAloon} [Recursion theory, Proc. Symp. Pure Math. 42, 447-460 (1985; Zbl 0589.03028)]. Wainer's theorem is generalized to: If \(\text{TI} (\varepsilon_ \alpha) \vdash\)``\(f\) is total'', then \(f\)…
Mathematics Subject Classification ID: 03F30
zbMATH DE Number: 444824
zbMATH Keywords: transfinite induction
zbMATH Keywords: provably total recursive functions
zbMATH Keywords: Hardy hierarchy
zbMATH Keywords: skeleton
zbMATH Keywords: combinatorial reflexion principles
author: Zygmunt Ratajczyk
MaRDI profile type: Publication
full work available at URL: 0168-0072(93)90031-8
OpenAlex ID: W1966414208
cites work: Q5848994
cites work: Q3773880
cites work: Q3794177
cites work: Transfinite recursive progressions of axiomatic theories
cites work: Systems of predicative analysis, II: Representations of ordinals
cites work: Hilbert's program relativized; Proof-theoretical and foundational reductions
cites work: Beweisbarkeit und Unbeweisbarkeit von Anfangsfällen der transfiniten Induktion in der reinen Zahlentheorie
cites work: Q5629622
cites work: Combinatorial principles concerning approximations of functions
cites work: Inductive full satisfaction classes
cites work: More on induction in the language with a satisfaction class
cites work: Rapidly growing Ramsey functions
cites work: On the interpretation of non-finitist proofs–Part II
cites work: Reflection Principles and their Use for Establishing the Complexity of Axiomatic Systems
cites work: Q4105666
cites work: Q3343982
cites work: Hierarchies of number-theoretic functions II
cites work: Q3717036
cites work: Locally finite theories
cites work: Q3893931
cites work: Satisfaction Classes and Combinatorial Sentences Independent From PA
cites work: A combinatorial analysis of functions provably recursive in $ΙΣ_n$
cites work: Arithmetical transfinite induction and hierarchies of functions
cites work: Q3325707
cites work: Q3866106
cites work: Built-up systems of fundamental sequences and hierarchies of number-theoretic functions
cites work: Postscript to “built-up systems of fundamental sequences and hierarchies of number-theoretic functions”
cites work: Proof theory. 2nd ed
cites work: Ordinal recursion, and a refinement of the extended Grzegorczyk hierarchy
Recommended article: Q4215632
Recommended article: Elementary descent recursion and proof theory
Recommended article: Arithmetical transfinite induction and hierarchies of functions
Recommended article: Paris-Harrington principles, reflection principles and transfinite induction up to \(\epsilon _ 0\)
Recommended article: Proofs and Computations
Recommended article: Q3527612
Recommended article: Transfinite induction within Peano arithmetic
Recommended article: Some variations of the Hardy hierarchy
Recommended article: Some combinatorial principles equivalent to restrictions of transfinite induction up to \(\Gamma _ 0\)
Recommended article: Functions provably total in $I^{-}Σ_{n}$
description: scientific article; zbMATH DE number 444824