Probability and the Finite Model Property

John T. Baldwin ^{∗}

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

June 21, 1999

Abstract

Theorem: Each of the ℵ_{0}-categorical stable theories constructed by Hrushovski can be viewed a countable model of an almost sure theory of finite structures. Thus, each theory has the finite model property.

1 Introduction

A complete first order theory T has the finite model property if every sentence ϕ ∈ T has a finite model. Clearly, a theory with the finite model property is not finitely axiomatizable. It is easy to see that in general the converse fails (take a disjoint union of a dense linear order with a non-finitely axiomatizable theory). Hrushovski (see the exposition in [4].) constructed a family T_{α} of stable ℵ_{0}- categorical theories parameterized by a suitable irrational α with 0 < α < 1. Since these theories are ‘continuous’ in α, it is straightforward to show they cannot be finitely axiomatizable. But such an argument does not suffice to show the T_{α} have the finite model property. However, if a theory T is achieved as an almost sure theory for a collection of finite models then T does have the finite model property. More precisely, suppose there is a class K_{0} of finite structures and a probability measure P_{n} on K_{n} (the members of K_{0} whose universe has cardinality n with n > 0). Suppose further that T is the collection of sentences ϕ such that lim_{n→∞} P_{n}(ϕ) = 1. Then T has the finite model property. For, if ϕ in T, lim_{n→∞} P_{n}(ϕ) = 1 so for sufficiently large n, P_{n}(ϕ) > 0 and so ϕ has a finite model.

This paper requires familiarity with both the Hrushovski construction as described in [4] and the account of the Shelah-Spencer 0-1 law as presented in [2].

∗Partially supported by NSF grant DMS-9803496. primary classification: 03C45 secondary 03C30, 60C05

The theory T_{α} was given as the theory of a generic (or homogeneous universal in an appropriate sense) structure for a class K_{0} = K_{α} of finite structures. Fix an irrational α. For any finite graph G, let δ(G) = δ_{α}(G) = |G| − αe(G), (where e(G) is number of edges of the graph G). For each α define ℓ_{n}/m_{n} to be the best rational approximation of α which is less than α with m_{n} ≤ n. A sequence of ordered pairs b_{i} = ⟨b_{i}^{0}, b_{i}^{1}⟩ for i < ω is defined from these rational approximations. Then K_{α} is the collection of finite graphs G such that δ(H) is above the polygonal line formed by connecting b_{i} to b_{i+1} for every H ⊂ G. If there is no bound on the size of the y-coordinates we say α has infinite index. The Baire category theorem guarantees that there are α with infinite index. The choice of the b_{i} guarantees that K_{α} has the amalgamation property (with ‘noedges’ amalgamation); the theory T_{α} of the resulting generic is ℵ_{0} categorical if and only if α has infinite index. (The amalgamation argument is given in [4]; we do not rely on any details of the argument here.) The case where α does not have infinite index is treated in [3]. The new point there is the proof that even in this case the theory remains stable.

By representing T_{α} as an almost sure theory we will show

1.1 Theorem. Each T_{α} has the finite model property.

We give now the general argument which works for each irrational α. In fact, for the ℵ_{0}-categorical examples singled out by Hrushovsky, (i.e. when α has infinite index) the proof can be significantly simplified and we will sketch that simplification at the end.

We write A ≤ B if for every B′ with A ⊆ B′ ⊆ B,

δ(B′/B) = δ(B′) − δ(B) ≥ 0.

Let J_{n} be the collection of isomorphism types of symmetric reflexive binary relational structures (graphs) with universe n. First consider the standard probability measure P̂_{n} on J_{n} with edge probability n^{−α}:

P̂_{n}(G) = n^{−αe} · (1 − n^{−α})^{(\binom{n}{2}−e)}

for each G ∈ J_{n} where e is the number of edges of G. Now we relativize this measure to K_{n}, the members of K_{α} with cardinality n. Thinking of K_{n} as a subset of J_{n}, set r_{n} = P̂_{n}(K_{n}). Define a probability measure on K_{n} by setting

P_{n}(G) = \frac{P̂_{n}(G)}{r_{n}}.

