This paper is devoted to the general question, which assertions φ have the property,

if φ is provable classically, then φ is

(*) provable constructively.

More generally, we consider the question, what is the “constructive content” of a given classical proof? Our aim is to formulate rules in a form applicable to mathematical practice. Often a mathematician has the feeling that there will be no difficulty constructivizing a certain proof, only a number of routine details; although it can be quite laborious to set them all out. We believe that most such situations will come quite easily under the scope of the rules given here; the metamathematical machinery will then take care of the details.

This basic idea is not new; it has been discussed by Gödel and by Kreisel. Kreisel's investigations [Kr] were based on Herbrand's theorem; in unpublished memoranda he has also used Gödel's methods on some examples. These methods of Gödel (the double-negation and Dialectica interpretations) lie at the root of our work here. Previous work, however, has been limited to traditional formal systems of number theory and analysis. It is only recently that formal systems adequate to formalize constructive mathematics as a whole have been developed. Thus, for the first time we are in a position to formulate logical theorems which are easily applicable to mathematical practice. It is this program which we here carry out.

Now that the work has been placed in some historical context, let us return to the main question: which φ have the property (*)? Upon first considering the problem, one might guess that any φ which makes no existential assertions (including disjunctions) should have the property (*).

An analogue of a theorem of Sierpinski about the classical operation () provides the motivation for studying κ-Suslin logic, an extension of Lκ+ω which is closed under a propositional connective based on (). This theorem is used to obtain a complete axiomatization for κ-Suslin logic and an upper bound on the κ-Suslin accessible ordinals (for κ = ω these results are due to Ellentuck [E]). It also yields a weak completeness theorem which we use to generalize a result of Barwise and Kunen [B-K] and show that the least ordinal not H(κ+) recursive is the least ordinal not κ-Suslin accessible.

We assume familiarity with lectures 3, 4 and 10 of Keisler's Model theory for infinitary logic [Ke]. We use standard notation and terminology including the following.

Lκ+ω is the logic closed under negation, finite quantification, and conjunction and disjunction over sets of formulas of cardinality at most κ. For κ singular, conjunctions and disjunctions over sets of cardinality κ can be replaced by conjunctions and disjunctions over sets of cardinality less than κ so that we can (and will in §2) assume the formation rules of Lκ+ω allow conjunctions and disjunctions only over sets of cardinality strictly less than κ whenever κ is singular.

Martin [10] has computed the degrees of several classes of ω-r.e. sets. Lachlan [3] and Shoenfield [14] have obtained some additional results. For most of the examples, a class of r.e. sets is given by a property that is first-order definable over the lattice of ω-r.e. sets. Then the set of degrees of sets in this class is computed. The only sets of nonzero degrees which arise from the known examples are the following: ϕ, {a∣a is ω-r.e. and a ≠ 0}, {a∣a is ω-r.e. and a′ = 0″}, and {a∣a is ω-r.e. and a″ > 0″} (see [14]).

There have been some results in this direction for α an arbitrary admissible ordinal. Sacks [13] has shown that every nonzero α-r.e. α-degree contains a regular α-r.e. set. Thus regularity does not separate the α-r.e. α-degrees. Simpson [18] has several theorems which give information about the kinds of α-r.e. sets a given α-degree can contain. The classes of α-r.e. sets considered do separate the α-r.e. α-degrees into two nonempty pieces for some α's, but they are not necessarily given by properties which are definable over the lattice of α-r.e. sets. Using some definability results of Lerman [6], we shall make some comments about the definability of these classes of sets.

In [1] there were given postulates for an abstract “projective algebra” which, in the words of the authors, represented a “modest beginning for a study of logic with quantifiers from a boolean point of view”. In [5], D. Monk observed that the study initiated in [1] was an initial step in the development of algebraic versions of logic from which have evolved the cylindric and polyadic algebras.

