Determined Theories and Limit Laws

John T. Baldwin^{∗} Marco Mazzucco^{†}

Department of Mathematics Statistics and Computer Science,

Laboratory for Advanced Computing University of Illinois in Chicago

May 12, 2001

Abstract

We provide a new model theoretic technique for proving 0-1 and convergence laws. As an application, we obtain a new (slightly less computational) proof of convergence laws due to Spencer and Thoma for the probability functions: p_{n}^{l} = \frac{ln(n)}{n} + \frac{l·ln(ln(n))}{n} + \frac{c}{n}.

1 Introduction

Consider the class K_{n} of all graphs on the set of vertices {1, 2, ...n}. One can define a probability space on K_{n} by assigning each graph in K_{n} equal probability, to form a uniform probability space. Fagin [5] proved that the probability of any property expressible in first order logic holding of a graph in K_{n} converges to 0 or 1 as n goes to infinity. We say that first order logic has a 0-1 law for the uniform probability space on finite graphs.

A probability space can be formed from the class K_{n} by assigning a probability p_{n} to the existance of an edge between any two vertices. Given a sentence ϕ, let p_{n}(ϕ) be the probability that ϕ is satisfied by a graph in K_{n}. In the case studied by Fagin, the uniform probability is induced by an edge probability of 1/2. A family of edge measures p_{n}, {p_{n}}, on graphs of size n obeys a 0-1 law (for first order logic) if for each first order sentence ϕ, lim_{n→∞} p_{n}(ϕ) is either 0 or 1. More generally the family p_{n} has a convergence law if each such limit converges.

∗Partially supported by NSF grant DMS-9893496.

†This paper is part of Mazzucco’s 2000 Ph.D. thesis at University of Illinois in Chicago.

Both authors thank the Mittag-Leffler institute for partial support during the fall of 2000.

Definition 1.1 Given a family of edge measures p_{n}, the almost sure theory T h is the set of sentences ϕ such that lim_{n→∞} p_{n}(ϕ) = 1. We refer to the models of T h as the limit models.

Notice that the almost sure theory is complete if and only if first order logic has a 0-1 law for {p_{n}}. We are concerned with the various methods used to prove 0-1 laws. Let L be the language of symmetric irreflexive graphs. One method is to prove the 0-1 law by induction on the complexity of L-formulas. Another method is to show that the almost sure theory T h is complete. In the case of uniform probability, this can be accomplished by proving that T h is ℵ_{0}- categorical. More generally one can show that all countable models of T h are elementarily equivalent. This can be done by the use of quantifier elimination or Ehrenfeucht-games.

Shelah and Spencer [6] proved the 0-1 law for first order logic with edge probability p_{n} = n^{−α} for irrational α, 0 < α < 1. Baldwin and Shelah [4] provided an alternative proof, without using Ehrehfreuht-games or quantifier elimination arguments to show completeness. Baldwin [3] abstracted this argument into the definition of a determined theory. In this paper, we generalize this method to deal with convergence. We use it to give a new proof of convergence for the edge probability p_{n}^{l} studied by Thoma and Spencer in [7]:

p_{n}^{l} = \frac{ln(n)}{n} + \frac{l · ln(ln(n))}{n} + \frac{c}{n}

where l is a arbitrary fixed nonnegative integer, and c is a positive constant.

Our interest in these edge measures arose from the fact that the limit models induced from the family {p_{n}^{l}} are similar to the limit models of the almost sure theories considered in [1], [2]. In particular, limit models are rather simple from a model theoretic standpoint. They decompose into components which are ‘almost’ trees; the completions of the almost sure theory can be seen to be ωstable. In this range of probabilities, the parameter l determines the possibility of the limit model admitting an ‘r-isolated point’, a vertex of degree r. There is none if r < l and infinitely many if r > l, but for r = l, the number of vertices of degree r is not determined. In essence, fixing this number determines a completion of the almost sure theory. Each completion is finitely axiomatizable over T h, so the probability of each completions can be computed, which in turn, allows one to compute the probability for each sentence in L.

Spencer and Thoma proved:

Theorem 1.2 1. A graph G satisfies the almost sure theory T h_{l} for p_{n}^{l} iff:

(a) For all finite A in G, the number of vertices in A is strictly less than the number of edges.

(b) For all t ≥ 1 and m ≥ 3, t copies of an m-cycle can be embedded in G.

