Suppose that G is a group that is not finitely generated. Then the cofinality of G, written c(G), is denned to be the least cardinal λ such that G can be expressed as the union of a chain of λ proper subgroups. If κ is an infinite cardinal, then Sym(κ) denotes the group of all permutations of the set κ = {α∣α < κ}. In [1], Macpherson and Neumann proved that c(Sym(κ)) > κ for all infinite cardinals κ. In [4], we proved that it is consistent that c(Sym(ω)) and 2ω can be any two prescribed regular cardinals, subject only to the obvious requirement that c(Sym(ω)) ≤ 2ω. Our first result in this paper is the analogous result for regular uncountable cardinals κ.

Theorem 1.1. Let V ⊨ GCH. Let κ, θ, λ ∈ V be cardinals such that

(i) κ and θ are regular uncountable, and

(ii) κ < θ ≤ cf(λ).

Then there exists a notion of forcing ℙ, which preserves cofinalities and cardinalities, such that if G is ℙ-generic then V[G] ⊨ c(Sym(κ)) = θ ≤ λ = 2κ.

Theorem 1.1 will be proved in §2. Our proof is based on a very powerful uniformization principle, which was shown to be consistent for regular uncountable cardinals in [2].

It is shown that for any computable field K and any r.e. degree a there is an r.e. set A of degree a and a field F ≃ K with underlying set A such that the field operations of F (including subtraction and division) are extendible to (total) recursive functions. Further, it is shown that if a and b are r.e. degrees with b ≤ a, there is a 1-1 recursive function f: ℚ → ω such that f(ℚ) ∈ a, f(ℤ) ∈ b, and the images of the field operations of ℚ under f can be extended to recursive functions.

In the presence of large cardinals, or sufficient determinacy, every equivalence relation in either admits a wellordered separating family or continuously reduces E0.

The κ-isomorphism property (IPκ) for nonstandard universes was introduced by Henson in [4]. There has been some recent effort aimed at more fully understanding this property. Jin and Shelah in [7] have shown that for κ < ⊐ω, IPκ is equivalent to what we will refer to as the κ-resplendence property. Earlier, in [6], Jin asked if IPκ is equivalent to IPℵ0 plus κ-saturation. He answered this question positively for κ = ℵ1. In this note we extend this answer to all κ. We also extend the result of Jin and Shelah to all κ. (Jin also observed this could be done.)

In order to strike a balance between the generalities of model theory and the specifics of nonstandard analysis, we will consider models of Zermelo set theory with the Axiom of Choice; we denote this theory by ZC. The axioms of ZC are just those of ZFC but without the replacement scheme. Thus, among the axioms of ZC are the power set axiom, the infinity axiom, the separation axioms and the axiom of choice.

Let(V, E) ⊨ ZC. If a ∈ V, we let *a = {x ∈ V: (V,E) ⊨ x ∈ a}. In particular, i ∈ *ω iff i ∈ V and (V,E) ⊨ (i is a natural number). A subset A ⊆ V is internal if A = *a for some a ∈ V.

The standard model of ZC consists of those sets of rank at most ω + ω. In other words, if we let V0 be the set of hereditarily finite sets and for n < ω, then (Vω, ∈) is the standard model of ZC, where Vω = ⋃n<ω. Vn.

The notion of logical reducibilities is derived from the idea of interpretations between theories. It was used by Lovász and Gács [LG77] and Immerman [Imm87] to give complete problems for certain complexity classes and hence establish new connections between logical definability and computational complexity.

However, the notion is also interesting in a purely logical context. For example, it is helpful to establish nonexpressibility results.

We say that a class of τ-structures is a >complete problem for a logic under L-reductions if it is definable in [τ] and if every class definable in can be ”translated” into by L-formulae (cf. §4).

We prove the following theorem:

1.1. Theorem. There are complete problemsfor partial fixed-point logic andfor inductive fixed-point logic under quantifier-free reductions.

The main step of the proof is to establish a new normal form for fixed-point formulae (which might be of some interest itself). To obtain this normal form we use theorems of Abiteboul and Vianu [AV91a] that show the equivalence between the fixed-point logics we consider and certain extensions of the database query language Datalog.

In [Dah87] Dahlhaus gave a complete problem for least fixed-point logic. Since least fixed-point logic equals inductive fixed-point logic by a well-known result of Gurevich and Shelah [GS86], this already proves one part of our theorem.

However, our class gives a natural description of the fixed-point process of an inductive fixed-point formula and hence sheds some light on completely different aspects of the logic than Dahlhaus's construction, which is strongly based on the features of least fixed-point formulae.

