2015/12/16 by Anton Freund, Freund, Anton
Computer Science · Mathematics · #03F30 #Computability, Logic, AI Algorithms #FOS: Mathematics #History and Theory of Mathematics #Logic (math.LO) #Mathematical and Theoretical Analysis #math.LO #msc:03F30
paper · pdf · doi:10.48550/arxiv.1512.05122
arxiv created 2015/12/16 · openalex publication_date 2015/12/16 · arxiv updated 2015/12/17 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28
We show that the theory IΣ1 of Σ1-induction proves the following statement: For all n≥ 2, the uniform Σ1-reflection principle over the theory IΣn is equivalent to the totality of the function Fωn at stage ωn of the fast-growing hierarchy. The method applied is a formalization of infinite proof theory. The literature contains several proofs which place the quantification over n in the meta-theory (and also prove the separate cases n=0,1). In contrast, the author knows of no explicit argument that would allow us to internalize the quantification while keeping the meta-theory as low as IΣ1. It is well possible that this has been considered before. Our aim is merely to provide a detailed exposition of this important result.