(c) For all integers r, s, t ≥ 0, s ≥ r, there does not exist a pair of vertices x, y ∈ G such that x has degree r and y has degree s and the distance from x to y is equal to t.

(d) For all integers r, t ≥ 0 and m ≥ 3 there does not exist a vertex x ∈ G of degree r that is of distance t from an m-cycle.

(e) For all integers r, 0 ≤ r < l, there does not exist a vertex of degree r ∈ G.

(f) For all integers t ≥ 1 and r > l, there exist t vertices of degree r ∈ G.

2. Moreover, for any integer s, if the sentence σ_{l,s} asserts“there exist precisely s vertices of degree l”, lim_{n→∞} p_{n}^{l}(σ_{l,s}) exists.

3. For each l and s, T h_{l} ∪ σ_{l,s} is complete.

From this analysis of graphs they established a convergence law for edge probability p_{n}^{l}.

Theorem 1.3 Let lim_{n→∞}p_{n}^{l}(σ_{l,s}) = q_{l,s}. Then for any L-sentence θ, there exists a finite set I of nonnegative integers such that lim_{n→∞}p_{n}^{l}(θ) = Σ_{i∈I}q_{l,i} or lim_{n→∞}p_{n}^{l}(θ) = 1 − Σ_{i∈I}q_{l,i}

This paper is a step in isolating the ‘model theoretic’ from the ‘probabilistic’ components of proofs of limit laws on finite models. In Section 2 we give a general definition of an indexed closure operator and a determined theory. Relying on the probability arguments of Spencer and Thoma for parts 1 and 2 of Theorem 1.2, we give in Section 3 a different model theoretic proof of part 3 of Theorem 1.2 and of Theorem 1.3. In particular, the fact (and computation showing it) that Σ_{i<ω}q_{l,i} = 1 which is a part of the Spencer-Thoma argument is avoided here.

We write Mod(T) for the class of models of a theory T. The collection of finite subsets of a set X is denoted by S_{ω}(X). For any model M, and for any \overline{a} ∈ M^{r}, θ(M, \overline{a}) denotes the set of solutions of θ(x, \overline{a}) in M. We denote the length of a tuple \overline{a} by lg(\overline{a}).

2 Indexed closure and determined theories

The key to the method of determined theories is a way of breaking the algebraic closure of a finite set into a (possibly infinite) sequence of finite sets by using an indexed closure operator. We give here a general notion of such a closure operator and use it to provide a method to prove not only 0-1 but also convergence laws. The closure operator of Definition 2.2 which is used in Section 3 to prove Theorem 3.15 and Theorem 3.17 is a special case.

If cl is a function from ω × S_{ω}(M) → S_{ω}(M), we write cl_{M}^{i}(\overline{a}) for cl(i, \overline{a}).

Definition 2.1 An indexed closure operator Cl for a theory T is a function, which for each M ⊧ T, maps ω × S_{ω}(M) → S_{ω}(M) and has the following properties.

1. For any model M ∈ Mod(T) and \overline{a} ⊆ \overline{b} ∈ M, for j < i < ω, cl_{M}^{j}(\overline{a}) ⊆ cl_{M}^{i}(\overline{a}) and cl_{M}^{i}(\overline{a}) ⊆ cl_{M}^{i}(\overline{b}).

2. For any M, N ∈ Mod(T), if for some s, cl_{M}^{s}(∅) ≃ cl_{N}^{s}(∅) then for all 0 ≤ i ≤ s, cl_{N}^{i}(∅) ≃ cl_{M}^{i}(∅).

We extend the notation by writing cl_{M}^{ω}(\overline{a}) for ∪_{i<ω}cl_{M}^{i}(\overline{a}). In the example considered in this paper, for all M ∈ Mod(T), there exists a k < ω, such that for all s > k, cl_{M}^{k}(\overline{a}) = cl_{M}^{s}(\overline{a}) so cl_{M}^{ω}(\overline{a}) = cl_{M}^{k}(\overline{a}) = acl_{M}(\overline{a}). Following is the indexed closure operator we will use in this paper. While it provides a natural way to ‘layer’ the algebraic closure, there is an unfortunate lack of monotonicity, described in Example 3.5, which require us to treat closure over the empty set with special care.

Definition 2.2 For k ≤ ω, let the k-closure of \overline{a} in M, cl_{M}^{k}(\overline{a}), be the set of solutions in M of all the formulas θ(x, \overline{a}) where the quantifier rank of θ and |θ(M, \overline{a})| are each less than k.

