Although 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 re predicates and closed under truth functions.