TY - JOUR

T1 - On principles between Σ1 - And Σ2 -induction, and monotone enumerations

AU - Kreuzer, Alexander P.

AU - Yokoyama, Keita

N1 - Funding Information:
The authors are grateful to Leszek Kolodziejczyk for remarks to an earlier version of this paper. Part of the work in this paper was done at the Institute of Mathematical Sciences (IMS) at National University of Singapore during the workshop "Sets and Computations". The first author was supported by the Ministry of Education of Singapore through grant R146-000-184-112 (MOE2013-T2-1-062). The work of the second author was partially supported by JSPS KAKENHI grant number 16K17640, JSPS fellowship for research abroad, JSPS-NUS Bilateral Joint Research Projects J150000618 (PI's: K. Tanaka, C. T. Chong), and JSPS Core-to-Core Program (A. Advanced Research Networks).
Publisher Copyright:
© 2016 World Scientific Publishing Company.

PY - 2016/6/1

Y1 - 2016/6/1

N2 - We show that many principles of first-order arithmetic, previously only known to lie strictly between Σ1-induction and Σ2-induction, are equivalent to the well-foundedness of ωω. Among these principles are the iteration of partial functions (PΣ1) of Hájek and Paris, the bounded monotone enumerations principle (non-iterated, BME1) 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 ωω is a far more widespread than usually suspected. Further, we investigate the k-iterated version of the bounded monotone iterations principle (BMEk), and show that it is equivalent to the well-foundedness of the (k + 1)-height ω-tower ωω.

AB - We show that many principles of first-order arithmetic, previously only known to lie strictly between Σ1-induction and Σ2-induction, are equivalent to the well-foundedness of ωω. Among these principles are the iteration of partial functions (PΣ1) of Hájek and Paris, the bounded monotone enumerations principle (non-iterated, BME1) 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 ωω is a far more widespread than usually suspected. Further, we investigate the k-iterated version of the bounded monotone iterations principle (BMEk), and show that it is equivalent to the well-foundedness of the (k + 1)-height ω-tower ωω.

KW - Ackermann function

KW - bounded monotone enumerations

KW - Fragments of arithmetics

KW - ordinal numbers

KW - Paris-Harrington theorem

KW - reverse mathematics

UR - http://www.scopus.com/inward/record.url?scp=84977263830&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84977263830&partnerID=8YFLogxK

U2 - 10.1142/S0219061316500045

DO - 10.1142/S0219061316500045

M3 - Article

AN - SCOPUS:84977263830

SN - 0219-0613

VL - 16

JO - Journal of Mathematical Logic

JF - Journal of Mathematical Logic

IS - 1

M1 - 1650004

ER -