On <i>n</i>-quantifier induction

Abstract

In this paper we discuss subsystems of number theory based on restrictions on induction in terms of quantifiers, and we show that all the natural formulations of ‘ n -quantifier induction’ are reducible to one of two (for n ≠ 0) nonequivalent normal forms: the axiom of induction restricted to (or, equivalently, ) formulae and the rule of induction restricted to formulae. Let Z 0 be classical elementary number theory with a symbol and defining equations for each Kalmar elementary function, and the rule of induction restricted to quantifier-free formulae. Given the schema let IA n be the restriction of IA to formulae of Z 0 with ≤ n nested quantifiers, IA n ′ to formulae with ≤ n nested quantifiers, disregarding bounded quantifiers, the restriction to formulae, the restriction to , formulae. IR n , IR n ′, , are analogous. Then, we show that, for every n , , , IA n , and IA n ′, are all equivalent modulo Z 0 . The corresponding statement does not hold for IR. We show that, if n ≠ 0, is reducible to ; evidently IR n is reducible to . On the other hand, IR n ′ is obviously equivalent to IA n ′ [10, Lemma 2].