Let and be two countable relational models of the same first order language. If the models are nonisomorphic, there is a unique countable ordinal α with the property that

i.e. and are L∞ω-equivalent up to quantifier-rank α but not up to α + 1. In this paper we consider models and of cardinality ω1 and construct trees which have a similar relation to and as a above. For this purpose we introduce a new ordering T ≪ T′ of trees, which may have some independent interest of its own. It turns out that the above ordinal α has two qualities which coincide in countable models but will differ in uncountable models. Respectively, two kinds of trees emerge from α. We call them Scott trees and Karp trees, respectively. The definition and existence of these trees is based on an examination of the Ehrenfeucht game of length ω1 between and . We construct two models of power ω1 with mutually noncomparable Scott trees.

In this work we give a complete answer as to the possible implications between some natural properties of Lebesgue measure and the Baire property. For this we prove general preservation theorems for forcing notions. Thus we answer a decade-old problem of J. Baumgartner and answer the last three open questions of the Kunen-Miller chart about measure and category. Explicitly, in §1: (i) We prove that if we add a Laver real, then the old reals have outer measure one. (ii) We prove a preservation theorem for countable-support forcing notions, and using this theorem we prove (iii) If we add ω2 Laver reals, then the old reals have outer measure one. From this we obtain (iv) Cons(ZF) ⇒ Cons(ZFC + ¬ B(m) + ¬ U(m) + U(c)). In §2: (i) We prove a preservation theorem, for the finite support forcing notion, of the property “F ⊆ ωω is an unbounded family.” (ii) We introduce a new forcing notion making the old reals a meager set but the old members of ωω remain an unbounded family. Using this we prove (iii) Cons(ZF) ⇒ Cons(ZFC + U(m) + ¬ B(c) + ¬ U(c) + C(c)). In §3: (i) We prove a preservation theorem, for the finite support forcing notion, of a property which implies “the union of the old measure zero sets is not a measure zero set,” and using this theorem we prove (ii) Cons(ZF) ⇒ Cons(ZFC + ¬U(m) + C(m) + ¬ C(c)).

Weakly minimal sets were first invented by Shelah [S] to solve Łoś' conjecture for uncountable theories. The first major result about them, which is that any nonalgebraic strong type either is of Morley rank 1 or has locally modular geometry, was proved by Buechler [B1]. Recently, Hrushovski [Hr] showed that a locally modular weakly minimal set interprets an abelian group, a result which revolutionized the study of these sets. Also Hrushovski showed that the geometry on the connected component of a weakly minimal locally modular group is that of a vector space over a division ring. This is also implicit in the result of Pillay and Hrushovski (Theorem 1.3 from [HP]) quoted below. In a sense, this completes their study, as any vector space over any division ring is in fact strongly minimal if there is no other structure. But the question remains as to what other structure such a group could have. This is the issue we address here.

Some work has been done on this question; in fact, Pillay ([Pi], generalized in [HP]) has demonstrated, in the more general context of a weakly normal group A, that any definable subset of An is in fact a Boolean combination of almost 0-definable cosets of almost 0-definable subgroups. In the weakly minimal case this can be sharpened a fair bit. The case of a weakly minimal group of bounded exponent is dealt with in [HL]. Here we consider the case where the group has unbounded exponent.

One of the simplest and yet most fruitful ideas in forcing was the notion of Karel Prikry in which he used a measure on a cardinal κ to change the cofinality of κ to ω without collapsing it. The idea has found connections to almost every branch of modern set theory, from large cardinals to small, from combinatorics to models, from Choice to Determinacy, and from consistency to inconsistency. The long list of generalizers and modifiers includes Apter, Gitik, Henle, Spector, Shelah, Mathias, Magidor, Radin, Blass and Kimchi.

This paper is about generalizing Prikry forcing and partition properties to “simple spaces”. The concept of a simple space is itself the generalization of those combinatorial objects upon which the notions of “measurable”, “compact”, “supercompact”, “huge”, etc. are based. Simple spaces were introduced in [ADHZ1] and [ADHZ2] together with a broader generalization, “filter spaces”. The definition provided here is a small simplification of earlier versions. The author is indebted to Mitchell Spector, whose careful reading turned up numerous errors, some subtle, some flagrant.

