Pseudo-Finite Homogeneity and Saturation

Jörg Flum  Martin Ziegler ^{∗}

June 22, 1998

Abstract

When analyzing database query languages a property of theories, the pseudo-finite homogeneity property has been introduced and applied (cf. [3]). We show that a stable theory has the pseudo-finite homogeneity property just in case its expressive power for finite states is bounded. Moreover, we introduce the corresponding pseudo-finite saturation property and show that a theory fails to have the finite cover property iff it has the pseudo-finite saturation property.

1 Pseudo-finite homogeneity

Throughout let T be a complete first-order theory in a countable language L with infinite models. Suppose that ρ is a finite non-empty set of relation symbols not contained in L. Set L(ρ) := L ∪ ρ. If M is a model of T, and (M, P̄) is an L(ρ)-structure with, say, P̄ = P_{1} … P_{r}, then P̄ is a (ρ)-state in M. fld(P̄), the field or active domain of the state P̄, is the set fld(P_{1}) ∪ … ∪ fld(P_{r}), where fld(P_{j}) is the field of the relation P_{j}. P̄ is a finite state, if every fld(P_{j}) is finite and non-empty. In the following we will denote finite states by s̄, s̄′ . . ..

A state P̄ in M is pseudo-finite, if (M, P̄) is a model of F (T, ρ), the theory of all finite states, i.e.,

F (T, ρ) := Th({(N, s̄) | N ⊧ T, (N, s̄) an L(ρ)-structure, s̄ a finite state}).

In general, we use r̄, r̄′, t̄… to denote pseudo-finite states.

Example 1.1 For L := ∅, T the L-theory of infinite sets, and ρ := {P } with unary P, a subset r of a model M of T is pseudo-finite iff M \ r is infinite. In fact, for every k, the complement of every finite subset contains at least k elements, hence the same holds for a pseudo-finite subset. If M \ r and r are infinite and l ≥ 1, then (M, r) satisfies the same sentences of quantifier rank ≤ l as (M, s), where |s| = l. Therefore, (M, r) ⊧ F (T, ρ).

∗e-mail address: {flum, ziegler}@uni-freiburg.de

We collect some properties of pseudo-finite states:

Proposition 1.2 (cf. [3])

a) For every L(ρ)-sentence φ there is a sequence (φ_{n})_{n≥1} of L-sentences such that

φ ∈ F (T, ρ) iff for all n ≥ 1, T ⊧ φ_{n}.

b) Let r be a pseudo-finite subset of M (i.e., ρ = {P } with unary P). If s ⊆ M is finite, then r ∪ s is pseudo-finite. If s is definable (in particular, finite) then r \ s is pseudo-finite.

c) If r̄ is pseudo-finite in M, then fld(r̄) is pseudo-finite in M.

d) If r̄ is a pseudo-finite ρ-state in M and ρ′ ⊆ ρ, then r̄|ρ′ is pseudo-finite.

Proof. a) For simplicty, let ρ := {P } with unary P. Fix an L(ρ)-sentence φ. Now, let the L-sentence φ_{n} express that φ holds, if P has at most n elements, e.g., φ_{n} := ∀x_{1} … ∀x_{n}φ^{∗}, where φ^{∗} is obtained from φ by replacing each subformula of the form P u, u a term, by (u = x_{1} ∨ … ∨ u = x_{n}).

The proofs of b) – d) make use of the corresponding facts for finite r and r̄, respectively (see [3] for details). □

The pseudo-finite homogeneity property H(T) was introduced in [3]: For an infinite cardinal λ denote by H(T, λ) the property

if r and t are pseudo-finite subsets of a model M of T, h : r → t is bijective and L-elementary, and (M, r, t, h) is λ-saturated, then for every a ∈ M there is b ∈ M such that h ∪ {(a, b)} is L-elementary.

H(T) means that H(T, λ) holds for some λ. T has the pseudo-finite homogeneity property, if H(T) holds.

Proposition 1.3 • If μ ≤ λ then H(T, μ) implies H(T, λ).

• H(T, λ) implies H(T, ω). Hence, H(T) is equivalent to H(T, ω).

