Expansions of Geometries

John T. Baldwin ^{∗}

Department of Mathematics, Statistics and Computer Science University of Illinois at Chicago

January 8, 2003

Abstract

For n < ω, expand the structure (n, S, I, F) (with S the successor relation, I, F as the initial and final element) by forming graphs with edge probability n^{−α} for irrational α, with 0 < α < 1. The sentences in the expanded language, which have limit probability 1, form a complete and stable theory.

Spencer and Shelah [17] established the 0-1 law for random graphs with edge probability n^{−α} (irrational α). In [5], Baldwin and Shelah connected the study of such limit laws with the model theoretic construction of generic structures (cf. [7]) and showed that the limit theory was stable and nearly model complete. We extend this analysis from graphs on a pure set to graphs on certain nontrivial structures. That is, we fix a pair of languages L′ ⊂ L and consider L-structures as expansions of L′-structures (random or otherwise). Our setting captures features of the Hrushovski generalization of Fraissé’s theory of amalgamation classes, as well as the Spencer-Shelah theory of random graphs. Considerable work (see the survey [3]) concerns expansions with respect to a weight function, δ which is a linear combination δ_{1} + αδ_{2} of simpler known weights. This is the first work for irrational α and a nontrivial structure in the base language. Our work concerns two distinct model theoretic situations. Speaking concretely we are expanding either case 1) successor or case 2) a vector space over a finite field. More generally, the two cases can be seen as non-locally-finite discrete geometry and as uniformly locally finite modular geometry. In Section 1 we prove Theorem A: In either case 1) successor or 2) a vector space over a finite field, there is an expansion to a strictly stable, complete, nearly model complete theory. In Section 2 we use the axiomatization found in Section 1 to prove Theorem B: The 0-1 law holds for random expansions of successor with edge probability n^{−α} (irrational α). Our treatment also provides a new proof of the probabilistic part of the Shelah-Spencer theorem.

The history of Theorem B begins with Lynch [12] asking whether the 0-1 law held when expanding structures with fixed basic relations (e.g. a finite segment with successor) by randomly adding an edge relation (with probability n^{−α}). He had earlier [11] studied this problem for uniform probability, where the 0-1 law fails, with the clearest results concerning expansion of successor. The still unpublished articles [15, 16] include the 0-1 law for successor but do not show the stability of the limit theories. Shelah [15] approaches this problem from the standpoint of iteratively adding random relations and deals with successor by considering ‘non-trivial algebraic’ closure in the basic structure. The proof and the viewpoint of the argument are different here. The Shelah-Spencer theorem has been applied to various definability problems in finite model theory (e.g [14]); potentially, there are similar applications of this result to definability in expansions of successor.

∗Partially supported by NSF grant 9308768 through DMS-0100594.

We now sketch the general framework of the paper. We begin with a class K′_{0} of finite L′-structures and a class K_{0} of finite L-structures. These classes can be regarded as amalgamation classes. For each n, the structures in K_{0} of cardinality at most n can also be regarded as the substructures of members of the probability space we are investigating. We also introduce a real-valued function δ on K_{0} which behaves somewhat like a rank in stability theory (and is ultimately responsible for the stability of our theories). The relative weight δ(B/A) is defined as δ(BA)−δ(A). The weight function δ depends on numerical weights assigned to the relations in L-L′, and these weights are chosen so that, together with 1, they are linearly independent over the rationals; thus δ(B/A) = 0 cannot arise by ‘cancellation’ between L and L′. For simplicity we refer to the set of numerical weights as α. All essential difficulties are met in the case where L-L′ is a single binary relation and α is a single real.

Roughly speaking, if δ(B/A) < 0, B is ‘intrinsic’ to A; it must be contained in the algebraic closure of A. In our earlier treatment of 0-1 laws ([5, 2] we introduced the notation ≤_{i} (intrinsic in) for the notion of algebraicity derived from δ(B/A) < 0 and ≤_{s} (strong in) for the opposite notion (one might say: free over). Here, we must deal with extensions of dimension 0 and we consider them to be intrinsic since the underlying structure on L′ forces algebraicity of them. From the notion of intrinsic extension we derive the intrinsic closure (icl_{M} and its approximations icl_{M}^{k}) of a set.

We call a theory determined (Definition 1.1.23) if the truth of a formula ϕ(x, b) in a structure is determined by a finite structure generated by b in a way which depends uniformly on ϕ (via the operator icl_{M}^{ℓ_{ϕ}}). Proving that a theory is determined yields a form of quantifier elimination which we call near model completeness. With control over certain finite structures one further deduces completeness and thus the 0-1 law. This is a result of the type given in [17] for graphs (with a proof which omits some essential points) and in full detail in [5]. The specific way in which near model completeness is attained here allows us (following ideas of Hrushovski and Hytinnen) to also conclude stability.

The argument for the 0-1-law requires two steps. The first is carried out in Sections 1.1, 1.3 and 1.4; the second in Section 2.

Proof Outline

1. Define the notion of a semigeneric structure. Show the theory of semigeneric structures is determined and deduce completeness relative to the structure of icl(∅). Moreover, show each formula is equivalent to a Boolean combination of existential formulas of a specific kind and deduce stability.

2. Prove that the axioms for the theory of semigeneric structures hold with asymptotic probability 1. Show that axioms determining icl(∅) are almost surely true. Deduce using 1) that the almost sure theory is complete and stable.

We conclude this introduction with a remark about expansions of successor that motivates our specific choice of vocabulary. While a common notion of ‘model theoretic limit’ of the finite structures (n, S) is the theory of (Z, S), the situation is different for assigning probabilities to expansions. Suppose we add relations randomly to the canonical model ({1, …, n}; S) and let n go to infinity. Since for each n the structure (n, S) has an initial and final element, the reduct to successor of any ‘almost sure’ theory of an expansion will be the theory of ω + ω^{∗}. However, the sentence asserting that the first and last elements are n-apart will be false in the limit although true (for appropriate n) in each finite model. The probability of there being an R-edge between the first element and any fixed k′th successor is n^{−α} which tends to 0. We keep track of this inevitable special character of the first and last segment in a convenient manner by adding constant symbols for the initial and final elements. (Shelah [16] addresses this problem in a different way, replacing (n, S) by a ‘circular order’.)

The author is grateful for some very careful referees who pointed out many difficulties, suggested some areas for simplification, and greatly improved the exposition. We also acknowledge fruitful conversations with Joel Berman, Michael Benedikt, Gregory Cherlin, James Lynch, Marco Mazzucco,Dave Marker, Wai Yan Pong, Dale Radin, Eric Rosen, Joel Spencer, and especially Alan Woods during the lengthy time this article has been in preparation.

1 Semigeneric Structures and Determined Theories

In studying the relation between Hrushovski’s modified Fraissé constructions and the Shelah-Spencer probabilistic theory ([5]) we found it useful to consider the notion of a semigeneric structure with respect to a class of finite structures on which a real-valued ‘weight function’ is defined. We originally thought of these structures as less homogeneous approximations to the generic structures which are central to the construction of the new ℵ_{1}-categorical theories. While this intuition is correct, they can perhaps more profitably be viewed as existentially closed structures in a suitably expanded language. From that viewpoint, the goal of Section 1 is to prove a certain universally existentially axiomatizable class of models (in an expanded language) has a model companion.

Remarkably, the same weight function may arise either as a notion of ‘rank’ in the sense of stability theory, or as a critical parameter in the computation of the expected number of configurations of fixed type in the probabilistic theory. In Subsection 1.1 we describe the basic framework and introduce our weight functions. As we deal here with two languages L′ ⊂ L, we will have two classes of finite structures, one for each language. In [17], the language L′ was scarcely mentioned, as it consisted of the equality relation alone, and largely went unnoticed. In particular, in that context the L′-dimension of a structure was its cardinality, a parameter which indeed plays a major role in [5], [17], but does not generally attract a great deal of attention. Here our weight function depends on the L′-dimension and the number of realizations of the new relations in L-L′. For suitable weight functions, we derive notions of relative algebraicity and its opposite, the strong substructure relation, denoted ≤_{i} and ≤_{s} respectively. We list two weight axioms which summarize the essential properties of these weights. We then convert the weight axioms into fundamental properties of ≤_{i} and ≤_{s}, on which most of the subsequent arguments depend. In Subsections 1.2 and 1.3 we introduce slightly different notions of semigeneric for the vector space and successor case. In each case we find an axiomatization of the semigenerics and show their theory is determined. Although, it is possible to give a notion of semigeneric which encompasses both cases [4], we think a presentation which uses two different definitions to reflect the different cases is less confusing. We show completeness and stability of these determined theories in Subsection 1.4.

1.1 Weight, Strong and Intrinsic Substructures

We work with a pair of finite relational languages, L′ ⊂ L. We are given a family of finite L′-structures K′_{0} (e.g. finite vector spaces); we want to study expansions of these structures. To define the class K_{0} of L structures that is the principal object of study, we pass through several auxiliaries (K̂_{0}, K′_{0} etc.) We will use K with various decorations to describe the general L′, L situation and replace with analogous S, V for the successor and vector space cases. Subsections 1.1 and 1.4 deal with the K; Subsection 1.2 restricts to the V while Subsection 1.3 and Section 2 are concerned with S.

First we lay out the important properties of the L′-structures. For successor, the role of K′_{0} is played by S′_{0}.

Example 1.1.1 (Successor Case: S′_{0}). The language L′ is the language of a successor relation S with constant symbols I, F for initial and final element. S′_{0} is the class of (isomorphism types of) finite substructures of ω + ω^{∗} with the obvious interpretations of S, I, F. Thus the models in S′_{0} have an ‘initial’ segment beginning with I, a (possibly different) ‘terminal’ segment ending with F, and possibly other segments which are ‘open’ at both ends.

Here are a few basic notations.

1.1.2 Notation. A, B, C, … denote finite structures; M, N, … denote structures of arbitrary cardinality. We often write AB for A ∪ B. We write A ⊂_{ω} B to indicate that A is a finite subset of B. If δ is a function on structures, δ(A/B) denotes δ(AB)−δ(B). A map h is a homomorphism if for any relation R, R(a) implies R(ha). An embedding is a 1-1 homomorphism such that, in addition, R(ha) implies R(a).

As promised in the title, there is a geometry on the L′-structures.

1.1.3 (L′-geometry). There is a function δ′ on subsets of structures in K′_{0}, whose value value does not depend on the ambient structure, and which is a geometric dimension function. That is, δ′ maps into the natural numbers, δ′ is lower semimodular (δ′(XY) ≤ δ′(X) + δ′(Y) − δ′(X ∩ Y)), X ⊂ Y implies δ′(X) ≤ δ′(Y), and for each A ∈ K′_{0}, δ′(A) ≤ |A|.

