Reflections on a Proof of Elementarity

Robert Goldblatt

Abstract

This is an exposition and analysis of van Benthem’s original proof, hitherto unpublished, that if the class of structures (frames) validating a modal formula is closed under elementary equivalence, then it is the class of all models of a single first-order sentence.

Contents

1 Introduction and Salutation 2

2 Definitions 3

3 ΣΔ-Elementary Implies Elementary 3

4 Commentary 5 4.1 What Does the Lemma Prove? . . . . . . . . . . . . . . . . . . . 5 4.2 The Role of Compactness . . . . . . . . . . . . . . . . . . . . . . 5 4.3 The Cardinality of L . . . . . . . . . . . . . . . . . . . . . . . . . 5 4.4 Other Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1 Introduction and Salutation

In the early 1970’s, Johan van Benthem and I were both graduate students working, in antipodal locations, on the semantics of modal logic. It was a time when the initial enthusiasm for Kripke modelling had been tempered by the revelation of its incompleteness, and research was focusing on the relationships between different semantics (algebraic, relational, neighbourhood) and between propositional modal logic itself and fragments of first and second order quantificational logic.

We were interested in similar questions and conducted some fruitful correspondence (by snail mail!). On reflection it could be said that his perspective was more model-theoretic, while mine was more algebraic and structural. These aspects are intimately entwined, but a couple of examples may illustrate the distinction I am trying to draw here. They concern questions as to when a class of structures is elementary in the sense of being the class Mod(σ) of all models of a single first-order sentence σ.

Firstly, when each of us published—in the same issue of the JSL [vB75, Gol75]—a proof that the class of structures validating the McKinsey axiom

⋄φ → ⋄ φ is not elementary, Johan used a Löwenheim-Skolem argument to exhibit failure of closure under elementary equivalence, while I demonstrated failure of closure under the ultraproduct construction.

Those two criteria for failure of elementarity turned out, surprisingly, to be interchangeable. This is the second example, and the subject of this article. I had observed in [Gol75] that the class Str(φ) of all structures validating a modal formula φ is elementary if, and only if, it is closed under ultraproducts. Johan then made the remarkable discovery that Str(φ) is elementary iff it satisfies the ostensibly weaker requirement of closure under elementary equivalence. This implies, and indeed is equivalent to, the assertion that Str(φ) is elementary iff it is closed under ultrapowers. Yet another formulation is that if Str(φ) is closed under ultrapowers, then it must be closed under ultraproducts.

The proof of all this was founded on a compactness argument. When I learned about it from [vB74] my initial reaction was to wonder if the phenomenon had a natural structural explanation. An answer soon presented itself: there is an evident embedding

(∏_{J} 𝔖_{j})/F ⟶ (∐_{J} 𝔖_{j})^{J}/F

of any ultraproduct of structures into the associated ultrapower of their disjoint union, and this maps the ultraproduct isomorphically onto an inner substructure (a.k.a. generated subframe) of the ultrapower. Since Str(φ) is invariably closed under disjoint unions, inner substructures and isomorphism, the desired result follows immediately from this embedding.

When Johan published his result in [vB76] he chose to give this construction of mine in place of the proof he first thought of. Of course I found that very satisfactory, but I have always thought it was a pity that the original proof was not available in the literature, since it does have considerable novelty and interest, and provides significant information about the interactive behaviour of definable classes of structures. Besides, I believe that the appreciation of any mathematical result is always enhanced by an understanding of how it was arrived at.

I am therefore pleased to take the opportunity that this Liber Amicorum affords to return the compliment by publishing an exposition of Johan’s original argument, with some additional analysis and commentary. A curious birthday present perhaps, being made from something given by the recipient 25 years ago, but one that I hope will still (like all good presents) be a pleasant surprise. Happy Birthday Johan!

2 Definitions

Let L be the first-order language of a single binary predicate R. An L-structure has the form 𝔖 = ⟨S, R^{𝔖}⟩, with R^{𝔖} a binary relation on set S. If a set T ⊆ S is R-closed in the sense that

sR^{𝔖}t and s ∈ T implies t ∈ T,

then ⟨T, R^{𝔖}↾ T ⟩ is an inner substructure of 𝔖.

The class Str(φ) of all structures validating a modal formula φ is always closed under inner substructures and under disjoint unions. Its complement is always closed under ultraproducts. The latter fact can be shown by considering ultraproducts of Kripke models on structures as in [Gol75], or by noting that the complement of Str(φ) is defined by a Σ_{1}^{1}-sentence, i.e. a second-order sentence of the form ∃S_{1} ⋯ ∃S_{n}σ with σ having no second-order quantifiers, and such sentences are preserved by ultraproducts [CK73, Corollary 4.1.14].

For a class X of structures, we use the following definitions and characterisations, details of which may be found in [BS69, Chapter 7].

