ABSTRACT

This chapter presents the effect of using unbounded quantifiers in definitions of relations. It is agreed that n designates a non–zero number. The results of this section are due to Kleene. Using equivalences, two adjacent universal quantifiers in a prefix can be replaced by a single quantifier, and similarly for existential quantifiers. A prefix is alternating if it does not contain two successive existential quantifiers or two successive universal quantifiers. The chapter is chiefly interested in the prefix, since it measures how far the definition is from being recursive. It also contains several propositions, an Arithmetical Enumeration Theorem, and Arithmetical Hierarchy Theorem. The chapter shows how the Hierarchy Theorem and the Enumeration Theorem fails.