DAVID

ULLRICH

THE

AND

MICHAEL

EXTENSIONS

BYRD

OF BAlt,

In contrast to the intensive, recent studies of specific modal logics, the investigation of the logical properties possessedby broad classesof modal logics is still very much in its infancy. Perhaps the most striking discoveries of this latter sort are the ‘extension’ results due to Scroggs [ 1] , Bull [2], Segerberg [3], and Fine [4]. These results establish the existence of modal logics all extensions of which have certain nice logical properties. For example, Bull and Fine show that all ex’tensions of $9.3 have the finite model property and are finitely axiomatizable, Now, in all the casesjust mentioned, the modal logic whose existence is established has the nice properties which its extensions are shown to have; note, for instance, that S4.3 has the finite model property and is finitely axiomatizable. This naturally raises the question of whether there could be a modal logic which lacked many of the nice logical features that all its extensions had to have. The present paper answers this question affirmatively. Specifically, consider the logic BAlts that is axiomatized by adding to the Brouwersche system B the axiom scheme: Alt,

LA, v L(AI >A*)vL((A, N-4,

&AZ &A31

&A*)>A3))V 3A4).

Segerberg has shown that BAlt, has an infinite number of modalities and is not finitely axiomatizable (see [3], pp. 60, 183). However, as we shall show, every extension of BAlts has a finite number of modalities and is finitely axiomatizable. We also prove that there are denumerably many such extensions and that they all possessthe finite model property. Thus, BAlts is unique among presently known modal logics in that it is an absolute upper bound on a number of interesting logical properties. 1. MODALITIES

We begin by proving the key lemma of the paper. While BAlt, does not have an L-reduction postulate, every extension of BAltJ does. Journal of Philosophical Logic 6 (1977) 109- 117. AN Rights Reserved. Copyright 0 1977 by D. Reidel Publishing Company, Dordrecht-Holland,

110

DAVID

ULLRICH

AND

MICHAEL

BYRD

LEMMA 1. Any logic (closed under substitution and detachment) properly containing BAlts contains some theorem of the formLkp >Lk+‘p. For any A, let [A] be the result of closing (A} under substitution. To prove the lemma, it suffices to show that if A is not a theorem in BAlt, , then there is some k such that [A] +BAlt, Lkp > Lk+‘p. By a straightforward completeness proof, we can discussinstead questions about validity in the frameM* = (Int, {(i,j>: Ii-j] < l}>. Now, suppose that A is a non-theorem of BAlts which has degree n > 0. (The degree of a wff is the number of embeddings of modal operators.) We show that [A] & L2”-‘p 3 L*“p. Letp,,. . . , pC b; the propositional variables in A. Since the degree of A is n, it follows that, for any valuation v on M* and any x E Int, v(A, x) is r 4i~e determined by the matrix of truth values ~@,,j) x-n
Since +BA,~ A, there is a matrix of truth values (ar,j) r G~Q=such that if ~1 -n< jX +I’) =Ui,j then v(A,X)= f. Let v* be a valuation which falsifies L2”-‘p > L2”p at point 0. So, by symmetry, v*@, - 2n + 1) = t, v*@, - 2n + 2) = t, . _ . v*(p, 2n - 1) = t and v*@J, 2n) = f. Note that ifj + m < 2n, then v*(Ljp, m) = t. Further V*(Ljp, m) = f, ifj + m = 2n. Given this information, it is possible to construct a substitution instance of A that is falsified by v* at 0; define .S! as follows: 1.

Ifai,-n

is&&:”

= p; otherwise St:” = - p .

2.

Srn+’ ifv*(,$~“+k,-n+k+ l)=ai,-n+k+l S;“+k+’ = S;n+k E LZ”-(-R+k+l)p, otherwise

We now show that for any natural number k < 3n and any natural number m < k, v* (S,:” l k , - n + m) = al, -” +,,,. That this is true fork = 0 is clear from part 1 of the definition. Suppose then that the property holds for j
THE

EXTENSIONS

OF

BAlt,

111

