Stability, the finite cover property and 0-1 laws

John T. Baldwin ^{∗}

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

March 8, 1998

1 Introduction

Much recent work (e.g. [6], [8], [9] [5], [7]) has considered the relationship between 0-1 laws for first order logic and for various extended logics. We introduce here a new technique for such investigations. We show that certain model theoretic properties of the almost sure first order theory either ensure or make unlikely the existence of a 0-1 law for particular extended logics: least fixed point logic and logic with the Ramsey quantifier. That is, we approximate the finite by the countable by studying a condition on countable models to determine a property of a class of finite models.

The distinction between ‘ensure’ on the one hand and ‘make unlikely’ on the other arises because we consider a slightly stronger condition than a 0-1-law. Hella, Kolaitis, Luosto introduced the notion of the almost everywhere equivlence of two logics to clarify the notion that two logics define ‘the same’ classes of finite models up to a set of measure zero for a specified probablility measure. We consider connections between stability theoretic properties of the almost sure first order theory and a putative almost everywhere equivalence between a generalized logic and first order logic. If two logics are almost everywhere equivalent and one has the 0-1 law so does the other. And if the logics are not almost everywhere equivalent the most frequently used tool for extending the 0-1-law is not applicable; hence, ‘make unlikely’.

Thus, in particular, LPF is almost everywhere equivalent to first order logic and the uniform distribution ([6] and below). Macarthur and Spencer [9] showed that the analogous proposition fails for the measure P_{α} which assigns edge probability n^{−α} for irrational α, despite the 0-1 law for the first order case ([10], [4]). We provide a new proof of this result which explains the conclusion in terms of the unstability of the almost sure theory. In contrast, we show that the Ramsey quantifier is eliminable.

∗Partially supported by NSF grant 9308768.

2 Almost everywhere (in)-equivalence

We begin with some notation and definitions and proceed to the results.

Definition 2.1 By a probability measure P on finite L-structures we mean P = {P_{n} : n < ω} where P_{n} is a measure on L-structures of size n. For a class C of finite models and n ∈ ω, C_{n} denotes the members of C with size n and P (C) denotes the limit (if it exists) of P_{n}(C_{n}).

Definition 2.2 ([6]) The logics L and L′ are almost everywhere equivalent with respect to the probability measure P if there exists a collection C of finite models such that P (C) = 1 and for every sentence θ of L there is a sentence θ′ of L′ such that θ and θ′ are equivalent on C (and conversely).

The two logics we focus on this paper are LFP (least fixed point) and logic with the Ramsey quantifier. It is well known that LFP is imbedded in L_{∞,ω}^{ω}. Hella, Kolaitis, and Luosto [6] showed that F O (first order logic) and L_{∞,ω}^{ω} (finite variable infinitary logic) are almost everywhere equivalent with respect to the uniform distribution. The proof easily generalizes to the following formulation which is folklore.

Proposition 2.3 Suppose K is a class of finite structures, the 0-1 law for first order logic holds for K with respect to the asymptotic measure P, and the almost sure theory T_{∞} is ℵ_{0}-categorical. Then the 0-1 law for L_{∞,ω}^{ω} holds for P on K. In fact, F O and L_{∞,ω}^{ω} are almost everywhere equivalent with respect to P.

Let P_{α} be the probability measure which assigns edge probability n^{−α} for 0 < α < 1, irrational. For the non-eliminability with respect to probability n^{−α}, we require the following result of [5].

Theorem 2.4 [5] For any finite relational language L and any k, there is a LFP-formula ζ(x_{1}, … x_{2k}) such that for any finite L-structure A and k-tuples s, s′, s′′ from A

1. if A ⊧ ζ(s, s′) then s and s′ realize distinct L^{k}-types in A;

2. it is not the case that A ⊧ ζ(s, s′) and A ⊧ ζ(s′, s);

3. if s and s′ realize distinct L^{k} types in A then either A ⊧ ζ(s, s′) or A ⊧ ζ(s′, s);

4. if A ⊧ ζ(s, s′) and A ⊧ ζ(s′, s′′) then A ⊧ ζ(s, s′′).

Recall that a first order theory T is unstable if it satisfies the following condition, which is slightly weaker than defining a linear on an infinite collection of n-tuples: in some modelM of T, there is a formula ϕ(\overline{x}, \overline{y}) and infinite sequences \overline{a}_{i}, \overline{b}_{j} ∈ M for i, j < ω such that ϕ(\overline{a}_{i}, \overline{b}_{j}) holds if and only if i < j. Now we can show Theorem 2.5 Let T_{∞} be the almost sure theory for a class K and probability P satisfying the first order 0-1 law. If there are infinitely many distinct L^{k}-types consistent with T_{∞} and LFP logic and first order logic are almost everywhere equivalent with respect to P then T_{∞} is unstable.

Proof. Let θ(x_{1}, … x_{2k}) be the first order formula equivalent to ζ(x_{1}, … x_{2k}) in T_{∞}. Let v, v′, v′′ be k-tuples of variables. Then almost surely θ has the following properties:

1. θ(v, v′) → v ≠ v′;

2. θ(v, s′) → ¬θ(s′, s);