In vector spaces we are just speaking of linear dimension; the successor case is slightly more complicated. Since theories constructed probabilistically have the finite model property and theories constructed in a ‘generic’ way often do not, to find theories that match from both perspectives one may expect to need additional constraints on the ‘generic’ models. As discussed at the end of the introduction, the enrichment of the language by symbols I and F is intended to force the models that we construct expanding successor to include a initial and final element, because that is what occurs spontaneously in our preferred probabilistic setting.

Example 1.1.4 (Successor Case: δ′).

The dimension of an L′-structure A, denoted δ′(A), is the number of connected components of A, minus 2. Normally, this is the number of connected components apart from the initial and terminal segments, but when the initial and terminal segments coincide it is one less than that; in particular when the model consists of a single segment, the weight is negative.

The requirement that δ′ be a geometric dimension function plays a subtle role in this section (see the argument for equation 1 in the proof of Theorem 1.3.12); we will use it for counting arguments in Section 2.

Notation 1.1.5 (L′-closure). For any L′-structure B and any finite A ⊆ B, we say x is in the geometric closure or L′-closure of A in B, and write x ∈ gcl_{B}(A), if x ∈ B and δ′(xA) = δ′(A).

Note that in the successor case the geometric closure of X in A is not uniformly locally finite; it extends X to include all of each segment in A which intersects X. Now we move from L′ to L.

1.1.6 Notation. We denote the set of L-expansions of structures in K′_{0} as K̂_{0}.

We will immediately restrict to a subclass K_{0} of K̂_{0} which is our main object of study, by a requirement (hereditarily nonnegative dimension) on the members of K̂_{0}. In the successor and vector space cases we will replace K by S and V to define classes S′_{0}, Ŝ_{0}, S_{0} and V′_{0}, V̂_{0}, V_{0}, respectively.

1.1.7 Definition. A relation symbol R is symmetric if its truth does not depend on the order of the arguments and strongly irreflexive if it holds only of sequences of distinct elements.

Notation 1.1.8 (Expansions and weights). Expand L′ to a language L as in Example 1.1.11, by adding symmetric and strongly irreflexive relations. The weight of an L-structure depends on auxiliary parameters α_{R}, one for each relation R in L-L′, and we require that the α_{R}, together with α_{0} = 1, be linearly independent over the rationals. If A is an L-structure, and δ′(A ↾ L′) < ω is the L′-dimension of its L′-reduct, its L-weight is

δ(A) = δ_{α}(A) = δ′(A ↾ L′) − ∑_{R∈L′−L} α_{R}|R| = δ′(A ↾ L′) − r

where |R| represents the number of unordered sets on which R holds, the subscript α on δ refers to the sequence of parameters α_{R}, and the last equality just reflects abbreviating ∑_{R∈L′−L} α_{R}|R| by r.

Now we define the central object of study. The restriction to this class is essential both to justify property S6 and to get the structure on icl(∅) required for the 0-1 law in Section 2.

1.1.9 Definition. Let K_{0} = {A ∈ K̂_{0} : for all B ⊂ A, δ(B) ≥ 0}.

Many of the definitions extend naturally from a class of finite models to the associated universal class.

1.1.10 Definition. Just dropping the subscript, let K be the class of L-structures (of arbitrary cardinality) whose finite substructures are in K_{0} and K̂ the class of L-structures whose finite substructures are in K̂_{0}. S, Ŝ, V, V̂ are defined analogously.

In our major application the role of K_{0} is played by S_{0}, which we now define. We state the basic lemmas used in the proof as ‘axioms’ to allow for other applications of the argument and discuss some such applications later in the paper.

Example 1.1.11 (Successor Case: S_{0}).

1. L is an expansion of the language L′ by finitely many additional relations in any number of variables, which are taken to be symmetric and strongly irreflexive (no sequence with two of its elements equal will satisfy any of the additional relations). Let Ŝ_{0} denote the class of all expansions of structures in S′_{0} by such relations and Ŝ the models of the universal theory of Ŝ_{0}.

2. Define δ_{α} on each member of the class of L-structures Ŝ as in Notation 1.1.8. We restrict to structures with nonnegative weight:

S_{0} = {A ∈ Ŝ_{0} : for all B ⊂ A, δ_{α}(B) ≥ 0}.

The aspects of the weight function described in Example 1.1.11, which are essential to the argument, are now codified.

Definition 1.1.12 (Weight Properties). Let L be a finite relational language and K̂_{0} a collection of finite L-structures. Naturally any real valued weight function δ on K̂_{0} defines a weight for each finite substructure of a member of K̂. A real-valued function δ which assigns real numbers to finite subsets of members of K̂ and satisfies conditions W1, W2 will be called a weight on K̂.

W1: If A, B, and C in K̂_{0} are disjoint subsets of N ∈ K̂ then

δ(A/B) ≥ δ(A/BC).

W2: If f is a 1-1 homomorphism from A to B and A, B ∈ K̂_{0} then for every X ⊆ Y ⊆ A, δ(Y/X) ≥ δ(f(Y)/f(X)).

The monotonicity condition W1 can be easily translated into lower semimodularity: δ(XY) ≤ δ(X) + δ(Y) − δ(X ∩ Y). The following remark is easily verified.

1.1.13 Lemma. The map δ on S satisfies W1 and W2.

We now describe the most important properties of the relation ≤_{s}. The notions of strong and intrinsic submodel are derived from weight; the arguments involving only these notions follow from the properties in Lemma 1.1.18.

1.1.14 (Intrinsic and strong extensions). Any weight function gives rise to notions of intrinsic and strong submodel as follows.

1. For A ⊆ B ∈ K̂_{0}, A ≤_{s} B (B is a strong extension of A) if for every B′ with A ⊂ B′ ⊆ B, δ(B′/A) > 0.

2. For B ∈ K̂ and possibly infinite A, A ≤_{s} B if for every finite B′ ⊂ B, B′ ∩ A ≤_{s} B′.

3. For B ∈ K̂ and possibly infinite A, A is intrinsic in B, written A ≤_{i} B, if and only if there is no B′ ≠ B with A ⊆ B′ ≤_{s} B.

For finite A, the notion A ≤_{i} B can be expressed in terms of dimension functions as δ(B/A) ≤ δ(B′/A) for any intermediate B′ and δ(B/A) ≤ 0. Note the following immediate consequence of the definition of ≤_{i}.

1.1.15 Lemma. For every A ⊂ B, there is a C with A ≤_{i} C ≤_{s} B.

Our main notion is semigenericity. Closely following the development in [5], we first describe intrinsic closure.

1.1.16 Definition. For any M ∈ K̂, any m ∈ ω, and any A ⊆ M,

icl_{M}^{m}(A) = ∪{B : A ≤_{i} B ⊆ M & |B − A| < m}.

icl_{M}(A) = ∪_{m<ω}icl_{M}^{m}(A).

Note that for any A, icl_{M}(A) ≤_{s} M.

1.1.17 Example. In contrast to [5], there are two ways points can enter the intrinsic closure. In the successor case, let A = {x} ⊂ M. Then all points on the component of x ∈ M which are less than m distant from x are in icl_{M}^{m}(A). Further if y, z are on a different component but both are R-related to x and if α_{R} > 1/2, then y, z ∈ icl_{M}^{m}(A) for any m ≥ 2 + r, where r is the distance from y to z.

The next result follows immediately from the definitions and properties W1 and W2. The first four parts were established in [7]; the proof of S5 is straightforward.

1.1.18 Lemma. If a weight function satisfies the properties of Definition 1.1.12 then (K̂, ≤_{s}) satisfies the following properties (S1 - S4).

S1. M ≤_{s} M.

S2. If M ≤_{s} N then M ⊆ N.

S3. If M ≤_{s} N ≤_{s} N′ then M ≤_{s} N′.

S4. If M ≤_{s} N, N′ ⊆ N then M ⋂ N′ ≤_{s} N′.

S5. Suppose g is an L′-isomorphism from A to B that is also an L-homomorphism. Then for any m < ω and X ⊂ A, icl_{B}^{m}(gX) ⊇ g(icl_{A}^{m}(X)).

We want to count L-embeddings of B over A. The (L-L′)-structure of A is irrelevant to the existence of such embeddings. This fact has been exploited since at least [17] to simplify arguments of the kind considered here. It is reflected here in the fact that the question of whether f preserves the (L-L′)-structure of A is not part of the definition of an (L-L′)-homomorphism relative to A. We prove in Subsection 2.2 that we need to count only 1-1 (L-L′)-homomorphisms as opposed to (L-L′)-embeddings.

The function N defined next is the heart of the paper. In greatest generality it depends on five variables; various subsets of these are relevant at different points in the argument. Four of the arguments are used here; the fifth is introduced in Subsection 2.1. In this section, the model M is kept fixed and N is a counting function. In the second part, M varies and N becomes a random variable.

1.1.19 Definition. 1. Let A ⊆ B be L-structures. Fix an L′-embedding f from A into M ∈ K̂. By an (L-L′)-homomorphism relative to A (or f) we mean an L′-embedding g : B → M which extends f such that for any b ∈ B with b ∩ (B − A) ≠ ∅ and any (L-L′)-relation R, B ⊧ R(b) implies M ⊧ R(gb).

2. We write N(f, A, B, M) for the number of g : B → M extending f which are (L-L′)-homomorphisms relative to A. We drop M when it is clear from context.

The earlier definitions and axioms held in the class K̂ of all expansions. The truth of the next axiom requires the restriction to non-negative dimension; thus K replaces K̂.

1.1.20 (Axiom S6). There is a binary function t : ω × ω → ω which is monotone increasing in both arguments such that if A, B ∈ K_{0}, A ≤_{i} B then for any M ∈ K and any f an L′-embedding of A into M, N(f, A, B, M) ≤ t(|A|, |B|).

This is slightly stronger than the analogous axiom in [5] or [7] where f was required to be an L-embedding. Since Axiom S6 bounds the number of copies of any intrinsic extension of A, Definition 1.1.16 implies that there is a uniform bound k(m, r) on |icl_{M}^{m}(a)| for any M ∈ K, and any sequence a of length r. Axiom S6 also immediately yields:

1.1.21 Lemma. For any M, A, m, n there exists a p depending on |A|, m, n but not on the embedding of A into M with icl_{M}^{m}(icl_{M}^{n}(A)) ⊆ icl_{M}^{p}(A).

