Regular groups and fields are common generalizations of minimal and quasi-minimal groups and fields, so the conjectures that minimal or quasi-minimal fields are algebraically closed have their common generalization to the conjecture that each regular field is algebraically closed. Standard arguments show that a generically stable regular field is algebraically closed. Let K be a regular field which is not generically stable and let p be its global generic type. We observe that if K has a finite extension L of degree n, then P(n) has unbounded orbit under the action of the multiplicative group of L.

Known to be true in the minimal context, it remains wide open whether regular, or even quasi-minimal, groups are abelian. We show that if it is not the case, then there is a counter-example with a unique nontrivial conjugacy class, and we notice that a classical group with one nontrivial conjugacy class is not quasi-minimal, because the centralizers of all elements are uncountable. Then, we construct a group of cardinality ω1 with only one nontrivial conjugacy class and such that the centralizers of all nontrivial elements are countable.

It follows constructively from weak versions of Markov's principle (MP) and of Church's thesis (WCT) that logical validity for single sentences is not arithmetically definable. This is a direct consequence of the constructive model-theoretic fact that, using MP and WCT, one can prove the categoricity of first-order Heyting arithmetic. By a straightforward refinement of this proof, we then obtain generalizations of the incompleteness theorem of Kreisel [K 2] as presented by van Dalen [Da] and improved by Leivant [L 1]. An analogous result for classical validity in r.e. models appears in [V].

Our methods of proof are new in that they rely not upon variants of the ideas of [K2] but upon a constructive proof idea inspired by the classical result of Tennenbaum ([Te], [E&K], [S]) on recursive models of arithmetic. This line of reasoning was suggested by the applications of readability to recursive mathematics described in [McC1], [McC2] and [McC3].

To eliminate quantifiers in the first-order theory of the p-adic field Qp, Ax and Kochen use a language containing a symbol for a cross-section map n → pn from the value group Z into Qp [1, pp. 48–49]. The primitive-recursive quantifier eliminations given by Cohen [2] and Weispfenning [10] also apply to a language mentioning the cross-section, but none of these authors seems entirely happy with his results. As Cohen says, “all the operations… introduced for our simple functions seem natural, with the possible exception of the map n → pn” [2, p. 146]. So all three authors show that various consequences of quantifier elimination—completeness, decidability, model-completeness—also hold for a theory of Qp not employing the cross-section [1, p. 453; 2, p. 146; 10, §4]. Macintyre directs a more specific complaint against the cross-section [5, p. 605]. Elementary formulae which use it can define infinite discrete subsets of Qp; yet infinite discrete subsets of R are not definable in the language of ordered fields, and so certain analogies between Qp and R suggested by previous model-theoretic work seem to break down.

To avoid this problem, Macintyre gives up the cross-section and eliminates quantifiers in a theory of Qp written just in the usual language of fields supplemented by a predicate V for Qp's valuation ring and by predicates Pn for the sets of nth powers in Qp (for all n ≥ 2).

Our results in this paper increase the model-theoretic precision of a widely used method for building ultrafilters, and so advance the general problem of constructing ultrafilters whose ultrapowers have a precise degree of saturation. We begin by showing that any flexible regular ultrafilter makes the product of an unbounded sequence of finite cardinals large, thus saturating any stable theory. We then prove directly that a “bottleneck” in the inductive construction of a regular ultrafilter on λ (i.e., a point after which all antichains of ${\cal P}\left( \lambda \right)/{\cal D}$ have cardinality less than λ) essentially prevents any subsequent ultrafilter from being flexible, thus from saturating any nonlow theory. The constructions are as follows. First, we construct a regular filter ${\cal D}$ on λ so that any ultrafilter extending ${\cal D}$ fails to ${\lambda ^ + }$-saturate ultrapowers of the random graph, thus of any unstable theory. The proof constructs the omitted random graph type directly. Second, assuming existence of a measurable cardinal κ, we construct a regular ultrafilter on $\lambda > \kappa$ which is λ-flexible but not ${\kappa ^{ + + }}$-good, improving our previous answer to a question raised in Dow (1985). Third, assuming a weakly compact cardinal κ, we construct an ultrafilter to show that ${\rm{lcf}}\left( {{\aleph _0}} \right)$ may be small while all symmetric cuts of cofinality κ are realized. Thus certain families of precuts may be realized while still failing to saturate any unstable theory.

