For every κ ∈ ω, there is an infinite set Aκ ⊆ ω and a d(κ) ∈ ω such that for all Q0, Q1, ⊆ Aκ where ∣Q0∣ = ∣ Q1∣, or d(κ) < ∣Q0∣, Q1∣ < ℵ0, the structures ‹ω, +, Q0› and ‹ω, +, Q1› are indistinguishable by first-order sentences of quantifier depth κ whose atomic formulas are of the form u = v, u + v = w, and Q(u), where u, v, and w are variables.

It is known that every < ε0-recursive function is also a primitive recursive functional. Kreisel has proved this by means of Gödel's functional-interpretation, using that every < ε0-recursive function is provably recursive in Heyting's arithmetic [2, §3.4]. Parsons obtained a refinement of Kreisel's result by a further examination of Gödel's interpretation with regard to type levels [3, Theorem 5], [4, §4]. A quite different proof is provided by the research into extensions of the Grzegorczyk hierarchy as done by Schwichtenberg and Wainer: this yields another characterization of the < ε0-recursive functions from which easily appears that these are primitive recursive functionals (see [5] in combination with [6, Chapter II]).

However, these proofs are indirect and do not show how, in general, given a definition tree of an ordinal recursive functional, transfinite recursions can be replaced (in a straightforward way) by recursions over wellorderings of lower order types. The argument given by Tait in [9, pp. 189–191] seems to be an improvement in this respect, but the crucial step in it is (at least in my opinion) not very clear.

A notion of relative reducibility for partial functions, which coincides with Turing reducibility on the total functions, was first given by S.C. Kleene in Introduction to metamathematics [4]. Following Myhill [7], this was made more explicit in Hartley Rogers, Jr., Theory of recursive functions and effective computability [8, pp. 146, 279], where some basic properties of the partial degrees or (equivalent, but notationally more convenient) the enumeration degrees, were derived. The question of density of this proper extension of the degrees of unsolvability was left open, although Medvedev's result [6] that there are quasi-minimal partial degrees (that is, nonrecursive partial degrees with no nonrecursive total predecessors) is proved.

In 1971, Sasso [9] introduced a finer notion of partial degree, which also contained the Turing degrees as a proper substructure (intuitively, Sasso's notion of reducibility between partial functions differed from Rogers' in that computations terminated when the oracle was asked for an undefined value, whereas a Rogers computation could be thought of as proceeding simultaneously along a number of different branches of a ‘consistent’ computation tree—cf. Sasso [10]). His construction of minimal ‘partial degrees’ [11], while of interest in itself, left open the analogous problem for the more standard partial degree structure.

A Krom formula of pure quantification theory is a formula in conjunctive normal form such that each conjunct is a disjunction of at most two atomic formulas or negations of atomic formulas. Every class of Krom formulas that is determined by the form of their quantifier prefixes and which is known to have an unsolvable decision problem for satisfiability is here shown to be a conservative reduction class. Therefore both the general satisfiability problem, and the problem of satisfiability in finite models, can be effectively reduced from arbitrary formulas to Krom formulas of these several prefix types.

One concern of descriptive set theory is the classification of definable sets of reals. Taken loosely ‘definable’ can mean anything from projective to formally describable in the language of Zermelo-Fraenkel set theory (ZF). Recursiveness, in the case of Kleene recursion, can be a particularly informative notion of definability. Sets of integers, for example, are categorized by their positions in the upper semilattice of Turing degrees, and the algorithms for computing their characteristic functions may be taken as their defining presentations. In turn it is interesting to position the common fauna of descriptive set theory in the upper semilattice of Kleene degrees. In so doing not only do we gain a perspective on the complexity of those sets common to the study of descriptive set theory but also a refinement of the theory of analytic sets of reals. The primary concern of this paper is to calculate the relative complexity of several notable coanalytic sets of reals and display (under suitable set theoretic hypothesis) several natural solutions to Post's problem for Kleene recursion.