Proof. For any r, let s(r, n) bound the cardinality of icl_{M}^{n}(A) with |A| ≤ r. Note s(r, n) is at most the product of the number of isomorphism types of structures of size r + n times t(r, n) times n. Let p = m + s(|A|, n) and check. _{1.1.21}

The next result is immediate, noting that A ≤_{i} X does not depend on any ambient model containing X.

1.1.22 Lemma. If A ⊆ B ⊆ C and icl_{C}^{m}(A) ⊆ B, then icl_{C}^{m}(A) = icl_{B}^{m}(A).

1.1.23 Definition. Let T be any extension of the universal theory of K_{0}. The theory T is determined if for any formula ϕ(x_{1} … x_{r}) there is an integer ℓ_{ϕ}, such that for any M, M′ ⊧ T and any r-tuples a ∈ M and a′ ∈ M′ if icl_{M}^{ℓ_{ϕ}}(a) ≈ icl_{M′}^{ℓ_{ϕ}}(a′) by an isomorphism taking a to a′, then M ⊧ ϕ(a) if and only if M′ ⊧ ϕ(a′).

1.2 Expansions of vector spaces

In this section we study expansions of vector spaces over a finite field. We show that expanding such vector spaces by weighted relations as described in Subsection 1.1 produces a determined theory. To show this we define a notion of a semigeneric model. This section is not required for the proof of the 0-1 law for successor. Theorem 1.2.7 provides a simpler version of Theorem 1.3.12, which may aid understanding of the more complicated result.

While we work directly with vector spaces, the crucial properties in the argument are the uniform local finiteness and the modularity of the geometry. Here is the context for this section.

1.2.1 (Vector Space Case: V_{0}). 1. Fix a finite field F_{q}. V′_{0} is the collection of vector spaces of finite dimension over F_{q}; L′ is a relational language with a ternary relation +, constant symbol 0 and binary relation symbols for each element of the base field to represent scalar multiplication.

2. The weight δ′ on V′_{0} is given by vector space dimension.

3. Let V̂_{0} be the expansions of L′-structures to L-structures by adding symmetric and strongly irreflexive relations and define δ as in Notation 1.1.8.

4. V_{0} = {A ∈ V̂_{0} : δ(B) ≥ 0 for all B ⊆ A}.

We fix some notation for the vector space case.

1.2.2 Notation. 1. If X is a subset of an L-structure M, ⟨X⟩_{M} is the vector space closure of X. We omit M if it is clear from context.

2. Let M be an L-structure and B, C vector subspaces of M with intersection A. Then B and C are freely joined over A in M if the only (L − L′)- structure on ⟨BC⟩_{M} is that on B or C.

1.2.3 Lemma. (V_{0}, ≤_{s}) satisfies S6 (Axiom 1.1.20).

Proof. As in the proof of Lemma 3.19 in [7], if there are too many extensions B ⊂ M with δ(B/A) < 0 there is a structure A^{∗} ⊂ M with δ(A^{∗}) < 0. There are only finitely many B of bounded size with δ(B/A) = 0 because vector spaces are uniformly local finite. _{1.3.1}

In this context we define the notion semigeneric as follows.

1.2.4 Definition. The countable model M is (V_{0}, ≤)-semigeneric, or just semigeneric, if

1. M ∈ V

2. If A ≤ B ∈ V_{0} and g : A ↦ M, then for each finite m there exists an embedding ĝ of B into M which extends g such that

(a) ⟨icl_{M}^{m}(ĝB)⟩ = ⟨icl_{M}^{m}(gA)ĝB⟩

(b) M ↾ ⟨icl_{M}^{m}(gA)ĝB⟩ is the free join over gA of ⟨icl_{M}^{m}(gA)⟩ and ĝB.

1.2.5 Lemma. There are (V_{0}, ≤_{s})-semigeneric models.

Proof. The class (V_{0}, ≤_{s}) has the amalgamation property by the obvious free amalgamation of vector spaces. The generic model obtained in the usual way [7] from this amalgamation is generic. _{1.2.5}

1.2.6 Fact. The class of semigeneric structures is first order axiomatizable. For details on how to write such axioms consult either [5] or Definition 1.3.10 below where the more complicated successor case is treated. The axioms have the form ϕ_{A,B,C}^{m} where A ≤_{s} B and C is a potential m-intrinsic closure of A.

The next result is a simpler version of Theorem 1.3.12 that avoids the complications that arise from dealing with infinite closures.

1.2.7 Theorem. The theory of the (V_{0}, ≤_{s})-semigeneric models is determined.

Proof. The proof is by induction on formula complexity; the cases involving Boolean connectives are easy. So suppose ϕ(x) is of the form (∃y)ψ(x, y).

Choose p_{1} large enough so that for any N ∈ \overline{V}, any r-tuple c from N and any d ∈ N, |icl_{N}^{ℓ_{ψ}}(c, d)| < p_{1}. More strongly, using the fact that V′_{0} is uniformly locally finite, choose p_{1} bigger than |⟨(icl_{N}^{ℓ_{ψ}}(c, d))⟩|. Set p = max(3p_{1}, ℓ_{ψ}). For i ≤ p, for any N ∈ \overline{V}, for any a ∈ N define by induction A_{0}^{N} = A_{0}^{N}(a) = a and A_{i+1}^{N} = A_{i+1}^{N}(a) = ⟨icl_{N}^{p}(A_{i})⟩. Now noting that for any X, and any m > 1, icl_{M}^{m}(X) ⊇ ⟨X⟩ and applying Lemma 1.1.21, choose ℓ_{ϕ} so that for every semigeneric N and every a ∈ N of length r, we have A_{p}^{N}(a) ⊆ icl_{N}^{ℓ_{ϕ}}(a). We want to show that for any semigeneric structures M and M′, for any a ∈ M^{r}, a′ ∈ M^{′r}, and b ∈ M, if icl_{M}^{ℓ_{ϕ}}(a) ≈ icl_{M′}^{ℓ_{ϕ}}(a′) then there is a b′ ∈ M′ with icl_{M}^{ℓ_{ψ}}(a, b) ≈ icl_{M′}^{ℓ_{ψ}}(a′, b′), by an isomorphism taking a to a′.

Let H = ⟨icl_{M}^{ℓ_{ψ}}(a, b)⟩. Fix g which maps a to a′ and icl_{M}^{ℓ_{ϕ}}(a) isomorphically onto icl_{M′}^{ℓ_{ϕ}}(a′). By the choice of ℓ_{ϕ}, g maps A_{i}^{M}(a) isomorphically onto A_{i}^{M′}(a′), for each i ≤ p. (Induct, using Lemma 1.1.22.) To avoid superscripts, for each i, let A′_{i} denote the image of A_{i} = A_{i}^{M} under g.

Immediately from the local finiteness and the choice of p_{1} we have for some j < p:

(A_{j+1} − A_{j}) ∩ H = ∅.  (1)

Since A_{j+1} = icl_{M}^{p}(A_{j}) and p > |H −A_{j}|, A_{j} ≤_{s} A_{j}H. As M′ is semigeneric, M′ ⊧ ϕ_{A_{j},H,A_{j+1}}^{p}. Thus, there is an L-isomorphism ĝ extending g ↾ A_{j} and mapping H into M′ with

icl_{M′}^{p}(ĝH) = ⟨(icl_{M}^{p}(A′_{j})ĝH⟩ = ⟨A′_{j+1}ĝH)⟩

and so that M′ ↾ ⟨(icl_{M}^{p}(A′_{j})ĝH⟩) is a free join of A′_{j+1} = ⟨icl_{M′}^{p}A′_{j}⟩ and ⟨ĝH⟩) over A′_{j}. Let H′ = ĝH and b′ = ĝ(b). Although in general H and A_{j+1} are not freely joined over A_{j}, we will show that icl_{M}^{ℓ_{ψ}}(a, b) ≈ icl_{M′}^{ℓ_{ψ}}(a′, b′), by constructing a 1-1 L-homomorphism back from ⟨A′_{j+1}H′_{j}⟩ onto ⟨A_{j+1}H_{j}⟩ and invoking Lemma 1.1.18 (S5).

By modularity A_{j+1} and H (and therefore A′_{j+1} and H′) are independent as L′-structures over A_{j} (and over A′_{j}, respectively) so there is an L′-isomorphism g̃ from ⟨A_{j+1}H⟩ onto ⟨A′_{j+1}H′⟩. As A′_{j+1} and H′ are freely joined over A′_{j} g̃^{−1} is a 1-1 L-homomorphism from ⟨A′_{j+1}H′⟩ onto ⟨A_{j+1}H⟩. By Lemma 1.1.18,

icl_{A_{j+1}H}^{ℓ_{ψ}}(a, b) ⊇ g̃^{−1} icl_{A′_{j+1}H′}^{ℓ_{ψ}}(a′, b′).

But icl_{A_{j+1}H}^{ℓ_{ψ}}(a, b) = H. So,

icl_{A′_{j+1}H′}^{ℓ_{ψ}}(a′, b′) = g̃g̃^{−1} icl_{A′_{j+1}H′}^{ℓ_{ψ}}(a′, b′) ⊆ g̃H = H′;

applying Lemma 1.1.22 again, we finish. _{1.2.7}

1.2.8 Remark. The only properties of (V_{0}, δ) used in proving Theorem 1.2.7 are that (V_{0}, δ) satisfies W1,W2 (so (V_{0}, ≤_{s}) satisfies S1-S5), (V_{0}, ≤_{s}) satisfies S6, and that the geometry on the L′ reducts is uniformly locally finite and modular. Because of our probabilistic goals in this paper we have begun with a family of finite structures V′_{0}. Another perspective would be to expand an infinite model carrying a geometry on its definable subsets. In view of Zilber’s work [19] on homogenous locally finite geometries, one could probably reformulate the result of this section in terms of expanding models of an ℵ_{0}-categorical strongly minimal theory.

1.3 The Successor Case

In this section we formulate an appropriate notion of semigeneric for the successor case. We find an axiomatization for the class of semigeneric structures and show that it is determined. In Section 2, we show these axioms have probability 1. The classes investigated here were defined in Subsection 1.1.

1.3.1 Lemma. (S_{0}, ≤_{s}) satisfies Axiom 1.1.20 (S6).

Proof. As in the proof of Lemma 3.19 in [7] (or Lemma 1.2.3), if there are too many extensions B with δ(B/A) < 0 there is a structure A^{∗} with δ(A^{∗}) < 0. Any B with δ(B/A) = 0 is contained in the L′-closure of A. _{1.3.1}

