A note on the arithmetical hierarchy.
Stephen L. Bloom · Notre Dame Journal of Formal Logic · 1968
The purpose of this paper is to give a new proof of this theorem:there is a Σ 2 ΠΠ 2 predicate having no inverse image 1 under any function from N onto N in Σ± or inli lmAlthough this is a fact about the arithmetical hierarchy, the only known proof (so far as I know) veers through quantification theory.Kleene [l] has shown that every consistent formula of quantification theory has a model in the domain of natural numbers N in which the satisfying predicates are in Σ 2 ΠΠ 2 .In [2] an example is given of a formula F with one predicate variable P having no model with domain N when P is interpreted as a Σi or Πi predicate.Since predicates of integers and their inverse images satisfy the same sentences of quantification theory without identity, we can conclude that the predicate which satisfies F has the property stated in the theorem.This is a somewhat surprising result, since it shows that the arithmetical hierarchy is, in a sense, independent of the 'names' of the integers.In contrast, Putnam [3] has shown that every Σ 2 ΠΠ 2 predicate has an inverse image under a certain function from N onto N in the smallest class of predicates containing the r.e.predicates and closed under truth functions.Since the theorem is a fact of recursive function theory, it would be appropriate to have a proof which does not involve extra-disciplinary detours.We present such a proof here.Proof of the theorem.The trick in our proof is to code enough predicates with one predicate S to guarantee its inverse images are not too simple.Let Si, S 3 , S 5 , be the following recursive predicates: Siix) x = 0; S 3 (#) x -1; S 5 (x,y) y -x + 1.Let S 7 (x) be a r.e.non-recursive predicate, and define S f +1 as ~S, , for i = 1,3,5,7.We let S(x,y,z) be 1.Throughout the remainder of the paper, "inverse image" will mean "inverse image under an arbitrary function from N onto N".We use the notations Σ n ,U n as Davis [4] uses P n , Q n .