Proof. The first assertion is clear. For the last one, suppose that (M, r, t, h) is ω-saturated, r and t are pseudo-finite, and h : r → t is onto and elementary. Let a ∈ M. Choose a λ-saturated elementary extension (M′, r′, t′, h′) of (M, r, t, h). By H(T, λ), there is b′ ∈ M′ such that h′ ∪ {(a, b′)} is elementary. Using ωsaturation, choose b ∈ M such that (M, r, t, h, a, b) ≡ (M′, r′, t′, h′, a, b′). Then, h ∪ {(a, b)} is elementary. □

In [3] it is shown that H(T) holds for o-minimal T (even for quasi-o-minimal T). There are theories T without H(T) (variants of the following example will play a role in the next section):

Example 1.4 Let T be the theory of an equivalence relation which, for every n ≥ 1, has exactly one equivalence class of cardinality n. H(T) does not hold: Let λ be an infinite cardinal and M a λ-saturated model of cardinality λ. Let A_{1} and A_{2} be two infinite equivalence classes and let a ∈ A_{1}. Set r := A_{1} \ {a} and t := A_{2}. Choose a bijection h : r → t. Then, r and t are pseudo-finite in M, h is elementary and (M, r, t, h) is λ-saturated. But, there is no b ∈ M such that h ∪ {(a, b)} is elementary.

2 Some collapsing results

Let s̄ be a finite state in a model M of T. In the theory of constraint databases the question has been addressed whether every L(ρ)-formula (“query”) is equivalent in M for finite states to a formula whose quantifiers are restricted to fld(s̄). Moreover, in case an order relation < is in L, one wants to know whether every L(ρ)-formula preserved under partial order-isomorphisms is expressible in terms of < and the symbols in ρ. We present some positive results (collapsing results) and some negative ones. More or less explicitly, these results are contained in [3], [4], [5], [6]. Moreover, for stable theories, we show that pseudo-finite homogeneity is equivalent to one of the collapsing properties.

L(ρ)-formulas φ(x̄) and ψ(x̄) are equivalent in T for finite states if for all models M of T, all finite states s̄ and all ā ∈ fld(s̄), (M, s̄) ⊧ φ(ā) ↔ ψ(ā). Of course, by completeness of T and finiteness of the states, it suffices to require the condition just for one model M of T. By the same reasons, the following fact, tacitly used in the next proofs, holds:

If, for i = 1, 2, N_{i} ⊧ T, N_{i} ⊧ φ_{i}(s̄_{i}), where s̄_{i} is a finite ρ_{i}-state and
ρ_{1} ∩ ρ_{2} = ∅, then in every model M of T there are finite states s̄′_{1}
and s̄′_{2} such that M ⊧ φ_{1}(s̄′_{1}) ∧ φ_{2}(s̄′_{2}).

An L(ρ)-formula is ρ-bounded, if it has the form

Q_{1}x̄_{1} ∈ P_{1} … Q_{m}x̄_{m} ∈ P_{m}ψ

where Q_{1}, …, Q_{m} ∈ {∀, ∃}, P_{1}, …, P_{m} ∈ ρ, and ψ is an L-formula (and x̄_{1}, …, x̄_{m} have the appropriate length). By our assumption that the relations in a finite state are non-empty, every Boolean combination of ρ-bounded formulas is equivalent for finite states to a ρ-bounded formula.

The first collapsing theorem reads as follows (the idea of the proof was used in [5] to show Corollary 2.2 below for o-minimal theories):

Theorem 2.1 If H(T) holds then, for every ρ, every L(ρ)-formula is equivalent in T for finite states to a ρ-bounded sentence.

Proof. For notational simplicity, let φ be an L(ρ)-sentence. If φ is not equivalent to a ρ-bounded sentence, then by a standard compactness argument, one obtains pseudo-finite r̄ and r̄′ in a model M of T such that M ⊧ φ(r̄) ∧ ¬φ(r̄′) and such that (M, r̄) and (M, r̄′) satisfy the same ρ-bounded sentences. An appropriate back and forth argument (together with further applications of the compactness theorem) shows that, in addition, we can assume that there is a partial L(ρ)-isomorphism h with h : fld(r̄) → fld(r̄′), which is onto and Lelementary, and that (M, fld(r̄), fld(r̄′), h) is ω-saturated. Now, for every l ≥ 1, the pseudo-finite homogeneity shows that h can be extended l times back and forth to an L-elementary map, which by fld(r̄) ⊆ do(h) and fld(r̄′) ⊆ rg(h) is a partial L(ρ)-isomorphism. Therefore, h is L(ρ)-elementary, which contradicts M ⊧ φ(r̄) ∧ ¬φ(r̄′). □

