On principles between ${\Sigma }_1$- and ${\Sigma }_2$-induction, and monotone enumerations

Abstract

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