There are essentially two ‘positive’ results concerning the extension of effective operations to partial recursive functionals. The first proved by Myhill and Shepherdson in [9] states that any effective operation whose domain is the set of all partial recursive (p.r.) functions is potentially p.r. The second proved originally by Kreisel, Lacombe, and Shoenfield in [5] states: Let F be an effective operation mapping a set of recursive functions into the natural numbers; if has a recursively dense base, then F is potentially p.r. The main objective of this paper is to present these two theorems in a general setting.

In this note we point out a limitation of the treatment of transfinite recursion in Quine's Set Theory and its Logic2 and develop a method for overcoming it. We shall also mention and indicate how to overcome a second more trivial limitation. We assume familiarity with Set Theory and its Logic and use its notation and terminology. Numbered references are to Quine's numbered formulae. In our work we continue the numbering of § 26.

The first difficulty is that the theorems which show that his device for defining functions by transfinite recursion (§ 25) accomplishes its purpose do not apply to functions defined by recursion over all the ordinals. Let γ be the function which gives the value of the function we want for an ordinal y from the sequence of its values for ordinals less than y.

In the original example of a transfinite hierarchy of degrees of unsolvability, a predicate Ha is associated with each a in the set 0 of ordinal notations. (See Kleene [K1], Spector [S1], and the references there to Davis and Mostowski.) The predicates are defined by means of induction over the partial well-ordering relation ≤0 on the set 0 of notations for the recursive ordinals. The usefulness of this hierarchy of predicates is enhanced by Spector's proof [S1] of the “uniqueness” property: viz. that the degree of Ha depends only on the ordinal |a| for which a is a notation.

This is really a note to Wajsberg's [4].

In [3] J. C. C. McKinsey proved the following two completeness theorems: (1) theorem 6: If A is a wff of S2 with just r (proper or improper) sub-wffs, then A is provable in S2 iff A is satisfied by every normal S2-matrix with no more than 22r+1 elements; (2) theorem 13: if A is a wff of S4 with just r sub-wffs, then A is provable in S4 iff A is satisfied by every normal S4-matrix with no more than 22r elements. Now, a similar theorem has not been explicitly formulated for S5, even though a similar, even simpler, theorem has been almost at hand since Wajsberg's [4] was published in 1933, namely:

Theorem. If A is a wff of S5 with just n propositional variables, then A is provable in S5 iff A is satisfied by a normal SS-matrix with 22n elements.