The previous lemma depends heavily on the class of restrictions in L′. This property cannot be abstractly derived from S1-S5. Counterexamples (even with rational weights) appear in e.g. [1].

We introduce several concepts designed to analyze the infinite component generated by any element of an infinite model of successor (in more generality, the infinite L′-closure of a singleton).

1.3.2 Definition. For any M ∈ K, any m ∈ ω, and any A ⊆ M,

Scl_{M}^{m}(A) = ∪{B : δ(B/A) = 0 & |B − A| < m}.

Thus the Scl_{M}^{m}(A) adds up to m points at each end of each segment contained in A. Recall that a geometry is called trivial or disintegrated if the closure of a pair of points is the union of the closures of the two points. We require a property which strengthens triviality of the L′-geometry by requiring it of Scl_{M}^{m}(A) rather than just of L′-closure.

Assumption 1.3.3 (J1). For c, X ⊂ M ∈ K, if c ∈ Scl_{M}^{m}(X) then there is a d ∈ X with d ∈ Scl_{M}^{m}(c).

Note that for Y ⊂ M ∈ K, Scl_{M}^{m}(Y) ⊆ icl_{M}^{m}(Y) so J1 implies that if c ∈ Scl_{M}^{m}(X) then there is a d ∈ X with d ∈ icl_{M}^{m}(c).

We need the following construction.

1.3.4 Notation. For any A ∈ S, and any natural number m, m∗A denotes the structure obtained by extending the beginning and end of each finite component of A by m-points but adding no new (L-L′)-structure.

The crucial properties of m ∗ A are codified in the next definition.

1.3.5 Definition. For any A ∈ K_{0}, the L-structure B is an m-universal closure of A if for any M ∈ K, Scl_{M}^{m}(A) is isomorphic to a substructure of B.

Assumption 1.3.6 (J2). For every m ∈ ω and any A ∈ K_{0}, there is a Lstructure in K_{0}, denoted m ∗ A, which is the m-universal closure of A.

Observe:

1.3.7 Lemma. If K_{0} = S_{0}, the successor case, then J1 and J2 (with m ∗ A chosen as in Notation 1.3.4) hold.

Thus for every embedding of A into M ∈ K, Scl_{M}(A) is isomorphic to a substructure of m ∗ A. (Some embedding may be into short components).

1.3.8 Notation. We say B and C are freely joined over A in M if all three are subsets of M with B ∩C = A and no L-L′ relation holds in M on BC except those which hold on B or on C. We denote the resulting structure as B ⊗_{A} C.

We christen the following notion (S_{0}, ≤_{s})-semigenericity to emphasize the role of ≤_{s}-embeddings. Note that (S_{0}, ≤_{s})-semigenericity depends only on the function δ, although not just on ≤_{s} as the notation might suggest.

1.3.9 Definition. The countable model M is (S_{0}, ≤_{s})-semigeneric if

1. M ∈ S;

2. If A ∈ S_{0} and f : A → M is an L-embedding then for each finite m < ω there exists an L′-embedding f̂ of (m ∗ A) ↾ L′ into M which extends f;

3. If A ≤_{s} B ∈ S_{0} and g : A → M is an L-embedding, then for each m ≥ 1 there exists an L-embedding ĝ of B into M which extends g such that

(a) Scl_{M}^{m}(ĝB) is isomorphic to the free join of Scl_{M}^{m}(A) and m∗(B −A).

(b) icl_{M}^{m}(ĝB) = icl_{M}^{m}(gA)Scl_{M}^{m}(ĝB − gA)

(c) M|icl_{M}^{m}(gA)Scl_{M}^{m}(ĝB) is the free join over Scl_{M}^{m}(gA) of icl_{M}^{m}(gA) and

Scl_{M}^{m}(ĝB).

We can’t require Scl_{M}^{m}(ĝB) to be isomorphic to m∗B since Scl_{M}^{m}(A) is given and the L-structure m∗A may not be embeddible in M. We settle for condition 3 a). The role of J2 is to allow 3a) to be stated. It does not appear explicitly in the following argument.

We can axiomatize the class of (S_{0}, ≤_{s})-semigeneric models. The structure M satisfies ϕ_{A,B,C}^{m} just if for some embedding of B into M over A the definition of semigenericity holds for the finite structures A ⊆ C and A ≤_{s} B when C ≈ icl_{M}^{m}(A). In more detail we have the following.

1.3.10 Definition. We define ϕ_{A,B,C}^{m} analogously to the sentence ϕ_{A′,B′,C}^{m} in 1.28 of [5]. As in that case, there is a formula θ_{D,E}^{m}(x, y) such that if D ⊆ E ⊂ M are enumerated by d, e then N ⊧ θ_{D,E}^{m}(d, e) if and only if E is icl_{N}^{m}(d). Similarly, there is a formula σ_{D,E}^{m}(x, y) such that if D ⊆ E ⊂ M are enumerated by d, e then N ⊧ σ_{D,E}^{m}(d, e) if and only if E is Scl_{N}^{m}(d). Using these formulas we can define a sentence ϕ_{A,B,C}^{m} which holds in N if for any a and c with c enumerating C = icl_{N}^{m}(a), there is a b a) with B′ = Scl_{N}^{m}(a, b) isomorphic to the free join of Scl_{M}^{m}(A) and m ∗ (B − A), b) with icl_{N}^{m}(b) equal to the union of C and Scl_{N}(b), and c) with CB′ a free join over Scl_{N}(b) of C and B.

A modification of the argument in [5] yields

1.3.11 Lemma. The structure N ∈ S is (S_{0}, ≤_{s})-semigeneric if and only if for each A ≤_{s} B, each m < ω, and each C which is a possible choice for icl_{N}^{m}(A), N ⊧ ϕ_{A,B,C}^{m}.

The following theorem reduces the truth of ϕ(a) in a semigeneric model M to the isomorphism type of icl_{M}^{ℓ_{ϕ}}(a). In Corollary 1.32 of [5] the completeness of the theory followed; the closure of the empty set was always empty in the context of that paper. Here, the closure of the empty set is not empty but we will show that for successor the isomorphism type of icl_{M}(∅) does not depend on M. In fact, because of S6 it is ω + ω^{∗} with no L-L′-structure.

1.3.12 Theorem. The theory of the (S_{0}, ≤_{s})-semigeneric models is determined.

Proof. The proof is by induction on formula complexity; the quantifier-free case is immediate and the cases involving Boolean connectives are easy. So suppose ϕ(x) is of the form (∃y)ψ(x, y).

Choose p_{1} large enough so that for any N ∈ S, any r-tuple c from N and any d ∈ N, |icl_{N}^{ℓ_{ψ}}(c, d)| < p_{1}. Set p = max(3p_{1}, ℓ_{ψ}). For i ≤ p, for any N ∈ S, for any a ∈ N define by induction A_{0}^{N} = A_{0}^{N}(a) = a and A_{i+1}^{N} = A_{i+1}^{N}(a) = icl_{N}^{p}(A_{i}). Now applying Lemma 1.1.21, choose ℓ_{ϕ} so that for every semigeneric N and every a ∈ N of length r, we have A_{p}^{N}(a) ⊆ icl_{N}^{ℓ_{ϕ}}(a). We want to show that for any semigeneric structures M and M′, for any a ∈ M^{r}, a′ ∈ M^{′r}, and b ∈ M, if icl_{M}^{ℓ_{ϕ}}(a) ≈ icl_{M′}^{ℓ_{ϕ}}(a′) then there is a b′ ∈ M′ with icl_{M}^{ℓ_{ψ}}(a, b) ≈ icl_{M′}^{ℓ_{ψ}}(a′, b′), by an isomorphism taking a to a′.

Let H = icl_{M}^{ℓ_{ψ}}(a, b). Fix g which maps a to a′ and icl_{M}^{ℓ_{ϕ}}(a) isomorphically onto icl_{M′}^{ℓ_{ϕ}}(a′). By the choice of ℓ_{ϕ}, g maps A_{i}^{M}(a) isomorphically onto A_{i}^{M′}(a′), for each i ≤ p. (Induct, using Lemma 1.1.22.) To avoid superscripts, for each i, let A′_{i} denote the image of A_{i} = A_{i}^{M} under g.

We want to establish:

(A_{j+1} − A_{j}) ∩ Scl_{M}^{p}(H) = ∅.  (2)

As p > 3p_{1}, the number of steps in the construction is greater than |H| so we have for some j,

(A_{j+2} − A_{j}) ∩ H = ∅.

We deduce Equation (2). For, if some c is in (A_{j+1} − A_{j}) ∩ (Scl_{M}^{p}(H) − H), then by J1 there is a d ∈ H which is in icl_{M}^{p}(c). But then, d ∈ A_{j+2}, which is impossible.

Since A_{j+1} = icl_{M}^{p}(A_{j}) and p > |H −A_{j}|, A_{j} ≤_{s} A_{j}H. As M′ is semigeneric, M′ ⊧ ϕ_{A_{j},H,A_{j+1}}^{p}. Thus, there is an L-isomorphism ĝ extending g ↾ A_{j} and mapping H into M′ with

icl_{M′}^{p}(A′_{j}ĝH) = icl_{M′}^{p}(A′_{j})Scl_{M′}^{p}(ĝH − A′_{j}) = A′_{j+1}Scl_{M′}^{p}(ĝH − A′_{j})

so that M′|(icl_{M′}^{p}A′_{j}ĝH) is a free join of A′_{j+1} = icl_{M′}^{p}A′_{j} and Scl^{p}(ĝH) over Scl_{M′}^{p}A′_{j}. Let H′ = ĝH and b′ = ĝ(b). Although in general H and A_{j+1} are not freely joined over Scl_{M}^{p}A_{j}, we will show that icl_{M}^{ℓ_{ψ}}(a, b) ≈ icl_{M′}^{ℓ_{ψ}}(a′, b′), by constructing a 1-1 L-homomorphism back from A′_{j+1}Scl_{M′}^{p}(H′ − A′_{j}) onto A_{j+1}Scl_{M}^{p}(H − A_{j}) and invoking Lemma 1.1.18.

Since both M and M′ are semigeneric, condition 2) of Definition 1.3.9 provides an extension g̃ of ĝ ↾ H which is an L′-isomorphism between Scl_{M}^{p}(H −A_{j}) and Scl_{M′}^{p}(H′ − A′_{j}) (as both are L′-isomorphic over ĝ to Scl^{p}(H − A_{j})). Note

