On principles between ∑1- and ∑2-induction, and monotone enumerations
Alexander Kreuzer, Keita Yokoyama · Journal of Mathematical Logic · 2016
We show that many principles of first-order arithmetic, previously only known to lie strictly between [Formula: see text]-induction and [Formula: see text]-induction, are equivalent to the well-foundedness of [Formula: see text]. Among these principles are the iteration of partial functions ([Formula: see text]) of Hájek and Paris, the bounded monotone enumerations principle (non-iterated, [Formula: see text]) by Chong, Slaman, and Yang, the relativized Paris–Harrington principle for pairs, and the totality of the relativized Ackermann–Péter function. With this we show that the well-foundedness of [Formula: see text] is a far more widespread than usually suspected. Further, we investigate the [Formula: see text]-iterated version of the bounded monotone iterations principle ([Formula: see text]), and show that it is equivalent to the well-foundedness of the ([Formula: see text])-height [Formula: see text]-tower [Formula: see text].