An L(ρ)-sentence is ρ-restricted, if all quantifiers are relativized to fld(ρ). Clearly, every ρ-restricted formula is equivalent to a ρ-bounded one, and if T admits quantifier elimination, the converse holds, i.e., every ρ-bounded formula is equivalent to a ρ-restricted one. Therefore:

Corollary 2.2 (cf. [5]) If T admits quantifier elimination and H(T) holds then, for every ρ, every L(ρ)-formula is equivalent in T for finite states to a ρrestricted formula.

For stable theories the converse of the preceding theorem holds (we do not know whether the assumption of stability can be omitted):

Theorem 2.3 Assume T is stable. If, for every ρ, every L(ρ)-formula is equivalent in T for finite states to a ρ-bounded formula, then H(T) holds.

Proof. We show H(T, ω). So, let r and t be pseudo-finite subsets of a model M of T, h : r → t onto and elementary, and (M, r, t, h) ω-saturated. Given a ∈ M let p := tp(a/r) (tp(a/r) denotes the type of a in (M, (e)_{e∈r})). For an L-formula φ(x, ȳ) set

p_{φ} := {φ(x, ā) | ā ∈ r, φ(x, ā) ∈ p} ∪ {¬φ(x, ā) | ā ∈ r, ¬φ(x, ā) ∈ p}.

By stability of T, the type p_{φ} is definable over r, i.e., there is an L-formula δ_{φ}(ȳ, z̄) and c̄_{φ} ∈ r such that for all ā ∈ r,

M ⊧ δ_{φ}(ā, c̄_{φ}) iff φ(x, ā) ∈ p.

For ρ = {P } with unary P and L-formulas φ_{1}(x, ȳ), …, φ_{m}(x, ȳ), the formula

α(P, c̄_{φ_{1}}, …, c̄_{φ_{m}}) := ∃x ⋀_{1≤i≤m} ∀ȳ ∈ P (δ_{φ_{i}}(ȳ, c̄_{φ_{i}}) ↔ φ_{i}(x, ȳ))

expresses in (M, r) that p_{φ_{1}} ∪ … ∪ p_{φ_{m}} is realized. By assumption, for finite, and hence, for pseudo-finite P, α(P, c̄_{φ_{1}}, …, c̄_{φ_{m}}) is equivalent to a ρ-bounded formula. But, M ⊧ α(r, c̄_{φ_{1}}, …, c̄_{φ_{m}}) and h preserves ρ-bounded formulas, therefore, M ⊧ α(t, h(c̄_{φ_{1}}), …, h(c̄_{φ_{m}})). Thus, there is b_{0} ∈ M such that for i = 1, …, m and ā ∈ r,

M ⊧ φ_{i}(a, ā) ↔ φ_{i}(b_{0}, h(ā)).

Hence,

q(x) := {∀ȳ ∈ P (φ(a, ȳ) ↔ φ(x, h(ȳ))) | φ(x, ȳ) an L-formula}

is finitely satisfiable in (M, r, h, a). Therefore, by ω-saturation, there is b ∈ M satisfying q(x). Then, h ∪ {(a, b)} is elementary. □

Example 2.4 (cf. [5]) Let T be the theory of the ordered field of real numbers. T admits elimination of quantifiers and is o-minimal and therefore, H(T) holds. By 2.2, for ρ := {P } with binary P the sentence

φ := ∃u∃v∀x∀y(P xy → y = u · x + v)

(φ expresses that the elements of P lie on some line not parallel to the y-axis) must be equivalent in T for finite states to a ρ-restricted sentence ψ. In fact, as ψ we can take

ψ := ∃x_{1}y_{1} ∈ P ∃x_{2}y_{2} ∈ P ∀xy ∈ P ((x = x_{1} ∧ y = y_{1}) ∨

(x_{1} ≠ x_{2} ∧ x ≠ x_{1} ∧ \frac{y − y_{1}}{x − x_{1}} = \frac{y_{2} − y_{1}}{x_{2} − x_{1}} )).

Example 2.5 Let T be the theory of (ℤ, <, +) and ρ := {P } with unary P. H(T) holds by quasi-o-minimality of T (cf. [3]). By 2.1, the L(ρ)-sentence

φ := “P contains even and odd numbers”