In this first section, we review simple spaces briefly, including a short introduction to the space Qκλ. In §2, we describe our generalizations of partition property and Prikry forcing, and discuss the relationship between them. In §3, we find a partition property for the huge space [λ]κ, but show that Prikry forcing here is impossible. We find partition properties for Qκλ and show that Prikry forcing can be done here.

Given a finite lexicon L of relational symbols and equality, one may view the collection of all L-structures on the set of natural numbers ω as a space in several different ways. We consider it as: (i) the space of outcomes of certain infinite two-person games; (ii) a compact metric space; and (iii) a probability measure space. For each of these viewpoints, we can give a notion of relative ubiquity, or largeness, for invariant sets of structures on ω. For example, in every sense of relative ubiquity considered here, the set of dense linear orderings on ω is ubiquitous in the set of linear orderings on ω.

A notion of reducibility ≤r between sets is specified by giving a set of procedures for computing one set from another. We say that a set A is r-reducible to a set B, A ≤rB, if one of the procedures applied to B gives A. Associated with any such reducibility notion is the structure of r-degrees, the equivalence classes of sets with respect to this reducibility, with the induced ordering. The most general notion of a computable reducibility is that of Turing, ≤T. Here we say that A ≤TB if there is a Turing machine φe which, when equipped with an oracle for B, computes A: φeB = A. Such Turing degree computations are characterized by the phenomenon that only during the computation itself do we discover which questions about B need to be answered to compute A(x). In contrast, for nearly all other computable reducibilities the set of questions needed is given in advance by a recursive procedure. Perhaps the most common example of such a procedure is many-one reducibility, ≤m: A ≤mB if there is a recursive function f such that x ∈ A ⇔ f(x) ∈ B.

Reducibilities with the property that the output, A(x), is determined by the answers that B gives to a set of questions calculated recursively from x are said to be of tabular type. The most general tabular reducibility is called truth-table reducibility, ≤tt. The procedures [e] associated with this reducibility are specified by a recursive function f (= {e}) which, for each x, gives a set of n questions about the oracle and, for each of the possible 2n sets of answers, gives the corresponding output. As usual this defines A ≤ttB as “there is an e such that [e]B = A”. It is with this notion of reducibility and the associated tt-degrees that we shall be concerned in this paper. Basic information on several such strong reducibilities can be found in Rogers [28]. For more information we recommend the survey articles by Odifreddi [25] and Degtev [2] as well as Odifreddi's book [26].

We say φ is an ∀∃ sentence if and only if φ is logically equivalent to a sentence of the form ∀x∃yψ(x, y), where ψ(x, y) is a quantifier-free formula containing no variables except x and y. In this paper we show that there are algorithms to decide whether or not a given ∀∃ sentence is true in (1) an algebraic number field K, (2) a purely transcendental extension of an algebraic number field K, (3) every field with characteristic 0, (4) every algebraic number field, (5) every cyclic (abelian, radical) extension field over Q, and (6) every field.

In [3], Todorčević showed that ω1 ⇸ [ω1]ω12. In this paper we use similar methods to prove an analogous partition theorem for Pω1(λ), for certain uncountable cardinals λ.

Recall that ω1 → [ω1]ω12, means that for every function f: [ω1]2 → ω1 there is a set A ∈ [ω1]ω1 such that f“[A]2 ≠ ω1, and of course ω1 ⇸ [ω1]ω12, is the negation of this statement. For partition relations on Pω1(→) it is customary to partition only those pairs of sets in which the first set is a subset of the second. Thus for A ⊆ Pω1(λ) we define

We will write Pω1(λ) → [unbdd]λ2 to mean that for every function f: [Pω1(λ)]⊂2 → λ there is an unbounded set A ⊆ Pω1(λ) such that f“[A]⊂2 ≠ λ, and again Pω1(λ) ⇸ [unbdd]λ2 is the negation of this statement.

