We shall prove the following theorem, which gives a necessary and sufficient condition for an elementary class to be characterized by a set of sentences having a prescribed number of alternations of quantifiers. A finite sequence of relational systems is said to be a sandwich of order n if each is an elementary extension of (i ≦ n—2), and each is an extension of (i ≦ n—2). If K is an elementary class, then the statements (i) and (ii) are equivalent for each fixed natural number n.

In a previous paper [1] it was proved, among other results, that a closed disjunction of intuitionistic elementary number theory N can be proved if and only if at least one of its disjunctands is provable and that a closed formula of the type (Ex)B(x) is provable in N if and only if B(n) is provable for some numeral n. The method of proof was to show that, as far as closed formulas are concerned, N is equivalent to a calculus N1 for which the result is immediate. The main step in the proof consisted in showing that the set of provable formulas of N1 is closed under modus ponens. This was done by obtaining a subset of the set which is closed under modus ponens and contains all members of the original set, with which it is therefore identical.

Basic notation in this paper is as in [3]. From [5] and [9] the following additional notation is derived, ϕi is the partial recursive function with index i, Wi its range. ∅ is the empty set. ‘≡’ denotes isomorphism between sets, ‘≡m’ many-one equivalence, ‘≡T’ Turing equivalence, ‘≦1’ and ‘≦m’ signify one-one and many-one reducibility respectively. ‘Recursive’ is used throughout for ‘general recursive’.

Let P0, …,Pq be predicates, of which at least one has two or more places. By a formula in P0, …, Pq (or simply a formula, when the list P0, …, Pq is fixed, as in this section) is meant any formula whose only symbols, other than sentential connectives, quantifiers, and (individual) variables, are among P0, …, Pq. A realization (or possible model) of such a formula is a system where A is a non-empty set and each Pk is a relation among the elements of A, having the same number of places as Pk.

R. Sherman Lehman has called my attention to an error which vitiates the proofs of two theorems in the paper mentioned in the title (this Journal, vol. 22, pp. 19–35, 113–129). New proofs are here presented.

Proof of Lemma, p. 27. Induction Step: Assume as hypothesis of induction that the lemma holds for formulas P with n—1 or fewer free restricted variables and consider a P having n (n>0) such variables.