On the Iterated ω-Rule

<div class="line" id="line-19"> Let &Gamma;n(&phi;) be a formula of LPA (PA = Peano Arithmetic) meaning &ldquo;there is a proof of &phi; from PA-axioms, in which &omega;-rule is iterated no more than <i> n </i> times&rdquo;. We examine relations over pairs of natural numbers of the kind.</div><div class="line" id="line-174"> ( <i> n </i> , <i> k </i> ) &leqq;H ( <i> n', k </i> ') iff PA + RFNn ( <i> H </i> k) &Vdash; RFNn ( <i> H </i> k). Where <i> H </i> denotes one of the hierarchies &sum; or &Pi; and RFNn( <i> C </i> ) is the scheme of the reflection principle for &Gamma;n restricted to formulas from the class <i> C </i> (&Gamma;n(&phi;) implies &ldquo;&phi; is true&rdquo;, for every &phi; &isin; <i> C </i> ). Our main result is that. ( <i> n </i> , <i> k </i> ) &leqq; <i> H </i> ( <i> n', k </i> ') if <i> n </i> &leqq; <i> n </i> ' and <i> k </i> &leqq; max ( <i> k', 2n </i> ' + 1).</div>