Atomic incompleteness

Marcus Kracht

                        kracht@math.fu-berlin.de

II Mathematisches Institut, Freie Universität Berlin

Tomasz Kowalski

                          kowalski@jaist.ac.jp

School of Information Science, JAIST

1 Introduction

A standard counterexample in modal logic looks somewhat like this: first conctruct a fancy Kripke frame, then take (some variation on) the algebra of finite and cofinite sets on this frame. It works. Algebraically, one outstanding feature of the algebra produced that way is that it is atomic. This may suggest the following, rather informally stated, conjecture: For any property P that does not hold of all modal logics, P can be falsified on an atomic modal algebra. True to the spirit of the great diagonalisation tradition we will exhibit a property P such that (1) if it does not hold of all modal logics then, by its very nature, it cannot be falsified on an atomic modal algebra, and (2) it indeed does not hold of all modal logics.

Let Λ be a modal logic, ϕ a formula. Further, let V(Λ) stand for the variety of modal algebras corresponding to Λ. Consider the following property:

(P) if ϕ ∉ Λ, then there is an atomic algebra A in V(Λ), with A |̸= ϕ.

Clearly, if there is a modal logic Λ that does not posses (P), then any atomic modal algebra is either not in V(Λ), or else it satisfies ϕ, hence (1) above indeed holds for our (P). All that remains is to show that (P) is not true of all modal logics Λ. Notice, that (P) expressed algebraically reads: V(Λ) is generated by its atomic members. Thus, we need to show that there is a variety of modal algebras not generated by its atomic members. This we will do in two stages. First, we will explicitly construct a variety V of tense algebras not generated by its atomic members. Then, we employ Kracht and Wolter’s simulation technique to produce a variety V^{S} of modal algebras with the same property.

2 Construction

We now proceed to construct a variety V of tense algebras which is not generated by its atomic members. Our V will be generated by a single algebra that is best described in terms of the frame defined below.

For each j ∈ ω and i ∈ {0, …, 2^{j} − 1} define U_{i,j} to be {k : k ≡ i (mod 2^{j})}. Let ℤ be the usual set of integers and ∞ an object not in ℤ. Put 𝕌 = {∞} ∪ ⋃_{i,j∈ℤ} U_{i,j}. The set of points of our frame will be W = 𝕌 ∪ ℤ. Then define the accessibility relation ◁ as follows:

• k ◁ U_{i,j} iff k ∈ U_{i,j} and i ≤ (2^{j} − 1)/2,

• U_{i,j} ◁ k iff k ∈ U_{i,j} and i > (2^{j} − 1)/2,

• U_{i,j} ◁ ∞, for all U_{i,j},

• U_{i,j} ◁ U_{k,l} iff U_{i,j} ⊂ U_{k,l}.

Put 𝔣 = ⟨W, ◁, ◁^{−1}, I⟩, with the family I of internal sets defined as follows: A ∈ I iff A = B ∪C, where B is a finite or cofinite subset of 𝕌 and C is a finite union of some U_{i,j}. Note the double role that sets U_{i,j} play: they are both points of the frame (as members of 𝕌) and internal sets (as subsets of ℤ).

Let I stand for the algebra of internal sets of the frame above. By means of a general algebraic argument, applicable to many more cases, we can prove:

Theorem 1 The variety V(I) is a minimal variety of tense algebras. It is not generated by its atomic members, in fact, it has none.

3 Lifting

Now, we lift the result from the previous section to the case of modal algebras. To do so, we make use of the simulation technique, originated in [1], [2] and developed in [3]. Intuitively, the technique works by associating with each polymodal frame a unimodal frame that consists of as many copies of the original frame as there were modal operators on it. These copies (with some additional points) form the universe of the new simulation frame, and the modal operator is so defined that: (a) it links the copies in a special way that allows to distinguish between them by constant formulas, (b) it behaves on each copy in exactly the way one of the original operators behaved on the original frame.

The same construction can be performed on any polymodal algebra A yielding a simulation algebra A^{S}. Simulation algebras form a rather well-behaved class. They are equationally definable, and given a unimodal simulation algebra B, the polymodal algebra A of which B is a simulation can be read off the structure of B.

For any class K of algebras, let H(K), S(K), P_{U}(K) stand, respectively, for the classes of homomorphic images, subalgebras, and ultraproducts of algebras from K. The key to our lifting procedure is the following slight strengthening of [4] Corollary 9.6:

Lemma 1 If K is a class of simulation algebras, so is SP_{U}(K).

Let V^{S} stand for the variety generated by the class of all simulation algebras of algebras from V, in other words: V^{S} = HSP ({A^{S} : A ∈ V}). With the help of the lemma above, we prove:

Theorem 2 The variety V^{S}(I) is not generated by its atomic members.

References

[1] S.K. Thomason, Reduction of tense logic to modal logic I, Journal of Symbolic Logic 39 (1974), 549–551.

[2] S.K. Thomason, Reduction of tense logic to modal logic II, Theoria 41 (1975), 154–169.

[3] M. Kracht, F. Wolter, Normal monomodal logics can simulate all others, Journal of Symbolic Logic 64 (1999), 99–138.

[4] M. Kracht, Tools and Techniques in Modal Logic, Elsevier Studies in Logic and the Foundations of Mathematics, vol. 142 (1999).