We will show that for this measure, for each ϕ, lim_{n→∞} P_{n}(ϕ) = 1 or lim_{n→∞} P_{n}(ϕ) = 0. For this, we show as in [2] that the semigeneric models for K_{α} are elementarily equivalent and that T_{α} is finitely determined in the sense of [1]. Let K (which of course depends implicitly on α) denote the universal class of models whose finite substructures are K_{0} = K_{α}.

1.2 Definition. The countable model M is (K_{α}, ≤)-semigeneric, or just semigeneric, if

1. M ∈ K

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

(a) cl_{M}^{m}(ĝB) = ĝB ∪ cl^{m}(gA)

(b) M| cl_{M}^{m}(gA)ĝB is the free join over gA of cl_{M}^{m}(gA) and ĝB.

Each theory T_{α} is axiomatized by a collection of axioms for semigenericity as defined in Notation 1.28 of [2]. That notation assigns a formula ϕ_{A,B,C}^{m} to each triple ⟨A, B, C ∈ K_{0}⟩ and each integer m where A ≤ B and C is a possible candidate for icl_{M}^{m}(A). It is then straightforward to show:

1.3 Lemma. The structure N ∈ K is semigeneric, if and only if for each appropriate triple ⟨A, B, C⟩ and each m < ω, N ⊧ ϕ_{A,B,C}^{m}

Note that there is a crucial dependence on the class K_{0} in determining these axioms. Although formally the axioms in the case appear the same as in [2] the actual axioms differ because the class K_{0} is different. Now the main result is:

1.4 Theorem. For each appropriate triple ⟨A, B, C⟩ and each m < ω,

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

Proof. Exactly as in the proof of Theorem 2.30 of [2], the argument is reduced to showing the probabilistic Theorem 1.9. We need the following definitions.

1.5 Remark. The essential aspect of the proof of Theorem 2.30 of [2] is that if A ⊆ B ⊆ B′ and δ(B′/B) < 0 then the probability of extending an embedding of A to an embedding of B′ is less than the probability of extending an embedding of A to an embedding of B exactly as described in Theorem 1.9.

1.6 Definition. Let A ⊆ B ∈ K_{0}. Fix a graph G with |G| = n and any W ⊆ n and suppose f embeds A into G. Then X_{f,W} is the number of sets ĝ(B−A) ⊆ W such that ĝ is an extension of f embedding B into G over A.

Viewing X_{f,W} as a function of G as G ranges through K_{n}, makes X_{f,W} a random variable. When W = n, we just write X_{f}. Similarly, we will shortly calculate the expectation μ_{f,W} of X_{f,W} and we write X_{f} when W = n.

1.7 Observation. Fix graphs A ⊆ B ∈ K_{0} with A ≤ B. Let f map A into n. Further let g_{1}, g_{2} be extensions of f mapping B into n. The probability that g_{i} is a graph homomorphism depends only on B, i.e is the same for both g_{1} and g_{2}. For, any graph G_{1} on n which makes g_{1} a homomorphism is transformed by any permutation of n which takes image of g_{1} to the image of g_{2} into a graph G_{2} on n which makes g_{2} a homomorphism. For this fixed f, A, B, with e = e(A, B) denoting the number of edges between B and A, let p_{n} be the probability that an extension of f to B is a graph homomorphism: \frac{n^{−eα}}{r_{n}}.

We write f ≈ g if f = O(g) and g = O(f).

1.8 Lemma. Fix A, B ∈ K_{α}, with e = e(A, B) denoting the number of edges between B and A, where v = |B − A|, and f is an embedding of A into n. For any W ⊂ n,

E(X_{f,W}) = μ_{f,W} ≈ |W |^{v} · p_{n} ≈ |W |^{v} \frac{n^{−eα}}{r_{n}} .

Proof. The probability of an extension g of f being a graph homomorphism is p_{n}. The number of such embeddings is approximately |W |^{v}. Since expectation is additive, we have the result.

Now, our main aim is to prove:

1.9 Theorem. Fix graphs A ⊆ B ∈ K_{0} with A ≤ B. Let V be the event (which depends on c_{1}): for every L′-isomorphism f:A → n,

μ_{f} · (log n)^{−(δ′(B/A)+1)} < X_{f} < c_{1}μ_{f}.  (1)

Then, for some choice of c_{1}

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