Several years prior to the publication of [1], J. C. C. McKinsey [3] presented a set of postulates for the calculus of relations. Following the publication of [1], McKinsey [4] showed that every projective algebra is isomorphic to a subalgebra of a complete atomic projective algebra and thus, in view of the representation given in [1], every projective algebra is isomorphic to a projective algebra of subsets of a direct product, that is, to an algebra of relations.

Of course there has since followed an extensive development of projective algebra resulting in the multidimensional cylindric algebras [2]. However, what appears to have been overlooked is the correspondence between the Everett–Ulam axiomatization and that of McKinsey.

It is the purpose of this paper to demonstrate the above, that is, we show that given a calculus of relations as defined by McKinsey it is possible to introduce projections and a partial product so that this algebra is a projective algebra and conversely, for a certain class of projective algebras it is possible to define a multiplication so that the resulting algebra is McKinsey's calculus of relations.

This note shows that the argument used in the proof of the inconsistency of Curry's system (see [1]) can also be applied to Fitch's system QD (see [3, Chapter 6]). As one vital rule of is not present in QD this argument does not lead to an actual contradiction, but it does lead to a theorem which is not a proposition if the system is consistent.

The method used below is that of [2], which is simpler than that of [1].

The axioms and rules of QD that we require are also present in [1] and [2] provided that Fitch's D is replaced by H. These axioms and rules are the following:

DD int: ⊦ D(Da),

m p: If ⊦ a ⊃ b2 and ⊦ a then ⊦ b, and

res imp int: If a ⊦ b then Da ⊦ a ⊃ b.

Let a be arbitrary and let G be [x](Dx ⊃ (x ⊃ a)). Then let X be BWBG(BWBG). We then have the following proof:

Thus, we have ⊦ X. Now suppose we also had ⊦ DX. Then by the method of the innermost subproof in the above proof, we would have ⊦ a, and since a is

arbitrary the system would be inconsistent. Hence, if QD is consistent, we do not have ⊦ DX, and so X is a theorem which is not a proposition.

We study the measure independent character of Gödel speed-up theorems, in particular, we strengthen Arbib's necessary condition for the occurrence of a Gödel speed-up [2, p. 13] to an equivalence result and generalize Di Paola's speed-up theorem [4]. We also characterize undecidable theories as precisely those theories which possess consistent measure independent Gödel speed-ups and show that a theory τ2 is a measure independent Gödel speed-up of a theory τ1 if and only if the set of undecidable sentences of τ1 which are provable in τ2 is not recursively enumerable.

Answering a problem of Fuhrken we prove that for every κ, 1 ≤ κ ≤ ℵ0, there is a (countable) complete theory T, with no prime model, and exactly κ minimal models (up to isomorphism).

In this paper, we give consistency proofs for the existence of a κ-saturated ideal on an inaccessible κ, and for the existence of an ω2-saturated ideal on ω1. We also include an historical survey outlining other known results on saturated ideals.

§1. Forcing. We assume that the reader is familiar with the usual techniques in forcing and Boolean-valued models (see Jech [3] or Rosser [11]), so we shall just specify here some of the less standard notation.

“cBa” abbreviates “complete Boolean algebra”.

If P (= ‹P, <›) is a notion of forcing, is the associated cBa. We write VP for .

Notions like κ-closed, κ-complete, etc. always mean < κ. Thus, P is κ-closed iff every decreasing chain of length less than κ has a lower bound, and a Boolean algebra is κ-complete iff sups of subsets of of cardinality less than κ always exist.

If is a cBa, x̌ is the object in representing x in V. In many cases, especially with ordinals, the ̌ is dropped. V̌ is the Boolean-valued class representing V — i.e.,

Let NBG be von Neumann-Bemays-Gödel set theory without the axiom of choice and let NBGA be the modification which allows atoms. In this paper we consider some of the well-known class or global forms of the wellordering theorem, the axiom of choice, and maximal principles which are known to be equivalent in NBG and show they are not equivalent in NBGA.