• X is elementary iff it is the class Mod(σ) of all models of some L-sentence σ. This holds iff both X and −X are closed under isomorphism and ultraproducts.

• X is Σ-elementary iff it is the union of elementary classes. This holds iff X is closed under ultrapowers and −X is closed under isomorphism and ultraproducts.

• X is ΣΔ-elementary iff it is the intersection of Σ-elementary classes. This holds iff X is closed under elementary equivalence, and is also equivalent to the requirement that both X and −X are closed under isomorphism and ultrapowers.

3 ΣΔ-Elementary Implies Elementary

Let X be a ΣΔ-elementary class that is equal to Str(φ) for some modal formula φ. We are going to show that X must be elementary.

Now X, being ΣΔ-elementary, is closed under ultrapowers while −X, being the complement of Str(φ), is closed under ultraproducts. From the above characterisations we then see that X is in fact Σ-elementary, so X = ⋃_{σ∈Σ} Mod(σ) for some set Σ of L-sentences.

Lemma. For each σ ∈ Σ there exists some finite subset Δ_{σ} ⊆ Σ such that if 𝔖 is any model of σ, then each inner substructure of 𝔖 is a model of at least one of the sentences in Δ.

Proof. Let J be the set of all finite subsets of Σ. If the Lemma is false then there is some sentence σ_{0} ∈ Σ such that for each Δ ∈ J there exists a model 𝔖_{Δ} of σ_{0} and an inner substructure 𝔗_{Δ} of 𝔖_{Δ} in which every member of Δ is false, i.e. 𝔗_{Δ} ⊧ {¬σ : σ ∈ Δ}.

We now invoke the standard ultraproduct proof of the Compactness Theorem. Let F be an ultrafilter on J that contains the set F_{σ} = {Δ : σ ∈ Δ} for each σ ∈ Σ. Let 𝔖 be the ultraproduct (∏_{J} 𝔖_{Δ})/F and 𝔗 the ultraproduct (∏_{J} 𝔗_{Δ})/F.

Since σ_{0} is true in every 𝔖_{Δ}, it follows by Łoś’s Theorem that 𝔖 is a model of σ_{0}, and so 𝔖 ∈ X. On the other hand, each σ ∈ Σ is false in 𝔗_{Δ} whenever Δ ∈ F_{σ}, so σ is false in 𝔗, i.e. 𝔗 ∉ Mod(σ). Hence 𝔗 ∉ X.

But the ultraproduct construction commutes with inner substructures, so 𝔗 is isomorphic to an inner substructure of 𝔖 [Gol93, Corollary 1.7.11]. Therefore we now have a contradiction because X, being of the form Str(φ), is closed under inner substructures and isomorphism.

It follows that the Lemma must be true. □

The set Σ of sentences is countable, since L is a countable language. Let σ_{1}, …, σ_{n}, … be an enumeration of Σ, and let δ_{n} be (σ_{1} ∨ ⋯ ∨ σ_{n}). This gives rise to a nested sequence

Mod(δ_{1}) ⊆ ⋯ ⊆ Mod(δ_{n}) ⊆ ⋯

of elementary classes whose union is X.

Now suppose, for the sake of contradiction, that X is not an elementary class. Then no term of this sequence is equal to X. Moreover we can suppose all terms are distinct, for if Mod(δ_{n}) = Mod(δ_{m}) with n < m we can delete δ_{n+1}, …, δ_{m} from Σ and still obtain a nested sequence whose union is X. Thus all inclusions in this sequence are proper, and so for each n there exists a structure 𝔖_{n} that is a model of δ_{n} but not of δ_{n−1}, and therefore a model of σ_{n} but not of σ_{k} for any k < n.

Let 𝔖 be the disjoint union of all the structures 𝔖_{n} with n ≥ 1. Each 𝔖_{n} is an inner substructure of 𝔖. Also 𝔖 belongs to X since X is closed under disjoint unions. Hence 𝔖 ∈ Mod(σ) for some σ ∈ Σ. For this σ, take Δ_{σ} to be the finite set given by the Lemma, and let N be greater than the index of any member of Δ_{σ}. Then by construction every member of Δ_{σ} is false in 𝔖_{N}. But this contradicts the conclusion of the Lemma, since 𝔖_{N} is an inner substructure of the model 𝔖 of σ and so is a model of at least one of the sentences in Δ_{σ}.

That completes the proof that X is elementary.

4 Commentary

The argument of Section 3 is essentially as in [vB74]. We now analyse some of its features and make some generalisations.

4.1 What Does the Lemma Prove?

The only properties of X required to prove the Lemma were that it is Σelementary and closed under inner substructures. We can distill from this proof the following general result about the behaviour of definable classes of structures. Here the notation 𝕊Y is used to denote the class of all isomorphic copies of inner substructures of members of a class Y.