In this paper we ask the question: to what extent do basic set theoretic properties of Loeb measure depend on the nonstandard universe and on properties of the model of set theory in which it lies? We show that, assuming Martin's axiom and κ-saturation, the smallest cover by Loeb measure zero sets must have cardinality less than κ. In contrast to this we show that the additivity of Loeb measure cannot be greater than ω1. Define cof(H) as the smallest cardinality of a family of Loeb measure zero sets which cover every other Loeb measure zero set. We show that card(⌊log2(H)⌋) ≤ cof (H) ≤ card(2H), where card is the external cardinality. We answer a question of Paris and Mills concerning cuts in nonstandard models of number theory. We also present a pair of nonstandard universes M ≼ N and hyperfinite integer H ∈ M such that H is not enlarged by N, 2H contains new elements, but every new subset of H has Loeb measure zero. We show that it is consistent that there exists a Sierpiński set in the reals but no Loeb-Sierpiński set in any nonstandard universe. We also show that it is consistent with the failure of the continuum hypothesis that Loeb-Sierpiński sets can exist in some nonstandard universes and even in an ultrapower of a standard universe.

In this paper we investigate omitting types for a certain kind of stable theories which we call stable ccc theories. In Theorem 2.1 we improve Steinhorn's result from [St]. We prove also some independence results concerning omitting types. The main results presented in this paper were part of the author's Ph.D. thesis [N1].

Throughout, we use the standard set-theoretic and model-theoretic notation, such as can be found for example in [Sh] or [M]. So in particular T is always a countable complete theory in the language L. We consider all models of T and all sets of parameters subsets of the monster model ℭ, which is very saturated. Ln(A) denotes the Lindenbaum-Tarski algebra of formulas with parameters from A and n free variables. We omit n in Ln(A) when n = 1 or when it is clear from the context what n is. If φ, ψ ∈ L(A) are consistent then we say that φ is below ψ if ψ⊢ψ. For a type p and a set A ⊆ ℭ, p(A) is the set of tuples of elements of A which satisfy p. Formulas are special cases of types. We say that a type p is isolated over A if, for some φ() ∈ L(A), φ() ⊢ p(x), i.e. φ isolates p. For a formula φ, [φ] denotes the class of types which contain φ. We assume that the reader is familiar with some basic knowledge of forking, as presented in [Sh, III] or [M].

Throughout, we work in ZFC. and denote (countable) transitive models of ZFC. cov K is the minimal number of meager sets covering the real line R. In this paper we prove theorems showing connections between omitting types and the combinatorics of the real line. More results in this direction are presented in [N2] and [N3].

The lattice of r.e. equivalence relations has not been carefully examined even though r.e. equivalence relations have proved useful in logic. A maximal r.e. equivalence relation has the expected lattice theoretic definition. It is proved that, in every pair of r.e. nonrecursive Turing degrees, there exist maximal r.e. equivalence relations which intersect trivially. This is, so far, unique among r.e. submodel lattices.

PA is Peano arithmetic. The formula InterpPA(α, β) is a formalization of the assertion that the theory PA + α interprets the theory PA + β (the variables α and β are intended to range over codes of sentences of PA). We extend Solovay's modal analysis of the formalized provability predicate of PA, PrPA(x), to the case of the formalized interpretability relation InterpPA(x, y). The relevant modal logic, in addition to the usual provability operator ‘□’, has a binary operator ‘⊳’ to be interpreted as the formalized interpretability relation. We give an axiomatization and a decision procedure for the class of those modal formulas that express valid interpretability principles (for every assignment of the atomic modal formulas to sentences of PA). Our results continue to hold if we replace the base theory PA with Zermelo-Fraenkel set theory, but not with Gödel-Bernays set theory. This sensitivity to the base theory shows that the language is quite expressive. Our proof uses in an essential way earlier work done by A. Visser, D. de Jongh, and F. Veltman on this problem.

