Assume ZFC + “There is a weakly compact cardinal” is consistent. Then:

(i) For every S ⊆ ω, ZFC + “S and the monadic theory of ω2 are recursive each in the other” is consistent; and

(ii) ZFC + “The full second-order theory of ω2 is interpretable in the monadic theory of ω2” is consistent.

It is known [4, Theorem 11-X(b)] that there is only one acceptable universal function up to recursive isomorphism. It follows from this that sets definable in terms of a universal function alone are specified uniquely up to recursive isomorphism. (An example is the set K, which consists of all n such that {n}(n) is defined, where λn, m{n}(m) is an acceptable universal function.) Many of the interesting sets constructed and studied by recursion theorists, however, have definitions which involve additional notions, such as a specific enumeration of the graph of a universal function. In particular, many of these definitions make use of the interplay between the purely number-theoretic properties of indices of partial recursive functions and their purely recursion-theoretic properties.

This paper concerns r.e. sets that can be defined using only a universal function and some purely number-theoretic concepts. In particular, we would like to know when certain recursion-theoretic properties of r.e. sets definable in this way are independent of the particular choice of universal function (equivalently, independent of the particular way in which godel numbers are identified with natural numbers).

We will first develop a suitable model-theoretic framework for discussing this question. This will enable us to classify the formulas defining r.e. sets by their logical complexity. (We use the number of alternations of quantifiers in the prenex form of a formula as a measure of logical complexity.) We will then be able to examine the question at each level.

This work is an approach to the question of when the recursion-theoretic properties of an r.e. set are independent of the particular parameters used in its construction. As such, it does not apply directly to the construction techniques most commonly used at this time for defining particular r.e. sets, e.g., the priority method. A more direct attack on this question for these techniques is represented by such works as [3] and [5]. However, the present work should be of independent interest to the logician interested in recursion theory.

We give two new finite combinatorial statements which are independent of Peano arithmetic, using the methods of Kirby and Paris [6] and Paris [12]. Both are in fact equivalent over Peano arithmetic (denoted by P) to its 1-consistency. The first involves trees and the second linear orderings. Both were “motivated” by anti-basis theorems of Clote (cf. [1], [2]). The one involving trees, however, is not unrelated to the Kirby-Paris characterization of strong cuts in terms of the tree property [6], but, in fact, comes directly from König's lemma, of which it is a miniaturization. (See the remark preceding Theorem 3 below.) The resulting combinatorial statement is easily seen to imply the independent statement discovered by Mills [11], but it is not clear how to show their equivalence over Peano arithmetic without going through 1-consistency. The one involving linear orderings miniaturizes the property of infinite sets X that any linear ordering of X is isomorphic to ω or ω* on some infinite subset of X. Both statements are analogous to Example 2 of [12] and involve the notion of dense [12] or relatively large [14] finite set.

We adopt the notations and definitions of [6] and [12]. We shall in particular have need of the notions of semiregular, regular and strong initial segments and of indicators.

Our results concern the existence of a countable extension of the countable atomless Boolean algebra such that is a “nonconstructive” extension of . It is known that for any fixed admissible indexing φ of there is a countable nonconstructive extension of (relative to φ). The main theorem here shows that there exists an extension of such that for any admissible indexing φ of , is nonconstructive (relative to φ).Thus, in this sense a countable totally nonconstructive extension of .

We give here an elementary proof of a recent result of Girard [4] comparing the rates of growth of the two principal (and extreme) examples of a spectrum of “majorization hierarchies”—i.e. hierarchies of increasing number-theoretic functions, indexed by (systems of notations for) initial segments I of the countable ordinals so that if α < β ∈ I then the βth function dominates the αth one at all but finitely-many positive integers x.

Hardy [5] was perhaps the first to make use of a majorization hierarchy—the Hα's below—in “exhibiting” a set of reals with cardinality ℵ1. More recently such hierarchies have played important roles in mathematical logic because they provide natural classifications of recursive functions according to their computational complexity. (All the functions considered here are “honest” in the sense that the size of their values gives a measure of the number of steps needed to compute them.)