ai, -n +m, by inductive hypothesis. And, as previously noted, v* (L 2n-(-n+k+1)p,-~+m)=tsince2n-(--n+k+l)+(-n+m)<2n if m Gk. Whence v*(S,~“+~+‘, - n + m) will be t or f, according to whether ai, + +m, is t or f. This completes the proof. Now, let Si = Sr. By construction, the matrix of truth values is identical with the matrix of values (Qi,j) used to falsify v*(sl,i> l$i
= ljp and (dually) E Mjp

This can be proved by a routine semantic argument. THEOREM 1. Every extension of BAlts has a finite number of modalities. Suppose BAlts C E. Let Lkp 3 Lk”p be an L-reduction postulate provable in E. Let M”~L”~Mc~ . . L’+ (ai > 0) represent the general form of a modality. We show that there are only a finite number of irreducible sequences (ao, . . . , a,) in E. If some Q is greater than k, then the modality is reducible. Further, by Lemma 2, any three consecutive ‘elements ar, ~i+~ , and ai+* must meet certain conditions if the modality is to be irreducible. < Ui then ai+ < ai+r . Otherwise, an LML or MLM string can be Ifai+l replaced by an L or M string. Consequently, an irreducible modal sequence must have one of the following forms: I. a strictly ascending sequence with no element greater than k. 2. a strictly decreasing sequence (except possibly a0 = al) with no element greater than k. 3. a sequence strictly ascending to a number n, less than k + 1, followed by a strictly decreasing sequence whose initial element is no greater than II. There are only a finite number of such sequences, thus proving the theorem.

112

DAVID

ULLRICH 2. FINITE

AND MODEL

MICHAEL

BYRD

PROPERTY

The fact that all extensions of BAlt, contain an L-reduction postulate enables us to show that all such logics have the finite model property. To show this for a given logic E, we exhibit a model for E and show that any non-theorem is falsified in a finite submodel of that model. The relevant model ME, to be called the BAltacanonical model for E, is a quadruple (KBAI~,,KE,RBQ,

V~lub),where

1) KBAlh is the set of all maximal BAlts-consistent sets; 2) KE is the set of all maximal E-consistent sets, and so KE C_KBAlt, ; 3) for all X, y in KBAlt,, XRB~Q iff (A : LA Ex) _Cy; 4) for all sentence variables pi and all x in KBMb , VBAlt, (pi, X) = t iffpi EX. A wff is valid in this model if it is assigned the value t at every member of KE. Thus, ME is what Segerberg calls a model with distinguished elements. Using methods and results from Segerberg [3], it is a relatively straightforward matter to establish the following facts about ME, where E is a logic containing BAlts : LEMMA 3. (a) For all wffs A and ail x E KBAlb, VBAlh(A, X) = t iff A E X. (b) ME is a model for E. (c) Every non-theorem of E is falsified at some point in KE. LEMMA 4. is reflexive and symmetric. RBAM, (b) No element in KBMt, has more than 3 alternatives.

(a)

Models which have the characteristics described in Lemma 4 have a feature naturally described as being ‘strung out.’ This feature will now be made precise, and an important property of models having this feature will be deduced. DEFINITION. Elements x and y in a model are connected iff there are x, in the model such that xSaxr, xrSixs, . . . , andx,Sd, where Xl,..., S, may be R or its inverse.

THE

EXTENSIONS

OF

BAII,

113

DEFINITION. Elements x and y are said to be k steps apart iff there are k distinct elements x1x2, . . . , xk, also distinct from x and y, such that xRxr , xtRxz , . . . , and x&. So, for example, if xRy, then x and y are 0 steps apart. Now, to the crucial fact about ‘strung out’ alternatives. LEMMA 5. Let R be a reflexive, symmetric relation on a field of 2k + 2 connected elements. Suppose that no element in the field has more than 3 alternatives. Then, for every element x in the field of R, there is an element y in the field such that: (1)

x and y are k steps apart;

(2)

there is no j < k such that x and y are j steps apart

To show this, let x0 be in the field of R. Define Si(i > 0) as the set of elements which are i steps, but no fewer than i steps, from x0. Then Se contains at most 3 elements, and each Si, for i > 0, contains at most 2 elements. So, eGjyh-r Si contains at most 2k + 1 elements. Whence S, is not empty. We now employ these facts about Me to show that ME can be fragmented into finite submodels. LEMMA 6. Suppose E is a logic containing B&t,. Let Lkp 3 L*+‘p be an L-reduction postulate provable in E. Let ME be as before. Then if u is an element of KE, there are at most 2k + 1 elements connected to U. Suppose the lemma is false and let x1, x2,. . . , xak+s all be connected to U, where u E KEb By Lemma 4, this portion of ME satisfies the hypothesis of Lemma 5. So, there is an element w among x1, x2, . . . , xZk+2 such that: (1)

u and w are k steps apart;

(2)