is equivalent for finite states to a ρ-bounded sentence ψ, e.g., to

ψ := ∃x ∈ P ∃y ∈ P ∃u∃v(x = u + u ∧ y = v + v + 1).

But, φ is not equivalent to a ρ-restricted sentence. Therefore, the assumption of quantifier elimination cannot be omitted in the preceding corollary.

Example 2.6 Let T be the theory of Example 1.4, i.e., the theory of an equivalence relation E that, for every n ≥ 1, has exactly one equivalence class of cardinality n. T is stable and H(T) fails. Hence, by 2.3, there is a formula that is not equivalent in T for finite states to a bounded one. In fact, the sentence

φ := “P is an equivalence class”

is not equivalent to a {P }-bounded one for finite states. To prove this, e.g., for each n ≥ 1, introduce a new unary relation R_{≥n} with

R_{≥n} := {a ∈ M | the equivalence class of a has ≥ n elements}.

Then, T_{1} := Th(M, E, (R_{≥n})_{n≥1}) allows elimination of quantifiers. But φ is not equivalent in T_{1} for finite states to a restricted formula.

A theory T has the finite cover property (we denote this by fcp(T)) if there is a formula φ(x, ȳ) such that for all k ≥ 1 there is a sequence (ā_{i})_{i∈I} in some model of T such that the set {φ(x, ā_{i}) | i ∈ I} is not finitely satisfiable but every subset of at most k formulas is.

The theory T of the preceding example is a standard example of a stable theory with the finite cover property. We have proved that this theory does not have the pseudo-finite homogeneity property. This proof does not generalize to arbitrary theories with the fcp. The theory constructed in the following example is stable, has the fcp and the pseudo-finite homogeneity property. In the next section we shall see that H(T) holds for every theory T which does not have fcp.

Example 2.7 Let L = {E, F } with binary relation symbols E and F. Take an L-structure M_{0} such that

E is an equivalence relation, every equivalence class is finite, and for every n ≥ 1 there is exactly one class of cardinality n; F is a symmetric and antireflexive relation (a graph relation), F ⊆ E, and F is a cycle of length n in the equivalence class of cardinality n.

Let T be the theory of M_{0}. Clearly, T is stable and has the fcp. We show that H(T) holds. So, let (M, r, t, h) be ω-saturated, M ⊧ T, r and t pseudofinite in M, and h : r → t onto and elementary. Furthermore, let a ∈ M be arbitrary. We have to find b ∈ M such that h ∪ {(a, b)} is elementary. Note that every infinite equivalence class, with respect to F consists of infinitely many “ℤcomponents” (connected components). An analysis of the different possibilities for tp(a/r) shows that we find such an element b in all cases but one: namely, if a is in the equivalence class of an element a_{0} ∈ r, but is an element of a new ℤ-component (that is, no element of this component lies in r), and moreover, in the equivalence class of h(a_{0}) every ℤ-component contains an element of t. We show that this cannot happen. First note that for every finite subset s in the model M_{0}, every c_{0} ∈ s and k ≥ 1, the following statements (1)_{k} and (2)_{k} are equivalent:

(1)_{k} The union of the k-balls whose center are elements of s equivalent to c_{0} is the whole equivalence class of c_{0}, i.e.,

M ⊧ ∀x(Exc_{0} → (sx ∨ ∃y ∈ s ⋁_{1≤l<k} ∃y_{1} … ∃y_{l}
(F yy_{1} ∧ … ∧ F y_{l−1}y_{l} ∧ y_{l} = x))).

(2)_{k} For every d ∈ s in the equivalence class of c_{0}, there are “at both sides of d” elements in s at a distance < 2 · k, i.e.,

M ⊧ ∀x ∈ s∃y ∈ s∃z ∈ s

(Exc_{0} → ⋁_{1≤l<2k} ⋁_{1≤m<2k} ∃y_{1} … ∃y_{l}∃z_{1} … ∃z_{m}(¬y_{1} = z_{1} ∧

(F xy_{1} ∧ … ∧ F y_{l−1}y_{l} ∧ y_{l} = y ∧ ⋀_{1≤i≤l} ¬y_{i} = x) ∧

(F xz_{1} ∧ … ∧ F z_{m−1}z_{m} ∧ z_{m} = z ∧ ⋀_{1≤i≤m} ¬z_{i} = x))).