icl_{M′}^{ℓ_{ψ}}(a′, b′) ⊆ icl_{M′}^{p}(a′, b′) ⊆ icl_{M′}^{p}(A′_{j}H′) = A′_{j+1}Scl_{M′}^{p}(H′ − A′_{j}).

By Lemma 1.1.22, icl_{M′}^{ℓ_{ψ}}(a′, b′) = icl_{A′_{j+1}Scl_{M′}^{p} (H′−A′_{j})}^{ℓ_{ψ}}(a′, b′).

Extend g̃ to A_{j+1}Scl_{M}^{p}(H −A_{j}) by letting g̃ ↾ (A_{j+1} −A_{j}) = g ↾ (A_{j+1} −A_{j}). As A′_{j+1} and Scl_{M′}^{p}(H′−A′_{j}) are freely joined over Scl_{M′}^{p}A′_{j} and δ(Scl_{M′}^{p}(H′)/H′) = 0, g̃^{−1} is a 1-1 L-homomorphism from A′_{j+1}Scl_{M′}^{p}(H′ −A′_{j}) onto A_{j+1}Scl_{M}^{p}(H − A_{j}). By Lemma 1.1.18,

icl_{A_{j+1}Scl_{M}^{p} (H−A_{j})}^{ℓ_{ψ}}(a, b) ⊇ g̃^{−1} icl_{A′_{j+1}Scl_{M′}^{p} (H′−A′_{j})}^{ℓ_{ψ}}(a′, b′).

But icl_{A_{j+1}Scl_{M}^{p} (H−A_{j})}^{ℓ_{ψ}}(a, b) = H. So,

icl_{A′_{j+1}Scl_{M′}^{p} (H′−A′_{j})}^{ℓ_{ψ}}(a′, b′) = g̃g̃^{−1} icl_{A′_{j+1}Scl_{M′}^{p} (H′−A′_{j})}^{ℓ_{ψ}}(a′, b′) ⊆ g̃H = H′;

applying Lemma 1.1.22 again, we finish. _{1.3.12}

1.3.13 Remark. We have chosen to formulate this section just for successor. The argument holds for any (K_{0}, δ) satisfying Assumptions J1, J2,W1,W2 (so (K_{0}, ≤_{i}) satisfies S1 - S5) and such that (K_{0}, ≤_{s}) satisfies S6. The theory of two commuting successor functions (or two free successor functions) satisfies these conditions. But the conditions still seem rather restrictive.

1.4 Stability and Completeness

In the last two sections we have shown (using slightly different notions of semigenericity) that either in the case of vector spaces or successor we can define a determined theory whose models are expansions of the base L′-theory. We now give additional conditions to find a complete stable theory. Hrushovski [9] suggested the following device to simplify the description of theories in expanded languages by expanding the language again.

1.4.1 Definition. 1. For any finite L-structure A, Δ_{A}(x) denotes the conjunction of the quantifier-free-L-diagram of A (lg(x) = |A|).

2. Form the language L^{+} by adding a relation symbol R_{AB}(x) for each pair (A, B) where B is a minimal intrinsic extension of A. For any L-theory T, denote by T^{+} the L^{+}-theory which extends T by adding the axioms:

[∃yΔ_{AB}(x, y)] ↔ R_{AB}(x).

We denote the natural expansion of an L-structure N to L^{+} by N^{+} and the collection of expansions of models in a class K by K^{+}.

3. An L-theory T is nearly model complete if T^{+} admits elimination of quantifiers in L^{+}.

This is a slightly more restrictive notion of nearly model complete than that in [5]. Note T_{α}^{+} is an expansion by definitions of T_{α}.

1.4.2 Lemma. If the L-theory T is determined then

1. T is nearly model complete

2. Let T_{1} be an extension of T such that for any models M, N of T_{1}, icl_{M}(∅) ≈ icl_{N}(∅). Then T_{1} is complete.

3. If T′, the theory of the reducts to L′ of models of T, is stable then so is T.

Proof. 1) For any formula ϕ(x_{1} … x_{r}) there is an integer ℓ_{ϕ}, such that for any M, M′ ⊧ T and any r-tuples a ∈ M and a′ ∈ M′ if icl_{M}^{ℓ_{ϕ}}(a) ≈ icl_{M′}^{ℓ_{ϕ}}(a′) by an isomorphism taking a to a′, then M ⊧ ϕ(a) if and only if M′ ⊧ ϕ(a′). That is, the truth of ϕ(a) is determined by the quantifier-free L^{+}-diagram of a, as required.

2) For completeness, note that the truth of any sentence has uniformly been reduced to the isomorphism type of icl_{M}^{m}(∅) for some m. If icl_{M}(∅) ≈ icl_{N}(∅) then icl_{M}^{m}(∅) ≈ icl_{N}^{m}(∅) for any m.

3) We show stability by verifying that no formula in L^{+} has the order property in T^{+}. In view of 1) it suffices to consider quantifier-free formulas of L^{+}. A use of Ramsey’s theorem shows that ‘not order property’ is preserved by Boolean combinations so we can restrict to atomic formulas of L^{+}. For formulas in L′, apply the stability hypothesis on T′. Now, consider atomic formulas R(x_{1}, x_{2}) (where R is a basic 2k-ary relation of L-L′) or atomic formulas of L^{+} ( i.e. L-formulas of the form ∃yΔ_{AB}(x_{1}, x_{2}, y)] where Δ_{AB} is the quantifier-free L-diagram of a minimal intrinsic extension). Suppose a formula ϕ(x_{1}, x_{2}) of the preceding form has the order property. Fix a large n and suppose a_{i}, b_{i} for i < n are ordered by ϕ. If ϕ is R there are \binom{n}{2} pairs satisfying R from a set of n k-tuples so for sufficiently large n, δ({a_{i}, b_{i} : i < n}) < 0. In the L-L′-case, for each ⟨i, j⟩, Δ_{AB} is the diagram of a set in the intrinsic closure of the free variables, so we can find a set D_{ij} (witnessing y) for each pair a_{i}, b_{j}. Let D_{ij}^{∗} = D_{ij} ∪ {a_{i}, b_{j}}, and r_{ij} denote the weighted sum of the number of relations that hold between D_{ij} and {a_{i}, b_{j}}. Then , δ(D_{ij}/{a_{i}, b_{j}}) = |D_{ij}| − r_{ij} < 0. Note that the numbers |D_{ij}| and r_{ij} depend only on the isomorphism type of AB and not on particular i, j. Let D_{n} = ⋃_{i<j<n} D_{ij}^{∗}. Then δ(D_{n}) ≤ \binom{n}{2} · [|D_{ij}^{∗}| − r_{ij} + n(lg(x_{1}) + lg(x_{2})]. The number of elements in the sequence grows linearly, the number of occurences of the negative number |(D_{ij}| − r_{ij} grows quadratically. For sufficiently large n this again gives δ(D_{n}) < 0. Since structures with negative δ are forbidden, T_{α} is stable. _{1.4.2}

1.4.3 Remark. The last argument is a direct generalization of the proof of stability for the pure graph case given in [10]. Similar ideas occurs in [6, 9, 13]. Any weight function can give rise to a notion of strong submodel in two ways, depending on the treatment of weight 0 extensions. Each gives rise to its own notion of intrinsic closure depending on whether dimension 0 extensions are viewed as intrinsic or strong. The original version of this paper used both notions but the simpler proof of stability allows us to restrict to the case where dimension 0 extensions are intrinsic. The alternative treatment appears in [4].

Remark 1.4.4 (Consistency). We sketched for vector spaces in Section 1.2 an argument for the consistency of the theory of the semigenerics. We could do the same for successor but consistency follows immediately from the fact (Section 2) that the axioms of T_{α} are almost surely true, so we content ourselves with that argument.

2 The Probability Argument

In this section we show the 0-1-law for expansions of successor by random relations with ‘edge’ probability n^{−α}. In the introduction we formulate the context and outline the argument. In Subsection 2.1 we count the number of finite structures of certain types and state fundamental estimates for the argument. In Subsection 2.2 we derive the 0-1-law, assuming these estimates. This argument is patterned on the argument in [5] which avoided some gaps in [17]. Finally, in Subsection 2.3 we prove the fundamental estimates. Our arguments here provide a simpler proof than the version in [17].

In more detail, let L′ be the first order language with a binary relation symbol S and two unary constants I, F. Let L be an extension of L′ by a family of additional relations symbols: \overline{R}. Let Ω_{n} be the set of L-structures (n, S, I, F, \overline{R}) with universe n, where S is the successor function, I and F are constant symbols denoting the initial and final elements respectively, and each R_{i} for i < k is a symmetric, irreflexive relation (i.e. R_{i} is a predicate of unordered sets not sequences). Fix α as ⟨α_{i} : i < k⟩, a set of linearly independent irrational numbers. As in [5], let p_{n} be a probability measure on Ω_{n} induced by setting the edge probability of each R_{i} independently to n^{−α_{i}}.

We are dealing with the same family of probability spaces as in the Shelah-Spencer theorem. The addition of successor allows us to define additional events (those subsets of Ω_{n} defined by L-sentences but not by ‘graph’ sentences); the new content is to extend the 0-1 laws to these additional (uniformly defined families of) events.

As in Example 1.1.11, let Ŝ_{0} be the class of all substructures of L-expansions of members of S′_{0}. Thus, Ŝ_{0} is the class of all substructures of members of ∪_{n}Ω_{n}. Define a weight function on Ŝ_{0} as in Notation 1.1.8 depending on the coefficients α_{i} which determine the probability. We review the notation from Section 1.1.

2.0.5 Notation. 1. For A ∈ Ŝ_{0}, let r(A) = ∑_{R∈L−L′} α_{R}|R|, δ′(A) denote the number of successor components (excepting the first and last) of (A| ↾ L′), and δ(A) = δ′(A)−r(A). Naturally, when A ⊆ B, we define r(B/A) = r(B) − r(A) and δ(B/A) = δ(B) − δ(A).

2. As in Example 1.1.11, S_{0} = {A ∈ Ŝ_{0} : δ(B) ≥ 0 for all B ⊆ A}.

The connection between the probabilistic setting and the model theoretic setting begins with the following observations. Let A ⊂ B be L-structures and suppose g mapping B into (n, S, I, F) is an L′-isomorphism. The probability that g is an (L-L′)-homomorphism (preserves the R_{i} for sequences with at least one element in B − A) is n^{−r(B/A)}.

We provide a name to the axioms given in Subsection 1.3 for the class of semigeneric models.

2.0.6 Definition. We denote by Σ_{α} the conjunction of a) the sentences axiomatizing (K_{0}, ≤_{s})-semigenericity and b) the sentences asserting that if a ∈ icl_{M}(∅) then ¬R(a) (for any R ∈ L-L′) and describing the L′-structure of icl_{M}(∅).