Let n ≥ 3. The following theorems are proved.

Theorem. The theory of the class of strictly upper triangular n × n matrix rings over fields is finitely axiomatizable.

Theorem. If R is a strictly upper triangular n × n matrix ring over a field K, then there is a recursive map σ from sentences in the language of rings with constants for K into sentences in the language of rings with constants for R such that K ⊨ φ if and only if R φ σ(φ).

Theorem. The theory of a strictly upper triangular n × n matrix ring over an algebraically closed field is ℵ1-categorical.

Let Γ be a class of subsets of Baire space (ωω) closed under inverse images by continuous functions. We say such a Γ is continuously closed. Let , the class dual to Γ, consist of the complements relative to ωω of members of Γ. If Γ is not selfdual, i.e., , then let . A continuously closed nonselfdual class Γ of subsets of ωΓ is said to have the first separation property [2] if

The set C is said to separate A and B. The class Γ is said to have the second separation property [3] if

We shall assume the axiom of determinateness and show that if Γ is a continuously closed class of subsets of ωω and then

(1) Γ has the first separation property iff does not have the second separation property, and

(2) either Γ or has the second separation property.

Of course, (1) and (2) taken together imply that Γ and cannot both have the first separation property.

Let T be a complete theory with infinite models in a countable language. The stability function gT(κ) is defined as the supremum of the number of types over models of T of power κ. It is proved that there are only six possible stability functions, namely κ, κ + 2ω, κω, ded κ, (ded κ)ω, 2κ.

Let V∞ be a fixed, fully effective, infinite dimensional vector space. Let be the lattice consisting of the recursively enumerable (r.e.) subspaces of V∞, under the operations of intersection and weak sum (see §1 for precise definitions). In this article we examine the algebraic properties of .

Early research on recursively enumerable algebraic structures was done by Rabin [14], Frölich and Shepherdson [5], Dekker [3], Hamilton [7], and Guhl [6]. Our results are based upon the more recent work concerning vector spaces of Metakides and Nerode [12], Crossley and Nerode [2], Remmel [15], [16], and Kalantari [8].

In the main theorem below, we extend a result of Lachlan from the lattice of r.e. sets to . We define hyperhypersimple vector spaces, discuss some of their properties and show if A, B ∈ , and A is a hyperhypersimple subspace of B then there is a recursive space C such that A + C = B. It will be proven that if V ∈ and the lattice of superspaces of V is a complemented modular lattice then V is hyperhypersimple. The final section contains a summary of related results concerning maximality and simplicity.

In this paper, we show that the theory of ordered differential fields has a model completion. We also show that any real differential field, finitely generated over the rational numbers, is isomorphic to some field of real meromorphic functions. In the last section of this paper, we combine these two results and discuss the problem of deciding if a system of differential equations has real analytic solutions. The author wishes to thank G. Stengle for some stimulating and helpful conversations and for drawing our attention to fields of real meromorphic functions.

§ 1. Real and ordered fields. A real field is a field in which −1 is not a sum of squares. An ordered field is a field F together with a binary relation < which totally orders F and satisfies the two properties: (1) If 0 < x and 0 < y then 0 < xy. (2) If x < y then, for all z in F, x + z < y + z. An element x of an ordered field is positive if x > 0. One can see that the square of any element is positive and that the sum of positive elements is positive. Since −1 is not positive, an ordered field is a real field. Conversely, given a real field F, it is known that one can define an ordering (not necessarily uniquely) on F [2, p. 274]. An ordered field F is a real closed field if: (1) every positive element is a square, and (2) every polynomial of odd degree with coefficients in F has a root in F. For example, the real numbers form a real closed field. Every ordered field can be embedded in a real closed field. It is also known that, in a real closed field K, polynomials satisfy the intermediate value property, i.e. if f(x) ∈ K[x] and a, b ∈ K, a < b, and f(a)f(b) < 0 then there is a c in K such that f(c) = 0.

