This note is an addendum to an incompleteness result of Feferman and Spector [1]: for any such progression satisfying the (natural) conditions listed in [1] there is a true Π10-formula which cannot be derived in the progression. The idea of their proof yields a stronger result.

If each numerical instance A[x/n] of the formula A (with the free numerical variable x) is decided in a recursive progression along a Π11-path then the set {n: ⊦ A[x/n]} is recursive.

In other words, only recursively solvable problems are decidable in such progressions. This yields the incompleteness result of [1] when specialized to some Π10 formula A which defines a nonrecursive set, since then some instance A[x/n] must be undecided and A[x/n] is a closed Π10 formula. The stronger result is needed to extend Church's thesis for total functions reckonable in formal systems to (total) functions reckonable in recursive progressions onΠ11-paths. A partially reckonable function always has a Π11 graph (and if its graph is Δ11 then it is by C. Jockusch, r.e.; so some Π11 sets are not partially reckonable). The relevance of these facts for the model of mathematical reasoning provided by (variants of) Turing's ordinal logics is analyzed in (b) (ii) of Part II, which goes into our current knowledge about Church's thesis.

Although there are many characterizations of weakly compact cardinals (e.g. in terms of indescnbability and tree properties as well as compactness) the most interesting set-theoretic (combinatorial) one is in terms of partition relations. To be more precise we define for κ and α cardinals and n an integer the partition relation of Erdös, Hajnal and Rado [2] as follows:

For every function F: [κ]n→ α (called a partition of [κ]n, the n-element subsets of κ, into α pieces), there exists a set C⊆ κ (called homogeneous for F) such that card C = κ and F″[C]n≠ α, i.e. some element of the range is omitted when F is restricted to the n-element subsets of C. It is the simplest (nontrivial) of these relations, i.e. , that is the well-known equivalent of weak compactness.1

Two directions of inquiry immediately suggest themselves when weak compactness is described in terms of these partition relations: (a) Trying to strengthen the relation by increasing the superscript—e.g., —and (b) trying to weaken the relation by increasing the subscript—e.g., . As it turns out, the strengthening to is only illusory for using the equivalence of to the tree property one quickly sees that implies (and so is equivalent to) for every n. Thus is the strongest of these partition relations. The second question seems much more difficult.

Although there is no smallest ω model [6], Putnam and Gandy independently proved about 1963 that the class of ramified analytical sets, as defined by Cohen [3], form the smallest β model of analysis [2], [8]. This paper will consider other restricted classes of models, namely the βn models for integers n > 1 [10], and prove under appropriate assumptions the existence of minimum such models. In fact we shall construct the minimum βn model in a fashion similar to the procedure yielding the class of ramified analytical sets, but adding at each stage a segment of the sets in those already obtained (for n a fixed integer > 1).

Roughly speaking a βn model is an ω model absolute for n-set-quantifier assertions about its subsets of natural numbers. A β model is simply a β1 model. See Enderton and Friedman [4] for a further investigation of βn models.

