In Part I of this paper no official significance was given to free occurrences of restricted-variables. Indeed doubt has been expressed as to the desirability or feasibility of such usage. Thus, to quote from Rosser [4], p. 146:

“We now raise the question of the significance of F (α), in which the occurrences of α are free [α a variable subject to the restriction K(α)]. In deciding to take (x).K(x) ⊃ F(x) and (Ex).K(x).F(x) as the meanings of (α)F(α) and (Eα)F(α), we were guided by the intuitive meanings. In the case of F(α), the intuitive meaning does not furnish a satisfactory guide. In everyday mathematics, if it has been agreed that α stands for a quantity satisfying the restriction K(α), it is commonly the case that, if one is assuming F (α), then K(α)&F(α) is understood, but if one is trying to prove F (α), then K(α) ⊃ F (α) is understood. It seems that in symbolic logic perhaps it is best not to give any especial significance to α in F(α) when it occurs free.”

Despite this anomalous behaviour we shall, in this Part, show how one can have unhampered use of free restricted-variables in appropriate contexts.

In Chapter X of his book on The structure of appearance, Goodman [1] studies the concept of linear order in finite linear arrays in terms of a two-place symmetrical predicate M, M(x, y) being read as x matches y. Although arising in the development of a nominalistic philosophical system, many problems relating to the properties of M are essentially of a mathematical and not of a philosophical nature. Some were considered by Fine in [2]. In the terminology of [1] and [2], the main result of this paper is that there is an effective method for embedding a weakly mapped array (consistently) in a uniform array. This carries with it the result that it is possible to obtain effectively a minimal uniform extension of the original array, that is, a uniform extension with minimum span for such an extension and with the minimum number of elements possible for a uniform extension with this span.

Hasenjaeger [2] has answered a question raised by Hilbert and Bernays [4] p. 279, by showing that the axiom

which, within lower predicate calculus, is independent of the remaining axioms of the system (B) p. 273, is no longer independent if the axiom 0 ≡ 0 of (B) is replaced by a ≡ a. The axioms from which (Cov) can be proved form the following system (B1) (obtained from (B), of course, by dropping (Cov) and replacing 0 ≡ 0 by a ≡ a):

In what follows we consider (B1) and also the systems (B′) and (B′1) which are obtained from (B) and (B1) respectively by dropping the induction axiom and which clarify the role of the induction axiom.

1. (B1) is equivalent to (B). For (B) can be obtained from (B1) by Hasenjaeger's result. On the other hand, by pp. 263 and 261, the axioms (<1) and (J1) of (B1) can be proved from the axioms (<3) and

which belong to the system (A) p. 263. Therefore (B1) can be obtained from (A) and the induction axiom, and hence from (B).

I once asked myself the question: How were the famous axiom systems, such as Euclid's for geometry, Zermelo's for set theory, Peano's for arithmetic, originally obtained? This was to me more than merely a historical question, as I wished to know how the basic concepts and axioms were to be singled out, and, once they were singled out, how one could establish their adequacy. One possible approach which suggests itself is to take typical theorems, proofs, definitions, and examine case by case what assumptions and concepts are involved. The obstacle in such an empirical study is, apart from the obvious demand of excessive time and energy, the lack of conclusiveness in both result and justification.

The attempt to find an answer to this question led me to some interesting fragments of history. For example, in 1899 Cantor distinguished consistent collections (the “sets”) from inconsistent collections ([1], p. 443), anticipating partly the distinction between the two kinds of classes stressed by von Neumann and Quine. Cantor had already proposed a form of the axiom of substitution ([1], p. 444, line 3), although Fraenkel and Skolem, more than twenty years later, had to adjoin it to Zermelo's list of axioms as a supplement. In another direction, the history of the development of axioms of geometry makes clear how natural it was for Hilbert to raise in 1900 the consistency question of analysis ([2], p. 299) quite independently of the emphasis on set-theoretical paradoxes.

By far the best piece of good fortune I had in these historical researches was, however, my findings with regard to Peano's axioms for arithmetic. It is rather well-known, through Peano's own acknowledgement ([3], p. 273), that Peano borrowed his axioms from Dedekind and made extensive use of Grassmann's work in his development of the axioms.

