On principles between ∑1- and ∑2-induction, and monotone enumerations

Journal of Mathematical Logic 16 (1):1650004 (2016)
  Copy   BIBTEX

Abstract

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 of Hájek and Paris, the bounded monotone enumerations principle 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, and show that it is equivalent to the well-foundedness of the -height [Formula: see text]-tower [Formula: see text].

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,031

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Analytics

Added to PP
2016-06-11

Downloads
35 (#470,721)

6 months
12 (#243,520)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Reverse mathematics and colorings of hypergraphs.Caleb Davis, Jeffry Hirst, Jake Pardo & Tim Ransom - 2019 - Archive for Mathematical Logic 58 (5-6):575-585.
Weak Well Orders and Fraïssé’s Conjecture.Anton Freund & Davide Manca - forthcoming - Journal of Symbolic Logic:1-16.
Dickson’s lemma and weak Ramsey theory.Yasuhiko Omata & Florian Pelupessy - 2019 - Archive for Mathematical Logic 58 (3-4):413-425.
Algebraic combinatorics in bounded induction.Joaquín Borrego-Díaz - 2021 - Annals of Pure and Applied Logic 172 (2):102885.

Add more citations