We come back to (M, r, t, h). By assumption, in the equivalence class of h(a_{0}) every ℤ-component contains an element of t. Hence, by ω-saturation of (M, r, t, h), there is k ≥ 1 such that (1)_{k} holds for s := t and c_{0} := h(a_{0}). Therefore, since t is pseudo-finite, (2)_{k} is true for t and h(a_{0}). But the formula in (2)_{k} is bounded and hence is preserved by L-elementary mappings, thus, (2)_{k} and therefore, (1)_{k} are true for s := r and c_{0} := a_{0}, a contradiction.

We turn to the second collapsing result. In the next definition and theorem we fix a binary relation symbol <. If < is in L, then we asssume that T contains the axioms of orderings for < and we set L_{0} = {<}. Otherwise, let L_{0} = ∅.

An L(ρ)-sentence φ is locally L_{0}-generic in T, if for some (or, equivalently, all) models M of T and all finite states s̄, all partial L_{0}-isomorphisms h (i.e., h is injective and <-preserving, in case L_{0} = {<}, and injective, in case L_{0} = ∅) with fld(s̄) ⊆ do(h), we have

M ⊧ φ(s̄) iff M ⊧ φ(h(s̄)).

Part a) of the next theorem is shown in [3] (and in [6] for o-minimal theories). We do not know, whether in part b) the assumption H(T) can be omitted.^{1}

Theorem 2.8 a) Assume < ∈ L and T contains the theory of orderings. Set L_{0} = {<}. If H(T) holds, then every L(ρ)-sentence φ, which is locally L_{0}- generic, is equivalent in T for finite states to an L_{0}(ρ)-sentence.

b) Set L_{0} = ∅. If T is stable and H(T) holds, then every L(ρ)-sentence φ, which is locally L_{0}-generic, is equivalent in T for finite states to an L_{0}(ρ)- sentence.

Proof. If not, a compactness argument gives a pseudo-finite (r̄, r̄′), a partial L_{0}-isomorphism h with do(h) = fld(r̄), h(r̄) = r̄′ such that

M ⊧ φ(r̄) ∧ ¬φ(r̄′) and (M, r̄)|L_{0}(ρ) ≡ (M, r̄′)|L_{0}(ρ).

It suffices to show that one can further assume that fld(r̄) and fld(r̄′) are subsets of one set of L_{0}-indiscernibles for L-formulas (i.e., <-indiscernibles in a) and total indiscernibles in b)). Then, h is L-elementary, and therefore, by H(T), we see, arguing as in the preceeding theorem, that h is L(ρ)-elementary, a contradiction.

To get the pseudo-finite states into indiscernibles, we take a disjoint copy ρ′ of ρ and let T_{1} consist of the L ∪ ρ ∪ ρ′ ∪ {I, f, f′}-sentences in (1)–(7):

1Added in proof: Meanwhile Baldwin and Benedikt ([1]) have proved that the assumption H(T) can be omitted. Compare also [7].

(1) Th(M, r̄, r̄′)

(2) I is infinite and L_{0}-indiscernible for L-formulas

(3) f and f′ are partial L_{0}-isomorphisms

(4) fld(r̄) ⊆ do(f), fld(r̄′) ⊆ do(f′)

(5) rg(f), rg(f′) ⊆ I

(6) φ(f(r̄)), ¬φ(f(r̄′))

(7) (f(r̄), f(r̄′)) is pseudo-finite.

We show that T_{1} is satisfiable and hence, by Robinsons joint consistency lemma, T_{1} ∪ Th(M, r̄, r̄′, h) is satisfiable. In a corresponding model, g := f′ ∘ h ∘ f^{−1} is a partial L_{0}-isomorphism with g(f(r̄)) = f′(r̄′), and fld(f(r̄)) and fld(f′(r̄′)) are contained in a set of indiscernibles.

T_{1} is satisfiable: Let γ ∈ Th(M, r̄, r̄′), m ∈ ω, and ψ_{1}(x̄), …, ψ_{k}(x̄) be Lformulas. It suffices to show that there exists a model of γ and of the sentences in (3)–(7) such that I contains at least m elements and is a set of L_{0}-indiscernibles with respect to ψ_{1}(x̄), …, ψ_{k}(x̄).

By pseudo-finiteness of (r̄, r̄′) there are finite s̄, s̄′ in some model N of T such that

N ⊧ γ ∧ φ(s̄) ∧ ¬φ(s̄′).