For sets of reals A and B one says A is Kleene recursive in B (written A ≤KB) iff there is a real y so that the characteristic function XA of A is recursive (in the sense of Kleene [1959]) in y, XB and the existential integer quantifier ∃; i.e. there is an integer e so that XA(x) ≃ {e}(x, y, XB, ≃). Intuitively, membership of a real x ϵ ωω in A can be decided from an oracle for x, y and B using a computing machine with a countably infinite memory and an ability to search and manipulate that memory in finite time. A set is Kleene semirecursive in B if it is the domain of an integer valued partial function recursive in y, XB and ≃ for some real y.

NFP is the predicative fragment of NF. In this system we do not allow a set to exist if it cannot be defined without using quantifiers ranging over its type or parameters of a higher type. NFI is a less restrictive fragment located between NFP and NF.

We show that NFP is really weaker than NFI; similarly, NFI is weaker than NF. This result will be obtained in the following manner: on the one hand, we will show that NFP can be proved consistent in elementary arithmetic and that second order arithmetic is interpretable in NFI; on the other hand, we will prove the consistency of NFI in third order arithmetic, which is contained in NF.

The paper is divided in four sections. In §1, we define the concepts needed and collect a few results together in such a way that they will be ready for later use. In §2, we will present a model-theoretic (quick) proof of the consistency of NFI (and thus of NFP). The proof will be chosen (it is not the quickest!) so as to motivate in a natural manner the details of the proof-theoretical version of it that will be presented in §3. §4 will be devoted to the axiom of infinity in NFP and NFI.

Let P0 be the subsystem of Peano arithmetic obtained by restricting induction to bounded quantifier formulas. Let M be a countable, nonstandard model of P0 whose domain we suppose to be the standard integers. Let T be a recursively enumerable extension of Peano arithmetic all of whose existential consequences are satisfied in the standard model. Then there is an initial segment M′ of M which is a model of T such that the complete diagram of M′ is Turing reducible to the atomic diagram of M. Moreover, neither the addition nor the multiplication of M is recursive.

Let ℒ be the first order language of field theory with an additional one place predicate symbol. In [B2] it was shown that the elementary theory T of the class of all pairs of real closed fields, i.e., ℒ-structures ‹K, L›, K a real closed field, L a real closed subfield of K, is undecidable.

The aim of this paper is to show that the elementary theory Ts of a nontrivial subclass of containing many naturally occurring pairs of real closed fields is decidable (Theorem 3, §5). This result was announced in [B2]. An explicit axiom system for Ts will be given later. At this point let us just mention that any model of Ts, is elementarily equivalent to a pair of power series fields ‹R0((TA)), R1((TB))› where R0 is the field of real numbers, R1 = R0 or the field of real algebraic numbers, and B ⊆ A are ordered divisible abelian groups. Conversely, all these pairs of power series fields are models of Ts.

Theorem 3 together with the undecidability result in [B2] answers some of the questions asked in Macintyre [M]. The proof of Theorem 3 uses the model theoretic techniques for valued fields introduced by Ax and Kochen [A-K] and Ershov [E] (see also [C-K]). The two main ingredients are

(i) the completeness of the elementary theory of real closed fields with a distinguished dense proper real closed subfield (due to Robinson [R]),

(ii) the decidability of the elementary theory of pairs of ordered divisible abelian groups (proved in §§1-4).

I would like to thank Angus Macintyre for fruitful discussions concerning the subject. The valuation theoretic method of classifying theories of pairs of real closed fields is taken from [M].

Let Bn, 0 ≤ n ≤ ω, be the equational classes of distributive p-algebras (precise definitions are given in §1). It has been known for some time that the elementary theories Tn of Bn possess model companions ; see, e.g., [6] and [14] and the references given there. However, no axiomatizations of were given, with the exception of n = 0 (Boolean case) and n= 1 (Stonian case). While the first case belongs to the folklore of the subject (see [6], also [11]), the second case presented considerable difficulties (see Schmitt [13]). Schmitt's use of methods characteristic for Stone algebras seems to prevent a ready adaptation of his results to the cases n ≥ 2.