Since the L′-reduct of T_{α} is manifestly ℵ_{1}-categorical and so stable, taking S_{0} for K_{0} we can immediately conclude from Theorem 1.4.2:

2.0.7 Corollary. If T_{α} is the theory of the semigeneric models of S_{0} then T_{α} is a complete theory, axiomatized by Σ_{α}. Moreover, T_{α} is nearly model complete and stable.

Our main aim is to show the following result. To attain this aim, we invoke the technology of Section 1.1 and freely use the terminology from that section.

2.0.8 Theorem. Each sentence in Σ_{α} has limit probability 1. Since Σ_{α} axiomatizes a complete theory, for any L-sentence ϕ, lim_{n→∞} μ_{n}^{α}(ϕ) is 0 or 1.

Here is an outline of the argument that is carried out in this section. Note that the L′-sentences with probability 1 are axiomatized by ‘I is initial’, ‘F is final’, and ‘there are no cycles’. We must show the sentences in (Definition 2.0.6) have probability 1. The sentences of type a) are shown to be almost sure in Theorem 2.2.1 modulo the important estimates given in Theorem2.1.8. This theorem is verified in Subsection 2.3. The sentences of type b) are shown to be almost sure in Corollary 2.2.2.

2.1 Setting the Scene

In [5] we expanded structures for equality by adding random relations. Here, equality is replaced by L′-structure. For some purposes, cardinality of the underlying set A is replaced by its dimension, δ′(A); for others (e.g. probability) one continues to use |A|. It turns out that the most serious obstacle to carrying over the proof is to find the proper analogy to following fact: for any sets A ⊆ B and subset X of n, the number of extensions of an embedding of A into X to an embedding of set B into X is approximately |X|^{|B−A|}. If we attempt to generalize this fact to the situation where A and B are L′-structures and n has the structure (n, S, I, F), a priori the number of such embeddings depends on both |B −A| and δ′(B). For large n, δ′(B) is the dominant factor. We formalize this fact in this subsection.

We begin with some properties of the L′-class K_{0}. Recall the notion of L′-closure from Definition 1.1.5. In particular, δ′(B/A) = k is the number of components of B − A (which don’t contain F or L). We say a subset of an L′-structure is connected if it is connected as a graph. For applications of the next results, note that if A, B ∈ S_{0} with A ≤_{s} B then A ↾ L′ is L′-closed in B ↾ L′.

2.1.1 Definition. Let A ⊆ B be L′ structures such that A is L′-closed in B. If A ⊆ M ∈ Ŝ, χ_{M}(B/A) denotes the number of distinct L′-embeddings of B into M over A.

We require the following easy universality property of the (n, S, I, F).

2.1.2 Lemma. If A, B ∈ K′_{0}, A an L′-closed substructure of B, then for some c = c(B/A) > 0 and for sufficiently large n, m, and any connected W contained in (n, S, I, F) with |W − A| ≥ m:

χ_{W} (B/A) ≥ c|W |.

Proof. In fact, a much stronger result holds. Any constant c with 0 < c < 1 will do. A very crude estimate shows that if m > \frac{|B|·|A|}{c}, |W − A| contains more than c|W | segments of length |B − A|. _{2.1.2}

It is straightforward to extend the argument of Lemma 2.1.2, by induction on the number of segments in B − A to the following finer result.

2.1.3 Lemma. Let A, B ∈ K′_{0}. Suppose δ′(B/A) = k and A is L′-closed in B. Then χ_{W} (B/A) ∼ |W |^{k}. That is, there exist positive constants c and d such that for all sufficiently large n, |W |, and any embedding of A into (n, S, I, F) and any connected W contained in (n, S, I, F):

d|W |^{k} ≥ χ_{W} (B/A) ≥ c|W |^{k}.

We generalize the function N(f, A, B, M) from Definition 1.1.19 by introducing a new argument W ⊂ M (and counting only maps into W). Further, we treat N as a random variable by letting M vary over L-expansions of (n, S, I, F).

2.1.4 Definition. Let A ⊆ B be L-structures. Fix an L′-isomorphism f from A into the L′-structure (n, S, I, F), and M ∈ Ω_{n}, i.e. M is an L-structure expanding (n, S, I, F).

1. Let U denote the range of f. By Lemma 2.1.3, for sufficiently large n there exist on the order of n^{δ′(B/A)} sets S ⊆ n such that S ∩ U = ∅, and there exists an L′-isomorphism between B and US which extends f. For each such S fix a particular L′-isomorphism g_{S}.

2. For each such S and L′-isomorphism g_{S} of B into (n, S, I, F), let N_{f,S} be a random variable such that N_{f,S}(M) is

\{ \begin{matrix}1 & if g_{S} is an (L-L′)-homomorphism over A mapping B onto US \\ 0 & otherwise. \end{matrix}

For W ⊆ n, let N_{f,W} = ∑{N_{f,S} : g_{S} : B → n and g_{S} ⊇ f and S ⊆ W }. Thus, N_{f,W} (M) is the number of (L-L′)-homomorphisms relative to A with image in W ⊆ M. If W = n, we write N_{f} for N_{f,W}.

3. We usually write μ_{f,W} for the expectation E(N_{f,W}).

Elaborating on the discussion preceding Definition 1.1.19, the function N actually depends on five variables, A, B, f, W and M. We interpret the function as the random variable N_{f,W} (M) or N_{f}(M) in the probability argument where A and B are fixed but we vary M and W. In the model theoretic argument, (Theorem 2.2.1), where W = n and we fix an expansion M, but deal with various choices for A and B, the notation N(f, A, B) is more useful.

2.1.5 Notation. 1. For any property Q of structures, in particular a first order property, the assertion, ‘for almost all sufficiently large M, M ⊧ Q’ (abbreviated a.a.) means ‘for every ϵ > 0 there is an N such that if n > N, p_{n}({M ∈ Ω_{n} : M ⊧ Q}) > 1 − ϵ’.

2. By an indicator random variable we mean one which takes values 0 or 1 and thus indicates a set.

3. We write f ∼ g if f = O(g) and g = O(f).

2.1.6 Lemma. For all sufficiently large n and all f : A → n, and any sufficiently large connected W ⊆ n the expectation

μ_{f,W} = E(N_{f,W}) ∼ |W |^{δ′(B/A)}n^{−r(B/A)}.

Proof. The probability of an L′-embedding of B ↾ L′ into (n, S, I, F) actually being an (L-L′)-homomorphism relative to A is n^{−r(A,B)}. By Lemma 2.1.3, the number of such embeddings has order of magnitude |W |^{δ′(B/A)}. Since expectation is additive this yields μ_{f,W} ∼ |W |^{δ′(B/A)}n^{−r(B/A)}. _{2.1.6}

2.1.7 Remark. If W = n this simplifies to

μ_{f} = E(N_{f}) ∼ n^{δ(B/A)}.

The main step in the proof that the axioms for semigenericity are almost surely true (Theorem 2.2.1) is the computation of the following estimates.

2.1.8 Theorem. Fix L-structures A ⊆ B with A ≤_{s} B. Let V be the event (which depends on c_{1}): for every L′-isomorphism f:A → n,

n^{δ(B/A)}(ln n)^{−(δ′(B/A)+1)} < N(f, A, B) = N_{f} < c_{1}n^{δ(B/A)}.  (3)

Then, for some choice of c_{1}

lim_{n→∞} P_{n}(V) = 1.

2.2 The estimates imply the 0-1 law

Before establishing the estimates in Theorem 2.1.8 we will show that they imply each of the axioms for semigenericity has limit probability 1. The derivation of the almost sure truth of the axioms (Theorem 2.2.1) from the estimates parallels the proof of Theorem 2.30 in [5]. Roughly, the program is to show that for A ≤_{s} B and for each L′-isomorphism f:A → n, the number of extensions of f to (L-L′)-homomorphisms of B relative to A is much greater than the number of such extensions which fail to witness the definition of semigenericity. This calculation is possible as the estimates of Theorem 2.1.8 show the number of copies of B over A depend on n^{δ(B/A)} and we will show that a ‘bad’ extension corresponds to a C with δ(C/A) < δ(B/A).

Recall that we denote the free join of B and C over A by B ⊗_{A} C (Notation 1.3.8). In the following theorem we estimate the probability than an expansion M of (n, S, I, F) satisfies an axiom ϕ_{A,B,C}^{m} from Definition 1.3.11, thereby fixing on C as a specific candidate for the isomorphism type of icl_{M}^{m}(fA).

2.2.1 Theorem. If A ≤_{s} B and A ≤_{i} C with |C| < m then

lim_{n→∞} P_{n}(ϕ_{A,B,C}^{m}) = 1.

Proof. For any f mapping C into n, and any (L-L′)-homomorphism f′ extending f to E, let B′ denote the free amalgam Scl_{M}^{m}(A)Scl^{m}(B − A) and E denote C ⊗_{A} B′, as at the end of Definition 1.3.9. We say (M, f′) fails as a witness for C, m, and f if M ∈ Ω_{n} and

1. f′ is not an (L-L′)-isomorphism (on B′-A) or

2. icl_{M}^{m}(f′B) ≠ Scl_{M}^{m}(f′B − fA) ∪ fC or

3. fC and Scl_{M}^{m}(f′B − fA) are not freely joined over Scl_{M}^{m}fA in M.

Each such failure is witnessed by an L-structure which extends B. We will show the number of extensions of f to a witness which violates one of these conditions is less than the lower bound on the number of extensions of f to B; thus there is an extension which does not fail any of the conditions.

Since we are trying to establish lim_{n→∞} P_{n}(ϕ_{A,B,C}^{m}) = 1, we may assume n is sufficiently large that the double inequality (3) of Theorem 2.1.8 counts the number of (L − L′)-homomorphisms into M over A.

Note that C ≤_{s} E and δ(B′/A) = δ(B/A) = δ(E/C). By the lower bound in Inequality (3), for each f,

|N(f, C, E)| > n^{δ(E/C)}(ln n)^{−c} = n^{δ(B′/A)}(ln n)^{−c}

where c = δ′(B′/A) + 1. Consider any F which is an expansion of E by adding additional (L-L′)-relations and violates condition 1) or 3). Then δ(F/C) = δ′(E/C) − r(F/C) and r(F/C) > r(E/C). By Inequality (3)

N(f, C, F) < c_{1}n^{δ(F/C)} ≤ c_{1}n^{δ(E/C)−α}.

