Subsystems of true arithmetic and hierarchies of functions (Q688433)

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\) is majorized by a Hardy function \(H_ \beta\), with \(\beta< \varepsilon_{\alpha+1}\). In the last chapter, the author considers the system that has the satisfaction predicate \(S\) for PA. Its increase of power is exhibited by the facts that \(\text{TI} (\varepsilon_ \alpha) \restriction \Pi_ 2\) with \(S\) is equivalent to a system that has axioms \(\forall x \exists y H_ \beta (x) =y\) for \(\beta< \varepsilon_{\varepsilon_{\alpha+1}}\); while the equivalent system to \(\text{TI} (\varepsilon_ \alpha) \restriction \Pi_ 2\) without \(S\) needs axioms only up to \(\varepsilon_{\alpha+1}\).