Search

1. Although the decision problem of the first order predicate calculus has been proved by Church to be unsolvable by any (general) recursive process, perhaps it is not superfluous to investigate the possible reductions of the general problem to simple special cases of it. Indeed, the situation after Church's discovery seems to be analogous to that in algebra after the Ruffini-Abel theorem; and investigations on the reduction of the decision problem might prepare the way for a theory in logic, analogous to that of Galois.It has been proved by Ackermann that any first order formula is equivalent to another having a prefix of the form(1) (Ex1)(x2)(Ex3)(x4)…(xm).On the other hand, I have proved that any first order formula is equivalent to some first order formula containing a single, binary, predicate variable. In the present paper, I shall show that both results can be combined; more explicitly, I shall prove theTheorem. To any given first order formula it is possible to construct an equivalent one with a prefix of the form (1) and a matrix containing no other predicate variable than a single binary one.2. Of course, this theorem cannot be proved by a mere application of the Ackermann reduction method and mine, one after the other. Indeed, Ackermann's method requires the introduction of three auxiliary predicate variables, two of them being ternary variables; on the other hand, my reduction process leads to a more complicated prefix, viz.,(2) (Ex1)…(Exm)(xm+1)(xm+2)(Exm+3)(Exm+4).

We wish to make a correction to our paper On definability of ordinals in logic with infinitely long expressions (this journal, vol. 31 (1966), pp. 365–375). Let Ω be an infinite singular cardinal and Ω+ the smallest cardinal >Ω. For the proof of the second half of Theorem 3, we incorrectly assumed that an ordinal γ is not definable in LΩ, if γ is not cofinal with any ordinal ≤Ω. However, Ω+ is indeed definable in LΩ and Theorem 3 should read:If Ω singular, then an ordinal α is definable in Lα, if and only if σ ≤ exp(Ω+, Ω+), where exp (β,γ) denotes ordinal exponentiation βγ.

A common method of obtaining the classical modal logics, for example the Feys system T, the Lewis systems, the Brouwerian system etc., is to build on a basis for the propositional calculus by adjoining a new symbol L, specifying new axioms involving L and the symbols in the basis for PC, and imposing one or more additional transformation rules. In the jargon of algebraic logic, which is the point of view we shall adopt, the “necessity” symbol L may be interpreted as an operator on the Boolean algebra of propositions of PC. For example, the Lewis system S4 may be regarded as a Boolean algebra ℒ together with an operator L on ℒ having the properties: (1)Lp ≤ p for all p in ℒ, (2)L1 = 1, (3) L(p → q) ≤ Lp → Lq for all p, q in ℒ, and (4) Lp = L(Lp) for all p in ℒ. Here, of course, → denotes the material implication connective: p→q = p′ ∨ q. It is easy to verify that property (3) may be replaced by either (3′) L(p ∧ q) = Lp ∧ Lq for all p, q in ℒ, or by (3″) L(p → q) ∧ Lp ≤ Lq for all p, q in ℒ. In particular, it follows from (1) through (4) above that L is a decreasing, idempotent and isotone operator on ℒ. Such mappings are often called interior operators.In a previous paper [5], we considered the problem of introducing an implication connective into a quantum logic. This is greatly complicated by the fact that the quantal propositions band together to form an orthocomplemented lattice which is only “locally” distributive. Such lattices are called orthomodular. For definitions and further discussion, the reader is referred to that paper. In it, we argued that the Sasaki implication connective ⊃ defined by p ⊃ q = p′ ∨ (p ∧ q) is a natural generalization of material implication when the lattice of propositions is ortho-modular. Indeed, if unrestricted distributivity were permitted, p ⊃ q would reduce to the classical material implication p → q. For this reason, we choose ⊃ to play the role of material implication in an orthomodular lattice. Further properties of ⊃ are enumerated in Example 2.2(1) and Corollary 2.4 below.

In this paper a converse of Barwise's completeness theorem is proved by cut-elimination considerations applied to inductive definitions. We show that among the transitive sets T satisfying some weak closure conditions (closure under primitive-recursive set-functions is more than enough), only the unions of admissible sets satisfy Barwise's completeness theorem in the form stating that if φ ∊ T is a sentence which has a derivation (in the universe) then φ has a derivation in T. See §1 for the origin of the problem in Barwise's paper [Ba].Stated quite briefly the proof is as follows (a step-by-step account including relevant definitions is given in the body of the paper):Let T be a transitive prim.-rec. closed set, and let is nonempty, transitive and closed under pairs}. For each let κ(A) be the supremum of closure ordinals of first-order positive operators on subsets of A (first-order with respect to By Theorem 1 of [BGM], it is enough to prove that rank(T) in order to obtain that T is a union of admissible sets. (The rank of a set is defined by rank(x) = supy ∊ x (rank(y) + 1); since T is prim.-rec. closed, rank(T) = smallest ordinal not in T.)Let We show how to find in T (in fact, in Lω(A)) a derivable sentence τ that has no derivation D such that rank(D) ≤ α. Thus, if τ is to have a derivation in T, rank(T) > α. α is arbitrary (< κ(A)), so rank(T) ≥ κ(A). Q.E.D.