3. for each L^{k} formula ϕ, if ¬[ϕ(v) ↔ ϕ(v′)] → θ(v, v′) ∨ θ(v′, v);

4. if θ(v, v′) ∧ θ(v′, v′′) → θ(v, s′) and A ⊧ θ(sv′, v′′).

This a routine translation of Theorem 2.4 except for the third clause. There to make the translation we look at individual formulas that cause the inequivalence of the types. In every model A, if the types of s and s′ are different then ζ(s, s′) or ζ(s′, s) holds. Thus, almost surely we have iii) as required. These four conditions together assert that θ is a linear order on k-tuples and since there are infinitely many L^{k} types in T_{∞} the domain of the order is infinite; thus T_{∞} is unstable. □_{2.5}

Corollary 2.6 ([9]) Least fixed point logic and, a fortiori L_{∞,ω}^{k} is not almost everywhere equivalent to first order logic on graphs with respect to the probability measure P_{α}, for irrational α.

Proof. By Baldwin and Shelah [4] the almost sure theory, T_{α}, with respect to P_{α} is stable. It is shown explicitly in [9] and implicitly in [3] that there are infinitely many L^{k} types consistent with T_{α} (for graphs). We have contradicted Theorem 2.5. □_{2.6}

This argument applies mutatis mutandis to the almost sure theory obtained by expanding successor or a vector space over a finite field. The appropriate 0-1 law and proof of stability appears in [1].

We show that the ‘Ramsey quantifier’, ‘there exists a large homogenous set such that … ’ is eliminable over first order logic for either the uniform probablity measure or the measure P_{α} for irrational α. Thus, we get the 0-1 laws for these logics in a particularly strong way. For an introduction to the Ramsey quantifier see [2]. We define the f-interpretation of the Ramsey quantifier on finite models.

Definition 2.7 Fix a nonincreasing function f, from N to N. For a finite structure A and tuple a⃗ ∈ A, and formula ϕ(x⃗, y⃗), A ⊧ (Q_{ram,f} x⃗)ϕ(x⃗, a⃗) holds if there is a set X ⊂ A with |B| ≥ f(|A|) such that A ⊧ ϕ(b⃗, a⃗) for every b⃗ ∈ B^{lg(x⃗)}.

We say a function f from N to N is appropriate if f(n) ≤ n and for every m and all sufficiently large k, f(k) ≥ m. A formula ϕ(\overline{x}, \overline{y}) has the finite cover property if for arbitrarily large n there exist \overline{a}_{1} … \overline{a}_{n} such that every n − 1 of the sets ϕ(\overline{x}, \overline{a_{i}} have a common solution but there is no common solution for all n. In the following argument, we do not appeal to the actual meaning of the ‘finite cover property’ but only use known consequences of the property for Ramsey quantification.

Theorem 2.8 If f is appropriate, the logic L_{ω,ω}(Q_{ram,f}) is almost everywhere equivalent to first order logic on graphs with respect to the probability measure P_{α}, for irrational α.

Proof. By Baldwin and Shelah [4] [3], the almost sure theory, T_{α}, with respect to P_{α} is stable without the finite cover property. By [2], for each formula ϕ(x⃗, y⃗) there is an N such that for m ≥ N, there is no maximal homogeneous subset of cardinality m. For each m, this can be expressed by a first order formula and so each holds almost everywhere on finite models. Thus for almost every finite model (Q_{ram,f} x⃗)ϕ(x⃗, y⃗) is equivalent to (H^{N} x⃗)ϕ(x⃗, y⃗) (where H^{N} asserts the existence of a homogeneous set of size N). As, for sufficiently large n, f(n) > N. □_{2.8}

Since there are not arbitrarily large maximal homogeneous sets in the random graph (or, indeed any ℵ_{0}-categorical theory), the same argument shows the eliminability of the Ramsey quantifier for the uniform distribution (edge probability 1/2).

Theorem 2.9 If f is appropriate, the logic L_{ω,ω}(Q_{ram,f}) is almost everywhere equivalent to first order logic on graphs with respect to the uniform probability measure.

We would like to acknowledge helpful conversations with Jouko Väänänen and Kevin Compton in formulating these results.

References

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

[2] J.T Baldwin and David Kueker. Ramsey quantifiers and the finite cover property. Pacific Journal of Mathematics, 90:11–19, 1980.

[3] J.T. Baldwin and S. Shelah. DOP and FCP in generic structures. to appear, JSL, 199?

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

[5] A. Dawar, S. Lindell, and S. Weinstein. First order logic, fixed point logic, and linear order. In H. Kleine-Büning, editor, Computer Science Logic ’95, pages 161–177. Springer-Verlag: LNCS 1092, 1996.

[6] L. Hella, P. Kolaitis, and K. Luosto. Almost everywhere equivalence of logics in finite model theory. The Bulletin of Symbolic Logic, 2:422–44, 1996.

[7] R. Kaila. Probabilistic elimination of generalized quantifiers. preprint.

[8] P. Kolaitis and M. Vardi. Infinitary logics and 0-1 laws. Information and Computation, 98:258–294, 1992.

[9] M. McArthur and J.Spencer. Nonconvergence for sparse random graphs. preprint.

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