The following fact, shown by straightforward calculatio [4], is fundamental for the kind of argument used here.

Lemma 2.3 For any first order T in a finite relational language. there exists a function f of |A|, m, n, such that for any M ⊧ T h_{l} and any embedding of A into M, cl_{M}^{m}(cl^{n}(A)) ⊆ cl_{M}^{f(|A|,m,n)}(A).

Definition 2.4 1. We write ≃ for isomorphism. We say cl_{M}^{k}(\overline{a}) ≃^{s} cl_{M′}^{k}(\overline{a}′) if cl_{M}^{k}(\overline{a}) ≃ cl_{M′}^{k}(\overline{a}′) by an isomorphism taking \overline{a} to \overline{a}′ and cl_{M}^{k}(∅) ≃ cl_{M′}^{k}(∅)

2. For an integer k and a theory T, a formula θ(\overline{x}) is determined by its kclosure in T if for any M, M′ ⊧ T and for any \overline{a} ∈ M^{r} and \overline{a}′ ∈ M′^{r}, if cl_{M}^{k}(\overline{a}) ≃^{s} cl_{M′}^{k}(\overline{a}′), then M ⊧ θ(\overline{a}) if and only if M′ ⊧ θ(\overline{a}′).

3. The theory T is determined if for any formula θ(\overline{x}), there is an integer k_{θ} such that θ(\overline{x}) is determined by its k_{θ}-closure in T.

3 An Application

In this section we consider the almost sure theory studied by Spencer and Thoma in [7], whose axioms are the theory T h_{l} of the introduction. Let T h_{l,s} denote the theory which consists of T h_{l} plus the axiom “there exists s isolated vertices of degree l” and T h_{l}^{>0} denote the theory which consists of T h_{l} plus the axiom “there exists an isolated vertex of degree l”.

Notation 3.1 A tree in which every vertex has infinite degree is denoted by T and called a complete tree. A hairy cycle is a cycle with a complete tree attached to every vertex of the cycle. Let H_{n} denote a hairy cycle whose cycle is of size n. An isolated component, denoted I_{n} is a tree which contains one point with degree n and all others have infinite degree.

As was pointed out in [7] it is easy to check that each model of T h_{l} is a direct sum of the following components:

1. For every integer i greater than one, infinitely many components each containing one cycle of size i and every vertex has infinite degree.

2. For every r > l, infinitely many components which do not contain a cycle and every vertex has infinite degree except one, which has degree r.

3. Any (possibly finite) number of components which do not contain a cycle and every vertex has infinite degree.

4. For some s > 0, s copies of components which do not contain a cycle and every vertex has infinite degree except one vertex which has degree l.

More formally:

Lemma 3.2 Let M be a countable model of T h_{l}, then there exists an s, 0 ≤ s < ω, and j, 0 ≤ j ≤ ω, such that M has the following form:

Σ_{1<i<ω}H_{i}^{(ω)} ⊕ Σ_{l<i<ω}I_{i}^{(ω)} ⊕ T^{(j)} ⊕ I_{l}^{(s)}

For 0 ≤ s ≤ ω, we denote the model with the form above and s copies of I_{l} by M_{s}.

Remark 3.3 From Lemma 3.2 we observe the following facts about algebraic closure. For any model M of T h_{l,s} with s < ω:

1. acl_{M}(∅) consists of the isolated vertices of degree l, and their neighbors.

2. acl_{M}(a) = acl_{M}(∅) unless a is on component which contains a cycle or an isolated point.

(a) In the first case acl_{M}(a) is the union of acl_{M}(∅) with all points on the path from a to the cycle.

(b) In the second case acl_{M}(a) is the union of acl_{M}(∅) with all points on the path from a to the isolated point.

3. acl_{M}(a, b) = acl_{M}(a)∪acl_{M}(b) unless a and b are on the same component; in that case it also includes all points on the path from a to b.

4. For any set A, acl_{M}(A) = ⋃_{a,b∈A} acl_{M}(a, b).

Definition 3.4 Let G_{n}^{l}, for n > 0, be the direct sum of n components, each consisting of one vertex with l neighbors. To ease notation, define G_{ω}^{l} to be equal to the empty set.