Proof. We prove the upper and lower bound separately, although there is some duplication of a main idea in the argument. We fix A ≤ B with |B − A| = v. We require the following definitions and fact from [2]. In particular, by induction, we can assume that B is primitive over A in the following sense.

1.10 Definition. 1. We say B is in the intrinsic closure of A and write A ≺_{i} B if for every B′ with A ⊆ B′ ⊂ B, δ(B/B′) < 0.

2. We say B is primitive over A if A ≤ B but for every B′ with A ⊂ B′ ⊂ B, B′ ≺_{i} B.

1.1 Fact. [2] 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 ∈ \overline{K} with A ⊆ M, X_{f} ≤ t(|A|, |B|).

Upper Bound for Theorem 1.9: Since B is a primitive extension of A, Ab ≺_{i} B for any b ∈ B − A. Thus, by Fact 1.1, for M = t(|A|, |B|), 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 X_{f,W} = s′, there is a set of s = s′/(M|B|^{2} + 1) disjoint extensions. If s < 3n^{v}p_{n}, (p_{n} is defined in Observation 1.7.) we are finished. Let p = |A|. For an appropriate constant c < 1, there are less than cn^{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 W. The probability that each of the g_{i} is a graph homomorphism extending f is p_{n} so (via Markov) the probability of such a pair of an L′-embedding and s homomorphisms is at most n^{p}n^{vs}p_{n}^{s}/s!. By Stirling’s formula, this is less than

\frac{n^{p}(2.72n^{v})^{s}p_{n}^{s}}{(2π)^{1/2}s^{s+1/2}(2.71)^{1/(12s+1)}}

which tends to 0 if s ≥ 3n^{v}p_{n}. (Observe that n^{p}(\frac{2.72}{3})^{s} tends to 0 as n tends to infinity.) Thus, a.a. for each f, s < 3n^{v}p_{n}.

In particular, a.a. for each f,

X_{f} ≤ 3(M|B|^{2} + 1)n^{v}p_{n}

which is the required upper bound.

Lower Bound:

We have fixed A and B. We first calculate a lower bound on the number of extensions of f mapping into a subset W of M_{n}. For this we relatize the upper bound argument by considering only mappings into W. Choose M as in the proof of the upper bound argument so that each extension g_{i} of f can intersect at most M|B| other extensions so if X_{f} = s′, there is a set of s = s′/(M|B|^{2} +1) disjoint extensions of f into W. Let h = 3 · (K|B|^{2} + 1). The following analysis applies for any b with 0 < b < μ_{f,W}; for us, b = \frac{μ_{f,W}}{[1+ln n]}. For each n and each f mapping A into n, just expanding the definition of expectation,

μ_{f,W} = ∑_{s>hμ_{f,W}} s·P (X_{f,W} = s)+ ∑_{b≤s≤hμ_{f,W}} s·P (X_{f,W} = s)+ ∑_{s<b} s·P (X_{f,W} = s).

Thus, adding and subtracting b · P (X_{f,W} > b),

μ_{f,W} ≤ ∑_{s>hμ_{f,W}} (s − b) · P (X_{f,W} = s)
+ (hμ_{f,W} − b) · P (b ≤ X_{f,W} ≤ hμ_{f,W})
+ b · P (X_{f,W} ≥ b) + b · P (X_{f,W} < b).

This implies

(μ_{f,W} −b) ≤ ∑_{s>hμ_{f,W}} (s−b)·P (X_{f,W} = s)+(hμ_{f,W} −b)·P (b < X_{f,W} ≤ hμ_{f,W}).

We conclude, (neglecting one division by hμ_{f,W} − b since it only improves the inequality, as hμ_{f,W} − b > 1),

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

Now s varies through the values of X_{f,W}, which is always at most |W |^{v}. As in the upper bound argument, if there are t embeddings, there are s = t/h whose ranges intersect in the range of f. Thus, invoking Markov’s inequality,

P (X_{f,W} = t) ≤ |W |^{vs}p_{n}^{s}/s!.  (2)

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 Equation 2 is less than

\frac{(2.72|W |^{v})^{s}p_{n}^{s}}{(2π)^{1/2}s^{s+1/2}(2.71)^{1/(12s+1)}} .

Recall that μ_{f,W} = |W |^{v}·p_{n}. Thus, for |W |^{v} ≥ s > hμ_{f,W}, the s^{s+1/2} dominates (\frac{|W |p_{n}}{3} )^{s}. This yields, for an appropriate constant c_{2},

∑_{s>hμ_{f,W}} (s − b) · P (X_{f,W} = s) ≤ c_{2}|W |^{v} · (2.72/3)^{|W |^{v}}.

Rewriting,

P (X_{f,W} ≤ b) ≤ [1 − (\frac{μ_{f,W} − b}{hμ_{f,W} − b} − c_{2}|W |^{v} · (2.72/3)^{|W |^{v}})] .

As n contains R = [1 + ln n] · |A| disjoint subsets W_{i} of length n/[1 + ln n], and the X_{f,W_{i}} are independent, the probability that for all i, X_{f,W_{i}} < \frac{μ_{f,W_{i}}}{R} is less than

[1 − (\frac{μ_{f,W_{i}} − b}{hμ_{f,W_{i}} − b} − c_{2}|W_{i}|^{v} · (2.72/3)^{|W_{i}|^{v}})]^{R} .

Thus,

P (X_{f} < μ_{f,W_{i}}/R) ≤ [1 − (\frac{μ_{f,W_{i}} − b}{hμ_{f,W_{i}} − b} − c_{2}|W_{i}|^{v} · (2.72/3)^{|W_{i}|^{v}})]^{R} .

(The last expression makes sense; all the μ_{f,W_{i}} are the same as |W_{i}| = |W |.)

Now, let V_{ℓ} (V lower) be the event that X_{f} < \frac{μ_{f,W_{i}}}{R} for all f. Thus P (V_{ℓ}) is bounded below by one minus the number of f’s times one minus the probability that an f has few extensions. That is,

P (V_{ℓ}) ≥ 1 − [n^{p} · (1 − (\frac{μ_{f,W_{i}} − b}{hμ_{f,W_{i}} − b} − c_{2}|W |^{v} · (2.72/3)^{|W |^{v}}))^{R}] .

More explicitly,

P (V_{ℓ}) ≥ 1 − [n^{p} · (1 − (\frac{1 − \frac{1}{R}}{h − \frac{1}{R}} − c_{2}(\frac{n}{R})^{v} · (2.72/3)^{( \frac{n}{R})^{v}}))^{R}] .

The right hand side of this expression goes to one. The key to this is repeated application of the fact that for any u and c with 0 < c < 1, uc^{u} tends to 0 as u tends to infinity. With this in mind we see that for sufficiently large n,

c_{2}(\frac{n}{R})^{v} · (2.72/3)^{( \frac{n}{R})^{v}}) < \frac{1}{4h}