In [5] S. S. Wainer introduces a hierarchy for arbitrary type-2-functionals. Given F, he defines a set of ordinal notations OF, and for each a ∈ OF, a function fa recursive in F and an ordinal ∣a∣F < For any f recursive in F there is an a ∈ OF such that f is primitive recursive in fa.

Let ρF be the least ordinal α such that for any f recursive in F there is an α ∈ OF with ∣a∣F ≤ α such that f is primitive recursive in fa. If ρF < the hierarchy breaks down. In Bergstra and Wainer [2] ρF is described as “the real ordinal of the 1-section of F”.

Using standard methods (originally due to Kleene) one may prove that if F is normal, then ρF = Feferman has proved that if F is recursive, then ρF = ω2.

Let 1-section (F) = l-sc(F) = {f; f is recursive in F} where f is a total object of type 1.

Grilliot [4] proved that F ↾ 1-sc(F) is continuous if and only if F is not normal.

Let h be an associate for a given functional F, and assume that h is recursive in the jump of an element of 1-sc(F).

Martin [12] has shown that the determinacy of analytic games is a consequence of the existence of sharps. Our main result is the converse of this:

Theorem. If analytic games are determined, then x2 exists for all reals x.

This theorem answers question 80 of Friedman [5]. We actually obtain a somewhat sharper result; see Theorem 4.1. Martin had previously deduced the existence of sharps from 3 − Π11-determinacy (where α − Π11 is the αth level of the difference hierarchy based on − Π11 see [1]). Martin has also shown that the existence of sharps implies < ω2 − Π11-determinacy.

Our method also produces the following:

Theorem. If all analytic, non-Borel sets of reals are Borel isomorphic, then x* exists for all reals x.

The converse to this theorem had been previously proven by Steel [7], [18].

We owe a debt of gratitude to Ramez Sami and John Steel, some of whose ideas form basic components in the proofs of our results.

For the various notation, definitions and theorems which we will assume throughout this paper, the reader should consult [3, §§5, 17], [8], [13] and [14, Chapter 16].

Throughout this paper we will concern ourselves only with methods for obtaining 0# (rather than x# for all reals x). By relativizing our arguments to each real x, one can produce x2.

We say that a ring admits elimination of quantifiers, if in the language of rings, {0, 1, +, ·}, the complete theory of R admits elimination of quantifiers.

Theorem 1. Let D be a division ring. Then D admits elimination of quantifiers if and only if D is an algebraically closed or finite field.

A ring is prime if it satisfies the sentence: ∀x∀y∃z (x =0 ∨ y = 0∨ xzy ≠ 0).

Theorem 2. If R is a prime ring with an infinite center and R admits elimination of quantifiers, then R is an algebraically closed field.

Let be the class of finite fields. Let be the class of 2 × 2 matrix rings over a field with a prime number of elements. Let be the class of rings of the form GF(pn)⊕GF(pk) such that either n = k or g.c.d. (n, k) = 1. Let be the set of ordered pairs (f, Q) where Q is a finite set of primes and such that the characteristic of the ring f(q) is q. Finally, let be the class of rings of the form ⊕q ∈ Qf(q), for some (f, Q) in .

Theorem 3. Let R be a finite ring without nonzero trivial ideals. Then R admits elimination of quantifiers if and only if R belongs to.

Theorem 4. Let R be a ring with the descending chain condition of left ideals and without nonzero trivial ideals. Then R admits elimination of quantifiers if and only if R is an algebraically closed field or R belongs to.

In contrast to Theorems 2 and 4, we have

Theorem 5. If R is an atomless p-ring, then R is finite, commutative, has no nonzero trivial ideals and admits elimination of quantifiers, but is not prime and does not have the descending chain condition.

We also generalize Theorems 1, 2 and 4 to alternative rings.