It is easy to see that for any M ⊧ T h_{l}^{>0}, there exists an s, 0 < s ≤ ω such that cl_{M}^{ω}(∅) ≃ G_{s}^{l} ≃ cl_{M}^{t}(∅) for t ≥ s. The following property of k-closure in models of T h_{l} is crucial. Let M be a model of T h_{l}, and let n = |acl_{M}(∅)|; if k < n, cl_{M}^{k}(∅) ≃ ∅. So, if M_{0} models T h_{l,0}, cl_{M}^{k}(∅) ≃ ∅ ≃ cl_{M_{0}}^{k}(∅). In particular, for any k < ω we have cl_{M_{ω}}^{k}(∅) ≃ ∅ ≃ cl_{M_{0}}^{k}(∅) and M_{ω} ≢ M_{0}. Thus the theory T h_{l} is not determined. However, we will show that T h_{l,0} and T h_{l}^{>0} are each determined with respect to our notion of closure.

The following example shows why we had to treat the closure of the empty set in a special way in Definition 2.4. It could easily be modified to show the theories in question were not determined if we omitted this special case.

Example 3.5 Consider the models M_{1} and M_{2} with the notation set after Lemma 3.2. Let a and a′ be neighbors of neighbors of isolated vertices in M_{1} and M_{2} respectively. Then the l + 2 closure of a and the l + 2 closure of a′ are isomorphic. Both consist of the neighbors of the isolated point near a, (a′) respectively. But the l + 2 closure of the empty set is empty in M_{2} and contains the neighbors of the isolated point in M_{1}.

Notation 3.6 We adopt the following notation. For any a in M, let C_{M}(\overline{a}) be the union of the components in M which intersect \overline{a}. Denote the number of free variables plus the quantifier rank of a formula θ by qr^{∗}(θ).

Definition 3.7 If θ(\overline{y}) is quantifier free, k_{θ} = (l + 1) · lg(\overline{y}). If θ(\overline{y}) is the formula (∃x)ϕ(x, \overline{y}) let k_{θ} be the least integer k > max(3k_{ϕ}, (l + 1)qr^{∗}(ϕ)) and such that for for any element b in cl^{k_{ϕ}}(\overline{a}), cl^{k_{ϕ}}(b, \overline{a}) ⊆ cl^{k_{θ}}(\overline{a}).

Our main induction concerns a formula ϕ(x, \overline{y}); we denote ∃xϕ(x, \overline{y}) by θ(\overline{y}).

The condition k_{θ} > (l + 1)qr^{∗}(ϕ) guarantees that if cl_{M}^{k_{θ}}(∅) ≃ cl_{M′}^{k_{θ}}(∅) and they each contain an isolated point, then they contain the same number of isolated points.

The main result is to show in Theorem 3.9 that the theories T h_{l}^{>0} and T h_{l,0} are determined. This argument is simply a different way to organize the backand-forth argument showing each T h_{l,s} is complete. We require one technical definition.

Definition 3.8 For any M and \overline{a}, b ∈ M, let d(b, cl_{M}^{k_{ϕ}}(\overline{a})) be the shortest distance from b to cl_{M}^{k}(\overline{a}). For any M and \overline{a} ∈ M, let

D_{M,\overline{a}}^{ϕ} = max\{d(b, cl_{M}^{k_{θ}}(\overline{a})) : b ∈ ϕ(M, \overline{a})\}

.

Theorem 3.9 Suppose both M and M′ are models of T h_{l}^{>0} or both are models of T h_{l,0}. For any θ(\overline{x}) in L (with arity r), and any \overline{a}, \overline{a} in M^{r} and M′^{r} respectively, there exists k_{θ} such that if cl_{M}^{k_{θ}}(\overline{a}) ≃^{s} cl_{M′}^{k_{θ}}(\overline{a}′) then M ⊧ θ(\overline{a}) if and only if M′ ⊧ θ(\overline{a}′).

Proof: The lemma follows by induction on the complexity of formulas. Let θ(\overline{y}) = ∃xϕ(x; \overline{y}). Choose k_{θ} as in Definition 3.7. Let \overline{a}, \overline{a}′ be in M and M′ respectively. We need to show, if cl_{M}^{k_{θ}}(\overline{a}) ≃^{s} cl_{M′}^{k_{θ}}(\overline{a}′) and θ(\overline{a}) holds in M, then we can choose b, satisfying ϕ(x, \overline{a}), such that there exists b′ for which cl_{M}^{k_{ϕ}}(\overline{a}, b) ≃^{s} cl_{M′}^{k_{ϕ}}(\overline{a}′, b′) (equivalently, since cl_{M}^{k_{θ}}(\overline{a}) ≃^{s} cl_{M′}^{k_{θ}}(\overline{a}′), cl_{M}^{k_{ϕ}}(\overline{a}, b) ≃ cl_{M′}^{k_{ϕ}}(\overline{a}′, b′)) whence by induction M ⊧ ϕ(b, \overline{a}) if and only if M′ ⊧ ϕ(b′, \overline{a}′).