By Ramsey’s theorem, there is a set I, |I| ≥ max{m, |fld(s)|, |fld(s′)|} of L_{0}- indiscernibles with respect to ψ_{1}(x̄), …, ψ_{k}(x̄). Choose partial L_{0}-isomorphisms f and f′ with domain fld(s) and fld(s′), respectively, and range in I. Set s̄_{1} := f(s̄), s̄′_{1} := f(s̄′). By local genericity of φ, N ⊧ φ(s̄_{1}) ∧ ¬φ(s̄′_{1}). □

Example 2.9 Let L := {ϵ, <} with binary ϵ. Consider the structure (V_{ω}, ϵ, <), where V_{ω} is the set of hereditarily finite sets, where ϵ is the ∈-relation on V_{ω} and < a total ordering of V_{ω}, say, of order type ω. Let T be the theory of (V_{ω}, ϵ, <). For ρ = {P } with unary P, let φ be the L(ρ)-sentence stating that there is a bijection between P and an even natural number which, thus, expresses that the cardinality of P is even. Clearly, φ is locally L_{0}-generic in T, but not equivalent to an L_{0}(ρ)-sentence. Hence, H(T) fails.

3 Pseudo-finite saturation

We already remarked that there is a relationship between the pseudo-finite homogeneity property and the finite cover property. In fact, in this final section, we show that the saturation property that corresponds to the pseudo-finite homogeneity property even is equivalent to the finite cover property.

We introduce S(T, λ) by if r is a pseudo-finite subset of a model M of T and (M, r) is λsaturated, then every type in S_{1}(r) is realized in (M, (a)_{a∈r})

(S_{1}(r) denotes the set of complete types in a variable x with parameters from r). S(T) means that S(T, λ) holds for some λ. T has the pseudo-finite saturation property, if S(T) holds.

Clearly, if μ ≤ λ then S(T, μ) implies S(T, λ). Below we shall see that S(T) is equivalent to S(T, ω_{1}).

Proposition 3.1 S(T) implies H(T).

Proof. Assume S(T, λ) holds. Let (M, r, t, h) be λ-saturated with pseudofinite r and t and elementary and bijective h. For a ∈ M and p := tp(a/r), h(p) := {φ(x, h(ā)) | φ(x, ā) ∈ p} is a type in S_{1}(t). By S(T, λ), there is b ∈ M realizing h(p). Then, h ∪ {(a, b)} is elementary. □

There are theories with H(T) but whithout S(T): By o-minimality, H(T) holds for the theory T of the ordering of the rational numbers. But S(T) fails, as shown by:

Lemma 3.2 If S(T) holds then T is stable.^{2}

Proof. By contradiction, suppose that T is unstable. Let λ be a cardinal. We show that S(T, λ^{+}) fails. By unstability, there is a model M of T and a subset A of M such that

(+)  |M| = |A| = 2^{λ} and |S_{1}(A)| > 2^{λ}.

We may assume that there is a pseudo-finite subset r of M with A ⊆ r (since, for ρ := {P } with a new unary predicate P,

Th(M, (a)_{a∈A}) ∪ F (T, ρ) ∪ {P a | a ∈ A}

is finitely satisfiable). Choose a λ^{+}-saturated elementary extension (M′, r′) of (M, r) of cardinality 2^{λ}. By(+), there are types in S_{1}(A), and hence in S_{1}(r′), that are not realized in M′. □

Theorem 3.3 If T does not have the finite cover property, then S(T, ω_{1}) holds.

Proof. Let (M, r) ⊧ T, where r is pseudo-finite and (M, r) is ω_{1}-saturated. Fix p ∈ S_{1}(r). Since a theory without the fcp is stable, p is definable over r, i.e., for every L-formula φ(x, ȳ) there is an L-formula δ_{φ}(ȳ, z̄) and c̄_{φ} ∈ r such that for all ā ∈ r,

M ⊧ δ_{φ}(ā, c̄_{φ}) iff φ(x, ā) ∈ p.

2In [3] the pseudo-finite isolation property I(T) is considered and related to H(T). Both S(T) and I(T) imply H(T). But S(T) and I(T) contradict each other, since I(T) implies that T is unstable.

Let P be a new unary relation symbol. For an L-formula φ(x, ȳ) set