A key idea in both Frege's development of arithmetic in the Grundlagen [7] and Zermelo's 1904 proof [10] of the well-ordering theorem is that of a “type reducing” correspondence between second-level and first-level entities. In Frege's construction, the correspondence obtains between concept and number, in Zermelo's (through the axiom of choice), between set and member. In this paper, a formulation is given and a detailed investigation undertaken of a system ℱ of many-sorted first-order logic (first outlined in the Appendix to [6]) in which this notion of type reducing correspondence is accorded a central role and which enables Frege's and Zermelo's constructions to be presented in such a way as to reveal their essential similarity. By adapting Bourbaki's version of Zermelo's proof of the well-ordering theorem, we show that, within ℱ, any correspondence c between second-level entities (here called concepts) and first-level ones (here called objects) induces a well-ordering relation W (c) in a canonical manner. We shall see that, when c is the “Fregean” correspondence between concepts and cardinal numbers, W (c) is (the well-ordering of) the ordinal ω + 1, and when c is a “Zermelian” choice function on concepts, W (c) is a well-ordering of the universal concept embracing all objects.

In ℱ an important role is played by the notion of extension of a concept. To each concept X we assume there is assigned an object e(X) in such a way that, for any concepts X, Y satisfying a certain predicate E, we have e (X) = e (Y) iff the same objects fall under X and Y.

A new method of “minimal” readability is proposed and applied to show that the definable functions of Heyting arithmetic (HA)—functions f such that HA ⊢ ∀x∃!yA(x, y) ⇒ for all m, A(m, f(m)) is true, where A(x, y) may be an arbitrary formula of ℒ(HA) with only x,y free—are precisely the provably recursive functions of the classical Peano arithmetic (PA), i.e., the < ε0-recursive functions. It is proved that, for prenex sentences provable in HA, Skolem functions may always be chosen to be < ε0-recursive. The method is extended to intuitionistic finite-type arithmetic, , and elementary analysis. Generalized forms of Kreisel's characterization of the provably recursive functions of PA and of the no-counterexample-interpretation for PA are consequently derived.

We define a complete theory SHFe of separably closed fields of finite invariant e (=degree of imperfection) which carry an infinite stack of Hasse-derivations. We show that SHFe has quantifier elimination and eliminates imaginaries.

A. M.Pitts in [Pi] proved that is a bi-Heyting category satisfying the Lawvere condition. We show that the embedding Φ: → Sh(P0, J0) into the topos of sheaves, (P0 is the category of finite rooted posets and open maps, J0 the canonical topology on P0) given by H ↦ HA(H, (−)) : P0 → Set preserves the structure mentioned above, finite coproducts, and subobject classifier; it is also conservative. This whole structure on can be derived from that of Sh(P0, J0) via the embedding Φ. We also show that the equivalence relations in are not effective in general. On the way to these results we establish a new kind of duality between and a category of sheaves equipped with certain structure defined in terms of Ehrenfeucht games. Our methods are model-theoretic and combinatorial as opposed to proof-theoretic as in [Pi].

Methods for carrying out transfinitely nested priority constructions have been developed by Harrington [7] and by Ash [2, 1, 3, 4]. Ash's method has different versions, with later ones becoming simpler. Lemmp and Lerman [11] have also developed a method, for finitely nested constructions. Ash formulated abstractly the object of a nested priority construction, and he proved a metatheorem for what he called “α-systems”, listing conditions which guarantee the success of the construction. Harrington's method of “workers”, at least in its original, informal state, seems more flexible than Ash's α-systems.

In [10, 9], there are finite and transfinite versions of a metatheorem for workers. The statements are complicated, and these metatheorems have not proved to be very useful. The present paper gives a new transfinite metatheorem. The statement is considerably simpler than the one in [9], although not so simple as that in [3]. The new metatheorem grew, in part, out of an effort to find a new proof of Ash's metatheorem. The new metatheorem yields the one in [3], and it seems more flexible. A different generalization of Ash's metatheorem will be given in [5].

Ash's metatheorem is easier to use than the one in the present paper, and the result in [3] is certainly the one to use wherever it applies. Here we give one application of the new metatheorem which does not seem to follow from the result in [3]. This is a theorem on models “representing” a given Scott set, which implies one half of a recent result of Solovay [18], on Turing degrees of models of particular completions of Peano arithmetic (PA).

By an equational theory we mean a set of equations from some fixed language which is closed with respect to logical consequences. We regard equations as universal sentences whose quantifier-free parts are equations between terms. In our notation, we suppress the universal quantifiers. Once a language has been fixed, the collection of all equational theories for that language is a lattice ordered by set inclusion The meet in this lattice is simply intersection; the join of a collection of equational theories is the equational theory axiomatized by the union of the collection. In this paper we prove, for languages with only finitely many fundamental operation symbols, that any nontrivial finitely axiomatizable equational theory covers some other finitely axiomatizable equational theory. In fact, our result is a little more general.

There is an extensive literature concerning lattices of equational theories. These lattices are always algebraic. Compact elements of these lattices are the finitely axiomatizable equational theories. We also call them finitely based. The largest element in the lattice is compact; it is the equational theory based on the single equation x ≈ y. The smallest element of the lattice is the trivial theory consisting of tautological equations. For all but the simplest languages, the lattice of equational theories is intricate. R. McKenzie in [6] was able to prove in essence that the underlying language can be recovered from the isomorphism type of this lattice.