The natural way to get a hold on is to determine the class E(Bn) of existentially complete members of Bn: Since exists, it equals the elementary theory of E(Bn). The present author succeeded [12] in solving the simpler problem of determining the classes A(Bn) of algebraically closed algebras in Bn (exact definitions of A(Bn) and E(Bn) are given in §1) for all 0 > n < ω. A(Bn) is easier to handle since it contains sufficiently many “small” algebras-viz. finite direct products of certain subdirectly irreducibles-in terms of which the members of A(Bn) may be analyzed (in contrast, all members of E(Bn) are infinite and ℵ-homogeneous). As it turns out, A(Bn) is finitely axiomatizable for all n, and comparing the theories of A(B0), A(B1) with the explicitly known theories of E(B0), E(B1)-viz. , , a reasonable conjecture for , 2 ≤ n ≤ ω, is immediate. The main part of this paper is concerned with verifying that the conditions formalized by suffice to describe the algebras in E(Bn) (necessity is easy). This verification rests on the same combinatorial techniques as used in [12] to describe the members of A(Bn).

Anderson and Belnap asked in §8.11 of their treatise Entailment [1] whether a certain pure implicational calculus, which we will call P − W, is minimal in the sense that no two distinct formulas coentail each other in this calculus. We provide a positive solution to this question, variously known as The P − W problem, or Belnap's conjecture.

We will be concerned with two systems of pure implication, formulated in a language constructed in the usual way from a set of propositional variables, with a single binary connective →. We use A, B,…, A1, B1, …, as variables ranging over formulas. Formulas are written using the bracketing conventions of Church [3].

The first system, which we call S (in honour of its evident incorporation of syllogistic principles of reasoning), has as axioms all instances of

The second system, P − W, has in addition to the axioms and rules of S the axiom scheme

We write ⊢SA (⊣SA) to mean that A is (resp. is not) a theorem of S, and similarly for P − W.

Flipping properties were introduced in set theory by Abramson, Harrington, Kleinberg and Zwicker [1]. Here we consider them in the context of arithmetic and link them with combinatorial properties of initial segments of nonstandard models studied in [3]. As a corollary we obtain independence resutls involving flipping properties.

We follow the notation of the author and Paris in [3] and [2], and assume some knowledge of [3]. M will denote a countable nonstandard model of P (Peano arithmetic) and I will be a proper initial segment of M. We denote by N the standard model or the standard part of M. X ↑ I will mean that X is unbounded in I. If X ⊆ M is coded in M and M ≺ K, let X(K) be the subset of K coded in K by the element which codes X in M. So X(K) ⋂ M = X.

Recall that M ≺IK (K is an I-extension of M) if M ≺ K and for some c∈K,

In [3] regular and strong initial segments are defined, and among other things it is shown that I is regular if and only if there exists an I-extension of M.

Qκλ. Pκλ the space of all < κ-sized subsets of λ, has provided numerous opportunities for the gainful employment of set theorists in recent years, thanks to its combinatorial richness and to its relationships with various large cardinals. In the spirit of Pκλ we offer the following definition:

For κ ≤ λ both cardinals, Qκλ is the set of all partitions of λ into < κ-many pieces (an element of q ∈ Qκλ is called a piece of q). Equivalently

An element of Pκλ may be viewed as an injection from a < κ-sized set into λ, with some information thrown away. An element of Qκλ is a surjection from λ onto a < κ-sized set, with analogous loss of information.

For p, q ∈ Qκλ, we say p ≤ q iff q is a refinement of p (every piece of q is contained in a piece of p).