The hierarchies we are concerned with fall into three main classes depending on their mode of generation at successor stages, the other crucial parameter being the initial choice of a particular (standard) fundamental sequence λ0 < λ1 < λ2 < … to each limit ordinal λ under consideration which, by a suitable diagonalization, will then determine the generation at stage λ.

Our later comparisons will require the use of a “large” initial segment I of proof-theoretic ordinals, extending as far as the “Howard ordinal”. However we will postpone a precise description of these ordinals and their associated fundamental sequences until later.

Notations, conventions, and definitions. {μi∣i < ω} will be an effective enumeration of all partial recursive μi{ω → 2. A type of a theory T will be a set of formulas in the language of T, in finitely many free variables, which is consistent with T. A complete type is a maximal type in some fixed number of free variables. A type is recursive if, relative to some effective enumeration of the formulas of the language, the characteristic function for the type is recursive. A set ψ of recursive types has property P if some set of indices of characteristic functions for all the types in ψ has property P. So, for example, we might say that a set of recursive types is . If is an L-structure, then the type spectrum of , denoted ‘TySp()’, is the set of complete types realized in (we will assume that an n-type has formulas with free variables among {x1, …, xn}). A type spectrum for a theory T is a type spectrum of some model of T. ‘TySp0(T)’ will denote the set of principal types of T.

We will assume that the reader is familiar with Henkin constructions of models, and of passing from a maximal consistent set of sentences, with “Henkin constants”, to a model. In particular, for a theory T in L we will let {ai∣i < ω} be new distinct constant symbols, and {φi < ω} a list of all sentences in the expanded language. ‘ΔN’ will denote the elementary diagram constructed at stage N, and .

It is shown how to define forcing semantics within metatheories not containing the power-set construction, in particular, how to construct exponents assuming only (a slightly strengthened form of) exponents in the metatheory. Some straightforward applications (consistency and independence results, and derived rules) are obtained for such systems.

The set of all words in the alphabet {l, r} forms the full binary tree T. If x ∈ T then xl and xr are the left and the right successors of x respectively. We consider the monadic second-order language of the full binary tree with the two successor relations. This language allows quantification over elements of rand over arbitrary subsets of T. We prove that there is no monadic second-order formula ϕ*(X, y) such that for every nonempty subset X of T there is a unique y ∈ X that satisfies ϕ*(X, y) in T.

L denotes a fixed finitary similarity type, B, respectively P a new relation symbol, an L-structure in the usual sense, and (, σ) a topological L-structure, where σ is a topology on A. (, σ) is countable if is countable and σ has a countable base. The formal language for our study of topological structures is . is the least fragment of the (monadic) second-order, infinitary language closed under negation (⇁), countable disjunction (∨), countable conjunction (∧), quantification over individual variables (∃ν, ∀ν), and quantification over set variables in the form ∃V(t ∈ V → φ) [respectively ∃V(t ∈ V → φ] where t is an L-term and each free occurrence of V in φ is negative [respectively positive]. We abbreviate ∃V(t ∈ V ∧ φ) and ∀V(t ∈ V → φ) by ∃V ∈ ν φ respectively ∀V ∈ ν φ. (For detailed information on we reIer to [1].)

i, j, … m, n range over ω. a, x, etc. denote finite tuples; a ∈ A means that all members of a are in A. IdA denotes the identity on A, Perm(A) the set of all permutations of A, and Aut() (respectively Aut(, σ)) the set of all automorphisms of (respectively (σ)). Let F ⊆ Perm(A), B ⊆ Am(m ≥ 1), and μ be a system of subsets of A. B (respectively μ) is called invariant under F if for all ƒ ∈ F, ƒ(B) = B (respectively ƒ(μ) = μ). denotes the least system of subsets of A which contains μ and which is closed under arbitrary union, .

For the rest of this paragraph let A be a countable nonempty set.

The class of 2-square ultrafilters on ω equals the union, for n ≥ 1, of the classes of strictly n Ramsey ultrafilters on ω.

By induction for a formula φ we mean the schema

(where the terms in brackets are implicitly substituted for some fixed variable, with the usual restrictions). Let be the schema IAφ for φ in Πn (i.e. ); similarly for . Each instance of is Δn+2, and each instance of is Σn+1 Thus the universal closure of an instance α is Πn+2 in either case. Charles Parsons [72] proved that and are equivalent over Z0, where Z0 is essentially Primitive Recursive Arithmetic augmented by classical First Order Logic [Parsons 70].

Theorem. For each n > 0 there is a Πn formula π for whichis not derivable in Z0from

(i) true Πn+1sentences; nor even

(ii) Πn+1sentences consistent withZ0.

In a paper of 1933 Gödel proved that every satisfiable first-order ∀2∃* sentence has a finite model. Actually he constructed a finite model in an ingenious and sophisticated way. In this paper we use a simple and straightforward probabilistic argument to establish existence of a finite model of an arbitrary satisfiable ∀2∃* sentence.

Let α be an admissible ordinal. An α-recursively enumerable set H is hyper-hypersimple (hh-simple) if its lattice of α-r.e. supersets forms a Boolean algebra. In [3], Chong and Lerman characterized the class ℋ() of hh-simple -r.e. sets as precisely those -r.e. sets whose complements are unbounded and of order type less than . Perhaps a nice example of such a set is {σ∣σ is not for any n < ω}. It follows that all hh-simple sets in are nonhyperregular and therefore of degree 0′. That ℋ() is a natural class to study can be seen from the role played by its ω-counterpart in the study of decision problems and automorphisms of ℰ*(ω), the lattice of ω-r.e. sets modulo finite sets (Soare [13] gives an extensive literature on these topics). In α-recursion theory the existence of hh-simple sets is not an all pervasive phenomenon, and there is as yet no complete characterization of the admissible ordinal α for which ℋ(α) is nonempty. While this situation is admittedly unsatisfactory, we feel that the lattice ℰ*(α) of α-r.e. sets modulo α*-finite sets for which ℋ(α) ≠ ∅ deserves a careful study. Indeed armed with some understanding over the last few years of the general theory of admissible ordinals, it is tempting to focus one's attention on some specific ordinals whose characteristics admit a more detailed analysis of the fine structure of sets and degrees. From this point of view, and ℋ() are natural objects of study since the former is a typical example of a non-Σ2-projectible, Σ2-inadmissible ordinal, while the latter is important for the investigations of automorphisms over ℰ*().

It will be shown that in the lattice of recursively enumerable sets all lattices L3(X) are elementarily definable with parameters, where X is and L3(X) consists of all sets containing X.

Higher-order theories of properties, relations, and propositions (PRPs) are known to be essentially incomplete relative to their standard notions of validity. There is, however, a first-order theory of PRPs that results when standard first-order logic is supplemented with an operation of intensional abstraction. It turns out that this first-order theory of PRPs is provably complete with respect to its standard notions of validity. The construction involves the development of a new algebraic semantic method. Unlike most other methods used in contemporary intensional logic, this method does not appeal to possible worlds as a heuristic; the heuristic used is that of PRPs taken as primitive entities. This is important, for even though the possible-worlds approach is useful in treating modal logic, it seems to be of little help in treating the logic for psychological matters. The present approach, by contrast, appears to make a step in the direction of a satisfactory treatment of both modal and intentional logic. For, by taking PRPs as primitive entities, we remain free to tailor the statement of their identity conditions so that it agrees with the logical data—modal, psychological, etc. In this way, the present approach suggests a strategy for developing a comprehensive treatment of intensional logic.

In [1] and [2] I explore this prospect philosophically. The purpose of the present paper is to lay out the technical details of the approach and to present the completeness results.

This paper's goal is to determine which complete theories of perfect, e-free Ax fields are model-complete. A field K is e-free for a positive integer e if the Galois group g(KS∣K), where Ks is the separable closure of K, is an e-free, profinite group. A perfect field K is pseudo-algebraically closed if each nonvoid, absolutely irreducible variety defined over K has a K-rational point. A perfect, pseudo-algebraically closed field is called an Ax field. The main theorem is

A complete theory of e-free Ax fields is model-complete if and only if its field of absolute numbers is e-free.

The sufficiency of the latter condition is an easy consequence of a result of Moshe Jarden and Ursel Kiehne [10] and has been noted independently by A. Macintyre and K. McKenna and undoubtedly by others as well. Consequently the necessity of the latter condition is the interesting part of this paper.

James Ax [3] initiated the investigation of 1-free Ax fields. He proved that these fields, which he called pseudo-finite fields, are precisely the infinite models of the theory of finite fields. He [3] also presented examples of perfect, 1-free fields which are not pseudo-algebraically closed and an example of a 1-free Ax field whose complete theory is not model-complete. Moshe Jarden [5] showed that the first examples are isolated cases in that almost all, perfect, 1-free, algebraic extensions of a denumerable, Hilbertian field are pseudo-algebraically closed. The results in this paper show that the second example is also an isolated case in that almost all complete theories of 1-free Ax fields are model-complete.

In this paper we give short proofs to the undecidability of the τ-theory for free groups and other relevant theories.

The complete, model-complete theories of pseudo-algebraically closed fields were characterized completely in [11]. That work constituted the first step towards determining all the model-complete theories of fields in the usual language of fields. In this paper the second step is taken. Namely, the methods of [11] are extended to characterize the complete, model-complete theories of pseudo-real closed fields and pseudo-p-adically closed fields.

In order to unify the treatment of these two types of fields, the relevant properties of real closed ordered fields and p-adically closed valued fields are abstracted. The subsequent investigation of model-complete theories of fields is based entirely on these properties. The properties were selected in order to solve three problems: (1) finding universal theories with the joint embedding property, (2) finding first order conditions in the usual language of fields which are necessary and sufficient for a polynomial over a field to have a zero in a formally real or formally p-adic extension of that field, and (3) finding subgroups of Galois groups whose fixed fields are formally real or formally p-adic.

This paper is related to, and uses in §1 but not in the other sections, parts of K. McKenna's work [8] on model-complete theories of ordered fields and p-valued fields. However, the results herein are not direct consequences of his work, both because these results apply to a more general situation and because they use a different formal language. Concerning the latter point, in some instances, such as real closed ordered fields and p-adically closed valued fields, model-complete theories in expanded languages do yield model-complete theories of ordinary fields other than theories of pseudo-algebraically closed fields. However, in other cases, such as differentially closed fields, this is not so.

It is well known that for all recursively enumerable sets X1, X2 there are disjoint recursively enumerable sets Y1 ⊆ Y2 such that Y ⊆ X1, Y2 ⊆ X2 and Y1, ⋃ Y2 = X1 ⋃ X2. Alistair Lachlan called distributive lattices satisfying this property separated. He proved that the first-order theory of finite separated distributive lattices is decidable. We prove here that the first-order theory of all separated distributive lattices is undecidable.

The study of preservation theorems for first order logic was the focus of much research by model theorists in the 1960's. These theorems, which came to form the foundation for classical model theory, characterize first order sentences and theories that are preserved under operations such as the taking of unions or submodels (see Chang and Keisler [5] for a discussion of preservation theorems for first order logic). In current model theoretic research, logics richer than first order logic and applications of logic to other parts of mathematics have assumed the central position. In the former area, preservation theorems are not so important; in the latter, especially in applications to algebra, many of the techniques developed for proving these theorems have been useful.

In this paper I prove several preservation theorems for first order logic which I discovered while investigating the asymptotic growth of classes of finite combinatorial structures. The significance of these theorems lies in their applications to problems in finite combinatorics. Since the applications require combinatorial and analytical techniques that are not pertinent to logical questions discussed here, I shall present them in another paper [7].