ifj
Now, since each of the xi’s is distinguishable from the others, there is for eachi,asentenceAisuchthatAiEx,iffi=j.Lety,,...,y,bethe elements fewer than k steps from u (or just consider w, if k = 0). Suppose B1, _ . _ , B, are the sentences distinguishing the yi’s. Let C = B, v . . . vB, S By Lemma 3, we have VrsAlt, (C, yi) = t for each y,; so, VBArt,(LkC,@ = t.

114

DAVID

ULLRICII

AND

MICHAEL

BYRD

But VBAlt3(C, w) = f; whence VBAltJ(Lk+r C,i() = f. But, sinceLkC>Lk+‘C is a theorem of E and u EKE, I/BAlt, must assignLkC 1 Lk” C the value t at u. So, a contradiction has been deduced, and the reductio completed. Thus, each element in KE is connected to at most 2k + 1 points. But, as far as assignment of truth values to wffs at points goes, the only points that matter at a given point are the ones connected to it. That is to say, the truth value of A at x is not affected by the deletion of points not connected to x. LEMMA 7. Let M = (K, K’ , R, I/) be a model of E: (with distinguished elements K’). Let x E K’ . Suppose S is the set of elements connected to x in M. Let M* be the restriction ofM to S. Then, for ally ES and all wffs A, V(A,y) = V*(A ,y). Consequently,M* is also a model of E. THEOREM 2. Every extension of BAlts has the finite model property. Suppose A is a non-theorem of E. Then A is falsified in M, at some point x EKE. By Lemma 6, at most 2k + 1 points are connected to x. By Lemma 7, the restriction of ME to these points is a finite (indeed, with at most 2k + 1 elements) model that falsifies A at a distinguished point. 3.

FINITE

AXIOMATIZABILITY

To show that each extension of BAlts is finitely axiomatizable, it suffices to prove that no extension meets Tarski’s criterion for non-finite axiomatizability. This is accomplished by first showing that there is no infinite ascending chain of logics containing BAlts and, second, that if an ascending chain of logics converged on an extension of BAlt,, then some logic in the chain would include BAlt,. Before attacking the first stage of the argument, we note the following generalization of a theorem of Segerberg’s ([31, p.3 1). LEMMA 8. Let M = (K, K’ , R, V) be a finite distinguishable model for the logic E with distinguished elements K1 . Then, the frame MF = (K, K1 , R) validates E. Now, for the first step of the argument. LEMMA 9. There is no infinite ascending chain of logics each containing BAlt,. Suppose there were such a chain. Let L r , Lz , . . . be the chain and

THE

EXTENSIONS

OF

BAlt,

115

suppose Ai 4 Li but Ai E Li+r . Since these logics contain BAlts, an L-reduction postulate holds in each. Suppose Lkp 3 Lk+‘p holds in L1, and consequently, in each chain element. Now, 1etMt be the BAlts-canonical model for the logic Li. The sentence Ai is falsified in Mi at some point x in KLI. By Lemma 6, at most 2k + 1 points are connected to x, and, by Lemma 7, MF is a model Of Li that falsifies A at a distinguished point. Now, MF is a finite distinguishable model for Lie So by Lemma 8, the frame FF on which MT is based is a finite frame (of the form K, D, R)) which validates Li. Consider two such frames FT and Fi* with i
P>Gl>P)

2.

(P ’ (4 >a

3.

(-P>-4)>(4>P)

4.

LPIP

5.

L(p~q)>(LP>La

6.

P>LMP

7.

LpvL@>q)vL(@&q)zJr)vL((p&9&r)>s)

1 N.P ’ 4) 2 o,> d)

116

DAVID

ULLRICH

AND

MICHAEL

BYRD

Axiom ride. If A is an axiom, so is LA. Rules. Detachment Substitution Each logic in the chain is closed under detachment and substitution, So, to show that some logic in the chain contains BAlts , it suffices to show that some logic contains all the axioms just listed. Since BAlta C E, an L-reduction postulate Lkp 3 Lk+‘p is in E. E = U L,; so some logic in the chain contains this L-reduction postulate. AU the basic axioms must be in one of the chain’s logics, since they are in E. Moreover, if A is a basic axiom and n G k, then L”A is in E and, so must be in some member of the chain. Thus, each member of this group of 7k + 1 formulas must be in one of the chain’s logics. And since these logics form a chain, there is a logic Li containing them all. Further, it is clear that BAlts E Li. The primitive axioms, preceded by k or fewer L’s, are in LI by construction. The L-reduction postulate guarantees the presence of axioms with a greater number of initial L’s. THEOREM 3. Every extension of BAlt, is finitely axiomatizable. By Lemmas 8 and 9, no extension of BAlt, is the union of an ascending infinite chain of logics. By Tarski’s criterion, each extension can be finitely axiomatized. Theorems 2 and 3 entail: THEOREM 4. All extensions of BAlts are decidable. It is also a straightforward matter to see how many extensions of BAIta there are. THEOREM 5. There are He extensions of BAlt, . By Theorem 3, the extensions can be individuated by finite sets of sentences; so there are at most He of them. Reflection on canonical models establishes that distinct L-reduction postulates yield distinct extensions; so there are at least He of them. Despite the fact that all extensions of BAlt, are finitely axiomatizable, decidable, and have only a finite number of modalities (indeed, a finite number of propositional functions in any number of variables), there are nevertheless non-normal extensions of BAlts . As Segerberg pointed out to

THE

EXTENSIONS

117

OF BAlt,

us, the rule of necessitation fails for the logic determined by the frame (W,D,R)withW={0,1,2),xRyiff]x-yI
fir

mathematische

Logik

und Grundkrgen

341-344. [3] Segerberg, Krister, An Essay in ClassicalModal Logic, [4] Fine, Kit, ‘The Logics Containing S4.3’, Zeitschriftfiir und Grundlagen derMathematik 17 (1971) 371-376.

der Mathematik

12 (1966)

3 volumes, (UppsaJa, 1971). Mathematische

Logik