We take a fixed countable model M0, and we look at the structure of and number of its countable elementary extensions (up to isomorphism over M0). Assuming that S(M0) is countable, we prove that if N is a weakly minimal extension of , and if then there is an elementary embedding of N into M over M0), then N is homogeneous over M0. Moreover the condition that ∣S(M0)∣ = ℵ0 cannot be removed. Under the hypothesis that M0 contains no infinite set of tuples ordered by a formula, we prove that M0 has infinitely many countable elementary extensions up to isomorphism over M0. A preliminary result is that all types over M0 are definable, and moreover is definable over M0 if and only if is definable over M0 (forking symmetry). We also introduce a notion of relative homogeneity, and show that a large class of elementary extensions of M0 are relatively homogeneous over M0 (under the assumptions that M0 has no order and S(M0) is countable).

I will now discuss the background to and motivation behind the results in this paper, and also the place of this paper relative to other conjectures and investigations. To simplify notation let T denote the complete diagram of M0. First, our result that if M0 has no order then T has infinitely many countable models is related to the following conjecture: any theory with a finite number (more than one) of countable models is unstable.

The purpose of this paper is to study a formal system PA(Q2) of first order Peano arithmetic, PA, augmented by a Ramsey quantifier Q2 which binds two free variables. The intended meaning of Q2xx′φ(x, x′) is that there exists an infinite set X of natural numbers such that φ(a, a′) holds for all a, a′ Є X such that a ≠ a′. Such an X is called a witness set for Q2xx′φ(x, x′). Our results would not be affected by the addition of further Ramsey quantifiers Q3, Q4, …, Here of course the intended meaning of Qkx1 … xkφ(x1,…xk) is that there exists an infinite set X such that φ(a1…, ak) holds for all k-element subsets {a1, … ak} of X.

Ramsey quantifiers were first introduced in a general model theoretic setting by Magidor and Malitz [13]. The system PA{Q2), or rather, a system essentially equivalent to it, was first defined and studied by Macintyre [12]. Some of Macintyre's results were obtained independently by Morgenstern [15]. The present paper is essentially self-contained, but all of our results have been directly inspired by those of Macintyre [12].

After some preliminaries in §1, we begin in §2 by giving a new completeness proof for PA(Q2). A by-product of our proof is that for every regular uncountable cardinal k, every consistent extension of PA(Q2) has a k-like model in which all classes are definable. (By a class we mean a subset of the universe of the model, every initial segment of which is finite in the sense of the model.)

We consider various strengthenings of the combinatorial principle ◊+ which are provable from V = L, and give applications in set theory.

There are two main axiomatic extensions of Zermelo-Fraenkel set theory without the axiom of choice, that associated with the axiom of determinateness, and that associated with infinite exponent partition relations. Initially, the axiom of determinateness, henceforth AD, was the sole tool available. Using it, set theorists in the late 1960s produced many remarkable results in pure set theory (e.g. the measurability of ℵ1) as well as in projective set theory (e.g. reduction principles for ). Infinite exponent partition relations were first studied successfully soon after these early consequences of AD. They too produced measurable cardinals and not only were the constructions here easier than those from AD—the results gave a far clearer picture of the measures involved than had been offered by AD. In general, the techniques offered by infinite exponent partition relations became so attractive that a great deal of the subsequent work from AD involved an initial derivation from AD of the appropriate infinite exponent partition relation and then the derivation from the partition relation of the desired result.

Since the early 1970s work on choiceless extensions of ZF + DC has split mainly between AD and its applications to projective set theory, and infinite exponent partition relations and their applications to pure set theory. There has certainly been a fair amount of interplay between the two, but for the most part the theories have been pursued independently.

Unlike AD, infinite exponent partition relations have shown themselves amenable to nontrivial forcing arguments. For example, Spector has constructed models for interesting partition relations, consequences of AD, in which AD is false. Thus AD is a strictly stronger assumption than are various infinite exponent partition relations. Furthermore, Woodin has recently proved the consistency of infinite exponent partition relations relative to assumptions consistent with the axiom of choice, in particular, relative to the existence of a supercompact cardinal. The notion of doing this for AD is not even considered.