χ_{φ}(x, c̄_{φ}) := ∀ȳ ∈ P (δ_{φ}(ȳ, c̄_{φ}) → φ(x, ȳ)).

By ω_{1}-saturation of (M, r), it suffices to show that

{χ_{φ}(x, c̄_{φ}) | φ(x, ȳ) an L-formula}

is finitely satisfiable in (M, r, (c̄_{φ})_{φ∈L}). If not, there are φ_{1}(x, ȳ), …, φ_{m}(x, ȳ) such that

{χ_{φ_{1}}(x, c̄_{φ_{1}}), …, χ_{φ_{m}}(x, c̄_{φ_{m}})}

is not satisfiable. First we show that we can assume m = 1. Let

φ_{0}(x, ȳ, ū) := ((u_{0} = u_{1} ∧ ¬u_{0} = u_{2} ∧ … ∧ ¬u_{0} = u_{m}) → φ_{1}(x, ȳ)) ∧
((¬u_{0} = u_{1} ∧ u_{0} = u_{2} ∧ … ∧ ¬u_{0} = u_{m}) → φ_{2}(x, ȳ)) ∧
⋮
((¬u_{0} = u_{1} ∧ ¬u_{0} = u_{2} ∧ … ∧ u_{0} = u_{m}) → φ_{m}(x, ȳ)).

Then, χ_{φ_{0}}(x, c̄_{φ_{0}}) is not satisfiable (M, r, c̄_{φ_{0}}).

So let φ(x, ȳ) be an L-formula such that χ_{φ}(x, c̄_{φ}) is not satisfiable in (M, r, c̄_{φ}). Since non-fcp(T), there is a natural number k such that

for every finite sequence (ā_{i})_{i∈I} in a model of T, if every subset of {φ(x, ā_{i}) | i ∈ I} of at most k formulas is satisfiable, so is the whole set.

But then, for every N ⊧ T and any finite s ⊆ N, (N, s) is a model of