The paper proves a predicate version of Solovay's well-known theorem on provability interpretations of modal logic:

If a closed modal predicate-logical formula R is not valid in some finite Kripke model, then there exists an arithmetical interpretation f such that PA ⊬ fR.

This result implies the arithmetical completeness of arithmetically correct modal predicate logics with the finite model property (including the one-variable fragments of QGL and QS). The proof was obtained by adding “the predicate part” as a specific addition to the standard Solovay construction.

For each ordinal α > 0, L(α) is the intermediate predicate logic characterized by the class of all Kripke frames with the poset α and with constant domain. This paper will be devoted to a study of logics of the form L(α). It will be shown that for each uncountable ordinal of the form α + η with a finite or a countable η(> 0), there exists a countable ordinal of the form β + η such that L(α + η) = L(β + η). On the other hand, such a reduction of ordinals to countable ones is impossible for a logic L(α) if α is an uncountable regular ordinal. Moreover, it will be proved that the mapping L is injective if it is restricted to ordinals less than ωω, i.e. α ≠ β implies L(α) ≠ L(β) for each ordinal α, β ≤ ωω.

In [10] we introduced a new first order language for valued fields. This language has three sorts of variables, namely variables for elements of the valued field, variables for elements of the residue field and variables for elements of the value group. contains symbols for the standard field, residue field, and value group operations and a function symbol for the valuation. Essential in our language is a function symbol for an angular component map modulo P, which is a map from the field to the residue field (see Definition 1.2).

For this language we proved a quantifier elimination theorem for Henselian valued fields of equicharacteristic zero which possess such an angular component map modulo P [10, Theorem 4.1]. In the first section of this paper we give some partial results on the existence of an angular component map modulo P on an arbitrary valued field.

By applying the above quantifier elimination theorem to ultraproducts ΠQp/D, we obtained a quantifier elimination, in the language , for the p-adic field Qp; and this elimination is uniform for almost all primes p [10, Corollary 4.3]. In §2 we prove that our language is essentially stronger than the natural language for p-adic fields in the sense that the angular component map modulo P cannot be defined, uniformly for almost all p, in terms of the natural language for p-adic fields.

Let L be a countable language which contains only constant and relation symbols but no function symbols. All theories considered here will be L-theories. A theory is coinductive if it can be axiomatized by a set of ∃∀ sentences, and a structure is coinductive if its theory is.

The object of this paper is to show that coinductive ℵ0-categorical structures are especially simple. First, they are ω-stable with Morley rank ≤ 1; and second, they have simple algebraic closures, by which is meant that the algebraic closure of the union of two sets is the union of their algebraic closures. While these two properties do not characterize coinductive ℵ0-categorical structures, they do characterize those structures which are cellular.

We will say that a countable structure is cellular if there is a finite subset A0 ⊆ A and there are equivalence relations E and F on A∖A0 such that the following hold:

(1) There are only finitely many E-classes.

(2) If C is an E-class and D an F-class, then ∣C ∩ D ∣ = 1.

(3) If a0, a1, …, ak − 1, b0, b1, …, bk − 1 Є A, then 〈a0, a1, …,ak − 1〉 and 〈b0,b1, …, bk − 1〉, satisfy the same quantifier-free formulas provided that:

(a) if i < k and either ai Є A0 or bi Є A0, then ai = bi;

(b) if i < k, then ai; and bi are E-equivalent; and

(c) if i, j < k, then ai; is F-equivalent to aj if bj is F-equivalent to bj.

The main result of this paper is the following theorem.

Theorem 1. Ifis coinductive and ℵ0-categorical, thenis cellular.

The results of this paper were obtained independently of similar results obtained by Lachlan which can be found in [4] and [5]. The proofs here are quite different.