For condition 2), it is clear that icl_{M}^{m}(f′B) ⊇ Scl_{M}^{m}(f′B − fA) ∪ fC. To show the containment is not proper, consider any D′ with f′B ≤_{i} D′ ⊆ M and |D′ − f′B| < m but such that D′ is not contained in Scl_{M}^{m}(f′B) ∪ fC. Then, δ(D′/f′B) < 0. We restrict our attention to a minimal such D′ and show there can be few extensions of f to maps with image isomorphic to D′. Any counterexample is a union of such minimal counterexamples; we show that there is an extension of f which cannot be extended to embed any minimal counterexample. Let B_{0} = {x ∈ CB : f′(x) ∈ D′}. Choose D ⊇ B_{0} such that D ∩ CB = B_{0} and D − (C − A) is isomorphic to D′ − (f′C − f′A). Then there is an (L-L′)-homomorphism from F = C ⊗_{B_{0}} D onto CD′. We will show the number of such homomorphisms is small. For this, we show a) C ≤_{s} F and b) δ(F/C) < δ(B/A). To verify a), clearly, for any X ⊆ F, δ(X/C) = δ(X/C∩B_{0}). But

δ(X/C ∩ B_{0}) = δ(X/X ∩ B) + δ(X ∩ B/C ∩ B_{0}).

If X is a proper subset of D, the first summand here is nonnegative and the second is strictly positive; the first by the minimality of D′, the second because A ≤_{s} B and B is free from C over A in F. For b), observe that δ(F/C) = δ(D/BC) + δ(B/C). But δ(D/BC) ≤ δ(D/B_{0}) < 0 and δ(B/C) = δ(B/A) by the choice of F so

δ(F/C) < δ(B/A) = δ(E/C).

Since C ≤_{s} F, by the upper bound in Inequality (3), a.a.

N(f, C, F) < c_{1}n^{δ(F/C)} ≤ c_{1}n^{δ(E/C)−α}.

So for each type of failure we have established the same bound. Now the number of isomorphism types of extensions of C that have failures (M, f′) is bounded in terms of the cardinality of A, B, and m; it does not depend on n. If this number is L, the total number of failures of any sort is less than

Ln^{δ(E/C)−α} < c_{2}n^{δ(E/C)}(ln n)^{−c}

for an appropriate constant c_{2}. Thus, the probability that for each f, one of the extensions of f witnesses ϕ_{A,B,C}^{m} tends to one as required. _{2.2.1}

As in Lemma 2.19 of [5], we directly derive from the upper bound estimate in Theorem 2.1.8 condition b) of Definition 2.0.6: the sentences asserting that if a ∈ icl_{M}(∅) then ¬R(a) (for any R ∈ L-L′) are almost surely true.

2.2.2 Corollary. If δ(B) < 0 then a.a. there is no embedding of B into M. In particular, the sentences asserting there is no L-structure on icl_{M}^{m}(∅) have probability 1.

This completes the application of the main model theoretic results of Section 1.1. We have shown that modulo the estimates in Theorem 2.1.8 the axioms Σ_{α} of the complete theory T_{α} are almost surely true.

2.3 Computing the Estimates

In this section we prove Theorem 2.1.8. We prove the upper and lower bounds on N_{f} = N(f, A, B) separately. We first, Theorem 2.3.5, prove directly the uniform upper bound on N_{f}. The proof of the lower bound, Theorem 2.3.8 is more circuitous. We split n into |A|·ln n·k equal size pieces W_{i} (for a k specified below) and compute a lower bound for each N_{f,W_{i}} and then combine them. In doing so we repeat the essence of the upper bound argument, now relativized to each W_{i}. This argument avoids the second moment argument used in Shelah-Spencer [17] and Baldwin-Shelah [5] and thus also provides a new proof of the Shelah-Spencer theorem.

For the original Shelah-Spencer theorem, the function δ(B) is interpreted as |B|−rα where r is the number of edges of the graph. Recall from Notation 2.0.5 that in our notation the α has been subsumed into r so δ(B) = δ′(B)−r. To read the following section as a proof of the Shelah-Spencer theorem, read δ′(B/A) as |B − A|.

For readability of formulas we make the following abbreviations. Note that v is natural for δ′(B/A) since in the case of pure sets δ′(B/A) is just the vertices in B − A; here it is the number of components of B − A (which don’t contain F or L). Similarly, r is the (weighted) number of realizations of the L-L′-relations. For reference we list here both some notations needed immediately; a further set are collected in Notation 2.3.9.

2.3.1 Notation. Let p = δ′(A), v = δ′(B/A) and r = r(B/A); so δ(B/A) = v − r. M is the bound on the number of disjoint embeddings of B over A; h = 3M|B|; k is chosen so that (1 − \frac{1}{4h})^{k} < (\frac{1}{e}). Thus, M, h and k are constants which depend only on the structures A and B.

With these substitutions the theorem becomes:

Theorem 2.3.2 (Theorem 2.1.8–estimate form). Fix L-structures A ⊆ B with A ≤_{s} B. Let V be the event (which depends on c_{1}): for every L′-isomorphism f:A → n,

n^{v−r}(ln n)^{−(v+1)} < N_{f} < c_{1}n^{v−r}.  (4)

Then, for some choice of c_{1}

lim_{n→∞} P_{n}(V) = 1.

We require the following definition to organize the argument.

2.3.3 Definition. B is called a primitive extension of A, if δ(B/A) > 0 and δ(B/A_{1}) ≤ 0 for each A_{1} with A ⊂ A_{1} ⊆ B.

An easy induction shows that it suffices to prove Theorem 2.1.8 for primitive extensions. Thus, we fix L-structures A ⊆ B with B a primitive extension of A. In particular, A is L′-closed in B.

The following observations are used repeatedly in both the upper and lower bound side of the proof. Let for i ∈ I, X_{i} be an indicator random variable for the event A_{i}. Suppose Y = Σ_{i∈I}X_{i}. Then, P_{n}(⋃_{i∈I} A_{i}) = P_{n}(Y ≥ 1) ≤ E(Y), by Markov’s inequality. Moreover if each A_{i} has the same probability g(n), E(Y) = |I| · g(n).

The next lemma plays a key role in both the upper and lower bound arguments.

2.3.4 Lemma. There is an M depending only on A and B such that with probability 1, if N(f, A, B) = t, there is a set of s = \frac{t}{M|B|} extensions of f whose ranges intersect in f(A).

Proof. Since B is a primitive extension of A, (Ab) ≤_{i} B for any b ∈ B − A. Thus, by Lemmas 2.2.2 and 1.3.1 we may assume S6 (1.1.20): for some constant M there are fewer than M extensions g_{i} with any fixed image of b. The range of each extension g_{i} can intersect at most M|B| other extensions so if N(f, A, B) = t, there is a set of s = t/M|B| extensions of f whose ranges intersect in f(A).

2.3.4

The next argument is the same as in [17].

2.3.5 Theorem. Fix L-structures A ⊆ B with B primitive over A. Let V_{u} (i.e. V_{upper}) be the event: for every L′-isomorphism f:A → n,

N_{f} = N(f, A, B) < c_{1}n^{v}n^{−r}.  (5)

Then, with c_{1} = 3M|B| (M from Lemma 2.3.4),

lim_{n→∞} P_{n}(V_{u}) = 1.

Proof. By Lemma 2.3.4, if N(f, A, B) = t, there is a set of s = \frac{t}{M|B|} disjoint extensions of f. There are less than n^{p}(n^{vs}/s!) pairs of an L′-embedding f taking A into n and a set of s extensions (disjoint over rng f) ⟨g_{1}, … g_{s}⟩ each taking B into n. The probability that each of the g_{i} is an (L-L′)-homomorphism relative to fA is n^{−r} so (via Markov) the probability of such a pair of an L′- embedding and s homomorphisms is at most \frac{n^{p}(n^{vs}n^{−rs})}{s!}. By Stirling’s formula,

\frac{n^{p}(n^{vs}n^{−rs})}{s!} ≤ \frac{n^{p}(en^{v})^{s}n^{−rs}}{s^{s+1/2}}

which tends to 0 if s ≥ 3n^{δ(B/A)} = 3n^{v−r}. (Observe that for such s, n^{p}(\frac{e}{3})^{s} tends to 0 as n tends to infinity.) Thus, a.a. for each f, s < 3n^{v}n^{−r}. In particular, a.a. for each f,

N_{f} ≤ 3M|B|n^{v}n^{−r}

which is the required upper bound with c_{1} = 3M|B|. _{2.3.5}

2.3.6 Remark. The following argument for the lower bound is motivated by a standard technique pointed out, for example, in Bollobas ([8]). If X is a random variable with 0 < X < c and E(X) = μ then for any b with 0 < b < μ,

P (X > b) ≥ \frac{μ − b}{c − b}.  (6)

We have established an upper bound with probability 1. The next argument is motivated by the idea of just plugging that bound into Equation 6. However, since the upper bound is only probabilistic, we actually have to look into the proof of Theorem 2.3.5 and employ again the key to the upper bound argument – the replacement of arbitrary embeddings by embeddings that are almost disjoint. Our situation differs from the standard case in several ways. We consider a family of measure spaces and instead of a constant upper bound, the upper bound is a constant times the mean. Moreover, this upper bound is obtained not absolutely but with probability one. A simple calculation with the definition of expectation shows a variant of Equation 6.

2.3.7 Fact. Let Y be a real valued random variable. If E(Y) = μ and 0 < Y < hμ for some constant h then for 0 < b < μ,

P (X > b) ≥ \frac{μ − b}{hμ − b} − Σ_{t>hμ}(t − b)P (Y = t).  (7)

2.3.8 Theorem. Fix L-structures A ⊆ B with B primitive over A. Let V_{ℓ} (i.e. V_{lower}) be the event (which depends on d): for every L′-isomorphism f:A → n,

d · n^{v−r}(ln n)^{−(v+1)} < N_{f}.  (8)

Then, for some choice of d

lim_{n→∞} P_{n}(V_{ℓ}) = 1.

Proof. We have fixed A and B. We first work with an arbitrary connected segment W of n and fix b with 0 < b < μ_{f,W}. For each f mapping A into n, we first calculate a lower bound on the probability that the number of extensions of f mapping into a subset W of n is greater than b. Then we will specify the cardinality of W and our precise choice of b for the final portion of the argument.

Applying Lemma 2.3.4, as in the upper bound argument, if there are t embeddings, there are s = \frac{t}{M|B|} whose ranges intersect in the range of f. Now t varies through the values of N_{f,W}, which by Lemma 2.1.3 is always at most |W |^{v}. Thus, invoking Markov’s inequality,