Now, all possible cases are handled by the next 4 lemmas. The major division depends on whether D_{M,\overline{a}}^{ϕ} > k_{ϕ}. Within each side of this dichotomy, there are several cases depending on the disjoint cases: cl^{k_{ϕ}}(b) is {b}, or contains a cycle, or contains an isolated point.

First we consider the case where D_{M,\overline{a}}^{ϕ} is large and cl^{k_{ϕ}}(b) is either \{b\} or contains a cycle.

Lemma 3.10 Let M, M′ ⊧ T h_{l} and \overline{a} ∈ M^{r}. Suppose D_{M,\overline{a}}^{ϕ} > k_{ϕ}. Fix b ∈ M

for which d(b, cl_{M}^{k_{θ}}(\overline{a})) = D_{M,\overline{a}}^{ϕ}. Suppose cl_{M}^{k_{ϕ}}(b) = \{b\} or cl_{M}^{k_{ϕ}}(b) contains a

cycle. If cl_{M}^{k_{θ}}(\overline{a}) ≃^{s} cl_{M′}^{k_{θ}}(\overline{a}′), there exists a b′ ∈ M′ such that cl_{M}^{k_{ϕ}}(\overline{a}, b) ≃^{s} cl_{M′}^{k_{ϕ}}(\overline{a}′, b′).

Proof: By assumption, cl_{M}^{k_{ϕ}}(b) is either just b or the vertex b and a cycle of cardinality less than k_{ϕ} and the vertices on a path, of length less than k_{ϕ}, from b to this cycle. In the first case, choose b′ to be a vertex of infinite degree, on a component which does not intersect \overline{a}′. In the second case, choose one of the infinitely many components in M′ which contains an n-cycle and does not intersect \overline{a}′, and choose b′ on this component with the same distance from the n-cycle as b is from the n-cycle on the component where b resides. In both cases, the result follows since cl^{k_{ϕ}}(\overline{a}, b) = cl^{k_{ϕ}}(\overline{a}) ∪ cl^{k_{ϕ}}(b) and similarly for \overline{a}′, b′. □

Now we consider the case where D_{M,\overline{a}}^{ϕ} is large and cl^{k_{ϕ}}(b) contains an isolated point. There are two traps which must be avoided in the following proof: M = M_{ω} and M′ = M_{0}, M = M_{i} and M′ = M_{j} where j is much greater than k_{θ} is much greater than i. We avoid the first by restricting to T h_{l}^{>0}; this is permissible since there are no isolated points in models of T h_{l,0} and so the case can occur only for T h_{l}^{>0}. The second is dealt with by using ≃^{s}.

Lemma 3.11 Let M, M′ ⊧ T h_{l}^{>0} and \overline{a} ∈ M^{r}. Suppose D_{M,\overline{a}}^{ϕ} > k_{ϕ}. Fix b ∈ M for which d(b, cl_{M}^{k_{θ}}(\overline{a})) = D_{M,\overline{a}}^{ϕ}. Suppose there is an isolated vertex contained in cl_{M}^{k_{ϕ}}(b). If cl_{M}^{k_{θ}}(\overline{a}) ≃^{s} cl_{M′}^{k_{θ}}(\overline{a}′), there exists a b′ ∈ M′ such that cl_{M}^{k_{ϕ}}(\overline{a}, b) ≃^{s} cl_{M′}^{k_{ϕ}}(\overline{a}′, b′).