and more easily

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

Thus

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

Since for any integer p and any n and c with 0 < c < 1, n^{p}c^{p·ln n} tends to 0 as n tends to infinity, we deduce that the probability that for all f, X_{f} < b tends to one. But since for each i,

μ_{f,W_{i}} = |W_{i}|^{v} · \frac{n^{−eα}}{r_{n}} = (n/R)^{v} · \frac{n^{−eα}}{r_{n}} ,

a.a. for every f, since r_{n} ≤ 1,

X_{f} ≥ (n/R)^{v} · \frac{n^{−eα}}{r_{n}} · (R)^{−1} ≥ n^{v} · n^{−eα} · (R)^{−(v+1)}.

Since R = |A| · ln n, incorporating |A|^{−(δ′(B/A)+1)} in the constant d, we get the required result. □_{1.9}

This completes the proof. The ℵ_{0}-categorical case is simpler in several respects. Since for any M ∈ K_{0}, and any finite A, icl_{M}(A) is finite it is possible to replace the axioms defining semigenericity by a set of Π_{2} sentences. The probability argument no longer requires the upper bound. (Under the argument given here, this is not much of a saving since the upper bound argument is essentially embedded in the lower bound proof. However, one could use the second moment argument of [?] instead.) Note that by Lindstrom’s theorem, the ℵ_{0}-categorical T_{α} are model complete while in general T_{α} is not model complete.

References

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

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

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

[4] B. Herwig. Weight ω in stable theories with few types. J. Symbolic Logic, 60:353–373, 1995.