The main purpose of this paper is to show that there exists a prime differentially closed extension over each differentially perfect field. We do this in a roundabout manner by first giving new and simple axioms for the theory of differentially closed fields (in the manner of Blum [1] for characteristic 0) and by proving that this theory is the model completion of the theory of differentially perfect fields. This paper can be read independently from [10], where we gave more complicated axioms for the same theory (in the manner of Robinson [6] for characteristic 0).I am indebted to E. R. Kolchin for answering many questions and for making the manuscript of his forthcoming book [2] available to me.

Bachmann, in [2] shows how certain ordinals <Ω(Ω = Ω1 where Ωξ is the (1 + ξ)th infinite initial ordinal) may be described from below using suitable descriptions of ordinals <Ω2. The aim of this paper is to consider another approach to describing ordinal <Ω and compare it with the Bachmann method. Our approach will use functionals of transfinite type based on Ω.The Bachmann method consists in denning a hierarchy of normal functions ϕδ: Ω → Ω (i.e. continuous and strictly increasing) for δ ≤ η0 < Ω2, starting with ϕ0(λ) = ω1 + λ. The definition of depends on a suitable description of the ordinals ≤ η0. This is obtained by defining a hierarchy 〈Fδ ∣ δ ≤ Ω2〉 of normal functions Fδ: Ω2 → Ω2 analogously to the definition of the initial segment 〈ϕδ ∣ δ ≤ Ω〉 of . The ordinal η0 is .Note. Our description of Bachmann's hierarchies will differ slightly from those in Bachmann's paper. Let and denote the hierarchies in [2]. Then as Bachmann's normal functions are not defined at 0 we let for λ, δ < Ω2. Bachmann defines for 0 < λ < Ω2 but it seems more natural to omit this so that we let . The situation is analogous for and leads to the following definitions:where n < ω and ξ is a limit number of cofinality Ω, and

In previous papers we developed two functional calculi of first order based on strict implication which we called S2 and S4. In the present paper, these systems will be extended to include a functional calculus of second order with the purpose of introducing the relation of identity of individuals.Primitive symbols. ̂ {the abstraction operator, the blank space to be replaced by an appropriate variable}.

Introduction. This paper is a sequel to our paper [3]. In that paper we introduced the notion of a finite approximation to an infinitely long formula, in a language L with infinitely long expressions of the type considered by Henkin in [2]. The results of the paper [3] show relationships between the models of an infinitely long sentence and the models of its finite approximations. In the present paper we shall apply the main result of [3] to prove a number of theorems about ordinary finitely long sentences; these theorems are of a type which one might call "preservation theorems". The following two known results are typical preservation theorems: A sentence qp is preserved under substructures if and only if q is (logically) equivalent to some universal sentence (Los [7] and Tarski [11]); q9 is preserved under homomorphic images if and only if p is equivalent to some positive sentence (Lyndon [8]). An expository account of preservation theorems may be found in Lyndon [9]. We shall use freely all of the notation introduced in [3], and shall not attempt to make this paper selfcontained. However, the reader should have no difficulty following this paper after he has read [3]. In ? 1 we cover some preliminary topics. In ? 2 and ? 3 we shall illustrate our method in familiar situations by proving anew the two preservation theorems mentioned above. We shall then obtain four new preservation theorems in ?? 4, 5, and 6, involving respectively direct powers and roots, strong homomorphisms and retracts, and direct factors. The result in ? 6 was stated in the abstract [4], while the results in ? 5 were stated in the abstract [5]. ? 1. Preliminaries. We let m be an arbitrary but fixed infinite cardinal. We consider the language L' which is exactly like the language L of [3], depending on the cardinal m, with the following two exceptions. First, L' has only the singly binary predicate symbol P, instead of an arbitrary list of at most m finitary predicate symbols. Second, L' has a doubly indexed, rather than singly indexed, sequence of variables va, a, f < m+. We let X = m+ x m+. These two changes are made only to

In this paper we deal with infinitary languages which allow arbitrary infinite disjunctions and conjunctions, but finite strings of quantifiers only. Furthermore, we shall assume that the primitive predicate symbols are finitary. (Cf. [K] and §2 for further information and unexplained notations.)Our main result shows that every “reasonable” language of this type is, in a certain sense, reducible to one of the same type which allows countable disjunctions and conjunctions only. More precisely if we let θ be the first measurable cardinal and μ ≤ θ, we have the following result partially announced in [R1]:Theorem. Every theory in a Lμω language is equivalent to some theory in a Lω1ω language in the sense that atomic formulas of one language can be mapped into formulas of the other in such a way that, for every set, these maps establish a bijective correspondence between their models having that set as a universe.The paper is divided into three sections. In the first, we derive the main result from a theorem of Sikorski on ω-homomorphisms of μ-complete boolean algebras. In the second, we give a refined version of Sikorski's theorem from which cardinality bounds can be given for the Lω1ω theories obtained by our reduction. In the last, we use a Skolem ultrapower construction to give examples for which these bounds are actually attained. As a corollary, we obtain the converse of our main result.

