Iterated trees and fragments of arithmetic (Q1892096)

The paper is devoted to some problems connected with the so-called Recursion Theory in Fragments of Arithmetic. It is an analogue of reverse mathematics. The main result of the paper states that the general \(O^{(n)}\)-priority method succeeds iff the induction scheme for \(\Sigma_n\) formulas \((I \Sigma_n)\) holds. As a consequence one gets that if we have an iterated trees style \(O^{(n)}\)-priority proof of a theorem, then we know that the theorem can be proved in the fragment \(\text{PA}^- + I \Sigma_n\). It is also shown that the iterated trees framework is in fact applicable to the finite injury level.