The Arithmetic Hierarchy, Parikh’s Theorem and Related Matters

part of discretely ordered rings in this language, consisting of e.g. the commutative, associate and distributive laws, the recursion equations for addition and multiplication, and ordering axioms. (See [2] page 16 for the exact definition of PA−.) The arithmetic hierarchy is a family of formula classes within PA and is defined as follows: • The ∆0 ( = Σ0 = Π0) formulas consist of atomic formulas closed under Boolean connectives and bounded quantifiers, i.e. quantifiers of the form ∃~x < t and ∀~x < t, where t is any LPA-term. • Σn+1 formulas are those of the form ∃~xφ(~x, ~y), where φ is Πn, • Πn+1 formulas are those of the form ∀~xφ(~x, ~y), where φ is, • A formula is ∆n if it is provably (in PA) equivalent to both a Σn formula and a Πn formula. A corresponding hierarchy of theories within PA is defined by restricting the induction axiom to a fixed level of the arithmetic hierarchy. Specifically we define IΣn as PA together with the induction schema for Σn formulas; IΠn and I∆n are defined similarly. The first fact which we observe is that the arithmetic hierarchy is strict. (Note: thi