Several new features arise in the generalization of recursion theory on ω to recursion theory on admissible ordinals α, thus making α-recursion theory an interesting theory. One of these is the appearance of irregular sets. A subset A of α is called regular (over α), if we have for all β < α that A ∩ B ∈ Lα, otherwise A is called irregular (over α). So in the special case of ordinary recursion theory (α = ω) every subset of α is regular, but if α is not a cardinal of L we find constructible sets A ⊆ α which are irregular. The notion of regularity becomes essential, if we deal with α-recursively enumerable (α-r.e.) sets in priority constructions (α-r.e. is defined as Σ1 over Lα). The typical situation occurring there is that an α-r.e. set A is enumerated during some construction in which one tries to satisfy certain requirements. Often this construction succeeds only if we can insure that every initial segment A ∩ β of A is completely enumerated at some stage before α. This calls for making sure that A is regular because due to the admissibility of α an α-r.e. set A is regular iff for every (or equivalently for one) enumeration f of A (f is an enumeration of A iff f: α → A is α-recursive, total, 1-1 and onto) we have that is the image of the set σ under f).

We prove that a countable complete theory whose prime model has an infinite definable subset, all of whose elements are named, has at least four countable models up to isomorphism. The motivation for this is the conjecture that a countable theory with a minimal model has infinitely many countable models. In this connection we first prove that a minimal prime model A has an expansion by a finite number of constants A′ such that the set of algebraic elements of A′ contains an infinite definable subset.

We note that our main conjecture strengthens the Baldwin–Lachlan theorem. We also note that due to Vaught's result that a countable theory cannot have exactly two countable models, the weakest possible nontrivial result for a non-ℵ0-categorical theory is that it has at least four countable models.

§1. Notation and preliminaries. Our notation follows Chang and Keisler [1], except that we denote models by A, B, etc. We use the same symbol to refer to the universe of a model. Models we refer to are always in a countable language. For T a countable complete theory we let n(T) be the number of countable models of T up to isomorphism. ∃n means ‘there are exactly n’.

The Rice-Shapiro Theorem [4] says that the index set of a class of recursively enumerable (r.e.) sets is r.e. if and only if consists of all sets which extend an element of a canonically enumerable sequence of finite sets. If an index of a difference of r.e. (d.r.e.) sets is defined to be the pair of indices of the r.e. sets of which it is the difference, then the following generalization due to Hay [3] is obtained: The index set of a class of d.r.e. sets is d.r.e. if and only if is empty or consists of all sets which extend a single fixed finite set. In that paper Hay also classifies index sets of classes consisting of d.r.e. sets which extend one of a finite collection of finite sets. These sets turn out to be finite Boolean combinations of r.e. sets. The question then arises “What about the classification of the index set of a class consisting of d.r.e. sets which extend an element of a canonically enumerable sequence of finite sets?” The results in this paper come from an attempt to answer this question.

Since classes of sets which are Boolean combinations of r.e. sets form a hierarchy (the finite Ershov hierarchy, see Ershov [1]) with the r.e. and d.r.e. sets respectively levels 1 and 2 of this hierarchy, we may define index sets of classes of level n sets. If is a class of level n sets which extend some element of a canonically enumerable sequence of finite sets and if we let co-, then we extend the original classification question to the classification of the index sets of the classes and co-.

Now if the sequence of finite sets enumerates only finitely many sets or if only finitely many of the finite sets are minimal under inclusion, then it is a routine computation to verify that the index sets of and co- are in the finite Ershov hierarchy. Thus we are interested in the case in which infinitely many of the sequence of finite sets are minimal under inclusion. However if the infinite sequence is fairly simple, for instance{0}, {1}, {2}, … then the r.e. index set of co- is Σ20-complete as well as the index sets of and co- for all levels n > 2. Since the finite Ershov hierarchy does not exhaust ⊿20 there is a lot of “room” between these two extreme cases.