We point out that a group first order definable in a differentially closed field K of characteristic 0 can be definably equipped with the structure of a differentially algebraic group over K. This is a translation into the framework of differentially closed fields of what is known for groups definable in algebraically closed fields (Weil's theorem).

I restrict myself here to showing (Theorem 20) how one can find a large “differentially algebraic group chunk” inside a group defined in a differentially closed field. The rest of the translation (Theorem 21) follows routinely, as in [B].

What is, perhaps, of interest is that the proof proceeds at a completely general (soft) model theoretic level, once Facts 1–4 below are known.

Fact 1. The theory of differentially closed fields of characteristic 0 is complete and has quantifier elimination in the language of differential fields (+, ·,0,1, −1,d).

Fact 2. Affine n-space over a differentially closed field is a Noetherian space when equipped with the differential Zariski topology.

Fact 3. If K is a differentially closed field, k ⊆ K a differential field, and a and are in k, then a is in the definable closure of k ◡ iff a ∈ ‹› (where k ‹› denotes the differential field generated by k and).

Fact 4. The theory of differentially closed fields of characteristic zero is totally transcendental (in particular, stable).

We present a faithful axiomatization of von Mises' notion of a random sequence, using an abstract independence relation. A byproduct is a quantifier elimination theorem for Friedman's “almost all” quantifier in terms of this independence relation.

Recursive model theory is supposed to be the study of the effectiveness of constructions and theorems in model theory. This often involves getting “effective” versions of various classical model-theoretic notions. The traditional way of doing this is to restrict attention to recursive models, and recursive isomorphisms between them, etc. Thus for example the following definition appears in the literature (in [3] and [1]).

Definition. Given a recursive model A and an n Є ω, a subset R ⊆ An is called intrinsically r.e. provided that for every recursive model B ≈ A, the isomorphic image in B of R is an r.e. subset of Bn.

It is clear that if R is definable by a (recursive, infinitary) Σ10 formula (with finitely many parameters from A), then R is intrinsically r.e. It seems natural for the converse to be true. Indeed, provided that (A, R) is sufficiently “regular” in a sense made precise in a theorem of Ash and Nerode (see [3]), the converse is true. However, if we drop the (rather strong) regularity conditions, there exist “pathological” examples of intrinsically r.e. relations which are not definable by a Σ10 formula (see [7]).

In this paper, we suggest a rather different approach to studying the effectiveness of model theory, an approach we have dubbed “effective model theory”. The basic idea is to allow arbitrary nonrecursive models, but to require all notions to be relativized to the complexity of the models involved. (Much the same notion has been used in [2] under the name “relatively recursive model theory”.) Thus for example we have the following effective model theory version of the property of being intrinsically r.e.

La première partie de cet article ([10], que nous désignerons par (I) dans la suite) était consacrée à la théorie élémentaire TX des algèbres de Boole munies d'idéaux distingués indéxés dans un ensemble X. On a vu que les idéaux définissables dans un modèle de Tx forment la sous-algèbre engendrée par les idéaux distingués de l'algèbre de Heyting des idéaux de munie de l'opérateur sa défini par sa(K) = {a: a/K est sans atome}, et que la théorie de peut être caractérisée par la structure composée de l'algèbre de Heyting des idéaux définissables munie de l'opérateur sa et des idéaux distingués, et par l'application qui à tout K de fait correspondre le nombre d'atomes de /K, pris dans N ⋃ {∞}.

Nous montrons maintenant que les structures possibles peuvent être définies de façon axiomatique en introduisant une classe équationnelle d'algèbres de Heyting munies d'une opération unaire, dites sa-algèbres de Heyting (en abrégé sa-AH), et en prouvant que cette classe est constituée des algèbres pouvant être plongées dans l'algèbre de Heyting des idéaux d'une algèbre de Boole, munie de l'opérateur sa. Ainsi les sont, à isomorphisme près, les sa-AH engendrées par des éléments distingués indéxés dans X; on en déduit une classification des extensions complètes de Tx en montrant que les applications qui peuvent être associées à une structure de la forme pour caractériser la théorie d'un modèle sont déterminées par leur restriction à une partie M() définie uniformément, sur laquelle elles prennent des valeurs dans (N − {0}) ⋃ {∞}, et que réciproquement toute application de M() dans (N − {0}) ⋃ {∞} est une telle restriction.