Proof. Since D_{M,\overline{a}}^{ϕ} > k_{ϕ}, cl_{M}^{k_{ϕ}}(\overline{a}, b) = cl_{M}^{k_{ϕ}}(\overline{a}, b) ∪ c_{M}^{k_{ϕ}}(b). If there is an isolated point c′ in M′ − cl_{M′}^{k_{θ}}(\overline{a}′), this is easy, we can map b to a point near c′. Specifically, since k_{θ} > l + 1, none of the neighbors of c′ can be in cl_{M′}^{θ}(\overline{a}′) either. Therefore, there exists a b′ such that cl_{M′}^{k_{ϕ}}(\overline{a}′, b′) = cl_{M}^{k_{ϕ}}(\overline{a}′, b′) ∪ cl_{M}^{k_{ϕ}}(b′) and cl_{M′}^{k_{ϕ}}(b′) ≃ cl_{M}^{k_{ϕ}}(b). So cl_{M′}^{k_{ϕ}}(\overline{a}′, b′) ≃ cl_{M′}^{k_{ϕ}}(\overline{a}′, b′).

We are left with the case that all isolated points of M′ are in cl_{M′}^{k_{θ}}(\overline{a}′). But then all isolated points of M′ are in cl_{M′}^{k_{θ}}(∅). Since cl_{M}^{k_{θ}}(\overline{a}) ≃^{s} cl_{M′}^{k_{θ}}(\overline{a}′), cl_{M}^{k_{θ}}(∅) ≃ cl_{M′}^{k_{θ}}(∅): this is the essential use of ≃^{s} instead of ≃. Since cl_{M′}^{k_{θ}}(∅) contains all the t > 0 isolated points in M′, cl_{M}^{k_{θ}}(∅) and therefore cl_{M}^{k_{θ}}(\overline{a}) contains all the t > 0 isolated points in M. So b ∈ C_{M}(\overline{a}). Let \overline{a}_{0} = C_{M}(b) ∩ \overline{a}. Since d(b, cl_{M}^{k_{θ}}(\overline{a})) = D_{M,\overline{a}}^{ϕ} > k_{ϕ}, the isolated point c of C_{M}(b) is not in cl_{M}^{k_{θ}}(\overline{a}_{0}). So

we can map b to a b′ on the component of \overline{a}′_{0} so that cl_{M′}^{k_{ϕ}}(\overline{a}′, b′) ≃ cl_{M′}^{k_{ϕ}}(\overline{a}′, b′). Now we turn to the cases where D_{M,\overline{a}}^{ϕ} is small; first, suppose cl^{k_{ϕ}}(b) = \{b\}.

Lemma 3.12 Let M, M′ ⊧ T h_{l} and \overline{a} ∈ M^{r}. Suppose D_{M,\overline{a}}^{ϕ} ≤ k_{ϕ}. Fix b ∈ M

for which d(b, cl_{M}^{k_{θ}}(\overline{a})) = D_{M,\overline{a}}^{ϕ}. For any \overline{a}′ ∈ M′^{r}, b ∈ M if cl_{M}^{k_{ϕ}}(b) = \{b\} and

cl_{M}^{k_{θ}}(\overline{a}) ≃^{s} cl_{M′}^{k_{θ}}(\overline{a}′), there exists a b′ ∈ M′ such that cl_{M}^{k_{ϕ}}(\overline{a}, b) ≃^{s} cl_{M′}^{k_{ϕ}}(\overline{a}′, b′).

Proof: We may assume that b ∉ cl_{M}^{k_{θ}}(\overline{a}), otherwise the result follows immediately from the second requirement in defining k_{θ}. First we claim there is at most one path whose vertices are in cl_{M}^{k_{ϕ}}(b, \overline{a}) − cl_{M}^{k_{θ}}(\overline{a}) from b to the k_{θ}-closure of \overline{a} in M. Suppose not, then we claim that any vertex c which lies on a fork of the path from b to the cl_{M}^{k_{θ}}(\overline{a}) is in fact in cl_{M}^{k_{θ}}(\overline{a}), which is a contradiction.

So assume there are two paths in cl_{M}^{k_{ϕ}}(b, \overline{a}) from c to cl_{M}^{k_{θ}}(\overline{a}), one going to say, a_{1} in \overline{a}, and the other going to say, a_{2} in \overline{a}, (a_{1} could be equal to a_{2}) with lengths k_{1} and k_{2} respectively. Note, since both paths are in cl^{k_{ϕ}}(b, \overline{a}), then we may assume both k_{1} and k_{2} are less than k_{ϕ} which is less than k_{θ}. Thus there is at most one other vertex with distance k_{1} to a_{1} and distance k_{2} to a_{2} (if a_{1} = a_{2}, c is the only vertex, since a component of a model of T h_{l} can have at most one cycle). Thus c satisfies a formula with only two solutions (or one solution if a_{1} = a_{2}) and quantifier rank less than k_{ϕ}. So c ∈ cl_{M}^{k_{θ}}(\overline{a}). This proves the claim.