We prove a variety of theorems about stationary set reflection and concepts related to internal approachability. We prove that an implication of Fuchino–Usuba relating stationary reflection to a version of Strong Chang’s Conjecture cannot be reversed; strengthen and simplify some results of Krueger about forcing axioms and approachability; and prove that some other related results of Krueger are sharp. We also adapt some ideas of Woodin to simplify and unify many arguments in the literature involving preservation of forcing axioms.

A major theme in arithmetic combinatorics is proving multiple recurrence results on semigroups (such as Szemerédi’s theorem) and this can often be done using methods of ergodic Ramsey theory. What usually lies at the heart of such proofs is that, for actions of semigroups, a certain kind of one recurrence (mixing along a filter) amplifies itself to multiple recurrence. This amplification is proved using a so-called van der Corput difference lemma for a suitable filter on the semigroup. Particular instances of this lemma (for concrete filters) have been proven before (by Furstenberg, Bergelson–McCutcheon, and others), with a somewhat different proof in each case. We define a notion of differentiation for subsets of semigroups and isolate the class of filters that respect this notion. The filters in this class (call them ∂-filters) include all those for which the van der Corput lemma was known, and our main result is a van der Corput lemma for ∂-filters, which thus generalizes all its previous instances. This is done via proving a Ramsey theorem for graphs on the semigroup with edges between the semigroup elements labeled by their ratios.

Measuring says that for every sequence ${\left( {{C_\delta }} \right)_{\delta < {\omega _1}}}$ with each ${C_\delta }$ being a closed subset of δ there is a club $C \subseteq {\omega _1}$ such that for every $\delta \in C$ , a tail of $C\mathop \cap \nolimits \delta$ is either contained in or disjoint from ${C_\delta }$ . We answer a question of Justin Moore by building a forcing extension satisfying measuring together with ${2^{{\aleph _0}}} > {\aleph _2}$ . The construction works over any model of ZFC + CH and can be described as a finite support forcing iteration with systems of countable structures as side conditions and with symmetry constraints imposed on its initial segments. One interesting feature of this iteration is that it adds dominating functions $f:{\omega _1} \to {\omega _1}$ mod. countable at each stage.

By the complexity of a finite sequence of 0’s and 1’s we mean the Kolmogorov complexity, that is the length of the shortest input to a universal recursive function which returns the given sequence as output. By initial segment complexity of an infinite sequence of 0’s and 1’s we mean the asymptotic behavior of the complexity of its finite initial segments. In this paper, we construct infinite sequences of 0’s and 1’s with given recursive lower bounds on initial segment complexity which do not compute any infinite sequences of 0’s and 1’s with a significantly larger recursive lower bound on initial segment complexity. This improves several known results about randomness extraction and separates many natural degrees in the lattice of Muchnik degrees.

We give a uniform construction of free pseudospaces of dimension n extending work in [1]. This yields examples of ω-stable theories which are n-ample, but not n + 1-ample. The prime models of these theories are buildings associated to certain right-angled Coxeter groups.

Let = {0,1, +,·,<} be the usual first-order language of arithmetic. We show that Peano arithmetic is the least first-order -theory containing IΔ0 + exp such that every complete extension T of it has a countable model K satisfying

(i) K has no proper elementary substructures, and

(ii) whenever L ≻ K is a countable elementary extension there is and such that .

Other model-theoretic conditions similar to (i) and (ii) are also discussed and shown to characterize Peano arithmetic.

It is shown that Con(ZF) implies Con(ZFC + there exists a Dowker filter on ω2). The problem is also considered on higher cardinals.