Ever since Spector's brilliant application of measure theory to recursion theory in 1958 [6] it has been realized that measure theory promotes sweeping simplifications in the theory of degrees. Results previously thought to be pathological were shown by Spector, and later Sacks [4], [5], to hold for almost all degrees (“almost all” in the sense of Lebesgue measure), often with much simpler proofs. Good examples of this phenomenon are Spector's demonstration that almost all pairs of sets are of incomparable degree (as an immediate consequence of Fubini's theorem) and Sacks' exquisitely simple deduction from this result that almost every degree is the join of two incomparable degrees (for if a random sequence is decomposed into its even and odd parts, the result is a random pair).

The present paper attempts to vindicate the feeling that almost all degrees behave in a simple manner by showing that if the quantifier in the theory of degrees with ′(jump), ∪ (join) and ∩ (meet) is taken to be (almost ∀a) instead of (∀a) then the theory is decidable. We are able to use ∩ because it will be shown that if t1, t2 are any terms built from degree variables a1, …, am with ′ and ∪ then t1 ∩ t2 exists for almost all a1, …, am. Thus the “almost all” theory presents a sharp contrast to the standard theory, where ∩ is not always defined (Kleene-Post [1]) and which is known to be undecidable (Lachlan [2]).

We study the relations between abelian groups B and C that every universal (resp. universal-existential) sentence true in B is also true in C, and give algebraic criteria for these relations to hold. As a consequence we characterize the inductive complete theories of abelian groups and prove that they are exactly the model-complete theories.

The complexity of a computable function can be measured by considering the time or space required to compute its values. Particular notions of time and space arising from variants of Turing machines have been investigated by R. W. Ritchie [14], Hartmanis and Stearns [8], and Arbib and Blum [1], among others. General properties of such complexity measures have been characterized axiomatically by Rabin [12], Blum [2], Young [16], [17], and McCreight and Meyer [10].

In this paper the speed-up and super-speed-up theorems of Blum [2] are generalized to speed-up by arbitrary total effective operators. The significance of such theorems is that one cannot equate the complexity of a computable function with the running time of its fastest program, for the simple reason that there are computable functions which in a very strong sense have no fastest programs.

Let φi be the ith partial recursive function of one variable in a standard Gödel numbering of partial recursive functions. A family Φ0, Φ1, … of functions of one variable is called a Blum measure on computation providing

(1) domain (φi) = domain (Φi), and

(2) the predicate [Φi(x) = m] is recursive in i, x and m.

Typical interpretations of Φi(x) are the number of steps required by the ith Turing machine (in a standard enumeration of Turing machines) to converge on input x, the space or number of tape squares required by the ith Turing machine to converge on input x (with the convention that Φi(x) is undefined even if the machine fails to halt in a finite loop), and the length of the shortest derivation of the value of φi(x) from the ith set of recursive equations.

Let α be a limit ordinal with the property that any “recursive” function whose domain is a proper initial segment of α has its range bounded by α. α is then called admissible (in a sense to be made precise later) and a recursion theory can be developed on it (α-recursion theory) by providing the generalized notions of α-recursively enumerable, α-recursive and α-finite. Takeuti [12] was the first to study recursive functions of ordinals, the subject owing its further development to Kripke [7], Platek [8], Kreisel [6], and Sacks [9].

Infinitary logic on the other hand (i.e., the study of languages which allow expressions of infinite length) was quite extensively studied by Scott [11], Tarski, Kreisel, Karp [5] and others. Kreisel suggested in the late '50's that these languages (even which allows countable expressions but only finite quantification) were too large and that one should only allow expressions which are, in some generalized sense, finite. This made the application of generalized recursion theory to the logic of infinitary languages appear natural. In 1967 Barwise [1] was the first to present a complete formalization of the restriction of to an admissible fragment (A a countable admissible set) and to prove that completeness and compactness hold for it. [2] is an excellent reference for a detailed exposition of admissible languages.

Let N, O and S denote the set of nonnegative integers, the graph of the constant 0 function and the graph of the successor function respectively. For sets P, Q, R ⊆ N2 operations of transposition, composition, and bracketing are defined as follows: P∪ = {〈x, y〉 ∣ 〈y, x〉 ∈ P}, PQ = {〈x, z〉 ∣ ∃y〈x, y〉 ∈ P & 〈y, z〉 ∈ Q}, and [P, Q, R] = ⋃n ∈ M(Pn Q Rn).

Theorem. The class of recursively enumerable subsets of N2 is the smallest class of sets with O and S as members and closed under transposition, composition, and bracketing.

This result is derived from a characterization by Julia Robinson of the class of general recursive functions of one variable in terms of function composition and “definition by general recursion.” A key step in the proof is to show that if a function F is defined by general recursion from functions A, M, P and R then F = [P∪, A∪M, R].

The above definitions of the transposition, composition, and bracketing operations on subsets of N2 can be generalized to subsets of X2 for an arbitrary set X. In this abstract setting it is possible to show that the bracket operation can be defined in terms of K, L, transposition, composition, intersection, and reflexive transitive closure where K: X → X and L: X → X are functions for decoding pairs.

In [5] Scott asked if there was a proof theoretic proof of his interpolation theorem. The purpose of this paper is to provide such a proof, working with the first order system LK of Gentzen [2]. Our method is an extension of the one in Maehara [3] for Craig's interpolation theorem. We will also sketch the original model theoretic proof and show how Scott used his result to obtain a definability theorem of Svenonius [7].

A language for LK contains the usual logical symbols: , ∧, ∨, ⊃, ∀, ∃; countably many free variables a0, a1, … and bound variables x0, x1, …; and some or all of the following nonlogical symbols: n-ary predicates ; n-ary functions ; and individual constants c0, c1, …. Semiterms are defined as follows: (1) Free variables, bound variables and individual constants are semiterms. (2) If f is an n-ary function and s1 …, sn are semiterms, then f(s1 …, sn), is a semiterm. A term is a semiterm that does not contain a bound variable. Formulas are defined as follows: (1) If R is an n-ary predicate and t1 …, tn are terms, then R(t1 …, tn) is a formula. (2) If A and B are formulas, then A, A ∧ B, A ∨ B and A ⊃ B are formulas. (3) If A(t) is a formula which has zero or more occurrences of the term t, and if x is a bound variable not contained in A(t), then ∀xA(x) and ∃xA(x) are formulas where A(x) is obtained from A(t) by substituting x for t at all indicated places.

Let T be a theory in a first-order language L. Let L have a predicate ν0 ≺ ν1 such that in every model of T, the interpretation of ≺ is a linear ordering with infinite field. The order-type of this ordering will be called the order-type of the model .

Several recent theorems have the following form: if T has a model of order-type ξ then T has a model of order-type ζ (see [1]). We shall add one to the list. The new feature of our result is that the order-type ζ may be in a sense “opposite” to ξ. Silver's Theorem 2.24 of [3] is a corollary of Theorem 1 below.

Theorem 1. Let κ be a strong limit number (i.e. μ < κ implies 2μ < κ). Suppose λ < κ, and suppose that for every cardinal μ < κ, T has a model with where the order-type of contains no descending well-ordered sequences of length λ. Then for every cardinal μ ≥ the cardinality ∣L∣ of the language L, T has models and such that

(a) the field of is the union of ≤ ∣L∣ well-ordered (inversely well-ordered) parts;

(b) .

The proof is by Ehrenfeucht-Mostowski models; we presuppose [2].

Chang [1], [2] has proved the following generalization of the Craig interpolation theorem [3]: For any first-order formulas φ and ψ with free first- and second-order variables among ν1, …, νn, R and ν1, …, νn, S respectively, and for any sequence Q1, …, Qn of quantifiers such that Q1 is universal whenever ν1 is a second-order variable, if

then there is a first-order formula θ with free variables among ν1, …, νn such that

(Note that the Craig interpolation theorem is the special case of Chang's theorem in which Q1, …, Qn are all universal quantifiers.) Chang also raised the question [2, Remark (k)] as to whether the Lopez-Escobar interpolation theorem [6] for the infinitary language Lω1ω possesses a similar generalization. In this paper, we show that the answer to Chang's question is affirmative and, moreover, that several interpolation theorems for applied second-order languages for number theory also possess such generalizations.

Maehara and Takeuti [7] have established independently proof-theoretic interpolation theorems for first-order logic and Lω1ω which have as corollaries both Chang's theorem and its analog for Lω1ω. Our proofs are quite different from theirs and rely on model-theoretic techniques stemming from the analogy between the theory of definability in Lω1ω and the theory of Borel and analytic sets of real numbers, rather than the technique of cut-elimination.

The central result of this paper was proved in order to settle a problem arising from B. H. Neumann's paper [10].

In [10] Neumann proved that if a finitely generated group H is recursively absolutely presentable then H is embeddable in all nontrivial algebraically-closed groups. Harry Simmons [14] clarified this by showing that a finitely generated group H is recursively absolutely presentable if and only if H can be recursively presented with solvable word-problem. Therefore, if a finitely generated group H can be recursively presented with solvable word-problem then H is embeddable in all nontrivial algebraically-closed groups.

The problem arises of characterizing those finitely generated groups which are embeddable in all nontrivial algebraically-closed groups. In this paper we prove, by a forcing argument, that if a finitely generated group H is embeddable in all non-trivial algebraically-closed groups then H can be recursively presented with solvable word-problem. Thus Neumann's result is sharp.

Our results are obtained by the method of forcing in model-theory, as developed in [1], [12]. Our method of proof has nothing to do with group-theory. We prove general results, Theorems 1 and 2 below, about constructing generic structures without certain isomorphism-types of finitely generated substructures. The formulation of these results requires the notion of Turing degree. As an application of the central result we prove Theorem 3 which gives information about the number of countable K-generic structures.

We gratefully acknowledge many helpful conversations with Harry Simmons.

Let < and ≼ be two distinguished binary relation symbols. A structure is κ-like iff is a linear ordering of A, card(A) = κ, and every proper initial segment of A has cardinality < κ. A structure is α-ordered iff is a (reflexive) linear ordering of type α with field a subset of A. We define when a cardinal κ is α-inaccessible. (In this paper, inaccessible always means weakly inaccessible.) The 0-inaccessible cardinals are just the inaccessible cardinals; if α > 0, then κ is α-inaccessible iff for each β < α, each closed, cofinal subset of κ contains a β-inaccessible. (The (1 + α)-inaccessibles are just the ρα cardinals of Mahlo.) This paper is concerned with the proof of the following theorem.

Main Theorem. There is an elementary sentence σ with the property that whenever α is an ordinal and κ an infinite cardinal, then σ has an α-ordered κ-like model iff κ is not α-inaccessible.

This theorem gives some additional answers to a question of Mostowski about languages with generalized quantifiers. Fuhrken [1] showed that this question is equivalent to the following one: For which cardinals κ and λ is it true that if an elementary sentence has a κ-like model, then it has a λ-like model? It is actually this question to which the theorem refers. The theorem limits the possible pairs κ, λ of cardinals which answer the question. In fact, if the question is generalized so as to permit sentences from some more extensive language, then the theorem still limits the possible answers. For a more thorough introduction to this problem, the reader is referred to the aforementioned article of Fuhrken as well as Keisler [2] and Vaught [6].

In previous articles ([4], [5]) it has been shown that the deductive system developed by Aristotle in his “second logic” (cf. Bochenski [2, p. 43]) is a natural deduction system and not an axiomatic system as previously had been thought [6]. It was also pointed out that Aristotle's logic is self-sufficient in two senses: First, that it presupposed no other logical concepts, not even those of propositional logic; second, that it is (strongly) complete in the sense that every valid argument formable in the language of the system is demonstrable by means of a formal deduction in the system. Review of the system makes the first point obvious. The purpose of the present article is to prove the second. Strong completeness is demonstrated for the Aristotélian system.

It is well known that in prepositional logic not every propositional connective is definable in terms of equivalence nor indeed in terms of equivalence together with negation. It is the purpose of this note to show that in a certain sense this is, however, possible within predicate logic.

Let F1 be the class of predicate logical formulae containing only the logical connectives ¬ (not), ∨ (or), E (exists), and F2 the class of predicate logical formulae containing only the logical connectives ≡ (if and only if) and E.

Our object will be to find a method for reducing any formulae ϕ of F1 to a formula ψ of F2 such that ϕ is valid if and only if ψ is valid.

Note first that for every domain D containing at least two individuals we can for every n-place relation R defined over D find an n + 1-place relation S defined over D such that for all x1, …, xn ∈ D,

holds. For instance, let S(y, x1, …, xn) be the relation y = x1 & R(x1, …, xn).

Now let ϕ be an arbitrary formula of F1 and A1, …, A3 a complete list of predicate letters occurring in ϕ of degree g1, …, gi, respectively. Let ϕ′ be the formula obtained from ϕ by replacing every prime formula Ai(x1, …, xgi) by

Then it follows immediately from the previous observation that (a) ϕ is satisfiable in D if and only if ϕ′ is satisfiable in D.

In this paper we shall construct nonregular ultrafilters showing many of the model-theoretic properties of their regular counterparts. The crucial idea in these constructions is to replace the use of regularity by independent functions. We shall use the notation and terminology of [1], our fundamental concepts being defined as follows:

Definition 1.1. (1) A uniform ultrafilter D over a cardinal κ is regular if there is a family {Xα ∣ α < κ} so that every infinite intersection of these Xα's is empty.

(2) A filter F over a cardinal κ is ω1-saturated if there is no family of sets {aα ∣ α < ω1} so that for every α < β < ω1

For more on regular ultrafilters, see [2]. The germinal theorem on the subject of nonregular ultrafilters is the following well-known result of Jack Silver:

Theorem 1.2 [1, Theorem 1.39]. If F is an ω1-saturated κ-complete filter over κ, then any ultrafilter extending F is nonregular.

This result will be the cornerstone of our constructions. Of course, the existence of a filter of the above type depends on large cardinal axioms. For more on un ω1-saturated κ-complete filters, see [1].

The main result of this paper is the following transfer theorem: If T is an elementary theory which has a κ-like model where κ is hyperinaccessible of type ω, then T has a λ-like model for each λ > card(T). Helling [3] obtained the same conclusion under the stronger hypothesis that κ is weakly compact. Fuhrken conjectured in [1] that the same conclusion would result if κ were merely inaccessible. (He also showed there the connection with a problem about generalized quantifiers.) Thus, our theorem lies properly between Helling's theorem and Fuhrken's conjecture. In [9] it is shown that this theorem is actually the best possible. This theorem and the other results of this paper were announced by the authors in [10].

In §1 we prove as Theorem 1 a slightly stronger form of the above theorem. This theorem is generalized in §2 to Theorem 2 which concerns theories which permit the omitting of types. The methods used in §§1 and 2 are also applicable to problems regarding Hanf numbers as well as to two-cardinal problems.

As Gödel [6] has pointed out, there is a certain interchangeability between the intuitionistic notion of proof and the notion of constructive functional of finite type. He achieves this interchange in the direction from logic to functionals by his functional interpretation of Heyting arithmetic H in a free variable theory T of primitive recursive functionals of finite type. In the present paper we shall extend Gödel's functional interpretation to the case in which H and T are extended by adding an abstract notion of constructive ordinal. In other words, we obtain the Gödel functional interpretation of an intuitionistic theory U of numbers (i.e., nonnegative integers) and constructive ordinals in a free variable theory V of finite type over both numbers and constructive ordinals. This allows us to obtain an analysis of noniterated positive inductive definitions [8].

The notion of constructive ordinal to be treated is as follows. There is given a function J which embeds the nonnegative integers in the constructive ordinals. A constructive ordinal of the form Jn is said to be minimal. There is also given a function δ which associates to each constructive ordinal Z and number n a constructive ordinal δZn which we denote by Zn. When Z is nonminimal, each Zn is called an immediate predecessor of Z. The basic principle for forming constructive ordinals says: for every function f from numbers n to constructive ordinals, there exists a constructive ordinal Z such that Zn = fn for all n. The principle of transfinite induction with respect to constructive ordinals says: if a property Q(Z) of constructive ordinals Z holds for minimal Z, and if ∀nQ(Zn) → Q(Z) holds for all Z, then Q(Z) holds for all Z.

Ackermann's set theory [1], called here A, involves a schema

where φ is an ∈-formula with free variables among y1, …, yn and w does not appear in φ. Variables are thought of as ranging over classes and V is intended as the class of all sets.

S is a kind of comprehension principle, perhaps most simply motivated by the following idea: The familiar paradoxes seem to arise when the class CP of all P-sets is claimed to be a set, while there exists some P-object x not in CP such that x would have to be a set if CP were. Clearly this cannot happen if all P-objects are sets.

Now, Levy [2] and Reinhardt [3] showed that A* (A with regularity) is in some sense equivalent to ZF. But the strong replacement axiom of Gödel-Bernays set theory intuitively ought to be a theorem of A* although in fact it is not (Levy's work shows this). Strong replacement can be formulated as

This lack of A* can be remedied by replacing S above by

where ψ and φ are ∈-formulas and x is not in ψ and w is not in φ. ψv is ψ with quantifiers relativized to V, and y and z stand for y1, …, yn and z1, …, zm.

First order properties of direct products and direct sums (weak direct products) of relational systems have been studied extensively. For example, in Feferman and Vaught [3] an effective procedure is given for reducing such properties of the product to properties of the factors, and thus in particular elementary equivalence is preserved. We consider here two-sorted relational systems, with the direct product and sum operations keeping one of the sorts stationary. (See Feferman [4] for a similar definition of extensions.)

These considerations are motivated by the example of direct products and sums of modules [8], [9]. In [9] examples are given to show that the direct product of two modules (even having only a finite number of module elements) does not preserve two-sorted (even universal) equivalence for any finite or infinitary language Lκ, λ. So we restrict attention here to direct powers and multiples (many copies of one structure). Also in [9] it is shown (for modules, but the proofs generalize immediately to two-sorted structures with a finite number of relations) that the direct multiple operation preserves first order ∀E-equivalence and the direct power operation preserves first order ∀-equivalence. We show here that these results for general two-sorted structures in a finite first order language are, in a sense, best-possible. Examples are given to show that does not imply , and that does not imply .