Abstract

Let Γn be a formula of LPA meaning “there is a proof of φ from PA-axioms, in which ω-rule is iterated no more than n times”. We examine relations over pairs of natural numbers of the kind. ≦H iff PA + RFNn' ⊩ RFNn .Where H denotes one of the hierarchies ∑ or Π and RFNn is the scheme of the reflection principle for Γn restricted to formulas from the class C implies “φ is true”, for every φ ∈ C). Our main result is that. ≦H if n ≦ n' and k ≦ max.