Preferential models is one of the important semantical structures in nonmonotonic logic. This paper aims to establish an isomorphism theorem for preferential models, which gives us a purely algebraic characterization of the equivalence of preferential models. To this end, we present the notions of local similarity and local simulation. Based on these notions, two operators Δ(•) and μ(•) over preferential models are introduced and explored respectively. Together with other two existent operators ρ(•) and ΠD(•), we introduce an operator ∂D(•). Then the isomorphism theorem is obtained in terms of ∂D(•), which asserts that for any two preferential models M1 and M2, they generate the same preferential inference if and only if ∂D(M1) and ∂D(M2) are isomorphic. Based on ∂D(•), we also get an alternative model-theoretical characterization of the well-known postulate Weaken Disjunctive Rationality. Moreover, in the finite language framework, we show that Δ(μ(•)) is competent for the task of eliminating redundancy, and provide a representation result for k-relations.

We study the weak truth-table and truth-table degrees of the images of subsets of computable structures under isomorphisms between computable structures. In particular, we show that there is a low c.e. set that is not weak truth-table reducible to any initial segment of any scattered computable linear ordering. Countable subsets of 2ω and Kolmogorov complexity play a major role in the proof.

In his famous paper [1] on the elementary theory of finite fields Ax considered fields K with the property that every absolutely irreducible variety defined over K has K-rational points. These fields have been called pseudo algebraically closed (pac) and also regularly closed, and extensively studied by Jarden, Éršov, Fried, Wheeler and others, culminating with the basic works [8] and [11].

The above algebraic-geometric definition of pac fields can be put into the following equivalent model-theoretic version: K is existentially complete (ec) relative to the first order language of fields into each regular field extension of K. It has been this characterization of pac fields which the author extended in [2] to ordered fields. An ordered field (K, <) is called in [2] pseudo real closed (prc) if (K, <) is ec in every ordered field extension (L, <) with L regular over K. The concept of pre ordered field has also been introduced by McKenna in his thesis [15] by analogy with the original algebraic-geometric definition of pac fields.

Given a positive integer e, a system K = (K; P1, …, Pe), where K is a field and P1, …, Pe are orders of K (identified with the corresponding positive cones), is called an e-fold ordered field (e-field). In his thesis [9] van den Dries developed a model theory for e-fields. The main result proved in [9, Chapter II] states that the theory e-OF of e-fields is model con. panionable, and the models of the model companion e-OF are explicitly described.

Let M be a given model with similarity type L = L(M), and let L′ be any fragment of L∣L(M∣+,ω of cardinality ∣L(M)∣. We call N ≺ ML′-relatively saturated iff for every B ⊆ N of cardinality less than ∥N∥ every L′-type over B which is realized in M is realized in N. We discuss the existence of such submodels.

The following are corollaries of the existence theorems.

(1) If M is of cardinality at least ℶω1, and fails to have the ω order property, then there exists N ≺ M which is relatively saturated in M of cardinality ℶω1.

(2) Assume GCH. Let ψ ∈ Lω1, ω, and let L′ ⊆ Lω1, ω be a countable fragment containing ψ. If ∃χ > ℵ0 such that I(χ, ψ) < 2χ, then for every M ⊨ ψ and every cardinal λ < ∥M∥ of uncountable cofinality, M has an L′-relatively saturated submodel of cardinality λ.

F. Richman raised the question of whether the following principle of second order arithmetic is valid in intuitionistic higher order arithmetic HAH:

and if not, whether assuming Church's Thesis CT and Markov's Principle MP would help. Blass and Scedrov gave models of HAH in which this principle, which we call RP, is not valid, but their models do not satisfy either CT or MP.

In this paper a realizability topos Lif is constructed in which CT and MP hold, but RP is false. (It is shown, however, that RP is derivable in HAH + CT + MP + ECT0, so RP holds in the effective topos.) Lif is a generalization of a realizability notion invented by V. Lifschitz. Furthermore, Lif is a subtopos of the effective topos.

Two rings are elementarily equivalent if and only if they satisfy the same sentences in the language of rings. To some extent this is reflected in the representation theories of the two rings (one may see both positive and negative results along these lines in [5]). Here we concentrate on the case of a ring S and an elementary subring R of S.

We show that if R is an elementary subring of S then the lattice of pp formulas for R-modules embeds in that for S-modules. These lattices, moreover, have the same finite sub-posets. From this we derive some corollaries. Then we consider to what extent the compositions of induction and restriction between R- and S-modules preserve elementary equivalence.

We prove that if every uncountable model of a first-order theory T is ω-saturated and T is superstable then T is categorical in some infinite power.