\begin{matrix}∀z̄((∀ȳ_{1} ∈ P … ∀ȳ_{k} ∈ P (δ_{φ}(ȳ_{1}, z̄) ∧ … ∧ δ_{φ}(ȳ_{k}, z̄) → ∃x ⋀_{1≤i≤k} φ(x, ȳ_{i}))) \\ → ∃x∀ȳ ∈ P (δ_{φ}(ȳ, z̄) → φ(x, ȳ)), \end{matrix}

and hence, (M, r) is a model of this sentence. For z̄ = c̄_{φ}, the hypothesis of this sentence is satisfied in (M, r) (since p is a type), and hence, χ_{φ}(x, c̄_{φ}) is satisfiable in (M, r, c̄_{φ}), contrary to our assumption. □

By 3.1 and 3.3 we get

Corollary 3.4 If T does not have the finite cover property, then T has the pseudo-finite homogenity property.

Theorem 3.5 If T has the finite cover proerty, then S(T) does not hold.

Proof. If T is unstable then S(T) fails by 3.2. So assume that T is stable and has the fcp(T). Then, (cf. [8]) there is a formula φ(x, y, z̄) such that for every model M of T and every ā ∈ M, φ(·, ·, ā) is an equivalence relation and for every natural number n there is ā_{n} ∈ M such that φ(·, ·, ā_{n}) has ≥ n but only finitely many equivalence classes.

Fix a model N of T and ā_{n} ∈ N according to the fcp. Let s_{n} be a complete set of representatives of φ(·, ·, ā_{n}). Let λ be an infinite cardinal. We show that S(T, λ) fails. By compactness, there is a λ-saturated model (M, r) and ā ∈ M such that r is infinite, pseudo-finite, and a complete set of representatives of φ(·, ·, ā). So t := r ∪ {ā} is pseudo-finite, but the type

{¬φ(x, b, ā) | b ∈ r}

is not realized in (M, (e)_{e∈t}). □

By 3.3 and 3.5:

Corollary 3.6 T has the pseudo-finite saturation property iff T fails to have the finite cover property.

Corollary 3.7 S(T) is equivalent to S(T, ω_{1}).

We show that there are theories T with S(T, ω_{1}) but without S(T, ω).

Example 3.8 Let T be the L := {E_{n} | n ≥ 0}-theory stating that

every E_{n} is an equivalence relation, E_{0} ⊇ E_{1} ⊇ …, E_{0} has exactly one equivalence class, and, for every n ≥ 1, every E_{n}-class splits into two E_{n+1}-classes.

Clearly, T is complete and does not have the finite cover property, hence, S(T) holds. We show that S(T, ω) fails. For this purpose, let ρ := {P } with unary P and let φ_{n} state that every E_{n}-class contains elements of P and elements of the complement of P. Then, T_{1} := T ∪ {φ_{n} | n ∈ ω} is complete in L(ρ) and every finite subset of T_{1} has a model (N, s), where N is a model of T and s is finite. Take a countable ω-saturated model (M, r) of T_{1}. Then, r is pseudo-finite in M, and it is not hard to see that there are 2^{ℵ_{0}}-many types in S_{1}(r); so, some of them are not realized in (M, (a)_{a∈r}).

We find that the pseudo-finite saturation property is a nice, conceptually clear reformulation of the non fcp. It also is a manageable one: We demonstrate this by reproving the result of [2] showing that a theory allows the elimination of all the Ramsey quantifiers in the ω-interpretation in case it does not have the fcp.

Proposition 3.9 If S(T) holds then the Ramsey quantifiers are eliminable.

Proof. Denote by Q^{n} the n-th Ramsey quantifier, i.e.,

M ⊧ Q^{n}x_{1} … x_{n}φ(x̄, b̄) iff there is an infinite set A

homogeneous for φ(x̄, b̄)

(A is homogeneous for φ(x̄, b̄), if for all ā = a_{1} … a_{n} ∈ A, M ⊧ φ(ā, b̄)).

Let H_{k}^{n} be the corresponding k-th first-order definable approximation of Q^{n}, i.e.,

M ⊧ H_{k}^{n}x_{1} … x_{n}φ(x̄, b̄) iff there is a set A of cardinality at least k

homogeneous for φ(x̄, b̄).

By a standard compactness argument (cf. [2]), one can prove that the Ramsey quantifiers are eliminable in T just in case

for every first-order formula φ(x̄, ȳ) there is a natural number k such that

T ⊧ ∀ȳ(H_{k}^{n}x̄φ(x̄, ȳ) → Q^{n}x̄φ(x̄, ȳ)).

Now assume that T does not allow the elimination of Ramsey quantifiers: By completeness of T, for some φ(x̄, ȳ) there is a model N of T such that for every k there are c̄_{k} ∈ N and a finite set s_{k} homogeneous for φ(x̄, c̄_{k}) with at least k elements such that for all b ∈ N \ s_{k}, the set s_{k} ∪ {b} is not homogeneous for φ(x̄, c̄_{k}). By compactness, there is an ω_{1}-saturated (M, r) and c̄ ∈ M such that r is infinite, pseudo-finite in M, and a maximal set homogeneous for φ(x̄, c̄). Therefore, t := r ∪ {c̄} is pseudo-finite, (M, t) is ω_{1}-saturated, and the type p ∈ S_{1}(t),

p := {¬x = a | a ∈ r} ∪ {φ(ȳ, c̄) | ȳ ∈ {x} ∪ {a | a ∈ r}}

is not realized in (M, (a)_{a∈t}). Thus, S(T) does not hold, a contradiction. □

References

[1] J. T. Baldwin and M. Benedikt, Stability theory, permutations of indiscernibles, and embedded finite models, preprint.

[2] J. T. Baldwin and D. W. Kueker, Ramsey quantifiers and the finite cover property, Pac. Jour. Math. 90 (1980), 11–19.

[3] O. V. Belegradek, A. P. Stolboushkin, and M. A. Taitslin, Extended ordergeneric queries, preprint.

[4] O. V. Belegradek, A. P. Stolboushkin, and M. A. Taitslin, On problems of databases over a fixed infinite universe, to appear in the volume “Helena Rasiowa in memoriam” of the Banach Center Publications.

[5] M. Benedikt and L. Libkin, On the structure of queries in constraint query languages, Proc. IEEE Symp. on Logic in Computer Science, 1996, 25–34 [6] M. Benedikt, G. Dong, L. Libkin, and L. Wong, Relational expressive power

of constraint query languages, to appear in Jour. of the ACM (Extended abstract in Proc. of ACM Symp. on Principles of Database Systems, 1996, 5–16.

[7] E. Casanovas and M. Ziegler, Stable theories with a new predicate, preprint.

[8] S. Shelah, Classification theory, North-Holland, 1990.

y