Kleene and Post [2] have shown that between each degree a and its completion a′ there are an infinity of mutually incomparable degrees of unsolvability, and that between a and its nth. completion a(n) there are an infinity of mutually incomparable degrees each incomparable with a′, …, a(n−1). They have left open the following questions: whether there exist complete degrees in similar profusion; whether indeed there exist incomparable complete degrees at all; and whether certain degrees, such as a(ω) ([2] p. 401), are complete. All these questions are answered affirmatively by the corollary of the present paper, which states that every degree greater than or equal to 0′ is complete. Since every complete degree is already known to be greater than or equal to 0′, it follows from the present paper that being greater than or equal to 0′ is both a necessary and a sufficient condition for completeness.

In his well-known paper [11], Post founded a general theory of recursively enumerable sets, which had its metamathematical source in questions about the decision problem for deducibility in formal systems. However, in centering attention on the notion of degree of unsolvability, Post set a course for his theory which has rarely returned to this source. Among exceptions to this tendency we may mention, as being closest to the problems considered here, the work of Kleene in [8] pp. 298–316, of Myhill in [10], and of Uspenskij in [15]. It is the purpose of this paper to make some further contributions towards bridging this gap.

From a certain point of view, it may be argued that there is no real separation between metamathematics and the theory of recursively enumerable sets. For, if the notion of formal system is construed in a sufficiently wide sense, by taking as ‘axioms’ certain effectively found members of a set of ‘formal objects’ and as ‘proofs’ certain effectively found sequences of these objects, then the set of ‘provable statements’ of such a system may be identified, via Gödel's numbering technique, with a recursively enumerable set; and conversely, each recursively enumerable set is identified in this manner with some formal system (cf. [8] pp. 299–300 and 306). However, the pertinence of Post's theory is no longer clear when we turn to systems formalized within the more conventional framework of the first-order predicate calculus. It is just this restriction which serves to clarify the difference in spirit of the two disciplines.

The main aims of this paper are firstly to present new and simpler postulate sets for certain well-known systems of modal logic, and secondly, in the light of these results, to suggest some new or newly formulated calculi, capable of interpretation as systems of epistemic or deontic modalities. The symbolism throughout is that of [9] (see especially Part III, Chapter I). In what follows, by a Lewis modal system is meant a system which (i) contains the full classical propositional calculus, (ii) is contained in the Lewis system S5, (iii) admits of the substitutability of tautologous equivalents, (iv) possesses as theses the four formulae:

We shall also say that a system Σ1 is stricter than a system Σ2, if both are Lewis modal systems and Σ1 is contained in Σ2 but Σ2 is not contained in Σ1; and we shall call Σ1absolutely strict, if it possesses an infinity of irreducible modalities. Thus, the five systems of Lewis in [5], S1, S2, S3, S4, and S5, are all Lewis modal systems by this definition; they are in an order of decreasing strictness from S1 to S5; and S1 and S2 alone are absolutely strict.

1. Let X be a statement which is formulated in the lower predicate calculus in terms of the relations of addition, multiplication, and equality, and — possibly — of the elements of a given commutative field M. Suppose moreover that X is in prenex normal form, e.g.

where Z does not include any further quantifiers. In order that X be satisfied by the algebraic closure M* of M, it is necessary and sufficient that there exist Herbrand functions (or choice functions) φ1(x1, x2), φ2(x1, x2), φ3(x1, x2, x3, x4) with arguments ranging over M* and taking values in M* such that

holds for all x1, x2, x3, x4 in M*. In general the definition of these functions is far from being unique, and a priori they bear no relation to the functions which are defined ‘naturally’ in M* i.e. the rational, and more generally the algebraic, functions with coefficients in M or M*. However, we shall show in the present paper that the entire domain of variation of the arguments x1, x2, x3, x4 — regarded as the affine space S4 over M* — can be divided up into a finite number of regions Di such that in each Di the functions ϕk can be chosen as algebraic functions of their arguments. Indeed, our complete result (§ 3) proves rather more than that. In particular, it turns out that the regions Di may be taken as differences of algebraic varieties in M*.