This paper is concerned with a class K of models and an abstract notion of submodel ≤. Experience in first order model theory has shown the desirability of finding a ‘monster model’ to serve as a universal domain for K. In the original constructions of Jónsson and Fraïssé, K was a universal class and ordinary substructure played the role of ≤. Working with a cardinal λ satisfying λ<λ = λ guarantees appropriate downward Löwenheim-Skolem theorems; the existence and uniqueness of a homogeneous-universal model appears to depend centrally on the amalgamation property. We make this apparent dependence more precise in this paper.

The major innovation of this paper is the introduction of a weaker notion (chain homogeneous-universal) to replace the natural notion of (K, <)-homogeneous-universal model. Modulo a weak extension of ZFC (provable if V = L), we show (Corollary 5.24) that a class K obeying certain minimal restrictions satisfies a fundamental dichotomy. For arbitrarily large λ, either K has the maximal number of models in power λ or K has a unique chain homogeneous-universal model of power λ. We show (5.25) in a class with amalgamation this dichotomy holds for the notion of K-homogeneous-universal model in the more normal sense.

The methods here allow us to improve our earlier results [5] in two other ways: certain requirements on all chains of a given length are replaced by requiring winning strategies in certain games; the notion of a canonically prime model is avoided. A full understanding of these extensions requires consideration of the earlier papers but we summarize them quickly here.

The notion of CM-triviality was introduced by Hrushovski, who showed that his new strongly minimal sets have this property. Recently Baudisch has shown that his new ω1-categorical group has this property. Here we show that any group of finite Morley rank definable in a CM-trivial theory is nilpotent-by-finite, or equivalently no simple group of finite Morley rank can be definable in a CM-trivial theory.

If S, T are stationary subsets of a regular uncountable cardinal κ, we say that S reflects fully in T, S < T, if for almost all α ∈ T (except a nonstationary set) S ∩ α stationary in α. This relation is known to be a well-founded partial ordering. We say that a given poset P is realized by the reflection ordering if there is a maximal antichain 〈Xp: p ∈ P〉 of stationary subsets of Reg(κ) so that

We prove that if , and P is an arbitrary well-founded poset of cardinality ≤ κ+ then there is a generic extension where P is realized by the reflection ordering on κ.

By using the notion of a simplified (κ, 1)-morass, we construct κ-thin-tall, κ-thin-thick and, in a forcing extension, κ-very thin-thick superatomic Boolean algebras for every infinite regular cardinal κ.

We design functional algebras that characterize various complexity classes of global functions. For this purpose, classical schemata from recursion theory are tailored for capturing complexity. In particular we present a functional analog of first-order logic and describe algebras of the functions computable in nondeterministic logarithmic space, deterministic and nondeterministic polynomial time, and for the functions computable by AC1 -circuits.

We study how equivalent nonisomorphic models of unsuperstable theories can be. We measure the equivalence by Ehrenfeucht-Fraïssé games. This paper continues [HS].

We consider structural completeness in modal logics. The main result is the necessary and sufficient condition for modal logics over K4 to be hereditarily structurally complete: a modal logic λ is hereditarily structurally complete iff λ is not included in any logic from the list of twenty special tabular logics. Hence there are exactly twenty maximal structurally incomplete modal logics above K4 and they are all tabular.

On sait que par le choix d’ un langage suffisamment complexe, toute structure peut admettre une élimination des quantificateurs, malheureusement cette extension du langage peut nous éloigner des phénomènes algébriques. Nous allons nous intéresser à l’ élimination des quantificateurs pour des paires de corps. Dans le cas des paires de corps algébriquement clos et des paires denses de corps réel clos, on obtient une élimination en ajoutant au langage des prédicats ayant une signification algébrique: on peut les exprimer en disant que pour deux ensembles algébriques et donnés, il existe des points du sous-corps rationnels pour et pas pour , ou qu’ un ensemble semi-algébrique donné a des points rationnels sur le sous-corps. Robinson avait déjà abordé de façon informelle le cas des paires denses de corps réel-clos (cf. [Ro 2, p. 198]). Partant du langage des paires de corps ordonnés, enrichi de symboles de relations correspondant à l’ indépendance algébrique, il proposait d’ ajouter pas à pas des fonctions de Skolem Herbrand pour faire disparaitre les quantificateurs existentiels des formules, mais sans préciser le langage obtenu. Ici nous approchons le problème différemment en explicitant dès le départ le langage utilisé.

Grâce à ces résultats nous pourrons étudier le cas des paires séparées de corps réels clos ainsi que des paires de corps valués henseliens. En élargissant la définition d’ ensemble algébrique à tous les symboles du langage, les prédicats relationnels ajoutés ont la même signification que dans le cas des paires de corps algébriquement clos.

En comparant les techniques employées ici avec celles déjà utilisées dans [K], [B], [D 1] et [L], on remarque qu’il est possible de traîter une grande partie de l’ étude (complétude, modèle complétude, élimination des quantificateurs) des paires de corps algébriquement clos, réel-clos ou henseliens en se basant sur des prolongements d’ isomorphismes entre sous-structures dénombrables où l’ une des deux est contenue dans une structure ω1-saturée.