If the union of a collection {X_{σ} : σ ∈ Σ} of elementary classes is closed under inner substructures, then for each σ ∈ Σ the class 𝕊X_{σ} is covered by finitely many member of this collection, i.e. for each σ ∈ Σ there exists some finite subset Δ_{σ} ⊆ Σ such that

𝕊X_{σ} ⊆ ⋃_{δ∈Δ_{σ}}X_{δ}.

4.2 The Role of Compactness

Instead of invoking ultraproducts in the proof of the Lemma, a direct application of the Compactness Theorem could be made, along the following lines.

Let L^{T} be the language resulting from the addition of a unary predicate T to L. For each L-sentence σ, let σ^{T} be its relativisation to the predicate T, got by replacing each subformula ∀xθ by ∀x(T (x) → θ^{T}) etc.

If an L^{T} -structure 𝔖^{T} = ⟨S, R^{𝔖}, T^{𝔖}⟩ satisfies the sentence

(τ) : ∀x∀y(xRy ∧ T (x) → T (y)),

then ⟨T^{𝔖}, R^{𝔖}↾ T^{𝔖}⟩ is an inner substructure of ⟨S, R^{𝔖}⟩ which satisfies an Lsentence σ iff 𝔖^{T} satisfies σ^{T}.

The structure 𝔖 in the proof of the Lemma can be realised as the L-reduct of an L^{T} -model of the set of sentences

Γ = {σ_{0}} ∪ {τ} ∪ {¬σ^{T} : σ ∈ Σ}.

This model may be shown to exist by proving that every finite subset of Γ has a model and appealing to the Compactness Theorem. 𝔗 is then defined as its inner substructure based on the set of elements satisfying the predicate T.

4.3 The Cardinality of L

In the second part of Section 3, the countability of L was used to obtain an enumeration of Σ. In fact this enumeration is avoidable, and the desired conclusion can be reached without appeal to any restriction on the size of L. Therefore it applies to other languages (cf. Section 4.4 below).

For each finite subset Δ of Σ (i.e. Δ ∈ J), let Δ^{+} be the disjunction of all the members of Δ. Suppose that X ≠ Mod(Δ^{+}) for any Δ ∈ J. Then for each such Δ there exists a structure 𝔖_{Δ} ∈ X such that 𝔖_{Δ} |̸= Δ^{+}.

Let 𝔖 be the disjoint union of all the structures 𝔖_{Δ} with Δ ∈ J. 𝔖 belongs to X by closure under disjoint unions. Hence 𝔖 = Mod(σ) for some σ ∈ Σ. For this σ, take Δ_{σ} as in the Lemma, and consider the structure 𝔖_{Δ_{σ}}. This is an inner substructure of 𝔖, and so by the Lemma it is a model of some member of Δ_{σ} and hence is a model of Δ_{σ}^{+}. But this contradicts the definition of 𝔖_{Δ_{σ}}.

Thus we must conclude that X is equal to some Mod(Δ^{+}), and so is an elementary class.

4.4 Other Languages

Many of the properties of classes of L-structures that are related to modal definability can be demonstrated for classes of structures of any similarity type. For arbitrary relational structures the notion of inner substructure is defined by imposing, for each n + 1-ary predicate R, the condition

R(s, t_{1}, …, t_{n}) and s ∈ T implies t_{1}, …, t_{n} ∈ T.

The conclusions of Section 3 can be summarized in their most general form as follows.

Let X be a class of structures that is closed under inner substructures and disjoint unions. Then X is elementary iff it is Σ-elementary. Furthermore, if the complement of X is closed under ultraproducts, then X is elementary iff it is ΣΔ-elementary, and this holds iff X is closed under ultrapowers.

These observations apply to structures for any first-order language, as does the general result distilled in Section 4.1 from the Lemma.

References

[BS69] J. L. Bell and A. B. Slomson. Models and Ultraproducts. North-Holland, Amsterdam, 1969.

[CK73] C. C. Chang and H. J. Keisler. Model Theory. North-Holland, Amsterdam, 1973.

[Gol75] R. I. Goldblatt. First-Order Definability in Modal Logic. Journal of Symbolic Logic, 40(1):35–40, 1975.

[Gol93] Robert Goldblatt. Mathematics of Modality. CSLI Lecture Notes No. 43. Center for the Study of Language and Information, Stanford University, 1993. Distributed by Cambridge University Press.

[vB74] J. F. A. K. van Benthem. Modal Formulas are Either Elementary or not ΣΔ-Elementary. Typescript, privately communicated, 1974.

[vB75] J. F. A. K. van Benthem. A Note on Modal Formulas and Relational Properties. Journal of Symbolic Logic, 40(1):55–58, 1975.

[vB76] J. F. A. K. van Benthem. Modal Formulas are Either Elementary or not ΣΔ-Elementary. Journal of Symbolic Logic, 41:436–438, 1976.