HAROLD
SOME
THEOREMS
LIMITATIONS
T. HODES
ON THE
EXPRESSIVE
OF MODAL
LANGUAGES
In [3] Allen Hazen considers certain statements expressible in an extensional language involving quantification over possible worlds, but which are not expressible in the corresponding modal language. In this paper, I derive a derive a variety of such claims from several model-theoretic theorems concerning SS. 1. PRELIMINARIES
Fix a set of predicates Pred, each of a particular number of places, and a countably infinite set of variables Var; for a set of names C form the language L(c) by following the usual formation rules, with the primitives ‘l’, ‘7, ‘Y’ and ‘0’. A term of L(c) is a member of Var U C. Use and mention shall be freely confused. Let 16, (3~)$, Og,and Eu abbreviate 0 E 1, l(Vv)l#, lol@ and (3~) (v = u) where u is a term of L(C) and v is a variable distinct from a; ‘82, ‘v’ and ‘z are defined as usual. We work entirely within the modal logic S5. So we may take a frame to be a pair F = (IU, A), W a non-empty set, A a function on W so that .4(w) is 1w E IV) = 1 is non-empty. An F-valuation a set for all w E IV, and U{A(w) for L(C) is a function V with domain C U (IV x Pred), V(c) E 1 for c E C; forwEWandPEPred,Pn-place:ifn>l, V(w,P)gZn;forn=O, V(w, P) E {t, f). A structure for L(C) is a triple J/= (W, A, v), Ya (W, A)valuation for L(C). For w E W, we say that w is from &, rf is an assignment fordiff d: Var +A. Let: den (4
a, u) =
a(u)
if (3 E Var;
V(0)
if c E C.
Define (& w) I= #[lr], ‘2 satisfies $ at w in&‘,
by the familiar recursion:
(-95w)kc:l[4; (& w) I= P[a] iff V(w, P) = t for P O-place; Journal of Philosophical Logic 13 (1984) 13-26. 0 1984 by D. Reidel Publishing Company.
0022-3611/84/0131-0013$01.40.
14
HAROLD
(4
T. HODES
w) I= Par . . . u, [a] iff (al, . . . , a,) E V(w, P) where ai=den(&b,oJfor 1 ~‘i~nandPisn-place,n>l;
(d, w) I= (I = ~‘[a]
(4w)i=(@~$)Pl
iff den (4
a, u) = den (4
d, 0’);
if(~w)#~[~lor(~w)l=~[61;
(Jai; w) I= (Vv)$[n] iff for every a E&w), (4 w) k $[$J, where nz is the assignment which differs from D at most in that it sends u to a; (d, w) I= @[a]
iff for every w’ E W, ( d, w) b $[a].
Where P is a set of formulae, (-s”; w) I= r[a] iff for all 4 E r, (4 w) k @[a]. Where the variables free in @J are understood to be xl, . . . , x,, we’ll write “[ar, . . . , u,]” instead of “[a]“, where it’s understood that ai = n(xi) for 1 < i < n. Let (M w) I= 9, “4 is true at w in X’, iff for all assignments a from 4 (Jai; w) I= $[-Ia , no t e.. f ree variables in 9 are thus treated as if bound by a “possibilist” universal quantifier, not by ‘Y’. (ral; w) b I’ is defined similarly. Where r U (qi) is a set of sentences, P implies Q1iff for all structures 4 w from dand assignments d for d, if L.x’C- I$?] then -c9t- $[a]. 9 is valid iff the empty set implies $. We formalize quantified S-5as in [2]. Keep in mind that the axiom schema of universal instantiation is: (VY)$J3 (Eu 3 #(V/U)) where u is a term of L(C) substitutable for v in 9. Other axiom schemata worth keeping in mind are (Vv)Eu and OEu (for all terms u of L(C)). Our rules of proof are Modus Ponens, Universal Generalization and Necessitation. Where r U (q%j is asetofformulae,r~~iff~~orl-($,&...&$,)>@forsome $, Er. Let or = {o($,&. . . tk+,I I J/,,. . . , tinEr}. J/l,..*, A diagram over W, C is a set of ordered pairs (w, $), w E W and # a sentence of L(C). Where D is a diagram, D(w) = {r$ I (w, $I) ED); OD = U(OD(w) ] w E W}; for W’ C W, D- w’ = D - {(w, #) I w E W’); D is consistent iff OD is consistent. We note the following facts. (1)
If D is consistent, then so is either D or D U {w, I#)}.
(2)
IfD u {tw, tW#d is consistent and c E C does not occur in D U {(w, (W/J)) then D U {(w, (3 W), (w, W/c)), (w, EC)} is consistent.
U {w,
9))
EXPRESSIVE
(3)
LIMITATIONS
OF
MODAL
LANGUAGE
15
If D u b, 0~)~ is consistent and w’ E W does not occur in D U {(w, O$)) then D U {w, O@),(w’, @)) is consistent.
2. THREE
HENKIN
COSTRUCTIONS
We consider a language L(CO). Let r,, be the set of universal closures of all formulae of the form: #3qvxl)~...
q (vx,)o($J&Exl&...&Ex~,
where 9 is a formula of L(CO) in which x1, . . . , x, are not free. THEOREM 1. Let T be a set of sentences of L(C,,). T U To is consistent iff there is a structure A’= (W, A, v) for L(C,J and a w. E W so that (4 wo) I= T and 2 = A(wo). Suppose &= (IV, A, v) and A(wo) = 2; then (X wo) I= T,,. This proves the “if” direction. We now consider the “only if” direction. Note that To I- (3x)Ex and To ~-EC for all c E C, Suppose T U To is consistent. Then so is I’ = T U To U ((3x)Ex) U {EC Ic E C,). Select sets W, C 1 Co, card(W) = card(C- Co) = max{No, card(Pred), card(Co)} = K, Fix a listing in order-type K of all pairs (w, 4), w E Wand $ a sentence of L(c); select w. E Wand let Do = {wo} x I’. Do is a consistent diagram. We now construct a sequence {Dt}r < K of consistent diagrams. Suppose DE has been defined, is consistent, and for every c E Coccurring in DE, EC E Dt(wo). Let (w, r$) be the ,$th pair on our list. If all names occurring in 4 already occur in DE, let: D; =
4 Uh
#)I
I Dg. U {w, l#)}
if this is consistent; otherwise
By remark (l), 0; is consistent. Otherwise suppose cl, . . . , c, are the members of Coccurring in @but not in DE. Let D, = Dg. U {w, 91, two, EC,), . . . , b, EC,)) t i Dg U {w, l#), (w,,, EC,), . . . , (w,,, EC,)}
if this is consistent; otherwise.
Suppose both Dg U {(w, @),(w,,, Ecd, . . . ) and Dg U {(w, +), (w,,, EcJ, . ) are inconsistent. Suppose w # w,, For some 8, a conjunction of members of Dt(wo), letting Cp= ODi’“* we:
HAROLDT.HODES
16 4, u
O(D&w)
@ u O(D&w)
u (@)) u {l#j
k
qe k
3
qe
(l&l
V.
2 (1ECl
. . VlEC,)),
V . . . V-EC”)).
By induction hypothesis, for the c E Coccurring in f3 we have EC E D[(w,-,); since To G D&w&
DE(WO) k
o(e&Ec~
dc . . . &EcJ.
From this, using S5 axioms, we may show that DE U {(w, 4)) and DE U {(w, -I$)) are both inconsistent, contrary to the consistency of Dg. Now suppose w = we. For 8, a conjunction of members of D&w&,
q((!3 oD$“p’t- q((e
OD$“o)
k
& (3x)Ex
& 4) 3 (~Ec,
& (3X)EX
& 14)
> (l&
v. . . v-IEc,)), V . . . V l&k,))
Thus O@d
t
(e & (3x)Ex)
3 (lEcI
V . . . V lEC,).
But since cl, . . . , c, do not occur in D$“‘d or 8, they may be replaced by variable and universally quantified; then by standard quantifier manipulations, oD$wd
k
(e & (3X)EX)
> (vX)
1EX.
Therefore OD$‘J J- ql(fI & (3x)Ex), showing that DE is inconsistent. Thus Di is consistent. Let #’ be $Jor 14 according to the case used in defining Db If 4’ is neither (3v)$ nor O$, let Dg+l = D’. If 4’ is (3v)$, select a c E Cnot occuring in 0; and let q = D; U {(w, J/ (dc)), (w, EC)); D;’ is consistent. Let DE+ 1 = 0;’ U {(wo, EC)). If Dt+ r were inconsistent there would be a 0, a conjunction of members of D&u,,), so that 00; -+‘Q)l- q(0 3 ~Ec). But D’;(wo) k I O(t9 & Ex); so Di(wo) I- O@ &EC), contrary to the consistency of 0;. If #’ is 09, select a w’ E W not occurring in 0; and let DC+ 1 = Di U {(w’, $)I. Ds+ r is consistent. For X d K, X a limit ordinal, DA = U {DE 1g < h}. D,T, is consistent; and for any c E C occurring in DA, EC E Do. D, is a maximal consistent diagram over Wand C. It determines a structure M= (IV, A, v) as follows. For c, c’ E C, let c 5 c’ iff for some w E W, c = C’ ED,(w); let [c] be the
EXPRESSIVE
LIMITATIONS
OF
MODAL
17
LANGUAGE
--equivalence classof c; let A(w) = {[cl IEc ED,(w)}; let V(c) = [cl; V(w, P) = t iff P E D,(w) where P is O-place; V(w, p) = {([c,], . . . , hl) ml. - . c, ED,(w)} for P n-place and n > 1. As usual, for all sentences $ of L(C), (M w) I= $ iff Q,ED(w). &is as desired. Q.E.D.
For any formula 4, let (O)b be n(Vvr) 0 . . . a (Vv,J 0 4, if vI, . . . , Y, are the variabes free in 9; if 9 is a sentence, (n)$ is ~$5.Where r is a set of formulae, (O)r = {(o)Q) I# E r). Let T1 be the set of formulae of t(Ce) of the form: (W
& w
& ~-w
& $1) ’ O(# & (3xM1L
& IW,
where x is not free in $.
THEOREM2. Suppose T is a set of sentences of L(Ce). T U (n)Tl
U
(o(3x)Ex) is consistent iff there is a structure J/= (FV,A, v) for L(Ce) and w. E W such that (ti wo) I= Tand for all w, w’ E IV, if w # w’ then A(w) is not a subset of A(w’). Suppose &= (IV, A, v) is a structure for L(Co), w. E Wand for all w, w’ E W, if w f w’ then A(w) is not a subset of A(w’). Then (& wa) k (n)T, U {0(3x)Ex}. Clearly no A(w) is empty. Suppose a = (ur, . . . , a,,), aiEAfOri=l,. ..,n,wEWand(~w)!=O$&OJ/&~~(#&$)[a]. Select wl, w2 E W, (4 wr) I= @[a], (& w2) I= $[a] and wr # WZ;selecting b EA(wr) - 4w2) as a witness, (&, wr) j= (3x)0($ & lEx)[a]. Thus (M w) I= O(4 &(3x) O(J, & -rEx))[a]. So (g wo) I= (0)Tl. These remarks suffice to prove the “if” direction. We now prove the “only if” direction. Fix IV, C and the sequence of pairs (w, 6) as in the previous argument. Let De = {wo) x (T U (o)Tl U ((3x)Ex)) for a selected w. E W. We construct a sequence of consistent diagrams under this constraint: only introduce a new world when consistency demands it. Furthermore, when we introduce a new world we also introduce new constants to insure that the final model has the desired structural property. Suppose DE has been constructed, is consistent, and for all w, w’ E Wand occurring in DE, if w f w’ then (1)
OD@ w? U O(Dc(w) U Q(w))) is inconsistent;
18
HAROLD
(2)
T.
HODES
There are c, c’ E C so that EC, iEc’ E DC(W) and EC’, 1Ec E DE(w’).
Let (w, $I) be the least pair in our list of pairs which has not been handled and for which w occurs in Dg. Let D, =
4
t I
if this is consistent;
” h, @>I
DC U {w, -r@)}
otherwise.
Let 9’ be 9 or 19 according to whether the first or second case applied. If 4’ is neither (3v)$ nor O$, let D E+r = 0;;. The induction hypothesis is preserved. If 9’ is (3v)$, select c E C not occurring in 0; and let DE+r = 0; U {(w, $(v/c)), (w, EC)}. If $J’is 09 and for some w’ occurring in D;, 0; U {(w’, J/)} is consistent, select such a w’ and let Dt+ I = 0; U ((w’, J/)}. The induction hypothesis is preserved. Suppose that there is no such w’. Select a w’ E W not occurring in D; and let Dt = 0; U ((w’, J/)1; this is consistent. Let (wn)n < Lybe a well-ordered list of the members of W occurring in 0;. For each 1)< 01select two members of C, call them cq and d,.,, all distinct and not occurring in D’;. Let D;” = 0’; U {w,.,, EC,), (w’, Ed,) 1n < a}. Since q(3x)Ex ED&w,,) and all cn and dn are “new”, 0;” is consistent. For 17< OL,let: D E,~ = 0’;’ U i&j, lEdq*), (w’, iEq) In’ < Q}. By induction on 9, each DC,n is consistent. This holds for 77= 0. Suppose DE,n is consistent but DE,q ” {wq, -4-,~~ is not. Let I’ = OD.$‘tl* W’! Thus there are 0 and 13‘, conjunctions of members of DE,n(wn) and DE,Jw’), so that r U (O(0 & -tEd,J, O(0’ &Ed,)}
is inconsistent. By (1) of our induction hypothesis we may, without loss of generality, suppose that r U {O(e & 0’)) is inconsistent. Using the machinery of S5 we may conclude that r t--(e’u-d,pqe
IE~,);
but since d,, doesn’t occur in r, 8 or 8’,
r t-e’3(vx)qe IEX). Because all members of r begin with ‘O’, using the machinery of S5 :
rk-qe’3(vx)qe Because (a) T1 2 Db ,(wo),
3~x1).
EXPRESSIVE
LIMITATIONS
OF
MODAL
LANGUAGE
19
Do,q(wo)t- (oe’tk 08&:qe dke’)) 3 o(e’8i(3x)(8tk -IEX)). Since r I-
qe &e’), OD~,~ t-
o(e’t2 (3~) o(e& TEX)),
contrary to the consistency of DE,rl. Thus Dt, r) U ((We, lb&$} is consistent. A similar argument with DE,q U ((wtl, x%&,)} in place of Dg, rl, cq in place of d,,, and the roles of wn and w’ exchanged, shows the consistency of DE,,,+ 1. Clearly DE,,I,for X a limit ordinal Qar is consistent. Thus DE+r = DE,a is consistent and satisfies our induction hypothesis. From D, we construct the desired structure B’= (w’, A, v) as usual, with W’ = {w B WI w occurs in DK). &has the desired properties. Q.E.D.
Let T2 be the set of all formulae of L(Ce) of the form: J/ ’ Wx)
qti & Ex)),
where x is not free in J/. THEOREM 3. Suppose T is a set of sentences of L(Ce). T U (0) T2 U (n(3x)Ex) is consistent iff there is a structure .M= (IV, A, v) and w. E W so that (4 wo) I= T and for all w, w’ E IV,A(w) and A(w’) are not disjoint. Clearly if &‘is as described on the right-hand side, (Lsl; we) k (n)Tz U {0(3x)Ex}. The “if” direction follows. Suppose T U (0) T2 U ( 0 (3 x )E x } is consistent. Fix W, Cand the listing of ordered pairs (w, $) as before; select w. E Wand let Do = (wg} x (TU (o)Tz U (o(3x)Ex)). We construct a sequence of consistent diagrams (D& $ K so that: for every w, w’ occurring in D there is a c E C so that EC ED(w) and EC E D(w’). The construction is easy and therefore left to the reader. We note the following corollaries to the previous theorems. COROLLARY 1. To b $ iff for all structures .-Q?‘=(W, A, V) for L(Co) and w. E W, if 2 = A(wo) then (4 wo) k 4. To I- 0 9 iff for all structures J/= (W, A, V) for L(Co), if x = A(w,) then (A w) b $I for all w E W. COROLLARY 2. (n)T1 U {0(3x)Ex} I- 9 iff for all structures M= (IV, A, v) for Jo such that for all w, w’ E W if w # w’ then A(w) $ A(w’), (d wo) k 9 for all w. E IV.
20
HAROLD
T. HODES
COROLLARY 3. (o)Ta U {0(3x)Ex} l- @iff for all structures, J/= (W, A, v) for L(Cc) such that for all w, w’ E WA(w) n A(w’) is non-empty, (& we) l= $Jfor all w. E W. 3. INEXPRESSIBILITY
RESULTS
We frrst consider three examples’, (1) A structure &= (IV, A, v) for L(Co) so that (x w) I= To but A(w) # ;i for all w E IV. Let I+’be the set of integers; select A so that all i E W: A(i) $ A(i + I), A(i) is infinite, card(A(i + 1)) = card@(i)), card(A(i + 1) --A(i)) is constant as i varies; suppose V”Co C_n {A(i) 1i E W} and for P E Pred, ~(w,P)isemptyor=fforallwEW.SelectwEWandal,...,a,EA(w). Select an automorphism u on 2 such that for all i E FV,o”A(i) = A(i + 1) and u is constant on V”Co U {ar, . . . , a,). For any br, . . . , bk E& and $J a formula of L(Co), c-4 w) I= fml, * - - , bkl iff
(4 w + 1) I=9E@d,. . . , Wdl.
Suppose (4 w) I= @[al,. . . , a,]. Given any a,,,, . . . , a,,,+” Ea select a EA(w+j).Then(dw+j)l= jEWsothata,+r,...,a,+, . . . . a,]and(~w+j)l=(E~~&...&Ex,)[a,+ ,,..., u,,,+,J. ml,
Thus(&
Tc,.
(2) A structure &= (IV, A, v) for L(Co) so that for we, w1 E IV, A(wo) S A(wr)and( J& wo) l= (o)Tl. First we go on an algebraic digression. Suppose A Cl, A and 1 -A are countably infinite. For F EA, GCA-A,FandGfinite,letA(F,G)=(A-P)UG. LEMMA. If u is an automorphism of 2 and 0’2 = A(F,-,,Go)then for any for F'=(u'!FnA) U (Fo-uol%),G'=
F and G, u'k(F,G)=A(F',G') (u"G-A)u(GO- ul%).
Suppose u is as in the antecedent. Consider a E A(F, G).We show that u(a)EA(F',G'). CaseI: a EA ---I;.Then u(a)E A(F,,, G,). Ifo( A -Fe u(a)6F';so u(a)EA(F',G'). 1fu(a)EG,,u(u)E(G,-u%‘,); so u(a) E G’, and so u(a) EA(F', G'). Case 2: a E G. Then u(u) 4 A(Fo,Go).If u(u) 4 A and 6! G,,, u(a) E (u”G -A); sou(a)E G'; so
EXPRESSIVE
LIMITATIONS
OF
MODAL
LANGUAGE
21
o(a) E A(F’, G’). If o(u) E Fo, u(a) EA. Since a 4 F, u(a) 6? u’!F; since u(u) E u”G, u(a) 6! F’; so u(u) E A(F’, G’). We next show that if a 6?A(F, G) then u(u) 6! A(F’, G’). Ckse I: u 4 A and a 6!! G. Then u(a) 6?A(Fo, Go). If u(a) 4 A and 4 Go, since u(a) 4 u”G, u(a) 4 G’; so u(u) 4 A(F’, G’). If u(a) E F& u(a) E F,, - 0°C; so u(a) E F’; so u(a) 4 A(F’, G’). Case 2: a E F. Then u(a) E A(Fo, G,,). If u(a) E A - F,-,,u(a) E u’!F n A ; so u(a) E F’; so u(a) 4 A(F’, G’). If u(u) E Go, u(u) 4 A; since u(a) 4 u”G; u(u) 6! G’; so finally u(a) 4 A(F’, G’). Q.E.D.
For 2 and A as above, let us introduce a constant w(F, G) for every FCA,G~a-A,FandGfinite,sothatw(F,G)=w(F’,G’)iffF=F’ and G = G’; let W = {w(F, G) I for all such F and G) U {wl}. Let A(w(F, G)) = A(F, G), A(w,) = 2. Select V, and (W, A)-valuation for (Ce) so that where P E Pred, V(w, P) is empty or = f for all w E W, and so that A - y’%c and 2 - (A U V”Cc) are infinite. Suppose u is an automorphism of 2, w, w’ E W - {wr}, u’h(w) = A(w’) and u is constant on V”Ce. Then u: .JY/” & (See [I], p. 202 for definition of (3: d-&?.) I?oofi Without loss of generality, we may suppose that A(w) = A. By the previous lemma for any u E W there is a v E W so that u%(u) = A(v). Since u is constant on V”Cc, our claim follows. LEMMA. Suppose al, . . . , a,, EA(w), w E W-{wl}, a = (al,. . . , a,). Then (& w) I= $[a] iff (4 wr) I= $[a]. Roof, Letting w. = w(( ), ( I), we may assume without loss of generality, that w = wo Select a function p: A +A, 1 - 1, onto A, and constant on V”Co U {al, . . . , a,}. Clearly there is such a p. Suppose p’ E p, p’ is finite. Let F be the empty set, G = range@‘) -A. Then there is an automorphism u of 2, u 2 p’, so that 0’2 = A(F, c). By a previous remark, u: &” JZ’I We may now apply Lemma 1 of [ 1] and conclude that (~~~)~1C([a]iff(~w,)~~[p(u~),...,p(a,)];sincepisconstanton {al,. . . , a,>, our result follows. LEMMA. For any w E IV, (N w) I= (n)Tr. To show this, suppose al,..., a, Eii, a = (al,. . . , a,), and (A w) I= (04 & W i% Ol(G & $))[a].
22
HAROLD
Then for some u, ZJE W, (& show that
T.
HODES
u) I= @[a], (.%‘, V) I= J/[a], u f o. We wish to
(4 w) I= O(@ 8~(3x)0($& lEx))[al. If u = w1 this is clear. Suppose u f wl. By the previous lemma, we may select v so that z,# wl. If A(u) is not a subset of A(v), we’re done. Select b B v’c, u {al, . . . , a,}, b &A(v), and let A(u’) = A(u) U {b). Select an automorphism u of Kconstant on V”CO U {Ql, . . . , Q,} and so that u”A(u) = A(u’). By previous remarks, u: d” &, so ( & u) k $[a] iff (& u’) k @[a] The lemma follows. Hence &and w. are as desired. (3) A structure JZ?= (W, A, V) for L(Co) so that for some wo, w1 E W, A(wo) and A(w,) are disjoint, but (4 wo) I= (o)Tz U (vex). Select ,4(wo) and A(wr) to be disjoint countable sets. For each b EA(wo) and c E A(wr) introduce distinct worlds wo(b, c) and wr(b, c), letting
A(wdh ~1)= &wo) - (b) U {c),4~) - {cl U {b), W= b’o, WI)U {w&r, c), wr(b, c) I b EA(wo), c EA(wr)}. Make sure that A(wo) - v”c, and A(wt) - V”Co are infinite; and let V(w, P) be empty or = f for all w E W, PEPred. For a=(Ql, . . . , Q,),Q~ El =A(Wo) UA(W,), if b,&(al,... , an) U v”c, (ti, wi) I= @[a] iff (d, wi(b, c)) I= @[a]. This is because of an automorphism u on A which fixes (ur, . . . , a”] U v”Ce and exchanges b and c. Using this fact, we easily show that dis as desired. We now consider various structural properties of frames (IV, A) and pairs of the form ((IV, A), wo), w. E FU. PROPERTY 1.
A = A(wo).
PROPERTY 01. For some w E W, 2 = A(w). PROPERTY 2.
For some w E W, A(wo) S A(w).
PROPERTY 02. For each w E W, there is a w’ E W so that A(w) 5 A(w’). PROPERTY 02. For some w and w’ E W, A(w) S A(w’). PROPERTY 3.
For some w E W, A(w) 5 A(wo).
PROPERTY 03. For every w E W, there is a w’ E W with A(w’) S A(w).
EXPRESSIVE
PROPERTY 4.
LIMITATIONS
OF
MODAL
LANGUAGE
23
For all w E IV, A(w) f~ A(w,) is non-empty.
PROPERTY 04. For all w and w’ E IV, A(w) rl A(w’) is non-empty. PROPERTY 04. For some w E W: for all w’ E IV,A(w) f~ A(w’) is non-empty. PROPERTY 5.
For some w E W, A(w) and A(we) are disjoint.
PROPERTY 0 5. For each w E W, there is a w’ E W with A(w’) disjoint from A(w). PROPERTY 05. For some w and w’ E W, .4(w) and A(w’) are disjoint. A structural property of frames (IV, A) for w. E W, is expressible in L(Co) iff for some set T of sentences of L(Co): for all structures LZ?‘=(IV, A, v) and we E IV, (&, wo) I= Tiff (W, A) has that property. A similar definition applies to properties of pairs ((IV, A), wo), where (W, A) is a frame and w. E W. THEOREM 4. The negation of Property 1 is unexpressible. This is equivalent to saying “There could be something which doesn’t acutally exist” is unexpressible. Suppose that for T a set of sentences of L(Co), if 2 f A(wo) then ((IV, A, V), wo) I= T. Example 1 shows that T U To is consistent; then Theorem 1 yields a structure d= ( W, A, v) and w. E W so that (-gll w) k T but 2 = A(wo). (Kit Fine has pointed out to me that this theorem follows painlessly from examination of the models described at the bottom of p. 203 of [ 11.) THEOREM 5. Property 1 is unexpressible. This is equivalent to saying that “Necessarily everything actually exists” is unexpressible. Suppose that T is a set of sentences of L(Co) and that for any structure d= (W, A, v) for L(Co) and w. E W, if (4 wo) I==T then ((W, A), we) has Property 1. For &as in Example 1, (& i) # T; select $JE T so that (4 i) I= 19; then To U {-I#} is consistent; so Theorem 1 yields a structure s= (U, B, V’) for L(Co) and u. E U so that (9, uo) I= -19, so (9, uo) # T, but ((V, B), uo) has Property 1.
24
HAROLD
T.
HODES
THEOREM 6. The negation of Property 01 is unexpressible. Identifying the proposition expressed by a sentence in a structure with the set of worlds at which that sentence is true, this tells us that the necessitation of the proposition expressed by “There could be something which doesn’t actually exist” is unexpressible. Notice: that proposition is not expressed by “Necessary there could be something which doesn’t actually exist”, because of the way in which “actually” refers back to the “starting world”. Suppose that for any structure JZ?= ( W, A, v) for L(C,), if ( W, A) does not have Property 01, then (& we) I= T for w. E W. By examining Example 1, T U To is consistent. Theorem 1 then delivers a structure a”= (W, A, v) for L(C,) so that for some w. E W, (x wo) I= Tand (W, A) has Property 01. Curiously, we can express the necessitation of the proposition expressed by “Necessarily everything actually exists” by “ibex”; of course, “(VX)DEX” doesn’t express “Necessarily everything actually exists”. So the necessitation of an unexpressible proposition may be expressible. THEOREM 7. Property 01 is unexpressible. This shows the possibilification of the proposition “Necessarily everything actually exists”, is unexpressible. Suppose that for some T, if &‘= (FV,A, v) and (& wo) I= T then (IV, A) has Property 01. For dof Example 1, (K i) # T; say (4 r) I= l@ for q5E T. The argument is as for Theorem 5. Again, the possibilification of the proposition expressed by “There could be something which doesn’t actually exist” is expressible by “O(3x)OEx”. THEOREM 8. Property 2 is unexpressible. This shows the unexpressibility of “There could be something which doesn’t actually exist without there not being something which does actually exist”. Suppose for any structure LX’= ( W, A, v) for L(C,) and w. E W, if (( W, A), wo) has Property 2 then (4 wo) I= T. Example 1 shows that T U To is consistent; Theorem 1 delivers a structure &= (W, A, v) and w. E W so that (A wo) I= T but (( ?V,A), wo) lacks Property 2. THEOREM 9. Property 02 is unexpressible. Proof is as above. THEOREM 10. Property 03 is unexpressible. Proof is as above. THEOREM 11. Property 02 is unexpressible. Suppose we have T so that
EXPRESSIVE
LIMITATIONS
OF
MODAL
25
LANGUAGE
for any structure &?= (IV, A, v) and w. E IV, if (IV, A) has Property 02 then (J;d; wo) I==T. Consideration of Example 2 shows that T U (0) T, U {0(3x),&} is consistent; Theorem 2 yields a structure A?‘= (W, A, I’) so that (K wo) I= T but (IV, A) lacks Property 02. THEOREM 12. Property 3 is unexpressible. Proof is as above. THEOREM 13. Property 4 is unexpressible. This says that “Necessarily something actual exists” is unexpressible. Suppose we have T so that if JV’= (W, A, v), (d wo) I= T, then ((IV, A), wo) has Property 4. For the A?’ of Example 3, ((IV, A), wo) does not have Property 4; so ( & wo) # T; select r#~E Tso that (4 wo) k 19; {-I$) U (n)Tz U (vex) is consistent; let .%= (U, B, V’) and u. E U be delivered by Theorem 3; ($ uo) I==l$, so (9, uo) I+ T, but ((u, B), uo) has Property 4. THEOREM 14. Property ~4 is unexpressible. Proof is as above. THEOREM 15. Property 5 is unexpressible. THEOREM 16. Property 05 is unexpressible. THEOREM 17. Property 04 is unexpressible. THEOREM 18. Property 05 is unexpressible. Proofs should now be routine. Conjecture. There is no set Tof sentences of L(Co) so that for all structures AZ’= (IU, A, v) for L(Co) and w. E W: (M wo) I= Tiff for all w E IV, if A(w,) f A(w) then A(w,) n A(w) is empty. It should be noted that (M wo) I= Q iff for all w, w’ E W, if A(w) f A(w’) then A(w) n A(w’) is empty, where 9 is: •(vx)~(v~)(o(~x&1Ey)~~(~x
3(vz)ql?y
3lEZ)).
Observation. If we consider logics other than S5, and permit correspond-
ing accessibility relations to occur in frames, these inexpressibility results
HAROLD
26
T. HODES
carry over to the resulting sort of structures. These results are really just weakenings of the preceding ones. It would be nice to have a single general theorem which explains exactly what distinguishes the expressible from the unexpressible properties. When we move to a second-order modal language, we can express, for example, ‘There could be something which doesn’t actually exist”: (3x)(l(3x)xx&o(3x)(xx&oxx)).
Note added in proof(Sept.
30, 1983): In fact, all properties discussed above are expressible in the second-order language in which type 1 variables range over essences(i.e. over subsets of x)), with Pred and C empty. This is discussed further in ‘On modal logics which enrich first-order SS, forthcoming in this Journal. REFERENCES
[ 1 ] Kit Fine, ‘Failures of the interpolation lemma in quantified modai logic’, JoumaZ of Symbolic Logic 44, No. 2 (1979). [ 21 Kit Fine, ‘Model theory of modal logic, I’, Journal of Philosophical Logic 7 (1978), 125-156. [ 31 Allen Hazen, ‘Expressive completeness in modal languages’, Journal of philosophical Logic 5 (1976), 25-46.
Sage School of Philosophy, Cornell University, Ithaca, NY 14853, U.S.A.