Assume the shortest path from b to cl_{M}^{k_{ϕ}}(\overline{a}) is of length k_{0} and the nearest vertex in cl_{M}^{k_{ϕ}}(\overline{a}) to b is a_{0}. Let a′_{0} be in cl_{M′}^{k_{ϕ}}(\overline{a}′) such that a′_{0} corresponds to a_{0} in the isomorphism from cl_{M}^{k_{θ}}(\overline{a}) to cl_{M′}^{k_{θ}}(\overline{a}′).

We need to choose a vertex b′ ∈ M′ a vertex and a path in M′ of size k_{0} none of whose vertices are in cl_{M′}^{k_{ϕ}}(\overline{a}′) except for a′_{0}. This is immediate if a′_{0} has infinite degree; a_{0} and a′_{0} have the same degree. If a_{0} has finite degree then all the neighbors of a_{0} are in cl_{M}^{k_{ϕ}}(\overline{a}) since k_{ϕ} > l. But then k_{0} was not chosen minimal. So a_{0} and thus a′_{0} has infinite degree and we can choose b′.

Finally by the first claim, cl_{M}^{k_{ϕ}}(b, \overline{a}) is contained in cl_{M}^{k_{ϕ}}(\overline{a}) along with b and a path of length at most k from b to cl_{M}^{k_{θ}}(\overline{a}) and cl_{M′}^{k_{ϕ}}(b′, \overline{a}′)is contained in cl_{M′}^{k_{θ}}(\overline{a}′) along with b′ and a path from b′ to cl_{M′}^{k_{θ}}(\overline{a}′) of the same length. Therefore we have cl_{M}^{k_{ϕ}}(b, \overline{a}) ≃^{s} cl_{M′}^{k_{ϕ}}(b′, \overline{a}′) □

Finally, we consider the case where D_{M,\overline{a}}^{ϕ} is small and cl^{k_{ϕ}}(b) = \{b\} contains a cycle or an isolated point.

Lemma 3.13 Let M, M′ ⊧ T h_{l}. Fix \overline{a} ∈ M^{r}, \overline{a}′ ∈ M′^{r}, b ∈ M with D_{M,\overline{a}}^{ϕ} ≤

k_{ϕ}. If there is an isolated vertex or a cycle contained in cl_{M}^{k_{ϕ}}(b) then the isolated vertex or the cycle is contained in cl_{M}^{k_{θ}}(\overline{a}). In particular, if cl_{M}^{k_{θ}}(\overline{a}) ≃^{s} cl_{M′}^{k_{θ}}(\overline{a}′), there exists a b′ ∈ M′ such that cl_{M}^{k_{ϕ}}(\overline{a}, b) ≃^{s} cl_{M′}^{k_{ϕ}}(\overline{a}′, b′).

Proof: Note that \overline{a} satisfies the formula which asserts: there is a path of length at most k_{ϕ} to a point x and there is a path of length at most k_{ϕ} from x to a cycle of length at most k_{ϕ} (or to an l-isolated point). Since k_{θ} > 3k_{ϕ} and l < k_{ϕ} the result follows.

This completes the proof of Theorem 3.9. We now apply this result to computing the probabilities of sentences with respect to p_{n}^{l}.

Definition 3.14 Let σ_{s}^{l} be the sentence: “there exists exactly s vertices of degree l”. Define q_{l,s} to be the limit probability of σ_{s}^{l} (the existence of the limit is shown in [7].) Note this limit also depends on the constant c in the definition of p_{n}^{l}.

Theorem 3.15 For every non-negative integer s and for s = ω, T h_{l,s} is a complete theory. Furthermore these are all possible completions of the almost sure theory T h_{l}.

