A remark about elementarity

Tomasz Kowalski

                          kowalski@jaist.ac.jp

Japan Advanced Institute of Science and Technology, School of Information Science

1 Introduction

Two notions related to modal logics—and thus to varieties of modal algebras—that have achieved a certain notoriety are elementarity and canonicity. Let us recall that a modal logic Λ is called elementary if Λ is determined by an elementary class of Kripke-frames, and Λ is called canonical if the corresponding variety V(Λ) of modal algebras is closed under canonical extensions (cf. e.g., [1]). Fine proved in [3] that every elementary logic is canonical. It is still not known whether the converse implication holds. Goldblatt (cf. e.g., [4]) has proposed an algebraic condition of singleton-persistence under which elementarity is equivalent to canonicity (and further to completeness). However, canonicity is known not to imply singleton-persistence (cf. again [4]).

On the other hand, Goldblatt [5] proves that a logic Λ is elementary if and only if Λ is determined by its class of Kripke-frames, and that class is closed under ultrapowers. In what follows, we define an algebraic counterpart of closure under ultraproducts of Kripke-frames and show that it is indeed equivalent to elementarity, providing thereby a “purely algebraic” characterisation of elementarity.

2 Definitions

We assume familiarity with basic notions from the area, such as complex algebras of Kripke-frames, canonical extensions of modal algebras, etc. For a Kripke-frame 𝔉 = ⟨W; R⟩, the full complex algebra of 𝔉 will be denoted by Cm𝔉; For a modal algebra A its canonical extension will be denoted by A^{σ}.

For an atomic algebra A let 𝔄 stand for the atom-structure of A, i.e., the structure ⟨AtA; R⟩, where R ⊆ AtA × AtA is defined by xRy iff fy ≥ x. If A is a full complex algebra, Cm𝔄 is isomorphic to A itself. A modal algebra A is completely additive if for every X ⊆ A, whenever ⋁ X exists, we have: f(⋁ X) = ⋁{fx : x ∈ X}. This property does not need to hold even if the boolean reduct of A is complete, i.e., ⋁ X exists for all X ⊆ A. However, all full complex algebras are completely additive. We will follow the custom of calling a modal algebra complete if it is complete as a boolean algebra and completely additive. Thus, all full complex algebras are complete and vice versa.

We will also make use of minimal extensions of modal algebras, as introduced by Monk [2]. There are several equivalent ways of defining these, we will however omit the technicalities altogether. All we need is contained in the next lemma.

Lemma 1 [Monk] If a modal algebra A is completely additive, then its minimal extension A^{c} exists. Moreover, A^{c} is complete, preserves all existing joins and meets from A, and is unique up to isomorphism.

For a Kripke-frame 𝔉, the singleton-algebra of 𝔉, denoted Sn𝔉 is the subalgebra of Cm𝔉 generated by the singletons of 𝔉. A variety V of modal algebras is singleton-persistent if for any Kripke-frame 𝔉, we have Sn𝔉 ∈ V implies Cm𝔉 ∈ V.

Lemma 2 [Goldblatt] For any Kripke-frame 𝔉, the algebra Cm𝔉 is the minimal completion of Sn𝔉.

Let (A_{i})_{i∈I} be a family of complete modal algebras, and U an ultrafilter on I. Consider the ultraproduct ∏_{i∈I} A_{i}/U.

Lemma 3 The algebra ∏_{i∈I} A_{i}/U is atomic and completely additive.

Let (A_{i})_{i∈I} and U be as above. The minimal completion of ∏_{i∈I} A_{i}/U, i.e., the algebra (∏_{i∈I} A_{i}/U)^{c} will be called complete ultraproduct of (A_{i})_{i∈I} over U.

Lemma 4 Complete ultraproduct of (A_{i})_{i∈I} over U is isomorphic to the full complex algebra of the ultraproduct ∏_{i∈I} 𝔄_{i}/U, where 𝔄_{i} is the atom-structure of A_{i}.

A variety V of modal algebras is complete if V is generated by a class of complete algebras. V is elementarily generated if V is generated by the class {Cm𝔉 : 𝔉 ∈ K} for some elementary class K of Kripke-frames. We have the following characterisation of elementarity:

Theorem 1 [Goldblatt] A variety V of modal algebras is elementarily generated if and only if V is generated by the class C = {A ∈ V : A is complete} and the class of atom-structures of algebras from C is closed under ultrapowers.

3 Corollaries and a question

We finish off by stating a number of facts that are immediate corollaries of the definitions (and a reasonable amount of folklore). The first of these provides the algebraic characterisation of elementarity, announced at the beginning of the paper.

Corollary 1 A variety V of modal algebras is elementarily generated if and only if V is complete and closed under complete ultrapowers.

The second corollary records the fact that singleton-persistence implies closure under complete ultraproducts. The converse does not hold. A counterexample is provided by the variety V(K4M) of transitive McKinsey logic, which is elementary and thus closed under complete ultraproducts, yet not singleton-persistent (cf. [4]).

Corollary 2 If a variety V of modal algebras is singleton-persistent, then V is closed under complete ultraproducts.

The third simply closes the circle with the help of Corollary 1.

Corollary 3 If a variety V of modal algebras is closed under complete ultrapowers, then V is elementarily generated iff V is canonical iff V is complete.

The fourth restates another theorem of Goldblatt’s in a purely algebraic language:

Corollary 4 Let A be complete. Then, A^{σ} ⊆ (A^{I}/U)^{c}, for some index set I and a certain ω-incomplete ultrafilter U on I.

Every elementarily generated variety is canonical. Since canonical extensions commute with subalgebras and homomorphic images, it can also be seen as a corollary of Corrollaries 1 and 4 above. Thus, the question “is every canonical logic elementary” is equivalent to the following:

Question 1 Is every canonical variety closed under complete ultrapowers?

References

[1] B. Jónsson and A. Tarski, Boolean Algebras with Operators, Part I, American Journal of Mathematics 73, 891–939, 1951.

[2] J.D. Monk, Completions of Boolean Algebras with Operators, Mathematische Nachrichten 46, 47– 55, 1970.

[3] K. Fine, Some Connections between Elementary and Modal Logic, in: S. Kanger (ed.) Proceedings of the Third Scandinavian Logic Symposium, North-Holland, 1975.

[4] R. Goldblatt, Persistence and Atomic Generation for Varieties of Boolean Algebras with Operators, Studia Logica 68, No. 2, 155–171, 2001.

[5] R. Goldblatt, Varieties of Complex Algebras, Annals of Pure and Applied Logic 44, 173–242, 1989.