The possibility of constructing a numerical equivalent of a system of trans-finite ordinals, in recursive number theory, was briefly indicated in a previous paper, where consideration was confined to ordinals less than ε (the first to satisfy ε = ω). In the present paper we construct a representation, by functions of number-theoretic variables, for ordinals of any type.In addition to definite numerals, and numeral variables, we introduce majorant variables σ, ω, ωr, r ≧ 1. A relation containing a single majorant variable σ is required to hold, not necessarily for all non-negative integral values of σ, but for all values greater than some assigned constant.

Sets of postulates for at least three different combinatory logics have been given ([2], [31, [4], [51, [6], [71). The logics and their sets of postulates are quite similar. In all cases it is the proof of the completeness of the set of postulates which causes the difficulty and makes the main papers so long ([3], [7]). It is the purpose of this paper to present a method of writing down sets of postulates for combinatory logics for which the proof of completeness will be fairly simple. We assume acquaintance with certain descriptive portions of [1], namely sections 1-6, 12, 13, 15. Otherwise the present paper is self-contained. We first solve our problem for the particular logic studied by Rosser ([7]) and then indicate how the method would apply to other logics. We start with a set, s, of primitive terms. We define s-combination as in [1], p. 43. The precise contents of s need not concern us. It suffices that there be s-combinations I, J, and Q, with no variables in them, and having properties as described below. I and J are to have the same meaning as in [1], p. 43, namely IA is the same as A and JABCD is the same as AB(ADC). QAB is to have the meaning that A and B, considered as functions, are the same. One obvious way of choosing a set of primitive terms to accord with our requirements would be to choose I, J, and Q for our primitive terms. However this is not the only way, as witness the primitive terms of [7]. As a first step toward giving the desired meanings to I, J, and Q, we choose postulates and rules which suffice for the derivation of the following rules: R1. If QAB and FA, then FB. R2. If FA, then QAA. R3. If QAB, then QBA. R4. If QAB and QBC, then QAC. R5. If IA, then A. R6. If A, then IA. R7. If F(IA), then FA. R8. If FA, then F(IA). R9. If F(IAB), then F(AB). R10. If F(AB), then F(IAB) R1I. If F(JABCD), then F(AB(ADC)). R12. If F(AB(ADC)), then F(JABCD). The motivation behind these rules will appear in the proofs of Theorems 1-8 below. The reader may wonder why, in R2, we must first prove FA before being allowed to infer QAA. The point is that QAA signifies that A and A are to have the same meaning, and for this to be the case, A must have a meaning. The prior provability of FA seems to offer reasonable assurance that A has a meaning. Incidentally, for the A's which arise naturally, it is usually quite simple to find F's such that FA is provable. In all cases known to the present

In a previous paper [1] Chang and the present author presented a system of infinite valued predicate logic, the truth values being the closed interval [0, 1] of real numbers. That paper was the result of an investigation attempting to establish the completeness of the system using the real number 1 as the sole designated value. In fact, we fell short of our mark and proved a weakened form of completeness utilizing positive segments, [0, a], of linearly ordered abelian groups as admissible truth values. A result of Scarpellini [8], however, showing that the set of well-formed formulas of infinite valued logic valid (with respect to the sole designated real number 1) is not recursively enumerable indicates the above mentioned result is the best possible.

In § 1 we present conceptual material concerning the notion of a Gödel numbering of the partial recursive functions. § 2 presents a theorem about these concepts. § 3 gives several applications. The material in § 1 and § 2 grew out of attempts by the author to find routine solutions to some of the problems discussed in § 3. The author wishes to acknowledge his debt in § 2 to the fruitful methods of Myhill in [M] and to thank the referee for an abbreviated and improved version of the proof for Lemma 3 in § 2.In the literature of mathematical logic, “Gödel numbering” usually means an effective correspondence between integers and the well-formed formulas of some logical calculus. In recursive function theory, certain such associations between the non-negative integers and instructions for computing partial recursive functions have been fundamental. In the present paper we shall be concerned only with numberings of the latter, more special, sort. By numbers and integers we shall mean non-negative integers. Our notation is, in general, that of [K]. If ϕ and ψ are two partial functions, ϕ = ψ shall mean that (∀x)[ϕ(x)≃(ψx)], i.e., that ϕ and ψ are defined for the same arguments and are equal on those arguments. We consider partial recursive functions of one variable; applications of the paper to the case of several variables, or to the case of all partial recursive functions in any number of variables, can be made in the usual way using the coordinate functions (a)i of [K, p. 230]. It will furthermore be observed that we consider only concepts that are invariant with respect to general recursive functions; more limited notions of Gödel numbering, taking into account, say, primitive recursive structure, are beyond the scope of the present paper.

In [3] Kemeny made the following conjecture: Suppose *Z is a nonstandard model of the ring of integers Z. Letand let F be the subgroup of those cosets ā which contain an element of infinite height in *Z. Kemeny then asked if the ring R = {a: ā ∈ F} is also a nonstandard model of Z. If so then Goldbach's conjecture is false because Kemeny also shows in [3] that Goldbach's conjecture fails in R.The papers [1] and [5] by Gandy and Mendelson show that R is not a nonstandard model of Z but we give here a simpler proof based on Mendelson's paper. Suppose R is a nonstandard model of Z. Then each positive number in R is a sum of four squares. Choose a in R so that a is a positive element of R of infinite height in *Z. Then since a is infinite in *Z, a − 1 is positive. Thus , xi ∈ R for i = 1, …, 4. Now each xi must be of the form ai + ni, where ai has infinite height in *Z and ni, ∈ Z.

If two nonstandard models of complete arithmetic are elementarily embedded in a third, then their intersection may be considerably smaller than either of them; indeed, the intersection may be only the standard model. For example, if D and E are nonprincipal ultrafilters on ω, then the nonstandard models D-prod and E-prod (where is the standard model) have canonical elementary embeddings into D-prod (E-prod , and the intersection of their images is easily seen to be the (canonical image of the) standard model. In this paper, we shall prove that, under certain conditions, this phenomenon will not occur. Our main result (Theorem 3) is that the intersection of countably many pairwise cofinal models is itself cofinal with these models, provided that at least one of them is generated by a single element. (Precise definitions will be given below.)The theorems in this paper were first formulated in terms of ultrafilters, then rephrased (using the methods of Chapter III of [1]) as statements about ultra-powers of , and finally generalized to their present form. Since the theorems and their proofs are now entirely model-theoretic, they are presented here separately from the study of ultrafilters in which they originated. That study, including applications of the present results, will appear in [2].Let L be the first-order language whose n-place relation symbols are all the relations R ⊆; ωn and whose n-place function symbols are all the functions f: ωn → ω. Let be the standard model for L; its universe is ω and every nonlogical symbol of L denotes itself. Let be an elementary extension of . The relation (or function) denoted by R (or f) in will be called *R (or *f).

A hierarchy of systems of quantifier-free elementary recursive arithmetics, based on the Grzegorczyk hierarchy of functions, was set up in [2] and some meta-mathematical properties of these systems were developed. The Grzegorczyk hierarchy has been extended recently, mainly by Löb and Wainer [5], and our metamathematical developments may be similarly extended; the αth member of this hierarchy of formal systems will be denoted -arithmetic throughout. The main result in [2] was: For α > 1, -arithmetic can be proved consistent in -arithmetic. In this paper we shall continue this work in particular, beginning with this consistency result, we shall find (for α > 1) the order type of the weakest simple transfinite induction scheme which is independent of -arithmetic, thus giving a ‘measure of the complexity of derivations’ of these systems. For example we shall show that transfinite induction on a sequence of type ωω is a nonderivable rule of primitive recursive arithmetic (-arithmetic). This particular result was proved by Guard in [4] by a specialisation of a version of Gentzen's proof that ∈0-transfinite induction is independent of some standard formal systems of arithmetic with quantifiers. These methods can be adapted to our hierarchy but require what we might term an ‘ωω-jump’—that is if β is the largest ordinal for which transfinite induction up to β is derivable in the system in question then a scheme of transfinite induction up to β·ωω is independent. The proof presented in this paper requires only an ‘ω-jump’ and allows more precise results to be obtained for the systems in the extended Grzegorczyk hierarchy; it is also more direct and less proof-theoretic in character. We show that the consistency of -arithmetic (for α > 1) can be proved in a system obtained by adding to -arithmetic a transfinite induction scheme up to ω2, and that this induction scheme can be adapted to obtain the required result by increasing the ordinal and simultaneously decreasing the complexity of the functions involved in the induction scheme (detailed definitions of these concepts will be given in the next section).

In this paper I shall show that no one of the four primitive symbols of Heyting's calculus of propositions is definable in terms of the other three. So as to make the paper self-contained, I begin by stating the rules and primitive sentences given by Heyting.The primitive symbols of the calculus are “⅂”, “∨”, “∧”, and “⊃”, which may be read, respectively, as “not,” “either…or,” “and,” and “if…then.” The symbol “⊃⊂”, which may be read “if and only if,” is defined in terms of these as follows:The rule of substitution is assumed, and the rule that S2 follows from S1 and S1⊃S2; in addition it is assumed that S1∧S2 follows from S1 and S2. The primitive sentences are as follows

Let be the class of recursively enumerable (r.e.) sets with infinite complements. A set M ϵ is maximal if every superset of M which is in is only finitely different from M. In [1] Friedberg shows that maximal sets exist, and it is an easy consequence of this fact that every non-simple set in has a maximal superset. The natural question which arises is whether or not this is also true for every simple set (Ullian [2]). In the present paper this question is answered negatively. However, the main concern of this paper is with demonstrating, and developing a few consequences of, what might be called the “density” of hyperhypersimple sets.

It is an immediate consequence of results of Church and Gödel that there exist arithmetical recursively unsolvable problems, that is, recursively unsolvable problems of the form [M](P = Q) where P and Q are polynomials and [M] is some finite sequence of existential and universal quantifiers. A question which is immediately raised by this result is whether there exist unsolvable problems of this form where [M] is some finite sequence of existential quantifiers only. As a matter of fact this question is easily seen to be closely related to the tenth problem in the famous list proposed by Hilbert in 1900.In this paper, we prove the existence of recursively unsolvable problems of the formwhere P and Q are polynomials with non-negative integral coefficients. As a matter of fact we show that every recursively enumerable predicate is of the form (1), and conversely that every predicate of the form (1) is recursively enumerable. While our result does not yield the recursive unsolvability of Hilbert's tenth problem, it is easily seen that any considerable improvement of our result would yield this unsolvability.The author wishes to take this opportunity to express his gratitude to Professors Alonzo Church and E. L. Post with whom he has had the privilege of discussing some of the questions involved in this paper. He also wishes to thank his friends Melvin Hausner and Jacob Schwartz who have made valuable suggestions.

{a : a e C} is of the form F(D). The converse of the theorem is still an open question: does every set F(D) have the form {a+ : a e C} where the set C is as above? The proof of the theorem is broken down into a series of lemmas. We start by proving the result for the case that C is a singleton, then for the case that C is finite, and we work our way step by step to the final result. Theorems about the cardinality of ultraproducts often have applications to model theory (see [5] for some references). The results of this paper are no exception. We shall apply our results to show that certain pathological models of number theory exist, and the application also works for a wide class of other theories. The application to number theory is related to, but different from, an unpublished theorem of Ehrenfeucht which is proved by another method. The paper is divided into three sections. In ? 1 we state some definitions and results which we need from the literature. We prove our main theorem in ? 2, and the applications to model theory are in ? 3. This work was supported in part by N.S.F. Grant No. GP-1621.

In a recent paper by Mostowski [1] we find an investigation of those formulas of quantification theory which are valid in all domains of individuals, including the empty domain. Mostowski gives a complete set of axioms for such a first order functional calculus (the system is called “”) and a comparison is made with a form of the usual calculus, Church's in [2]. It is pointed out that is much less elegant; in particular, the distributivity laws for quantifiers (e.g., (x){A . B) .{x)A . (x)B) do not hold in general, and likewise the rule of modus ponens does not preserve validity in all cases.In this paper we show that a not inelegant system is obtained if one modifies Mostowski's approach in two respects; and once this is done a somewhat neater proof of completeness can be given.The first respect in which we diverge from Mostowski is in the treatment of vacuous quantifiers. For him if p has no free x, then (x)p and (∃x)p are both to have the same value (interpretation) as p1. But this is not the only way to assign values to vacuous quantifications. For when universal quantification is viewed as a generalized conjunction, the formula (x)Fx has the significance of Fa . Fb…. for as many conjunctands as there are individuals in the domain, and if Fx should have the “constant” value p, then (x)p is to mean the conjunction of p with itself for as many times as there are individuals in the domain (compare the arithmetical ).

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].

ring theory. In Part I we characterize the rings A such that the class of free (respectively projective, respectively flat) left A-modules is elementary. In [12] we solved the corresponding problems for invective modules; here we show that the class of injective A-modules is definable in Lo if and only if it is elementary. Moreover we identify the right noetherian rings A such that the class of projective (respectively free) left A-modules is definable in L.,,. Some of the results are obtained by investigating the equivalence with respect to L.. of the direct sum and the direct product of a family of modules. For example we prove that if A is right noetherian, then the left A-modules A04o) and AMo are oow-equivalent. We prove some other results of this type and we also present a conjecture about the elementary equivalence of the direct sum and product of modules. In Part II we consider the case where W is a class of rings. For example we show that the class of artinian rings is definable in L, but the class of noetherian rings is not definable; also the class of (commutative) principal ideal domains is definable in Le, but the class of (not necessarily commutative) principal left ideal domains is not definable. We also discuss the case where W is the class of (left) perfect rings and relate it to a problem of H. Bass. This paper is written in the spirit of [12] and uses some of its terminology, although it is self-contained. Parts I and II are essentially independent except that the notational conventions and algebraic preliminaries necessary for the entire paper are contained in ??I.0 and I.1.

1. Introduction. In this paper we study some of the consequences of adding as new axioms to consistent re (recursively enumerable) extensions T of Peano arithmetic P sentences undecidable in Tof the fl10 variety, as are those one naturally comes upon. The question arises: how much can two extensions "differ" when each is obtained by adding just once distinct fl10 sentences undecidable in T? We shall show that if T is as stated above, we can find extensions T, and T2, constructed very simply from T, having the property that if (A, B) is any pair of re sets with recursive intersection, there can be found a flI1 formula of P which represents A in T, and B in T2. Another question concerns the relative strength of flI1 undecidable sentences. In this connection, the position of an undecidable sentence which asserts the consistency of Tin a direct, legitimate way is of special interest; it is known that there are plenty of undecidable 1110 sentences S which are stronger than the consistency statement in the sense that the latter becomes provable when S is adjoined as a new axiom, whereas the reverse is not the case. Also, the completeness result of Turing, established in his fundamental paper [9], implies that a consistency statement for any system in a recursive progression of theories based on reflection principle I of [6, p. 289], becomes provable at level W + 1. In fact, this holds true of progressions which proceed by the successive addition of consistency statements, [6, p. 287], and hence in some progressions in which the new axioms are always flH1 sentences. We shall show, on the other hand, that there is a

The infinite-valued statement calculus to which this paper refers is that of Łukasiewicz [10], whose axiomatization was proved complete in [5]. In [9], Rutledge extended this system to include predicates and quantifiers2 and presented a deductively complete set of axioms for the monadic predicate calculus. This paper represents an attempt to axiomatize the full predicate calculus; for the proposed axiomatization, a property akin to but weaker than completeness is proved. An attempt to prove full completeness along similar lines failed; it has since been shown [11] that the set of valid formulas of the infinite-valued predicate calculus is not recursively enumerable. The method of this paper was suggested by Professor J. Barkley Rosser.

In this paper we shall use a logic with truth values ranging over all the real numbers x such that 0 ≦ x ≦ 1.1 will be “complete truth” and 0 will be “complete falsity.” The primitive sentential connectives are ‘⊃’ and ‘∼’; other connectives are ‘∨’ and ‘·’. Assume that ‘p’ and ‘q’ are sentential variables, whose truth values are respectively x and y. Then1.1. ‘p ⊃ q’ has the value min(1 − x + y, 1),1.2. ‘∼p’ has the value 1 − x,1.3. ‘p∨q’ has the value max(x, y), and1.4. ‘p·q’ has the value min (x, y).‘∨’ and ‘·’ can be defined as follows:It is the purpose of this paper to prove a theorem which will be stated in the next section. The following symbolism and convention will be used throughout the paper:S is a logical formula.ν (S) is the value of S.‘p’, ‘pi1, ’p2, …, ‘q’, are sentential variables.ν(p) = x and ν(x1) = x1, etc.ν(S) = σ and ν(S1) = σ1, etc.If S contains the sentential variables ‘p1’, ‘p2’, …, then we write for S, S(p1, P2, …). Also ν{S(p1, p2, …)) = σ(x1, x2, …).A logical formula is defined in the usual manner. 1. A sentential variable is a logical formula; 2. if S is a logical formula then ·S is a logical formula; and 3. if S and S′ are logical formulae then (S ⊃ S′) is a logical formula.

In this paper we prove some theorems concerning measures on complete Boolean algebras. Among other things, in §I of this paper, we construct a counterexample to the following conjecture of W. Luxemburg: Every measure on a nonatomic hyperstonian Boolean algebra is normal. (See [3, p. 57].) This result is expressed by Theorem 1, §I. In order to construct this example we have to suppose that a real-valued measurable cardinal exists. This hypothesis is independent of the usual axioms of set theory. Luxemburg proved that our assumption is necessary. Our second result is stated in Theorem 2 near the end of the paper.

The purpose of the present paper is to construct a fragment of number theory not subject to Gödel incompletability. Originally the system was designed as a metalanguage for classical mathematics (see section 10); but it now appears to the author worthwhile to present it as a mathematical system in its own right, to serve however rather as an instrument of computation than of proof. Its resources in the latter respect seem very extensive, sufficient apparently for the systematic tabulation of every function used in any but the most recondite physics. The author intends to pursue this topic in a later paper; the present one will simply present the system, along with proofs of consistency and completeness and a few metatheorems which will be used as lemmas for future research.Completeness is achieved by sacrificing the notions of negation and universal quantification customary in number-theoretic systems; the losses consequent upon this are made good in part by the use of the ancestral as a primitive idea. The general outlines of the system follow closely the pattern of Fitch's “basic logic”; however the latter system uses combinatory operators in place of the variables used in the present paper, and if variables are introduced into Fitch's system by definition their range of values will be found to be much more extensive than that of my variables. The present system K is thus a weaker form of Fitch's system.It is apparently not known whether or not Fitch's system is complete.

Since the publication in 1967 of the two papers [1] and [2] by Manuel Blum, the techniques and results of "pure" recursion theory, particularly the recursion theorem and priority methods, have come to play an increasingly important role in studies of computational complexity. This paper gives a typical application of the recursion theorem with a fairly intricate diagonalization to answer a question raised by Blum in [3]. Roughly, we prove the existence of functions which have the property that if we are given any program for computing the function and want to pass to a program which computes the function much more efficiently, then we can only do so at the expense of obtaining a much larger program: the function which describes the necessary increase in the size of the more efficient program must grow more rapidly than any recursive function. Let Aide be any standard indexing of all partial recursive functions. In [1], Blum defined a measure

In this third and last paper on inner models we consider some of the inherent limitations of the method of using inner models of the type defined in 1.2 for the proof of consistency results for the particular system of set theory under consideration. Roughly speaking this limitation may be described by saying that practically no further consistency results can be obtained by the construction of models satisfying the conditions of theorem 1.5, i.e., conditions 1.31, 1.32, 1.33, 1.51, viz.:This applies in particular to the ‘complete models’ defined in 1.4. Before going on to a precise statement of these limitations we shall consider now the theorem on which they depend. This is concerned with a particular type of complete model examples of which we call “proper complete models”; they are those complete models which are essentially interior to the universe, those whose classes are sets of the universe constituting a class thereof, i.e., those for which the following proposition is true:The main theorem of this paper is that the statement that there are no models of this kind can be expressed formally in the same way as the axioms A, B, C and furthermore it can be proved that if the axiom system A, B, C is consistent then so is the system consisting of axioms A, B, C, plus this new hypothesis that there exist no proper complete models. When combined with the axiom ‘V = L’ introduced by Gödel in (1) this new hypothesis yields a system in which any normal complete model which exists has for its universal class V, the universal class of the original system.

1. This paper grew out of an attempt to answer a question raised in [4]. Let a logic L containing “numerals” z1, z2, … and a certain statement N(x) (intended to express the proposition that x is a natural number) be called ω-inconsistent if there is a statement such that ⊦ F(zk) for k = 1, 2, …, and ⊦ ∼(x)·N(x) ⊃ F(x); then it is evident that L cannot have a model in which N(x) is satisfied by the images of the numerals and nothing else if L is ω-inconsistent.Question: If L is ω-consistent, i.e. not ω-inconsistent, must there be such a model? Calling a model of the kind just described a special model, we ask for necessary and sufficient conditions on L to insure the existence of a special model. We give several sets of such conditions, applicable to a certain very inclusive class of logics, in Theorem 1 and Theorems 3 and 4. Theorem 2 shows that a logic may be ω-consistent but still not have a special model.This paper was close to completion when [3] appeared. For systems with only denumerably many symbols our results include Henkin's, for, by adjoining a new predicate N(x) to each of the systems considered in [3] which have only a denumerable number of constant symbols and then adding as an axiom (x)N(x), these systems become special cases of the systems we consider. It is easily seen that Henkin's Theorem 7 essentially proves the equivalence of conditions (2) and (3) in our Theorem 1, and Theorem 3 of [3] corresponds to our Theorem 2. Incidentally, our argument of Theorem 2 could also serve to prove Henkin's Theorem 6.

In this paper we consider classes of quantificational formulas specified by restrictions on the number of atomic subformulas appearing in a formula. Little seems to be known about the decision problem for such classes, except that the class whose members contain at most two distinct atomic subformulas is decidable [2]. (We use “decidable” and “undecidable” throughout with respect to satisfiability rather than validity. All undecidable problems to which we refer are of maximal r.e. degree.) The principal result of this paper is the undecidability of the class of those formulas containing five atomic subformulas and with prefixes of the form ∀∃∀…∀. In fact, we show the undecidability of two sub-classes of this class: one (Theorem 1) consists of formulas whose matrices are in disjunctive normal form with two disjuncts; the other (Corollary 1) consists of formulas whose matrices are in conjunctive normal form with three conjuncts. (Theorem 1 sharpens Orevkov's result [8] that the class of formulas in disjunctive normal form with two disjuncts is undecidable.) A second corollary of Theorem 1 shows the undecidability of the class of formulas with prefixes of the form ∀…∀∃, containing six atomic subformulas, and in conjunctive normal form with three conjuncts. These restrictions to prefixes ∀∃∀…∀ and ∀…∀∃ are optimal. For by a result of the first author [5], any class of prenex formulas obtained by restricting both the number of atomic formulas and the number of universal quantifiers is reducible to a finite class of formulas, and so each such class is decidable; and the class of formulas with prefixes ∃…∃∀…∀ is, of course, decidable.

In the monograph [1] of Chang and Keisler, a considerable extent of model theory of the first order continuous logic (that is, roughly speaking, many-valued logic with truth values from a topological space) is ingeniously developed without using any notion of provability.In this paper we shall define the notion of provability in continuous logic as well as the notion of matrix, which is a natural extension of one in finite-valued logic in [2], and develop the syntax and semantics of it mostly along the line in the preceding paper [2]. Fundamental theorems of model theory in continuous logic, which have been proved with purely model-theoretic proofs (i.e. those proofs which do not use any proof-theoretic notions) in [1], will be proved with proofs which are natural extensions of those in two-valued logic.

Let T be a set of axioms for a classical theory TC (e.g. abelian groups, linear order, unary function, algebraically closed fields, etc.). Suppose we regard T as a set of axioms for an intuitionistic theory TH (more precisely, we regard T as axioms in Heyting's predicate calculus HPC).Question. Is TH decidable (or, more generally, if X is any intermediate logic, is TX decidable)? In [1] we gave sufficient conditions for the undecidability of TH. These conditions depend on the formulas of T (different axiomatization of the same TC may give rise to different TH) and on the classical model theoretic properties of TC (the method did not work for model complete theories, e.g. those of the title of the paper). For details see [1]. In [2] we gave some decidability results for some theories: The problem of the decidability of theories TH for a classically model complete TC remained open. An undecidability result in this direction, for dense linear order was obtained by Smorynski [4]. The cases of algebraically closed fields and real closed fields and divisible abelian groups are treated in this paper. Other various decidability results of the intuitionistic theories were obtained by several authors, see [1], [2], [4] for details.One more remark before we start. There are several possible formulations for an intuitionistic theory of, e.g. fields, that correspond to several possible axiomatizations of the classical theory. Other formulations may be given in terms of the apartness relation, such as the one for fields given by Heyting [5]. The formulations that we consider here are of interest as these systems occur in intuitionistic mathematics. We hope that the present methods could be extended to the (more interesting) case of Heyting's systems [5].

This paper is an attempt to explain as non-technically as possible the principles and devices used in the various proofs of Gödel's Theorems and Church's Theorem.Roman numerals in references shall refer to the papers in the bibliography. In the statements of Gödel's Theorems and Church's Theorem, we will employ the phrase “for suitable L.” The hidden assumptions which we denote by this phrase have never been put down explicitly in a form intelligible to the average reader. The necessity for thus formulating them has commonly been avoided by proving the theorems for special logics and then remarking that the proofs can be extended to other logics. Hence the conditions necessary for the proofs of Gödel's Theorems and Church's Theorem are at present very indefinite as far as the average reader is concerned. To partly clarify this situation, we will now mention the more prominent of these assumptions.I. In any proof of Gödel's Theorems or Church's Theorem, two logics are concerned. One serves as the “logic of ordinary discourse” in which the proof is carried out, and the other is a formal logic, L, about which the theorem is proved. The first logic may or may not be formal. However L must be formal. Among other things, this implies that the propositions of L are formulas built according to certain rules of structure.

The purpose of the present paper is to introduce a generalisation of the concept of productive set introduced by Post (2) and studied by Dekker (3) and others. Throughout the paper we shall use small Latin letters to denote both non-negative integers (referred to as numbers) and functions (both partial and total) from numbers to numbers. Sets of numbers will be denoted by small Greek letters and classes of such sets by capital Latin letters. ωη is the range of the ηth partial recursive function.

The consistency of the theory of combinators, when based on the combinatory axioms, the rules of equality, and the equationswas proved in my thesis; likewise some theorems expressing certain completeness properties of this theory of combinatory equivalence formed the principal subject of that thesis and a succeeding paper. Further theorems of this sort were later demonstrated by Rosser; his theorems are, in some cases, more powerful than those just mentioned, but they apply to a weakened system. The purpose of this note is to discuss the extension of these theorems to the case where the whole of the theory of combinators is taken into account, and the rules for equality are derived from more fundamental considerations.The paper is based on a formulation of the theory of combinators contained in a previous paper, acquaintance with which is presupposed.A key theorem in investigations of this character is a theorem proved in 1936 by Church and Rosser. It is necessary to give a brief account of this theorem together with a generalization of it.The theorem concerns a certain formalism, which I shall here call the λ-formalism. The terms of this formalism, which I shall call λ-terms, are constituted as follows. For primitive terms we have an infinite set of variables, together with certain constants, the nature of which is arbitrary. Further terms are formed by two operations: a binary operation (analogous to application in the theory of combinators) which combines two λ-terms and to form a new λ-term here symbolized by ; and another binary operation combining a variable x and a term containing x as free variable to form a term .

Dugundji has proved that none of the Lewis systems of modal logic, S1 through S5, has a finite characteristic matrix. The question arises whether there exist proper extensions of S5 which have no finite characteristic matrix. By an extension of a sentential calculus S, we usually refer to any system S′ such that every formula provable in S is provable in S′. An extension S′ of S is called proper if it is not identical with S. The answer to the question is trivially affirmative in case we make no additional restrictions on the class of extensions. Thus the extension of S5 obtained by adding to the provable formulas the additional formula p has no finite characteristic matrix (indeed, it has no characteristic matrix at all), but this extension is not closed under substitution—the formula q is not provable in it. McKinsey and Tarski have defined normal extensions of S4* by imposing three conditions. Normal extensions must be closed under substitution, must preserve the rule of detachment under material implication, and must also preserve the rule that if α is provable then ~◊~α is provable. McKinsey and Tarski also gave an example of an extension of S4 which satisfies the first two of these conditions but not the third. One of the results of this paper is that every extension of S5 which satisfies the first two of these conditions also satisfies the third, and hence the above definition of normal extension is redundant for S5. We shall therefore limit the extensions discussed in this paper to those which are closed under substitution and which preserve the rule of detachment under material implication. These extensions we shall call quasi-normal. The class of quasi-normal extensions of S5 is a very broad class and actually includes all extensions which are likely to prove interesting. It is easily shown that quasi-normal extensions of S5 preserve the rules of replacement, adjunction, and detachment under strict implication. It is the purpose of this paper to prove that every proper quasi-normal extension of S5 has a finite characteristic matrix and that every quasi-normal extension of S5 is a normal extension of S5 and to describe a simple class of characteristic matrices for S5.

In a previous paper, a functional calculus based on strict implication was developed. That system will be referred to as S2. The system resulting from the addition of Becker's axiom will be referred to as S4. In the present paper we will shw that a restricted deduction theorem is provable in S4 or more precisely in a system equivalent to S4. We will also show that such a deduction theorem is not provable in S2.The following theorems not derived in Symbolic logic will be required for the fundamental theorems XXVIII* and XXIX* of this paper. We will state most of them without proofs.

In a previous paper it was shown that the system K of basic logic could be formulated in a simpler way owing to the fact that the proper ancestral could be defined in terms of the other concepts of that system. In the present paper analogous but more far-reaching results will be obtained for the system K′ of extended basic logic. In particular we will show that negation and the dual of the proper ancestral, as well as the proper ancestral itself, are definable in terms of the other concepts of K′. Hence, in order to define K′, we need to add only a single non-finitary rule to the rules used to define K. This rule was already among the rules originally used to define K′. It asserts that ‘Aa’ is in K′ if (and only if) every ‘b’ is such that ‘ab’ is in K′.We will also show that a large class of non-finitary classes and relations are represented in K′, among which is K′ itself, just as all finitary syntactical classes and all finitary two- and three-place syntactical relations are represented in K, one of which is the finitary syntactical class K itself. The point is that K′ is adequate to handle the sort of transfinite induction that is essential in formulating K′, just as K is adequate to handle the ordinary finitary mathematical induction required in defining K′.