Proof: First we show {T h_{l,s} : 0 < s ≤ ω}, is the set of all possible completions of the theory T h_{l}^{>0}. Fix an integer s or let s = ω. It is clear that if M and M′ model T h_{l,s}, then cl_{M}^{ω}(∅) ≃ cl_{M′}^{ω}(∅) ≃ G_{s}^{l}. (Remember, by convention, G_{ω}^{l} = ∅.) Furthermore, for all t ≥ s, cl_{M}^{t}(∅) ≃ cl_{M′}^{t}(∅) ≃ G_{s}^{l}, since t is large enough to capture the algebraic closure of M and M′. Finally, for all q < s cl_{M}^{q}(∅) ≃ cl_{M′}^{q}(∅) ≃ ∅. Thus, since for all t, 0 < t ≤ ω, cl_{M}^{t}(∅) ≃ cl_{M′}^{t}(∅), Theorem 3.9 implies M ≡ M′. Therefore T h_{l,s} is complete. Since T h_{l}^{>0} is determined, {T h_{l,s} : 0 < s ≤ ω} is the set of all completions of T h_{l}^{>0}.

We note now that T h_{l,0} is the theory T h_{l} plus the negation of the axiom “there exists an isolated vertex”(recall, this axiom plus T h_{l} is T h_{l}^{>0}). Since T h_{l,0} is determined, and the algebraic closure of the empty set of any model of T h_{l,0} is empty, T h_{l,0} is complete. Thus we have now all possible completions of T h_{l}. □

The existence of k^{∗} below follows from our characterisation of the closure of the empty set in models of T h_{l}.

Definition 3.16 For any k, let k^{∗} be the least integer s greater than or equal to k such that for any t ≥ s, cl_{M_{t}}^{k}(∅) = ∅.

We write p^{l}(θ) for lim_{n→∞}p_{n}^{l}(θ) if it exists.

Theorem 3.17 For any L-sentence θ, there exists a finite set I of positive integers such that p^{l}(θ) is one of Σ_{i∈I}q_{l,i}, p^{l}(θ) = 1−Σ_{i∈I}q_{l,i}, or q_{0}^{l}+1−Σ_{i∈I}q_{l,i}.

Proof: Note that p^{l}(θ) = p_{l}(σ_{0}^{l} → θ) × p_{l}(σ_{0}^{l}) + p_{l}(¬σ_{0}^{l} → θ) × p_{l}(¬σ_{0}^{l}) if this limit exists. The first term always exists and is either 0 or p_{l}(σ_{0}^{l}) since T h_{l,0} is complete.

We compute the second term using that T h_{l}^{>0} is determined. By Theorem 3.9, there exists a finite k_{θ} such that the k_{θ}-closure of the empty set determines θ in T h_{l}^{>0}. Without loss of generality, assume that M_{k_{θ}^{∗}} ⊧ θ (an analogous argument works if M_{k_{θ}^{∗}} ⊧ ¬θ). Consider the set I (possibly empty) of nonnegative integers bounded by k_{θ}^{∗} such that for all i ∈ I, T h_{l,i} models¬θ. If this set is empty we conclude by Lemma 2.2 and Theorem 3.15, that T h_{l}^{>0} proves θ. In this case, it is clear that lim_{n→∞}p^{l}(θ) = 1 − q_{0}^{l} or 1, depending on whether T h_{l,0} ⊧ θ. If however the set I is not empty T h_{l}^{>0} proves ∨_{i∈I}σ_{i}^{l} ↔ ¬θ. Thus p^{l}(θ) is 1 − Σ_{i∈I}q_{l,i} plus the contribution from T h_{l,0}. □

4 Conclusion and Questions

We have provided another proof of the convergence law for the edge probability p_{n}^{l} considered in [7]. Our analysis allows for one less probability calculation. But the argument depends very heavily on Lemma 3.16 which seems to be an unusual and overly strong condition. In particular, it implies that in every model the algebraic closure of the empty set is finite. This seems to be a necessary condition for this type of argument to work. Basically, the key is to be able to compute the probability of assertions, ‘acl_{M}(∅) has form X’. Can a general method of showing convergence be developed by adding this hypothesis?

References

[1] R.D. Aref’ev.  K_{(H,|A|−e(A),≤)}-homogeneous-universal graphs.  In

B.S. Baizhanov M.B. Aidarkhanov, editor, Proceedings of Informatics and Control Problems Institute, Almaty, pages 27–40. 1995. In Russian.

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

[3] J.T. Baldwin. Random expansions of geometries. submitted.

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

[5] Ronald Fagin. Probabilities on finite models. Journal of Symbolic Logic, 41:50–58, 1976.

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

[7] L. Thoma and J. Spencer. On the Limit Values of Probabilities for the First Order Properties of Graphs. In DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 49, pages 317–336. Amer. Math. Soc., Providence, RI, 1999.