On principles between Σ₁- and Σ₂-induction, and monotone enumerations

2013/06/08 by Alexander Kreuzer, Alexander P. Kreuzer, Kreuzer, Alexander P. +2
Computer Science · Mathematics · #03B30 #03F30 #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #Mathematical and Theoretical Analysis #math.LO #msc:03B30 #msc:03F30

paper · pdf · doi:10.48550/arxiv.1306.1936

openalex publication_date 2013/06/08 · arxiv created 2015/12/14 · arxiv updated 2015/12/15 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

We show that many principles of first-order arithmetic, previously only known to lie strictly between Σ₁-induction and Σ₂-induction, are equivalent to the well-foundedness of ω^ω. Among these principles are the iteration of partial functions (PΣ₁) of Hájek and Paris, the bounded monotone enumerations principle (non-iterated, BME₁) 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 (BME_k), and show that it is equivalent to the well-foundedness of the k+1-height ω-tower.

Related

• Two remarks on proof theory of first-order arithmetic
• Implications between Induction Principles for ℕ in Peano Arithmetic
• Combinatorial principles equivalent to weak induction
• A Uniform Characterization of Σ₁-Reflection over the Fragments of Peano Arithmetic
• On some Σ^B₀-formulae generalizing counting principles over V⁰