One might fairly say that the very meaning of our subject has changed since Hilbert introduced it under the name Beweistheorie (it was meant to be the principal tool for formulating Hubert's general conception of how to analyze mathematical reasoning). Specifically, the roles of the two principal elements of proof theory, namely the intuitive proofs accepted and the formal proofs (or derivations) studied, have turned out to be quite different from what Hilbert thought. In his view the hard work had been done in the discovery of formalization, and what remained was the study of certain given formal systems.

Metarecursion theory is an analogue of recursion theory which deals with sets of recursive, or constructive, ordinals rather than of natural numbers. It was originated by Kreisel and Sacks [3], who make extensive use of an equation calculus developed by Kripke. We assume that the reader is acquainted with the outline of it given in [3], and especially in [3, §3].

In intuitionistic mathematics one distinguishes between sets with a constructive character and sets in a more general sense. The first kind consists of spreads and the latter of species. The definition of a spread utilizes so-called choice sequences (in [5] infinitely proceeding sequence or ips), i.e., sequences of well-determined mathematical objects which are chosen more or less freely. One can restrict the choices by some law, which, however, need not be predetermined (changing one's mind is allowed).

The correspondence decision problem was first formulated and shown to be recursively unsolvable in Post (1946). The method of proof was to reduce the known unsolvable decision problem for the class of normal systems on a, b to the correspondence decision problem. In the present paper the concept of a standard Post normal system is used so as to obtain some equivalence reductions of combinatorial systems. In particular the following main result is obtained.

The purpose of this paper is to present two new theorems concerning the degrees of coinfinite recursively enumerable (r.e.) sets which have no maximal supersets Let the class of all such degrees be denoted by A. Martin in [2] conjectured that there was some equality or inequality involving a′ or a″ characterizing the degrees a in A. Martin himself proved ([2, Corollary 4.1]) that a′ = 0″ is sufficient for ar r.e. degree a to be in A, and Robinson [3] announced that a′ ≥ 0″ is necessary. In this paper we improve both of these theorems by a factor of the jump, i.e., we shall show that a″ = 0″ is sufficient for an r.e. degree a to be in A, and that a″ ≥ 0″ is necessary.

In this note a proof is supplied of a fairly easily-made conjecture: that the system S3.5, formulated by Åqvist in [1] and proved complete with respect to some Kripke-style semantics by Cresswell in [2], is indeed the same system as S3(S), formulated by Lemmon in [3]. Any otherwise unexplained terms and notation are taken from the latter two papers.

In this paper we define the notions of invariant implicit definability (i.i.d.) and semi-invariant implicit definability (s.i.i.d.) on ε-models, A, of a certain weak set theory. These notions are intended to be the analogs of recursiveness and recursive enumerability, respectively. Following Barwise, with each A is associated an infinitary language whose formulas are elements of A.

I shall prove in this paper that Gentzen's Hauptsatz is extendible to simple type theory, i.e., to the predicate logic obtained by admitting quantification over predicates of arbitrary finite type and generalizing the second order quantification rules to cover quantifiers of other types. (That Gentzen's Hauptsatz is extendible to this logic has been known as Takeuti's conjecture; see [4].) Gentzen's Hauptsatz has been extended to second order logic in a recent paper by Tait [3]. However, as remarked by Tait, his proof seems not to be extendible to higher orders. The present proof is rather an extension of a different proof of the Hauptsatz for second order logic that I have presented in [1].

In [1], Lemmon provides us with his now well-known formulations of the Lewis-modal systems S1 through S4. This paper will present similar bases for the related systems S1° and S2° of Feys [2], and S3° and S4° of Sobocinski [3]. Notation and definitions here will be as in [1]. Standard bases for the Lewis-modal systems may be drawn from the following stock of axioms and rules, as is done in [1].

In [1], the principle of semisubstitutivity of implication (SSI) was introduced for ordinary PC and quantification theory. This metatheorem generalizes the notions of “antecedent” and “consequent” to cover all wf subformulas of a given formula; each such subformula will be classified as being either in “antecedental position” (A-pos) or “consequential position” (C-pos). It is simplest to check these positions in a conjunction-negation primitive system: reduce a formula φ to primitive notation (K—N) ; choose a subformula ψ of φ; count the negation signs in φ within whose scope ψ falls.