P (N_{f,W} = t) = P (N_{f,W} = M|B|s) ≤ |W |^{vs}n^{−rs}/s!.  (9)

In contrast to the upper bound argument, we treat each f separately for the moment. By Stirling’s formula, for each s, the right hand side of Inequality 9 is less than

\frac{(e|W |^{v})^{s}n^{−rs}}{s^{s+1/2}} .

For s satisfying

|W |^{v} ≥ s ≥ 3|B||W |^{v}n^{−r},

s^{s+1/2} dominates (3 · |W |^{v}n^{−r})^{s+1/2} and (|W |^{v}n^{−r})^{s+1/2} dominates |W |^{vs}n^{−rs}. This yields, for an appropriate constant c_{2},

P (N_{f,W} = t) ≤ c_{2} · (\frac{e}{3})^{s} ≤ c_{2}(\frac{e}{3})^{|W |^{v}n^{−r}}.

Recall μ_{f,W} ∼ |W |^{δ′(B/A)}n^{−r(B/A)} ∼ |W |^{v}n^{−r}. We now apply Equation 7

with h = 3M|B|, μ = μ_{f,W}, and b = \frac{μ_{f,W}}{p · [1 + n] · k} where p = δ′(A) (k is ex-

plained later). This yields:

P (b ≤ N_{f,W}) ≥ \frac{μ_{f,W} − b}{hμ_{f,W} − b} − ∑_{t>hμ_{f,W}} (t − b) · P (N_{f,W} = t). (10)

Consider the second term on the right hand side of Equation 10. There are at most |W |^{v} summands in the following sum and each t − b is at most |W |^{v} (since each t is a number less than |W |^{v}); so

∑_{t>3M|B|μ_{f,W}} (t − b) · P (N_{f,W} = t) ≤ c_{2} · |W |^{2v} · (\frac{e}{3})^{|W |^{v}n^{−r}}.  (11)

This completes the analysis for fixed W; we will now divide n into R(n) equally sized pieces W_{i}. We will want to show that the right hand side of Equation 14 raised to the R and multiplied by n^{p} tends to 0. To that end we make the following choices.

2.3.9 Notation. Choose k so that (1 − \frac{1}{4h})^{k} < (\frac{1}{e}). (This choice will be used to evaluate the right hand side of Equation 15; the necessity for this step was pointed out to me by Jim Lynch.) Let R = [1 + ln n] · p · k. Choose R disjoint connected subsets ⟨W_{i} : i < R⟩ of n, each with cardinality approximately \frac{n}{R}. (More precisely with cardinality [\frac{n−|A|}{R}].) Let b = \frac{μ_{f,|W_{i}|}}{R} = n^{v−r} · R^{−(v+1)}. The computation of μ_{f,W} depends only on the cardinality of W so it makes sense to write μ_{f,|W_{i}|}.

The key idea here is the choice of R so that with |W_{i}| = \frac{n}{R},

\frac{μ_{f,|W_{i}|}}{R} = \frac{μ_{f}}{R^{−(v+1)}}

and then choosing b as that common value for applying Fact 2.3.7.

Recall that V_{ℓ}(d) is the event that for all f, N_{f} > d · b. There are n^{p} choices for f so

P (V_{ℓ}) ≥ 1 − n^{p} · P (N_{f} < d · \frac{n^{v−r}}{R^{v+1}} ).  (12)

If N_{f} < d · \frac{n^{v−r}}{R^{v+1}} then certainly for each i, N_{f,W_{i}} < d · \frac{n^{v−r}}{R^{v+1}} . Since the N_{f,W_{i}} are independent,

P (N_{f} < d · \frac{n^{v−r}}{R^{v+1}} ) ≤ [P (N_{f,W_{i}} < d · \frac{n^{v−r}}{R^{v+1}} )]^{R}.  (13)

Rewrite Equation 10, using Equation 11, (and replacing b by db)

P (N_{f,W} ≤ db) ≤ 1 − (\frac{μ_{f,W} − db}{hμ_{f,W} − db} − c_{2} · |W |^{2v} · (\frac{e}{3})^{|W |^{v}n^{−e}}).  (14)

Now combining inequalities 12,13, and 14, since we chose |W_{i}| as \frac{n}{R} and b as \frac{μ_{f,|W_{i}|}}{R} = n^{v−r} · R^{−(v+1)}, we get

P (V_{ℓ}) ≥ 1 − [|n|^{p} · (1 − (\frac{1 − \frac{d}{R}}{h − \frac{d}{R}} − c_{2}(\frac{n}{R})^{2v} · (\frac{e}{3})^{( \frac{n}{R})^{v}n^{−r}}))^{R}] .  (15)

The right hand side of this expression goes to one. More specifically, for sufficiently large n,

c_{2}(\frac{n}{R})^{2v} · (\frac{e}{3})^{( \frac{n}{R})^{v}n^{−r}} < \frac{1}{4h}.

More easily

\frac{1 − \frac{d}{R}}{h − \frac{d}{R}} > \frac{1}{2h}.

Thus,

1 − (\frac{1 − \frac{d}{R}}{h − \frac{d}{R}} − c_{2}(\frac{n}{R})^{2v} · (\frac{e}{3})^{( \frac{n}{R})^{v}n^{−r}}) ≤ 1 − \frac{1}{4h}.

We deduce from R = [1 + ln n] · |A| · k and (1 − \frac{1}{4h})^{k} < (\frac{1}{e})^{p+1} and |A| ≥ p that n^{p}((1 − \frac{1}{4h})^{k})^{R} tends to 0. Thus, P (V_{ℓ}) tends to 1, i.e. a.a for all f, N_{f} ≥ b.

Recall that b = \frac{n^{v−r}}{R^{(v+1)}} . Since R = p · ln n · k (where p = |A| and k does not depend on n), incorporating p · k^{−(v+1)} in the constant d, we get the required result: a.a for all f

N_{f} > d\frac{n^{v−r}}{(ln n)^{(v+1)}} .

2.3.8

Proof of Theorem 2.1.8: We have established the estimates if B is primitive over A. The induction for arbitrary B with A ≤_{s} B is routine. _{2.1.8}

This completes the proof of the estimates and so establishes that each of the axioms of the complete theory T_{α} is almost surely true; thus we have the 0-1 law.

3 Further Problems

There are several natural directions for generalization of this work. The most obvious is to try to find a 0-1 law for expansions of vector spaces (a result we originally thought we had proved). The difficulty in carrying out the analogous proof to the successor case arises because the probability depends on the size of the universe n = q^{r} while the dimension function depends on the size r of a basis. The fact that one grows exponentially faster than the other prevents the identity \frac{μ_{f,W}}{ln n} = \frac{μ_{f}}{(ln n)^{v+1}} , which was key to our argument. This same difficulty prevents using the Shelah-Spencer [17] approach: the argument reducing probability of a bad map from less than 1/2 to probability 0 ([17, 5]) fails for similar reasons. We have only recently learned of a (rather old) argument by Spencer [18] invoking Janson’s inequalities to show that in the [17] that the lower bound on N_{f} is actually a constant times μ_{f}. One line would be to see if this argument remains valid in the vector space context.

There is the question of extending the model theoretic results of Section 1. A minor goal would be to make them fully axiomatic. A more important aim would be to consider the non-modular case. Even with rational coefficients expansion of fields while preserving rank has involved significant algebraic geometry.

Our procedure can be viewed as a way of generating new weight functions satisfying W1 and W2 from old ones. One could attempt to give a general formulation of this procedure. One difficulty is that the expansions with irrational coefficients do not give geometric dimension functions so the iteration breaks down unless the aims are reduced.

Finally, one can ask whether is there is a more general formulation of the counting argument in Subsection 2.3; even, perhaps, one which moves away from the 0-1 context altogether.

References

[1] Roman Aref’ev, J.T. Baldwin, and M. Mazzucco. δ-invariant amalgamation classes. Journal of Symbolic Logic, 64:1743–1750, 1999.

[2] J. T. Baldwin. Near model completeness and 0-1-laws. In R. Boppana and James Lynch, editors, Proceedings of the DIMACS Workshop on Logic and Random Structures: 1995. American Mathematical Society, 1997.

[3] John T. Baldwin. Rank and homogeneous structures. In Katrin Tent, editor, Tits Buildings and the Theory of Groups Wurzburg Sept 14-17 2000. Cambridge University Press, 2002.

[4] J.T. Baldwin. Random expansions of geometries. Original version on web: www.uic.edu/ jbaldwin.

[5] J.T. Baldwin and S. Shelah. Randomness and semigenericity. Transactions of the American Mathematical Society, 349:1359–1376, 1997.

[6] J.T. Baldwin and S. Shelah. DOP and FCP in generic structures. Journal of Symbolic Logic, 63:427–439, 1998.

[7] J.T. Baldwin and Niandong Shi. Stable generic structures. Annals of Pure and Applied Logic, 79:1–35, 1996.

[8] Béla Bollobas. Extremal Graph Theory with Emphasis on Probabilistic Methods. American Mathematical Society, 1986. Conference Board of the Mathematical Sciences regional conference series; number 62.

[9] E. Hrushovski. Simplicity and the Lascar group. preprint.

[10] T. Hyttinen. Canonical finite diagrams and quantifier elimination. Canonical F Mathematical Logic Quarterly, 48:533–554, 2002.

[11] J. Lynch. Almost sure theories. Annals of Pure and Applied Logic, 18:91– 135, 1980.

[12] J. Lynch. Probabilities of sentences about very sparse random graphs. Random Structures and Algorithms, 3:33–53, 1992.

[13] M. Pourmahdian. Simple Generic Theories. PhD thesis, Oxford University, 2000.

[14] E. Rosen, S. Shelah, and S. Weinstein. k-universal finite graphs. In R. Boppana and James Lynch, editors, Proceedings of the DIMACS Workshop on Logic and Random Structures: 1995. American Mathematical Society, 1996.

[15] S. Shelah. 0-1 laws. preprint 550, 200?

[16] S. Shelah. Zero-one laws with probability varying with decaying distance. Shelah 467, 200?

[17] S. Shelah and J. Spencer. Zero-one laws for sparse random graphs. Journal of A.M.S., 1:97–115, 1988.

[18] J. Spencer. Counting extensions. Journal of Combinatorial Theory A, 55:247–255, 1990.

[19] B.I. Zil’ber. Uncountably Categorical Theories. Translations of the American Mathematical Society. American Mathematical Society, 1991.