UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

An essay in natural modal logic Apostoli, Peter J. 1992

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-ubc_1993_spring_phd_apostoli_peter.pdf [ 3.87MB ]
Metadata
JSON: 831-1.0098835.json
JSON-LD: 831-1.0098835-ld.json
RDF/XML (Pretty): 831-1.0098835-rdf.xml
RDF/JSON: 831-1.0098835-rdf.json
Turtle: 831-1.0098835-turtle.txt
N-Triples: 831-1.0098835-rdf-ntriples.txt
Original Record: 831-1.0098835-source.json
Full Text
831-1.0098835-fulltext.txt
Citation
831-1.0098835.ris

Full Text

W accept this thesis as conformingto the requ^tandardAN ESSAY IN NATURAL MODAL LOGICbyPETER APOSTOLIB. A., The University of British Columbia, 1984M.A., The University of British Columbia, 1986A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinTHE FACULTY OF GRADUATE STUDIESDepartment of PhilosophyTHE UNIVERSITY OF BRITISH COLUMBIAApril 1991© Peter John Apostoli, 1991In presenting this thesis in partial fulfilment of the requirements for an advanceddegree at the University of British Columbia, I agree that the Library shall make itfreely available for reference and study. I further agree that permission for extensivecopying of this thesis for scholarly purposes may be granted by the head of mydepartment or by his or her representatives. It is understood that copying orpublication of this thesis for financial gain shall not be allowed without my writtenpermission.(Signature)Department ofThe University of British ColumbiaVancouver, CanadaDate 7- cg \cO7DE-6 (2/88)AbstractA generalized inclusion (g.i.) frame consists of a set of points (or "worlds") W and anassignment of a binary relation Rw on W to each point w in W. generalized inclusionframes whose Rw are partial orders are called comparison frames. Conditional logics ofvarious comparative notions, for example, Lewis's V-logic of comparative possibility andutilitarian accounts of conditional obligation, model the dyadic modal operator > oncomparison frames according to (what amounts to) the following truth condition: oc>13"holds at w" iff every point in the truth set of a bears Rw to some point where holds.In this essay I provide a relational frame theory which embraces both accessibilitysemantics and g.i. semantics as special cases. This goal is achieved via a philosophicallysignificant generalization of universal strict implication which does not assume accessibilityas a primitive. Within this very general setting, I provide the first axiomatization of thedyadic modal logic corresponding to the class of all g.i. frames. Various correspondencesbetween dyadic logics and first order definable subclasses of the class of g.i. frames areestablished. Finally, some general model constructions are developed which allow uniformcompleteness proofs for important sublogics of Lewis' V.Table of ContentsAbstract^ iiAcknowledgements^ ivIntroduction 1Chapter 0: Logical Preliminaries^ 10Chapter 1: Presenting JS5 17Chapter 2: Presenting JK and Some First Degree Extensions^28Chapter 3: Some Semantic Correspondences^ 36Chapter 4: Prestudy For Model Constructions 52Chapter 5: Model Construction for Normal Dyadic Logic^74Chapter 6: Model Construction for Normal Logics Containing STR^87Chapter 7: Model Construction for Natural Dyadic Logic^102Bibliography^ 109iiiAcknowledgementsThis essay is the development of an approach to modal logic started fifteen fearsago by Ray Jennings in his manuscript Leibnizian Semantics: An Essay in MonotoneModal Logic. I want to thank Ray for introducing me to this area of modal logic and thusproviding me with an ideal theses topic and a very stimulating and congenial researchenvironment. I owe much to Ray for providing crucial financial and "modal" support.My supervisor Dick Robinson introduced me to modal logic in my undergraduatestudies; I thank Dick for thus helping me start what has proved to be a very happy scientificjourney. This thesis (and my logical style) has greatly benefitted from Dick's carefulreading. Many thanks to due to Dick and the Department of Philosophy at the Universityof British Columbia for supporting my early research.Finally I want to acknowledge the support of the Killam Trust, Canada Council andthe Simon Fraser Advanced Systems Institute. Also, many thanks to the Department ofComputer Science at the University of British Columbia for generously providingcomputing facilities. This essay was produced there on a Macintosh IIcx runningMicrosoft Word 4 and printed on an Apple Laser printer.ivIntroduction^ 1Introduction.Kripkean accessibility semantics is a generalization of the so-called leibnizian truthcondition according to which necessary truths are those true in all possible worlds. On theKripkean account, the range of possibilities relevant to the evaluation of a necessitystatement is relativized to the point of evaluation, according to the truth condition that asentence is necessarily true just in case it is true in every accessible (or, as we sometimessay, alternative) world. The leibnizian account is restored when the relation of accessibilityis taken to be universal, so following Scott [19], the leibnizian truth condition may be saidto model universal necessity.It's worth noting that the Kripkean account of necessity is only incidentally leibnizian.In [12], the universality of necessity is held to be consequence of Leibniz's more basicintuition concerning the relation of entailment, viz., that necessary truths are those whosenegations analytically entail a contradiction. (And hence "would also obtain if God hadceated a world with a different plan" ([20], p.438).) In accord with the conceptual priorityLeibniz places on the analytical account necessity, this essay presents normal modal logicas the definitional extension of a theory of generalized strict implication obtained bydefining necessary truths to be those whose negations imply a contradiction.In its strict implication form, universal necessity captures the central notion of classicalentailment, according to which a entails 13 iff the set of possible worlds (read: valuations)where a is true is a subset of those where is true. This inclusion, or categorical,representation of strict implication is maintained in Kripkean relational semantics for strictimplication, since a strictly implies 13 at a world w iff the set of w-alternatives where ais true is a subset of those where 13 is true. As Ray Jennings has argued (in [7], [8]),accessibility semantics is thus unsuited to the general study of dyadic modal logic, since thecategorical representation forces a whole range of deductively independent classicalIntroduction^ 2principles upon us (as shown in Chapter 3). Indeed, in terms of mathematical generality,we shall see that dyadic logic is in many respects a more suitable vehicle for the study ofunary modal logic than the latter is for the study of the former.The present-day possible worlds literature contains an approach to modelling dyadicmodal operators on relational frames that is not based on truth-set inclusion. Dyadic logicsof various comparative notions, for example, Lewis's notion of comparative possibility(see [14], [15], [16]) , and utilitarian accounts of conditional obligation (as in [0], [3], [4],[6]) interpret dyadic modal operators on frames under partial orders determined by the pointof evaluation. This is done according to (what amounts to) the following truth condition:[T C] a> (3 holds at w iff every point in the truth set of a bears Rw to some point inthe truth set of 13.wherew is the point of evaluation and 12,4, is w's partial order.Although these "comparison semantics" are not motivated as modifications of strictimplication, they nevertheless fall under Jennings' notion of a generalized inclusion frame.A generalized inclusion (g.i.) frame consists of a set of points (or "worlds") W and afunction which assigns a binary relation Rw on W to each point w in W. Generalizedinclusion models are defined on these frames according to CT C] above. Within the class ofsuch structures, g.i. frames which place order-theoretic restrictions on the Rw are calledcomparison frames.With the exception of Jennings [6], [7] and [8] the study of generalized inclusionsemantics has been restricted to the theory of comparison frames. This seems odd, sinceeven if one concedes the philosophical primacy of the comparison-theoretic interpretation ofgeneralized inclusion, mathematical generality would still seem to require a characterizationof the logic validated by the full class of g.i. frames. But perhaps a more pointed complaintIntroduction^ 3concerns the surprising absence of provably complete axiomatizations of proper subclassesof the class of comparison frames. The only successful axiomatic characterization of anyclass of comparison frames that I am aware of is Lewis' presentation of the V-logics in his[15]. But even here, consideration is restricted to a very small subclass of comparisonframes, those featuring strongly connected, transitive and reflexive comparison relations.Since nothing in Lewis' philosophical account of comparative possibility requires such astrong brand of comparison, the technical problem of closing this gap in the literatureshould have philosophical merit.One of the goals of this essay is to axiomatize the logic of various classes of g.i.frames that properly extend the class of comparison frames, as well as axiomatize propersubclasses of Lewis' comparison frames.Another goal is to present a unified relational frame theory which embraces bothaccessibility semantics and g.i. semantics as special cases. This goal is achieved via ageneralization of universal strict implication which does not assume accessibility as aprimitive. This unified framework is an extension of Jennings' generalization of universalstrict implication presented in [6], [7] and [8].The motivation for Jennings' generalization of the categorical perspective given in [6],[7] and [8] is largely independent of order-theoretic considerations. It has its conceptualand historical roots in a temporal view of hypotheticals nominally attributed by Jennings toDe Morgan. This view allows for (but does not require) an element of temporal lag toseparate the situation in which an antecedent of a conditional holds from those in which theconsequent holds. One metaphor operative in Jennings' analysis of conditionals is ageneric notion of the causal or temporal "production" of situations or states: On this view,at least some natural language conditionals express the claim that situations where theIntroduction^ 4conditional's antecedent holds "result in", "produce" or (at least) are "temporally succeededby" situations where the consequent holds.The causal / temporal transition between states is given frame-theoretic articulation viathe g.i. frame-relations: a> 0 holds at a given point just in case every a-state "produces" a0-state in the sense of bearing the given point's relation to some 0-state. As emphasized byJennings, on the categorical view of conditionals, one situation may "produce" anotheronly by virtue of being identical with it.In order to present Jennings' generalization of universal strict implication, suppose wehave at hand a propositional language containing material implication, —*, and the familiarnecessity operator, 0. Within this language, we represent the strict implication of 0 by aby the sentence 0(a—> (3). Now, suppose we have a "pre-accessibility" model .M =(W,V), where W is a nonempty set of possible worlds and V a valuation which assignstruth values to sentences relative to possible worlds according to the truth condition that Octis true at a possible world w just in case a is true at all possible worlds in W. We mayMexpress the truth of a at a possible world w by the familiar notation k a . It iswconvenient to think of V as assigning "truth-sets" to the sentences of our language such thatMthe truth set of a, Eta Al , is the set worlds w such that^a.wThen the defining truth condition for strict implication may be taken to be:Atkw 0(a —0)^<=>^cram Al c 1113EMJennings proceeds by expressing the inclusion of II a.11.84 in [PIM by the quantificationalscheme (VxE if an) (ly e ff [3]Dx = y . Then the truth-set inclusion representation ofuniversal strict implication may then be expressed by the condition0(a—* ^<=* (VxE [Calm ) (lye CI DE M ) x = y .Introduction^ 5M is now "transformed" into a generalized inclusion model by generalizing role of identityto that of arbitrary binary relations determined by the choice of w. Taking the wedge toexpress the resulting notion of generalized strict implication, we obtain the truth conditionM[U>l k a> (3 4.> (Vxe MI") (3y e [E(311M ) x Rw y .wHere, of course, we think of )14 as a model based on a g.i. frame (W,R), where R is afunction which assigns Rw to w E W.Let's call the logic determined by the class of g.i. frames under truth condition [U>]JS 5 (for "generalized S5"). Now, within the setting JS 5 , the original "universal" necessityoperator 0 may be recovered via the liebnizian definition thatDa =df "la > 1.JS5 is an extension of S5 in the sense that S5 is its unary fragment under the leibniziandefmition of the necessity operator. (See chapter 0 for a definition of the unary fragment ofa dyadic logic). Further generalization is required to model relative necessity in this setting.So, an obvious question arises: how best to parallel the introduction of the accessibilityrelation into the g.i idiom and thereby allow for the semantic articulation of J/ for unarymodal logics Z extending the base monadic modal logic K? (See Chapter 0 for apresentation of K.)David Lewis' presentation of the V-logics of comparative possibility (in [14], [15],[16]) provides two answers to this question. We can modify one to provide for an"accessibility-theoretic" relativization of the [U>] which maintains the philosophical spiritand the mathematical form of Jennings' generalization of universal strict implication. First,consider the following version of the comparison semantics presented in [16], where ourIntroduction^ 6'a >13' stands for Lewis' '(3-<^, (read "(3 is at least as possible as a", or "a is as far-fetched as 13 is")Assume a propositional language with the wedge as a dyadic modal connective. LetW be a nonempty set (of "worlds") and let D be a function which assigns a set D(w) c Wof "accessible" points to each w in W. Let R be a function that assigns a transitive,strongly-connected binary relation on D(w) to each w in W. Let hitit be a model on aframe (IV, D, R). Then Lewis' truth condition for the wedge may be presented thus:[L>] k a > 13 <=> (vxE D(w)) [x [laMM (3yE I[1311 M )xwIn [15] Lewis considers the suggestion that rather than assuming the accessibilityfunction D as an additional primitive, he might have let the comparison relation do thestructural work of D(w) by relativizing the universal quantifier in condition [L>] to thefield of v. In effect, R would come to assign a set of accessible points to a given pointin the form of the field of that point's comparison relation. Lewis rejects this suggestion as"clumsy", but we shall take advantage of a related proposal which relativizes the universalquantifier in [L>] to the domain of 5..w.Recall the causal intuitions among those that motivated Jennings' generalization ofuniversal strict implication. It seems reasonable, in evaluating the truth of a conditionalwhich is asserted on roughly causal grounds, not to require every a-sate to produce a 13-state, but rather only those a-state's which satisfy certain preconditions. For example,causal conditionals which are asserted against a background of theory might be committedonly to the causal outcome of antecedent states that satisfy certain theory-global (asopposed to antecedent-relative) ceteris paribus conditions. Or some conceptually possiblestates might not be causally efficacious at all (perhaps because they are physicallyimpossible).Introduction^ 7In both cases, it seems appropriate to articulate such restrictions in terms of the statesor events to which the causal relations apply, namely, those in the domain of the causalrelation. We might want to say then that 13 on the condition that a" is true if every a-state that "produces" anything (according to our theory) produces a I3-state. For any binaryrelation H, Let dom(H) stand for the domain of H, i.e., dom(R) =df {x I (3y) x Hy). Wewould then obtain the truth condition[R>] a>{3 <=> (VxE dom(Rw ))[.,x€ Dm ),(3 E ViMM XRwy] ,for models ,44 on a g.i. frame (W, R).The key virtue of this style of proposal is that it allows g.i. semantics in general, andcomparison semantics in particular, to be viewed as a mathematical generalization ofKripkean semantics, as follows.Let a Kripke frame (14/, D) be given, where D is an accessibility function, that is, afunction which assigns a subset of W to each point in W.. For each subset S of W, let=s be the identity relation on S. Note that dom(=s) is S itself. Assuming a model M ,we can express the Kripkean truth condition for the strict implication of 0 by a at W E Wby.1tv CI( a (3) <=› (Vx dom(=D(w)))[x llocEM (3y Eff 13Bm ) X 7-1D(w)Y1•Generalizing the role of identity to that of an arbitrary binary relation R w, determined by thechoice of w on a generalized inclusion frame (W, R), we obtain [ll>], as desired.Jennings' original truth condition [U>) is not quite restored in the special case of"universality", viz. when dom(Rw) = W for all w in W, since [U>] does not requireevery frame relation to provide every point in W with a relatum. Under [U>], thisrequirement on g.i. frames corresponds to the principleIntroduction^ 8[N*) T>T.(or, equivalently, a > T). So, under [R>], we are stuck with [N*], and thus in the movefrom [U>] to [R>] we trade some of the semantic generality afforded by Jennings' analysisfor greater flexibility in modelling unary modal logic.In this way, we come to simulate the Kripkean accessibility relation by the domains ofg.i. frame relations. In effect, each g.i. frame F = (1 V , R) induces a unique Kripkeanframe (IV, RF), where the accessibility relation RF is defined as the existential projectionin y of the ternary relation Rwx, y :wRFx 4:=>df (3ye W) xRw y (w, XE W).Thus I can unify two formerly unbridged semantic idioms. One immediate payoff is thatmany of the preservation concepts and results for Kripkean definability theory areautomatically translatable into the model theory of dyadic modal logic under the uniformprocess of generalizing on the relation of "Kripkean identity" between worlds.In this essay, I use the terms "possible world", "frame-object", "point" and "state"interchangeably. It is not my intention to invoke a notion of possible world which is anymore metaphysically robust than is the model theorist's mathematical point. Frame-objectsshould be thought of in any way that will yield a good interpretation. Prima faciecandidates are: points in time, counterfactual situations, situation types, physical states orstate types, events or event types, actual or possible global welfare distributions, states of amachine, etc. I want to play down the admittedly important task of finding significantinterpretations for my relativization of the truth-set inclusion schema. Readers who arehappy with the the Kripkean notion of metaphysical accessibility ([10], [11]) or Lewis'notion of comparative metaphysical accessibility ([15], [16]) are free to interpret [R>] as anotational variant [L>] intended to apply to the full range of g.i. models; no oldIntroduction^ 9interpretations are lost in the move to [R>]. Those who are not will be assuaged by the factthat [12>] does not require such interpretations: the door is open for new, perhapsnaturalistically acceptable, interpretations of the wedge.In Chapter 1, JS5 is presented and semantically determined as the logic of the"universal" g.i. truth condition. Chapter 2 presents JK and various of its first degreeextensions. In Chapter 3, semantic correspondences between these logics and first ordersentences in a single ternary relation are established. In Chapter 4, further completenesstheory is developed which serves as a basis in Chapters 5, 6 and 7 for model constructionsthat provide for the semantic determination of many of these logics. These constructionsallow, in particular, for the semantic isolation of the order-theoretic principles employed inLewis' V-logics.Chapter 0^ 10Chapter 0: Logical Preliminaries.Most of our notational conventions and metatheoretic definitions are taken over fromGoldblatt [5]. I shall observe Chellas [2] in the naming of modal principles and inferencerules. We shall be considering a propositional language L(0) whose primitive basisconsists of a countably infinite set = {Pi , P2, - ..} of propositional variables (or,atomic formulae), a propositional constant 1 (the falsum), a binary truth functionalconnective --> (material implication), and a binary modal connective > (the wedge). Theset Fma(0) of formulae, or sentences, of our language is generated from this primitivebasis according to the following scheme:_LE Fma(0)0 g Fma(0)a, 0e Fma(0)^(a>f3)E Fma(0).As indicated 'a' ,^,^, '8' , . . . will be used to denote formulae. Parentheses willoften be omitted or replaced by informal scope-delimeting punctuation (such as brackets,braces, dots etc.) when it is convenient to do so.A formulae a is called first degree iff it contains no nested occurrences of '>', that is,iff no occurrence of '>' is in any subformula of a of the form (3>y.I'll assume a enumeration •:1) : w ---> Fma(0) of the language with the convention that'4)i' denotes the i th formula in the ordering.We introduce expressions for the familiar truth-functional constants and connectivesinto our metalanguage according to the standard abbreviatory definitions, as follows:-1a=dfa-*1, T =df avr3 =df 0, a/4i =df -IP) etc. The unary modaloperators are introduced by the following definitions: Da =df -la> 1 and o a =df11Chapter 0-1(a>1). I shall make use of another defined unary modal operator: Da =df T > a. Aconvention used in the sequel is that in case n = 0, the expression '(ai A . . . n an )'denotes T and '(a1 v v an)' denotes I. Hence,'(al A ... A an)--4 13 1may be taken to denote the formula 13, and'13 —)(ai v v an)'to denote -113, when n = 0.A schema is a collection of uniform substitution instances of a given formulae. Forexample, by the schema Da-* a , we intend the set of formulae0=0—>P :13E Fma(0)).A (dyadic) logic is a set A c Fma(0) such that:i) A includes all tautologiesii) A is closed under the rule modus ponens, [MP], i.e.,a, a -313 E A^PE A.iii) A is closed under uniform substitution, [US], i.e.,OCE A^a'e A,where a' results from uniformly substituting formulae for atomic formulae in a.If A is a logic, we write 'FA a' (a is a theorem of A) for 'ae A'. If F is a set offormulae, 'F FA a' ("a is deducible from r") means there are n E CO and al, . . an E Fsuch that.FA (ai A • A an) --> a12Chapter 0Observe that tivially: r FA a iff there is a finite subset r of r such that r' FA a .A formula a is quasi-atomic if either cm 0 or a is 0>y for some (3,y€ Fma((). Let04 be the set of quasi-atomic formulae. A valuation of Fma(0) is a function Val :^-4T, F ). Since every formula can be constructed from members of 04L)^) using --> ,every valuation Val may be extended to a unique assignment of truth-values to all formulaeaccording to the truth tables for 1 and ; we shall identify Val with its truth-tabularextension.A formula a is a tautological consequence of formulae al, , an iff a is assigned Tby every valuation of Fma(0) which assigns T to all the al, . ., a n . It is well known thatevery logic A is closed under the rule[RPL] FA al, • • • , an^FA a ,where a is a tautological consequence of al, . • an (cf. [2], p.3'7) . Hence, [RPL] willbe used as a derived rule in the sequel.A set of formulae is A- consistent just in case F/A 1; otherwise it is A- inconsistent .A set of formulae is maximally A- consistent, or, A-maximal (sometimes: a A- maxi-set )iff it is A-consistent and has only A-inconsistent proper extensions. Throughout thesequel, we wil assume as given, and make free and often implicit use of, the followingwell-known results concerning the existence and properties of A-maximal sets. The readeris referred to [2], pp.53-56, or [5], pp. 18-20 for further details.Let r be a maximally A-consistent set of formulae. Then:(1) a e F^iff^r F A a(2) A c r(3) T E r13Chapter 0(4) a --) 00 r^iff^if a E F, then 13 E r(5) 1 0 r(6) r is closed under tautological consequence.Lindenbaum's Extension Lemma: Let F be a set of formulae. If r is A-consistent,then there exists a set A of formulae suchc that (i) r g A, and (ii) A is maximally A-consisitent.Let MAXA be the set of all A-maximal sets. For any formula a, let I a1 A be the setof all A-maximal sets that have a as a member (the A superscript will often be omitted).For any set of formulae F, let Ir. A1 be { s E MAXA 1 F s s } . We'll also observe thestandard convention that for any unary connective • (defined or otherwise):•{11 =df (*a I ae r) and•(r) =df { a I •cm r}For example, Dm =df {Oa I ae r} and On =df fa 1 0a€ F ) .By the unary fragment of Fma(0), denoted Fma(0)0, I intend the collection offormulae all of whose modal subformulae are of the the form Oa or 0 a. Fma(()0 maybe defined recursively as the least subset of Fma(() which includes 0, contains 1, andcontains a-->13, -I a> _l_ and -1(a>.1) whenever it contains a and J3. The unary fragmentof a dyadic logic A, denoted Ao, is defined as the restriction of A to the sublanguageFma(0)0, i.e.,A° =df Fma(40)13 nA.The above definition of deducibility and [RPL] allows us to prove a "DeductionTheorem":rufal FA 13 <4.^r FA a--->13 .14Chapter 0Let A be a dyadic logic. A is prenormal if it is closed under the rule schemata for"right" and "left" "monotonicity",[IRK[RMT]FA a-43^FA D>7 --> a>7 ,FA a --0^FA 7>OC -4 7>P ,and includes the schema of "disjunctivity",[DS]^FA (a>7 .n. 3>7) -4 ((avP)>7 ) ,together with the principle of "necessitation" for ^ :[N]^FA DT,^i.e.,^PA 1>1_(equivalent to 1> a given [RMTD. A is normal if it is prenormal and includes theschema of necessitation for[N*]^FA 0 T,^i.e.,^FA T >T.(equivalent to a> T ginen [RM]si,). If A is (pre)normal and A includes the schema[M11^FA ^(a -) (3) -> (7>a .—>. 7>(3 ) ,then A is called (pre)natural.Its easy to show that a logic which is closed under [1RM] and [RMT] is closed underthe replacement of provable equivalents, allowing admission of the derived "Rule ofExtensionality" for (pre) normal dyadic logics:[RE]^FA ai--->a'^FA (3<-->3'where 13' is obtained from 0 by replacing one or more occurrences of a by a'.Chapter 0^ 15Since this essay presents dyadic modal logic as a generalization of monadic modallogic, it seems fitting to briefly present K, the smallest monadic modal logic admitting of aKripkean semantics. Rather than repeating the standard definition of the language ofmonadic modal logic (as in [2], pp. 25-26, or [5], pp. 3-4), we will use the languageFma(0)0, since it is allready at hand. Then we can define K to be the smallest dyadic logiccontained in Fma(0)0 which includes the axiom schemata [N] and[C]^(^an^O) -4 I:1(a A (3)and is closed under the "Rule of Monotonicity"[RM]^F a-> (3^I- 0a-4013.Now let's table some semantic notions: A frame is a pair F = (W, R), where W is anonempty set and R : W ----> 2W is a function which assigns a binary relation Rw on Wto each w E W. A 4)-model based on F is a triple .1Vi = (W, R, V) , with V:0--> 2Wa function assigning to each atomic formula p €0 a subset V(p) of W. The prefix 'Ix'will generally be omitted.We extend V to valuations II DM : Fma(0)---> 2Wx W via the usual inductive clausesfor 1 and --->, viz,MLLB =0m mff(a-4(3)31M = (IV— if a 11 ) u 1113]] .In Chapter 1, V is extended under the following inductive clause for > :M^ m^A4[U>]^ffa>133)^= { 141 E W I (b5cE ffall ) (3y€ Q(3.11 ) x R wy) .Chapter 0^ 16so that we may briefly study the "universal" generalized inclusion. These models are calleduniversal g. i. models.The remainder of the essay focuses on "relativized" generalized inclusion modelsobtained by the truth condition, ^,^M ,[R>] Ila > 13B^t= we WI Vx e dom(RwAxe Man^k By E Q131 )xRw y]l .These models are called relativized g.i. models.In both semantic settings, we define the relation of a is true at a point w in a modelM.A4, symbolically, k , byw.A4k a 4:=> cif w E Ea.A4^(w € W)wThe notion of truth on a model and validity are defined as usual: A formula a is trueMon a model M, denoted .,A4 ka or k a, iff it is true at all points in M, i.e., ifMk a for all w E W .wa is valid in a frame F = (W, R) , denoted F k a , iff.A4 k a for all models M based on FI shall often identify a frame F with the unique ternary relational structure (W, RF),where RF c W3 is given byRF (x,y , z) iff yRxz^(x, y, z E IV)Accordingly, I shall often identify a model ,A4 based on F with the triple (W,RF,V). Incontexts where F is given, RFwill often be referred to simply as R. I will use expressionsof the forms 'Rx(y, z)', 'y R x z' , 'R (x, y , z)' , 'xR y, z' interchangeably.17Chapter 1Chapter 1: Presenting JS 5 .In this chapter we present JS 5 and determine it as the logic of the "universal" g.i. truthcondition [U>]. One of the themes of this and the next chapter is that when the unarymodal operator is introduced by the leibnizian definition, the conditions that constitutenormality in Kripkean modal logic are seen to be special cases of some fairly subtleproperties of classical implication. For example, the axiom[K]^0(a -4 (3) -4 (^a—>^0)is an instance (modulo an application of [RE]) of the following left-downwardmonotonicity principle, to the effect that the wedge admits strengthening of antecedentsunder its defined strict implication:0(a --> (3) -÷ (13>y —> ot>y) .(0(cc-43) --> ^(1(3--ria) by [RE], so 0(a --> (3) --> (-1a>1 -4 -1(3>1) by [1M], butthis last is [K], by the definition of ^.)Note that, from a deductive point of view, [.ARM] stands to [1M] as the "Rule ofMonotonicity"[RM]^I- a-->I3^I- ^a—>^13stands to [K] in monadic modal logic. Indeed, in the derivation of [IM] from OM]below, [DS] plays the same role as does the modal "aggregation principle"[C]^(^aA^13) --> ^(an(3)in the derivation of [K] from [RM].Chapter 1^ 18Such principles as [1.M] relating the wedge to its defined strict implication are hard toisolate semantically when the study of generalized inclusion is restricted to comparisonframes. The reflexivity and transitivity of comparison are particularly guilty offenders.Reflexivity of the frame relations R w forces enough of the classical subsetrepresentation on us to guarantee that the wedge preserves classical entailment, whence thevalidity on comparison frames of a "deduction theorem" for the wedge:[RD]^I- a-0^F a>13.However, reflexivity corresponds to the principle of "Preservation of Strict implication"[PS]^El(a--> 13) ---> (a>13) .which is equivalent to closure under [RD] in some prenormal logics. Notice that [PS]entails [1M] given the transitivity of the wedge. Hence, [PS] is not separable from [1M]on comparison frames.Let JS5 be the smallest prenatural logic which includes the S5 principles [5] and [T]below. Recalling Chapter 0, JS5 may be presented as follows:[IRK^liss a—>13^1s5 py .—>. a>y ,[RMi]^I- a—> f3^I-SS y> a .-4. y>(3.JS5^J[DS]^lis5 (a>y .A. I:3>y) —> ((avI3)>y)[N]^I- OTJS5[MT]^F 0(a-413) --> (y>a .—>. y>p)Js5[5]^I- oa-400aJS5Chapter 1^ 19[1] I-0a-> a155The explicit inclusion of [N] is redundant, since [N] is an [RPL] consequence of [5] and[T]. Noting that [RM] is an [RPL] consequence of [1RM] and recalling that [K] is an [RE]consequence of [1M], to show that (JS 5)° is S5, it suffices to show that [.I.M] is derivable:0.^0I- -1(a--413)>1.--->. -1(a-->0)>y^[RMi], [RPL]51. I- 0(a—> (3) --> ( -1(a --> r3)>y)JS5^ 0, df. 02. I- 0(a -4 5) -4 (([3>'y) —> (( --7 (a ---> f3)v 13)>y)) 1, [DS], [RPL]JS53. F 1=1(a —>13) -5 ((3>7) --> ((avi3)>Y ))JS5^ 2, [RE]4. I- 0(a—> r3) -4 (0>y .-4. a>y )JS5^ 3, [RPL] and [.ARM]The "Rule of Necessitation"[RN]^I- a^I- Daendows the wedge with the classical property that the negation of a logical truth implies acontradiction, whence, on the leibnizian definition, the necessity of logical truth. JS 5 'sclosure under [IRM] , respectively, [RMi] is guaranteed by [RPL], [RN] and [IM],respectively, [MT]. Therefore, JS 5 may be more elegantly characterized as the smallestdyadic logic with [T], [5] which is closed under [RN] and includes[DS] (a>7 .A. 13>y) -4 ((avf3)>y)[-I-M] o(a--->13) --> (0>Y .—>. a>y)[MT] 0(a—> I3) —> (y>a .-->. y> 13) .(Hence the explicit inclusion of [RMi] in the first characterization is redundant.)Chapter 1^ 20Of importance in the sequel is the "preservation of diamonds" principle[PD]^lis5 (a>(3)^(0 a - ^o(3)to the effect that the wedge preserves possibility:0. F13>1 .-->. -1-10>J_ [RE], [RPL]JS51. lis5^El((3 -41) 0, df. El, df. i2. I-S5 DO —>.1) ---> Qa>(3)--> (a>1))J3. lis5^((a> (3) —> (a>_L)) 1, 2, [RPL]4. I-^(a> fi) --> (-1(a>1) —> --1(0>1))JS5 3, [RPL]5. F.^(a> f3)^(o a—) 0(3)JS5 4, df. 0 ,At this point the reader may whish to recall from Chapter 0 (pp.15 - 16) the semanticsof "universal" generalized inclusion, in particular, the definitons of frame and universal g.i.model . The proof of the semantic completeness of JS5 with respect to the class of universalg.i. models requires a few preliminary results:Theorem (Scott's Rule) 1.0:^r F a^o[F] I- DaProof: Suppose F F a. By the definition of deducibility (Chapter 0, pp. 11 - 12) there aren E Co and al E r (1^n) such that(ai A . . . A an ) -->so bt [RM],F 0(a1 A . . A an) --> Da.Now generalized aggregation (repeated applications of [C]) yieldsChapter 1^ 21F (oai A . . . A Dan ) --) 0(ai A . . . A an)whence I- (^ai A. . . A Elan) --> Oa by [RPL]. Then we have the desired result that^[r] F Oa by the definition of deducibility.^■Separation Lemma 1.1: Let A be a prenatural logic. Let WE MAXA and a,13 beformulae such that a> 130 w. Letr = { 8 I (37)[ (8>y)E w & ^(w) FA y-413 ll.Then there is a UE MAXA with 0(w) g u such that aE u and Fnu = 0.Proof: Suppose that a>fle w. By Lindenbaum's Extension Lemma, it suffices to showthat 0(w) u { al un [F] is A-consistent. Towards a contradiction, suppose not. Then bydef. deducibility and deLA-inconsistency and [RPL], there are n 0 and S1, . . ., 8n E rsuch that ^(w) FA ('61A ... A --1811) —> —la ; by [RPL],(1) ^(w) F A a ---) (Si v . . . v 8n),whence the choice of F gives yi, . . . , yn E Fma(0) such that(8i>yi)E w and 0(w)F Ayi —>I3 (1 S i 5_ n).Let 8n = Siv ... An and yi . yi v ... v yn . Then (1) yields,(2) w F A E(a--)8n),by Scott's Rule and the fact that ^[^(w)] g w. Now, repeated applications of [DS] and[RPL] yield(3)^FA ((8 1 >Y)A — A(5n>Y)) -9 (8/1>r).Chapter 1^ 22By [RPLJ, F A^[RMT] yields FA (81>yd (Si> r); since Si> yiE w , wehave Si>rE w (1 S i S n). Then (Si> 'Yn) A^A on>yoe w , whence (3) yields theresult On>yle w .Now, 0(w)I- Ayi—>p (1^n) yields 0(w)i- A r—>I3 by [RPL], whence we havew F A Exyn—*(3) by Scott's Rule, whereby [Mt] yieldsBut by [1M], (2) yieldsSOw F A (a>71) --> (a>(3).w F A (8n>1) (a>yl) ,W FA (On>r) --> (a> P).Since 811>r) e w, we have (a>13)E w, contrary to the hypothesis of the lemma. ■Let A be a dyadic logic with [T] and [5]. Define a binary relation^on MAXA bys t^iff^^(s) g r.^(s,tE MAXA)Lemma 1.2:^is an equivalence relation.Proof: The proof is routine: [T] insures that is reflexive, [5] that is euclidean. Henceis symmetric and transitive.^ ■Corollary: s t^^(s) = ^(t). ■I shall now establish the completeness of JS 5 with respect to the class of universal g.i.models. Let A be a -prenatural logic which includes the S5 reduction principles. Thestrategy is to construct, for a given A-consistent set A, a -model MA which satisfies A inChapter 1^ 23the sense that MA contains a point where all of A members are true. The universe of MAwill be constructed out of the traditional (i.e., Lemmon-Scott, cf. [13]) canonical universeMAXA by a proccess which may be thought of as the addition of extra "copies" ofelements of MAXA. Hence, .84A will contain numerically distinct worlds which do notdiffer according to the sentences they verify.Invoking Lindenbaum's Lemma, let ME MAXA be a A-maximal extension of A.For each WE MAXA and a> 0 0 w as given in the hypothesis of the SeparationLemma (1.1), let 'wa>j' denote a fixed u given by that lemma. That is, when a> Pe w,then wa>0 E MAXA is given by 1.1. such that ^(w) c wa>p, a e wa>p and rn w oc>0 =0, where F = [8 I (3y)[ (8>y)E w & ^(w) FAy--> p.• }}. Note that this choice of u givenw and a> 0 does not require the Axiom of Choice, since we could specify u uniquely (interms of our enumeration 0:a) --> Fma(0) from Chapter 0) as the 0—canonical maximallyconsistent extension of la } u 0(w) u —1[F] , which the proof of 1.1 shows to be A-consistent.Recall from Chapter 0 that I ^(A*) I A =df {SE MAXA I ^(M) g s} . Define WA, theuniverse of MA, to be the following subset of I ^(0*) 1 A x (Fma(0)U f 0 1) :{ (w, 0) I WE I D(0*) I A 1 U { (wa>13, a>13) I WE 1 0(M)1 A & a>f3e w } .We will use the left and right projection operators LL), R(_) so that P = (L(P), R(P)) forany pair P E 10(A*)1 A x (Fma(0)L4 0 } ). The pairs Pe WA are treated as "copies" ofthe A-maximal sets L(P)e I ^(A*) I A .For the rest of this chapter, we will use the variables x, y, z to range over W.Chapter 1^ 24Lemma 1.3: Let XE W. Then ^(L(x)) = ^(A*).Proof: If xe { (w, 0) :wE I 0(6.*)1 A 1 , then A*.---L(x), whence the desired result followsby the Corollary to 1.2. So assume that xe { (wa>p, a>13): w e I D(A*)I A & a> PE w } .Then L(x)=wcf>0 for some wE I ^(6,*) I A, whence ^(w) g wa>13 by Lemma 1.1 and thechoice of wa>0. But ^(0*) c w and ^(w) c w oc>0 yields A*.--: w = w oc>o, so by thetransitivity of ..-- (Lemma 1.2.), we have 0*----.wa>0. It follows by the Corollary to 1.2 that^(wa>0) = ^(0*), as required. ■The construction of M 6, is in two stages; the first stage guarantees that the left-to-right direction of the truth condition [U>] holds on MA and the second that [U>] holdsright-to-left.T FFor XE WA, define a pair of binary relations Rx, RX on WA by:TRx = { (y, z)I (13a>(3)[y= (L(x)a>p,a>13)] & (38>y E L(x))(SE L(y) & ye L(z))}R x = {(y, z) 1(3 a>I3)[y = (L(x)a>p,a>13)] &(38>y E L(X))[OE L(y) & ye L(z) & (3o L(z)] 1_.>Then let RX =df RX l.) RX . Define a frame F = (WA, R) where R: We 2 WAxWA i sa function which assigns RX to each x in WA.Lemma 1.4 : Let xe WA. Let 8>y be a formula. Then8>ye L(X) <=> (bye WA)[8e L(y)^(3ze WA)(yE L(z) & yRx z)].Proof:^. Let S>yE L(x). Let y E WA such that SE L(y). We need to show that thereis a ZE WA such that yE L(z) and yRx z There are two cases:Chapter 1^ 25i) (13 a>(3)[y = (L(x) a>p,a>13)]. Since x, y E WA, we have El(L(x)) g 111(L(y)) byLemma 1.3, whence o [L(y)] c L(x). So SE L(y) yields 0SE L(x), whence 8> yE L(x)gives oyE L(x) by [PD]. So y>10 L(x), whence there is a UE MAXA such that ^(L(x))S u and ye u by Lemma 1.1. Then 0(L(x))= O(0*) (from 1.3) yields ^(A*) g u, thatis, UE 10(A *) I A . Let z= (u, 0). Then zE WA by the definition of WA. So we have aZE WA such that ye L(z). Then (y, z )E R. by the definition of that relation. This issufficient.ii) (304)[Y=(L(x) ce>p,a>(3)]. Then L(x) ce>pe MAXA was chosen using Lemma 1.1such that EXL(x))g L(x) ce>p, ae L(x)a>0 and rnL(x) ct>13 = 0, wherer = {8 I (3y)[ 8>ye L(x) & ^(L(x)) F A y--)13 ] ).Since 8> yE L(x), it follows that ^(L(x))1/ A y--> 0, since otherwise SE I' by def. r,contrary to the fact that SE L(y) and 1-nL(x) a>0 = 0. Now, XE WA gives ^(L(x)) =OW) by Lemma 1.3. So we have El(A*)W A y --) 0, whence 0(0*)u { y, -101 is A-consistent. So by Lindenbaum's Lemma, there is a z= (L(z), 0) E WA such that yE L(z)and 13e L(z). Then we have (y,z)E 'RFx by the def. RFx as required.. Suppose that 8>ye L(x). We need to show that there is a yE WA with SE L(y) suchthat for all zE WA, yRx z ye L(z). Since XE WA, we have L(x)E I ^(A * )1 A ,whence 8>ye L(x) yields (L(x)8,7,8>y)E WA by the definition of WA. Also, L(x) 5>y isgiven by 1.1 such that SE L(x)8,7. Then it suffices to show thatL(x)8>yRx z^ye L(z)^(zE WA)Towards this, let ZE WA such that L(x)8,1,Rx z. Then we have L(x)5>yRxz by def. R x.iThen the definition of Rx insures that ye L(z), as required to complete the proof ofLemma 1.4.^ ■Chapter 1^ 26Now, we can define our desired model Jtot A to be (WA,R , V), where V: d• --* 2 w eis defined by :XE V(p) .> pE L(x)^(xe W°).MAThen, as usual, V is lifted to a valuation II 11^of Fma(0) with the desired propertythatTruth Lemma (L5): II a 3MA = {xe WA I a e L(x)} .Proof: By induction on the complexity of formulae, using the properties of maximalconsistent sets for —) and 1 and Lemma 1.4. for the wedge.^■Theorem 1.6 ("Determination of JS 5"): lis5 a if, and only if, a is valid in all frames.Proof: Soundness: For any frame F, IF = fp! F 1 131 is a prenormal dyadic logic whichincludes S5, so JS 5 c EF , i.e.,F a^Fa.Js5^•^•Completeness: Suppose that fis5a. Then -1a is JS 5 -consistent, so by Lindenbaum'sLemma there is a A*E MAX05 with { -ta} c A*, and thus, ae A*. Then taking JS 5 asthe value of A in the construction of ,M °, the Truth Lemma guarantees that A4 (tea}falsifies a at A*, i.e., ,A4 (tea) VA,, a. Hence, ,A4 (-la) V a, as required. ■The above construction is admittedly messy. In Chapters 5, 6 and 7 more elegantconstructions yielding uniform completeness results for extensions of normal logics arepresented. However, the present construction illustrates in a straightforward fashion theapparent need, in modelling weak dyadic logics, to replace the traditional canonicaluniverse by a "copy" in which it is not the case that distinct points are differentiable27Chapter 1according to the formulae they contain. The constructions to come can be viewed asimplementations of more sophisticated coloring schemes.Still, we can squeeze one more determination result out of the above construction. Asnoted in the introduction, necessitation for[N*]^T =df T >Tcorresponds under [U>] to the first order condition on g.i. frames (W , R) that dom(R,v)= W for all w in W, or,Vx b'y 3z .Rx y, z .To establish that JS 5+N*, the smallest natural logic containing S5, is determined by theclass of universal g.i. models whose frames satisfying this condition, we simply note thatif A of the construction of MA includes [N*], then by Lemma 1.4, for every XE WA,(VyE WA)[T E L(y)^Oze WAXT E L(z) & YR x z)] •More on normal dyadic logics in the next chapter.Chapter 2^ 28Chapter 2: Presenting JK and Some First Degree Extensions.In this chapter, I present JK, the weakest of the normal dyadic logics studied in thisessay. Our main goal is to make some proof theoretic remarks concerning JK and some ofits first degree extensions.Let JK be the smallest normal logic. Recalling Chapter 0, we have :[1RM] JK "—)0^!if( (0>Y . -4. a>Y) ,[RMi]^I- a-413J1C^I-A (y> a .-4. y>13).[DS]^JK (a>y .A. (3>y) ---> ((a v [3)>y)[N]^I- DTJK^=df 1>1[N1^JK ©T^=df T>T .In Chapter 1, we saw that [RM] is an [RPL] consequence of [1RM], and that [K] is an[RE] consequence of [ LM], while [1M] is itself derivable by [RPL] and [RE] from [DS]and [1RM]. This suffices to show that (JK) ° is the monadic logic K.JK may also be characterized as the smallest dyadic logic which is closed under [RN]and [RMT] and includes[DS] (a>y .A. 0>y) --> ((a v (3)>y)[J,1■4] 1(a-> 13) -4 ((3^.—>. a>1')[N*] 1:11 =df T>T .Gone with U■411 is the principle13) -4 o(ocA(3)(ManChapter 2^ 29[PD]^I- (a>(3)---,(0a--> o (3)which functions as an important "consistency principle" in natural dyadic logics. Note that[PD] is "hypothetical syllogism" for the special case involving logically false consequents:(a>(3 .A. 13>J) -9 a>1 .Recall from Chapter 0 that a dyadic formula is called first degree just in case it contains nonested occurrences of >. Some first degree principles extending JK to be studied in thisessay are:13[PW][SI][TRIV][TRIV 1][AD][C*][m1][1:132][GI][CP]Ea —) Daa -Oa(oa--4E1(3)—)(a>(3)(oa—f3)—>(a>13)[CON][PS]Chapter 2^ 30[NE]^(a>(0 v y) .A. 7>i) -+ (CC>(3)and, of course, [MT]. Here are some order-theoretic principles relevant to comparisonsemantics:[TR]^(a> 0) -4 ((3 >7 .-4. a>Y)[STR]^(a> (R v 7)) -4 (PS .--.). a>(8 v y))[CONNEX]^(a> (3) v ((3>y)[DIS]^(a>(13v7)) -4 (a>f3 .v. a>7) .A few proof theoretic remarks on the comparison principles: Both [IM] and [MT] are[RPL] consequences of [TR] ("transitivity") plus [PS]. Conversely, [TR] is an [RPL]consequence of [PW] ("preservation of the wedge") in the presence of either [MT] or[1M].[STR] ("strong transitivity") yields [TR] by [RE]. But note that [STR] is obtainablefrom [TR] in the presence of Lewis's [DIS] by using [RMT]. Alternatively, [DIS] isobtained from [STR] in the presence of [CONNEX] as follows:logic which includes [STR] and [CONNEX]. Then,Let A be a normal dyadic0. FA (a>((3 v y)) A (0>7) .-9. (a> (Y V Y)) By [STR]1. FA (a>(13 v y)) A (11>i3) .-*. («>(13 v 13)) By [STR]2. FA (0>Y) v (Y>13) By [CONNEX]3. }-n(a>(13 v Y))--3(«>(13 v p) .v. a>(7 v l)). 0, 1, 2 by [RPL]4. FA(a>(13 v y))—qa>13 .v. a>Y). From 3 by [RE],31Chapter 2as required to show that A includes [DIS].Surprisingly, [NE] is equivalent to [MT] : Let A be a natural dyadic logic. Then0.^FA ^-17 .- ^((13 V y) -> 0)^ By [RM]1. FA ^((0 \ '0-43) -) (a>(3 v 7) .-). (a>13))^[Mt]2. FA ^ny -4 (a> ((3 v 7) •-4. (a>(3))^From 0, 1 by [RPL]3.^FA (a>((3 v y) .A. y>1) -4 (a>13), From 2, [RPL], df. ^and [RE]since anis equivalent to 'pl. This suffices to show that A includes [NE]. Conversely,let A be a normal dyadic logic and assume that A includes [NE]. Then0.^I-. A y>a .--). y>((an(3) v (aA -1(3)) [RE], [RPL]1.^FA (7>(an(3 .v. an -10)) A (an -1(3)>1. .->. y>(anri) [NE]2. FA (an -11)>1 .4-4. 0(a --)13)3. FA ^(a-43)A(y>a) .-4. 7>(ocA(3)4.^FA ^(a->13)A(y>a) .--). y> f3[RPL], df. ^ and [RE]0, 1, 2, [RPL]3, [RMT], [RPL]which is sufficient to establish that A includes [MT]. Since [NE] is an [RE] consequence of[STR], it follows that [MT] is a consequence of [STR].Note that the principle of "implicational reflexivity"[WIZ] a>aChapter 2^ 32is obtained directly from [CONNEX]. In (pre)normal dyadic logics, [PS] is equivalent to[WR]. To demonstrate: Given [PS], obtain El(a---) a) by [RPL] and [RN]; then a>afollows. Conversely, given (13>(3), assume D(a---> 0). Then (a> [3) follows by [1M].Note that many of the comparison-theoretic principles are consequences of the"triviality" principles. For example, [CONNEX] follows from [TRIV1], and [STR]follows from [TRIV].[C*], the "aggregation principle" for El is an instance of [AD].[IB1] is a consequence of [MI] : Let A be a natural dyadic logic. Then0. FA Oa —1:1(T--)a) By [RE] and [RPL]1. FA T>T By [N*]2. FA D(T--)a) —* QT>T)--4(1->a)) by [Mr]3. FA 0a--->(T>cc) From 0, 1, 2 by [RPL]as required to show that A contains [1131].Further, [GI] is equivalent to [IBI] : Let A include [1131]. Then:0. FA a>1^a>I3 By [RMI], [RLP]1. FA-1(a>f3)--) o a From 0 by [RPL] and df.2. FA 013 --> (T>0) By [IB1]3. FA 00 -> (a> 0) From 2. by [1RM] and [RLP].4. 1-A-1(a>13)^o By [RPL],Chapter 2^ 335. FA -1(a>(3) ---> (Oa A 0'(3)^From 1 and 4 by [RPL]6. FA (0a —4E1(3) -4 (a>(3)^From 5 by [RPL] and df. 0,as required to show that A includes [GI]. Conversely, let A include [GI]. Then:0.^FA (0T A D(3) -- (T> (3)^By [GI] and [RPL]1. FA (-1^1 A ^(i) —* (T> ()^From 0 by df. 0, df. ^2. FA 1:11-->(T>(3)^By [RMT], df. ^ and [RE]3. FA ^1 v -Ca^[RPL]4. FA ^f3 -- (T>(i)^From 1, 2, 3 by [RPL],as required to show that A includes [II3 1].[IB2] is equivalent to the elegant preservation principle(a> 0) --) (Da —>^(i).To see that [IB2] is a consequence of the given principle, suppose it. Then0.^FA (T>(3)---)(01- --400)^By [1B2]1.^FA CID -----) DP^From 0 by [N], df. 0 and [RPL],as required to show that A includes [IB2]. Conversely, let A include [IB2]. Then:0. FA ^a->^(T-xa) By [RM] and [RPL]1. FA ^(T->a)-q(a>13)-->(T>(3)) By [1,1‘4]2. FA Oa .-*. (a>(3)->cr>(3) From 0, 1 by [RPL]34Chapter 23.^FA (a>13)—“Da--3 0 (3) From 2 by [RPL], df. El4.^FA (a> I3)--> (Cla-40(3). From 3 by [IB2] and [RPL],as required to show that A includes the given principle.Since I have occasion to refer to Lewis' V-logics, it might be helpful to present one ofLewis' axiomatizations of V, the smallest V-logic, and characterize it in our terms. In his[15], Lewis characterizes V as the smallest dyadic logic which contains [TR] (there called"Trans") and [CONNEX] and is closed under the Rule for Comparative Possibility :F v a —030./...4n) 1- v (a41)v... v(a>13n) (n 1)Notice that [DIS] is a consequence of the Rule for Comparative Possibility in the presenceof [TR]:0.^1-v ((3v7) --*(0v7)^[RPL]1. 1-v (0v7)>0 .v. (13 v7)>7^0, Rule Comp. Poss.2. 1-v a>(13v7) . -4 . ((i3 v -Y)>(3 .—>. a>0) [FR]3. I-v a>((3vy) .—>. (((3vy)>y .—>. a>y)^[TR]4. I-v a>((3v7) --> ((ct>(3) v (a>7))^1, 2, 3, [RPL]We can characterize V in our terms as the smallest natural logic containing [PS],[CONNEX], and [DIS]. Since [MI] is a consequence of [PS] in the presence of [TR], and[PS], equivalently [WR], is a consequence of [CONNEX], this logic may be denoted by'JK[CONNEX] [DIS] [TR]'.Chapter 2^ 35For convenience, we shall refer to JK[CONNEX][DISNTR] as A. To see that V is asublogic of A, we need only show that the Rule of Comparative Possibility is a derived ruleof A: Towards this goal, let n^1 and assume FA a --> (131v. . .v (3 1). Then0. FA a -9 (Pi v. . .v f3„) Assumption1. FA ^(a —> (Pi v. . .v PO) 0 by [RN]2. FA a>.(131 v. . .v (3n) 1 by [PS], [RPL]3. FA (a> (31) v... v (a> (3n) 2 by [DIS], [RPL],as required. Conversely, since [DIS] follows from the Rule for Comparative Possibilityand [TR], to see that A is a sublogic of V, it suffices to show that JK is a sublogic of V.Now, [1RM] and [RMT] are obvious consequences the Rule of Comparative Possibilityand [TR]. And [N] and [N*] are obvious consequences of the Rule of ComparativePossibility. Hence, it suffices to show that [DS] is derivable in V:0. Fy (avO) ---> (av(3) [RPL]1. 1- v (av(3)>(avi3) 0, Rule Comp. Pos.2. Fy (av(3) >a .v. (av(3)>13 1, [DIS], [RPL]3. Fy (av(3) >a^(a>y.-4.^v(3)>Y) [TR]4. Fy (avr3)>13 .-*. (13>T.—>. (ocv0)>Y) [TR]5. Fy (a>'Y .A. (>Y)^(0/13)>Y 2, 3, 4, [RPL]This concludes our presentation of the dyadic logics to be studied in this essay.Chapter 3^ 36Chapter 3: Some Semantic Correspondences.This chapter establishes some purely model-theoretic correspondences between firstdegree extensions of JK and first order sentences in a single ternary relation R.Let L be a first order language (with identity) whose only nonlogical symbol is theternary predicate symbol R. In accord with the convention of Chapter 0, we will writeRx y z for R (x ,y , z). Thus, frames F = (W, R) are first order structures for L (or, L-structures). The double turnstile will serve both its customary role of expressing truth andvalidity of dyadic formulae, as well as the concept of truth on an L-structure for L-sentences: when A is an L-sentence, we write F k A just in case A is true on F. Thecontext will usually serve to disambiguate this double usage.Given a formula a and an L-sentence A, we say that a corresponds to A just incase, for all frames F ,F k A a F a,that is, just in case a and A determine (in their own ways) the same class of L-structures.We shall let the informal expression 'yE dom(Rx)' denote the L-formula (3z)Rxy zand '(dye dom(Rx))A' denote the L-formula (Vy )(ye dom(R x) --> A).We associate an L-sentence with each of the first degree extensions of JK presented inthe previous chapter:0. [MI]^^(a—> 13) (y> a .—>. y>13)(Vx)(VY)R3z)(Rx z y) --4 yE dom(Rx)]1. [CON]^-ID 1(Vx)(3Y)(3z) Rx y z37Chapter 32. [PS] ^ (a (1)^(a> 13)(Vx)(VyE dom(R))Rxy y3. [PW] (a> po ^(a -* (3)(Vx)(VA(Vz)(Rx z --> y =z)4.[SI]^^(a-4 0) +4 (a> f3)(Vx)(VyE dom(R))(Vz)(Rx y z<-> y=z)5.[TRIV1]^(a—> 0) -4 (a> [3)(Vx)(dy)(ye dom(Rx) (y=x A RX X x))6. [TRW] (a>13) <-4 (a(dx)( 5IY)(Vz)(Rx Y z <->x=y=z)7.[AD]^((a> 13) A (a>y)) -4 (a> (f3Ay))(Vx)(VyE dom(Rx))(3!z)(Rxy z)8. [C*]^(aotA 00)^©(a n(3)(Vx)(VyE dom(Rx))(3z)(Rxy z n (3u )(k/f)(Rxu z' <-> z=z')9. [IB1] ^ a -4 ma(dx)(klyE dom(Rx))(3zE dom(R))Rx y z10. [1B2] a -->Cla(Vx)(Vy€ dom(Rx))(3u)(\lz)(Rx u z H y =z)(0a-><>(3) -> (a>13)(Vx)(biy, zE dom(Rx))Rxy z11. [CP]Chapter 3^ 3812. [STRJ^(a>(3vy))—> (p>8 .-->. a>(8 vy))(Vx)(VY)R3z)(Rxz y)---)yE dom(Rx)] A(V x)(Vy)(V z)(V u)[(Rxy z) -4 (Rxzu-4RxY 0113. [CONNEX]^(a> (3) v (0>y)(Vx)(Vy,ze dom(Rx))(Rxy z v RxzY)14. [DIS]^(a> ((lvy)) —) ((a>f3) v (a>y))(Vx)(Vy,ze dom(Rx))[(Vu)(Rxyu -3 Rxz u) v(V u)(R xz u -412xY14)1First order principle 0. will be refered to as "pointwise seriality" and is equivalent to thecondition that the range of Rx be a subset of the domain of Rx. Pointwise seriality is afeature of comparison frames (indeed, of any frame where the Rx are reflexive), and, inparticular, of Lewis' frames for his V-logics. Note that first order principle 14., here called"mutuality", is a property of connected, transitive relations. Logics containing theassociated dyadic principle [DIS] will be called "transparent", since [DIS] is one of thefeatures of material implication which is not shared by strict implication. As we shall see,although [DIS] is undesirable as a principle governing implication, it plays an importantrole in simplifying the presentation of dyadic logics (and, in particular, of V-logics).Theorem 3.0: Dyadic principles 0- 7, 9 - 14 inclusive correspond to their associated firstorder principles.Proof: By the following lemmata:Let F = (W, R) be a frame. Then,0. F k (V x)(VY)[(3z)(Rxz y) ---> y E dom(Rx)] <=> F k o(a —> 13) —> (y> a .--->. 7> () •Chapter 3^ 39Proof of 0:^Assume that F (Vx)(VY)[(3z)(Rxzy)—> y.€ .dom(Rx)]. Note that thisis equivalent to the condition that mg(Rx) S dom(Rx). To see thatF ^(a^(3)^(y>a .-->. y>13),let V be a valuation and xe W such that (W, R,^6 ^(a—)p), y>a.Claim: (W, R, V) 6 y> 13. Pf.: Let y E dom(Rx) such that (W,R,V) y. Wewant to find a 13-point that y bears Rx to. By assumption, there is a u such that Rxy uand (W,R ,V) 6 cc. Since (W,R,V) D(a —> (s), it follows that (W,R,V) (3.Hence, u is our desired (3-point . This is sufficient.Suppose that F^x)(V y)[(3z)(Rx z y) —4 y E dom(Rx)] Let Pl,P2,P3Edistinct. By assumption, there are x,y ,ze W such that Rxy z but ze dom(Rx). Let V be avaluation based on F such that all of the following hold:i) V(pi) = {z}ii) 17(P2) = 0iii) V(P3) = {y}.By i), there is no UE dom(Rx) such that (W,R , V) 6 pi. Hence, we have (W,R,V) 4El(Pi —> P2). By iii), y is the only p3-point in dom(R x), whence Rxy z and i) yield(W,R,V) P3>Pi. By y^ in dom(Rx) is a P3-point. But by ii), there is no p2-pointfor y to bear in Rx to, whence (W,R ,^bk P3 >P2. This suffices to establish that(W,R , V) ix ^—>p2) (p3>pl .—>. p3>p2), and completes the proof of Lemma O. ■1. F k (Vx)(3Y)(3z)Rxy z^<=>^F^--ID _L.Proof of 1: Trivial.2. F k (Vx)(VyE dom(Rx))Rxyy <=> F^---> (a> (3) •40Chapter 3Proof of 2: . Assume that F (V x)(Vy E dom(Rx))Rxyy. We need to show thatF k 1:1(a—)(3)—)(a>(3). Towards this goal, let V be a valuation and XE W such that(W,R, V) 6 ^(a—> 13). It suffices to show that (W,R, V) 6 a> 0. Towards this, letyE dom(R) such that (W,R, V) a. Since (W,R, V) 6 ^(a —> (3), it follows that(W,R,V) 13. But by assumption, Rxyy. Hence, (W,R,V) 6 a>13, as required.. Suppose that F bk (Vx)(Vy€ dom(Rx))Rx yy. We need to find an instance of[PS] which is not valid on F. Towards this, let p1,P2€ O. By assumption, there is anX E W and a yE dom(Rx) such that not Rxyy. Now we let V be a valuation based on Fsuch that both of the following hold:i) v(pi) = {y}ii) v(p2)= fylBy i) and ii) P1 -P2 is true under V everywhere in dom(R x), whence (W,R ,V)^(p1 —q,2). Further, y E dom(Rx) such that yE V(p1) but for all z such that Rx u z,zi V(p2). Hence (W,R , V) ik P1 >P2. Then (W,R,V) 14 1=(P 1 -->P2) -4 (P1> P2), asrequired to complete the proof of Lemma 2.^ ■3.^F k (V 4(9' y)(V z)(R x y z -- y= z) <=:. F k (a>(3) —> o(a->(3).Proof of 3.:^. Assume that F k (V x)(Vy)(V z)(Rxy z —4 y = z). We need to showthat F k (a>f3) ---> ^(a—> 13). Towards this goal, let V be a valuation and XE W suchthat (W,R,V) 6 a> f3 . It suffices to show that (W,R,V) 0(a —>13): Let yE dom(Rx)such that (W,R,V)^a. Since (W,R, V) 6 a> 13, it follows that there is a z such thatRxy z and (W,R,V) k 0. Then by assumption, y is such a z. Hence, (W,R , V)a —) 13. Since y E dom(Rx) was arbitrary, it follows that (W,R , V)^Cl(a --) 13), asrequired.41Chapter 3. Suppose that F V (V x)(V y)(V z)(Rx y z —4y= z). We need to find an instance of[PW] which is not valid on F. Towards this, let p1,P2E 0 distinct. By assumption, thereare x,y,zeW such that Rxy z but y #z. Let V be a valuation based on F such that bothof the following hold:i) V(Pi) = {y}ii)V(P2) = rneRx) — {AClaim 1: (W,R,V) 6 pi >p2. Pf.: By i), y is the only pi-point in dom(Rx). Byassumption, Rxyz . And by ii), ZE V(p2), since ze rng(Rx) and y# z. This is sufficientto establish the Claim.Claim 2: (W,R,V) IA 1:3(pi -4/02). Pf.: Since yE dom(R x) and ye V(pi) it sufficesto observe that, by ii), y 0 V(p2).From Claims 1 and 2, we have (W,R , V) vxI (nv- 1> P2) --> D(P1 -4 /32), as required tocomplete the proof of Lemma 3.^ ■4. F k (Vx)(Vy E dom(R))(Vz)(Rxyz <--> y=z) <=> F k 0(a-0) <—> (oc>(3)•Proof of 4: By 2 and 3 above.^ ■5.F = (Vx)(Vy)(yE dom(Rx) -4 (Y=x A Rxxx)) <=> F k (a -4 0) —) (a> (3).Proof of 5: . Assume that F = (Vx)(Vy)(yE dom(Rx) -4 (y=x A Rxxx)). We needto show that F k (a —>I3) —4 (a>13). Towards this goal, let V be a valuation and XE Wsuch that (W,R , V) 6 a —>13. To see that (W,R, V) 6 a > 0, let yE dom(Rx) such that( V ,R ,V) a. Then by assumption, y=x and Rxx x. From y=x it follows that(W, R, V) R. Then Rxy y yields (W,R, V) 4 a> f3, as required.42Chapter 3. Suppose that F ik (Vx)(Vy)(yE dom(Rx) -4 (y=x A Rxxx)). We need to find aninstance of [TRIV11 which is not valid on F. Towards this, let pi,p2e 0 distinct. Thenby assumption, there are xe W and yE dom(Rx) such that either x #y or not Rxx x. Weseparate these two cases:Case 1: x *y. Let V be a valuation based on F such that the following hold:i) V(P1) = {Y}ii) V(p2) = 0.By i), x*y yields (W,R ,V) 4 P1-4P2 . But i) and ii) yield (W ,R ,V) bk P1 >P2,since yE dom(Rx). So (W,R,V)iik (P1 —>P2) - (Pi >P2).Case 2: not Rxx x. From Case 1, we may assume that x=y. Let V be a valuation basedon F such that the following hold:i) V(pi) = {x)ii) V(pz) = (x).By i) and ii) we have (W,R ,V) 4 P 1 -- )1,2. But i), ii) and Rxx x yield (W,R , V)Pi>p2, since XE dom(Rx). So (W,R,V) ix (13 1 —>P2) --> (P1>P2)•In both cases, then, we have the desired falsifying valuation V. This completes the proofof Lemma 5.^ ■6. F k (V x)(V y)(V z)(Rxy z i 4 x =y =z) < F^(a>13) +4 (a --)0.).Proof: Similar to 5.7. F k (d x)(V y € dom(R x))(3!z )(R xy z) <#. F k ((a>0) A (a>7) —> a>(i3 AY)).Proof of 7: . Assume that F k (Vx)(VyE dom(Rx))(3!z )(Rxyz). We need to showthat F k ((a>() A (0C> y) .-* . a> 03 A y). Towards this goal, let V be a valuation and43Chapter 3xe W such that (W,R, v) 6 (a>(3)A(a>y). To see that (W,R, V) j a> ((3 A y), let y Edom(Rx) such that (W,R , V) a. Since (W,R , V) 6 a >13, a> y, it follows that thereare z, z' e W with Rxyz, RxY z", (W ,R ,V) 613 and (W ,R ,V) k. y. Then by assumption,z=z', whence (W,R, V) kz f3Ay. Since y was an arbitrary a-point in dom(Rx), it followsthat (W,R , V) 6 a> (J3 A y), as required.. Suppose that F ik (Vx)(VyE dOM(Rx))(3!Z )(RxyZ). We need to find an instance of[AD] which is not valid on F. Towards this, let pi,p2,p3E 0 all distinct. By assumption,there are x,zi,z2E W and y E dom(Rx) such that Rxyzi andRxyz2 but z i #z2. Let V be avaluation based on F such that the following hold:i) V(Pi) = {y)ii) V(p2) = { z i )iii) V(p3) = { z2) .Claim 1: (W ,R , V) 6 (P i> P2) A (Pl> p 3). Pf: Let u E dom(Rx) such thatUE V(pi). Then by i), u= y. By ii), ZiE V(pi) (i= 2, 3). By assumption, Rx u zi(i=2, 3). This suffices to establish the Claim.Claim 2: (W,R , V) lit pi > (p2Ap3). Pf: Since y E dom(Rx) with yE V(p 1), itsuffices to observe that, by ii) and iii), there is no UE W such that UE V(p2)nV(p3).From Claims 1 and 2, we have (W,R, V) ix (pi>p2)A(p1>p3).--3•p1> (P2Ap3), asrequired to complete the proof of Lemma 7.^ ■8. F k (Vx)(Vye dom(Rx))(3zE dom(R))Rxy z <#. F k Cla ---> Da.Proof of 8: . Assume that F k (Vx)(Vye dom(Rx))(3zE dom(R))Rxy z. To see thatF k Da -4 cla, let V be a valuation and X E W such that (W,R , V) Oa. Let y Edom(Rx). By assumption, y bears Rx to some UE dom(Rx). Since (W,R, V) Ea, itfollows that (W,R,V) 6 a. Hence, (W,R, V) 6 T>a. This is sufficient.44Chapter 3. Suppose that F V (V x)(V ye dom(Rx))(3zE dom(Rx))Rxy z. Let p E 0. Byassumption, there are xE W, ye dom(R x) such that y does not bear Rx to any ZE dom(Rx).Let V be a valuation based on F such that V(p)=dom(Rx). Then clearly, (W,R ,V) Op.Further, y does not bear Rx to any point in V(p), whence (W,R , V) T >p. Thissuffices to show that (W,R,V) bk Oa -*Da. ■9. F k (V4(`9/yE dom(Rx))(30(Vz)(Rxuz <-) y=z) t=> F k ©a—)Da.Proof of 9: =. Assume that F H3(Vx)(Vy e dom(Rx))(3u)(Vz)(Rxu z <--->y=z). Tosee that F kaa -40a, let V be a valuation and XE W such that (W,R , V) ®a. Lety E dom(Rx). By assumption, y is the unique Rx-successor of some UE dom(Rx). Since(W,R,V) 6 T> a, it follows that (W,R,V) a. Hence, (W,R,V) kx Oa.. Suppose that F 1(kf x)(Vy e dom(Rx))(3u)(Vz)(Rxuz <-3 y=z). We need to findan instance of [IB2] which is not valid on F. Towards this, let pE 0. By assumption,there are XE W and ye dom(Rx) such that y is not the unique R x-successor of any UE W.There are two cases:Case 1: yo rtig(Rx). Then let V be a valuation based on F such that V(p)= nig(Rx). Thenclearly, (W,R , V) 6 T>p but (W,R , V) bk Op.Case 2: Otherwise. Then let V be a valuation based on F such that V(p)=rng(Rx) - {y 1 .Claim: (W,R, V) 6 T>p . Pf.: Let uE dom(Rx). Since y is not the unique Rx-successor of u, there is a ZE rng(Rx)- fy 1 such that Rxu z. By the choice of V, we thenhave (W,R , V) kz p . Since u was an arbitrary element of dom(Rx), this suffices toestablish the Claim.Chapter 3 45 Since ye dom(Rx) but ye V(p), we have (W,R , V) Li Op. In both cases, then, we havea valuation V based on F such that (W,R, V) lk Da —1:1a. This completes the proof ofthe Lemma. ■10. F k (Vx)(Vy,ze dom(Rx)) Rxyz^<=> F 1 (0a —> 00) —> (a>(3).Proof of 10:^Assume that F k (Vx)(Vy, ze dom(Rx))Rxy z. To see that F(0 a 0 0) -4 (a> (3), let V be a valuation and xe W such that (W,R , V) k <>a ---> 0 0.Let ye dom(Rx) such that (W,R , V) a. Then (W,R, V) o a , so by assumption(W,R ,V) 4 o 0, that is, there is a ue dom(R x) such that (W,R, V) 6 0. By assumption,R x y u. Since y was chosen as an arbitrary a-point in dom(R x), it follows that(W ,R ,V) 4 a>0.Suppose that F ik(V x) (V y, Z E dom(Rx))Rxy z. Let p 1,p 2 E 0 distinct. Byassumption, there are xe W and y,zE dom(Rx) such that y does not bear Rx to z. Let Vbe a valuation based on F such that both of the following hold:i) 17(P1) = tY1ii) V(p2) = {z) •Then clearly, (W,R, V) I Opi, 0p2, whence (W,R,V) l Opl-* 0/32. Further, y is aPi -Point which does not bear Rx to any point in “P2), whence (W,R ,^kk P1>P2. Thissuffices to show that (W,R , V) IA (0 a 0(3) ---> (a> .^■11. F (vx)(vY)1(3z)(Rxz y) -4 y E dom(Rx)](V x)(Vy)(V z)(V u)[Rxy z (Rx z u —> Rx y u)]<=> F 1 (a>(0vy))^(0>8 .-->. a>(Svy))•Proof of 11.:^Assume thatChapter 3^ 46(a) F (Vx)(VY)R3z)(Rx zy) ye dom(Rx)] and(b) F (Vx)(Vy)(Vz)(Vu)[Rxy z -4 (Rx Z U Rxy u)).To see that F (a>(f3vy))^((3>8 .- ). a> (8v y)), let V be a valuation and XE Wsuch that (W, R, V) 6 a>a3vy), 13>8.Claim: (W,R, V) 6 a> (8vy). Pf.: Let ye dom(Rx) such that (W,R, V) a. Weneed to find a z such that Rxy z and (W,R, V) kz 8 vy. By assumption, there is a usuch that Rxy u and (W,R,V) 6 13vy. Then one of 13 or y holds at u. If y holds, then z isour desired (8v y)-point u. So assume that (W,R,V) 6 13. By assumption (a)., mg(Rx)dom(Rx), so UE dom(Rx). Since (W,R,V) 6 ((3>8), it follows that there is a z suchthat Rxu z and (W,R, V) kz 8. Then Rxyu and Rx uz yield Rxy z by assumption (b).Hence, z is our desired (6vy)-point.Suppose one of (a) or (b) above fail. It suffices to find an instance of [TR] which isnot valid on F. Let pi,p2,p3E^all distinct.Claim: 14 (P1>P2) (P2>P3^P1 >P3). Pf•: There are two cases:Case 1: (a) fails. By assumption, there are x,y, ZE W such that Rxy z but ze dom(Rx).Let V be a valuation based on F such that all of the following hold:i) v(pi) = fylii) v(p2) = (z}iii) V(p3) = 0.By i) and ii), Rxy z ensures that (W,R,^6 pl> p2. By ii), there are no p2-points indom(Rx), so (W,R,^6P2>P3. By i), y is a pi-point in dom(Rx). But by iii), there isno p3-point for y to bear Rx to, whence (W,R, V) it pl>p3, as required.47Chapter 3Case 2: (b) fails. By assumption, there are x,y,z,u E W such that Rxy z and Rxz u butnot Rxy u. Let V be a valuation based on F such that all of the following hold:i) v(pi) = fylii) V(P2) = {z}iii) v(p3) = { u ) .By i) and ii), Rxy z ensures that (W,R ,^6 P1> P2 By ii), Rxz u ensures that(W ,R,V) 6p2>p3. By^y is a pi-point in dom(Rx). But by iii), not Rxy u ensuresthat y bears Rx to no P3-points, whence (W,R ,^It P1> P3. This suffices to establishthe claim, and completes the proof of Lemma 11. ■12. F k (Vx)(Vy,ze dom(Rx))(Rxyz v Rxzy)^a^F k (a>13)v 03>7)•Proof of 12:^Assume that F k (V x)(Vy,z E dom(Rx))(Rxyz v Rxzy). To see thatF (a> (3) v((3>7), let V be a valuation and XE W such that (W,R, V) ik a> P.Claim: (W,R,V) 613>a. Pf.: Let yE dom(Rx) such that (W,R,V) (3. We wantto find an a-point that y bears Rx to. By the assumption that (W,R , V) a> 0, there isan a-point ue dom(Rx) such that not Rxuz for all ZE if n, and hence, not Rxuy. Thenby the assumption that Rx is strongly connected on its domain, we have Rxy u . Hence, uis our desired a-point, and the Claim is proved.Suppose that F V(Vx)(Vy,ZE dom(Rx))(Rxy z v Rx z y). Let p1,p2E 0 distinct.By assumption, there are x,yE dom(Rx) such that neither Rx y z nor Rx z y. Let V be avaluation based on F such that both of the following hold:i) v(pi) = {y }ii) v(p2) = f zl.48Chapter 3By i), there is a pi-point, namely y, in dom(Rx), which, because of not Rxy z and ii), isnot Rx-related to any pa-points. Hence, we have (W,R,V) bk p 1 > P2. By symmetricreasoning, (W,R, V) 14p2>p i. This suffices to establish that(W,R, V) ik (P1>P2) v (P2>P1),and completes the proof of Lemma 12.^ ■13. F k (Vx)(Vy,ze dom(Rx))[eclu)(Rxyu -4 Rxzu) v (Vu)(Rxzu ---> RxYu)1<=>^F k ((a> (0 vy)) —> ((a> (3 v (a> y))Proof of 13.:^. Assume thatF k (V x)(VY,z€ dom(Rx))[(Vu)(Rxyu -4 Rxzu) v (Vu)(Rxzuz  --> Rxy u)].To see that F k (oc>((3vy)) -+ (a> 0 .v. a>y), let V be a valuation and XE W such that(W ,R ,V) 6 a> ((3 v y) and also (W,R , V) K a> 0. Then it suffices to show that(W,R, V) 6 a>y. Towards this goal, let yE dom(R x) such that (W,R,V) I a .Claim: There is a y-point s such that Rxy s . Pf.: Suppose not. Then, y bears Rxto some f3-point z, since (W,R, V) 6 a>((3vy). By the assumption that (W,R, V) it a>13, there is an a-point ue dom(Rx) such that not Rxuz. Again, since (W,R , V) a> ((3 vy), there is a y-point g such that Rxug. Now, z witnesses that it is not the case that u isRA-related to everything that y is, so by the assumption that Rx is "mutual" on its domain,we know that y is RA-related to everything that u is. Hence, we have Rx y g. Taking g asour desired s, we are done.Since y was an arbitrary a-point in dom(R x), the desired result that (W,R, V) 6 a > yfollows from the Claim.. Suppose that49Chapter 3F (Vx)(Vy,zE dom(Rx))[(Vu)(Rxyu ---)Rxzu) v (Vu)(Rxzu --) Rxyu)].Let pi,p2,p3E fi distinct. By assumption, there are XE W and y,z e dom(Rx) such thatneither (V u)(Rxy u Rxzu) nor (V u)(Rxz u —) Rxy u). So there are ui,u2E W suchthat Rxy ui but not Rxz ui and Rx z u2 but not Rxy u2. Let V be a valuation based on Fsuch that all of the following hold:i) V(pi) = (y, z)V(P2) =^}iii) v(P3) = (1421.Then every pi-point in dom(Rx) is Rx-related to a (p2v p3)-point. Hence, we have(W ,R , 6pi> (p2vp3). But by i) and iii), y is api-point that does not bear Rx to anyp3-point. And similarily, by i) and ii), z is a p i-point that doesn't bear Rx to any p2-point.Hence, (W,R , ikpi>p2 and (W,R , V) p >p3. This suffices to establish that(W ,R,V) ii(13 1>P2) v (P1>P3),and completes the proof of Lemma 13.^ ■Lemma 3.1: F k (Vx)(VyE dom(Rx))(3z)(Rxyz n (Bu )(Vz')(Rxuz' H z =z))F^( anci(3)--> Ei(aA (3).Proof: Assume thatF k (Vx)(VyE dom(Rx))(30(Rxyz A (3u )(Vf)(Rxuz' H z =z')).Let V be a valuation and WE W such that (W,R ,^]a A^To  see that (W,R , V)(a A (3), let yE dom(Rx). Then, by assumption, there is a ZE W such that Rxy z and z isthe unique Rx-successor of some UE W. Since (W,R , V) 6 T > a, T > it follows thatChapter 3^ 50(W,R, V) kz a AO. Since y was an arbitrary element of dom(Rx), we have shown that(W ,R ,V) 6 T>(aAf3), as required.^■The converse of Lemma 3.1 does not hold, as we will now show by constructing a g.i.frame on which [C*] is valid but first order principle 8 is false.Let IR be the set of real nunbers and N g IR be the set of natural numbers. LetPinf(N) be the set of all infinite subsets of N. Since IR has the same cardnality as Pinj(N),let •:1) :IR --> Pinf(N) be an injective, onto map. Let F = OR ,R) be a ternary relationalframe, where R g IR x IR x N is given byR= {(x,y, 4 I x = 0, Z EClaim: F k (a OCA 13)-4 0 (aA13)ElProof: Suppose there is valuation V and an xE R such that .M= (F,V) It a(ccA (3). Thenthere is a y E dom(Rx) such that(#).A4^.A4Rxyz .. zoffall^or z 0 II(311^(zE R).Since dom(Rx,) = 0 (w x), it follows that x =0 by def. R. Then by (#), we can partitionM^m4)(y) into two sets A, B such that EMI n B = 0, CPI n A = 0. Since 0(y) is infinite,one of A or B must be infinite. Without loss of generality, suppose A is infinite. Then,since 4) : R --> Pini(N) is an onto map and AEPinf(N), there is a w € III such that 4)(w) =MA. Hence, by def. R and the fact that [IP n A = 0, we haveRx w z^z 0 EP M^(z E R ).Since dom(Rx) = IR , W E dom(Rx). Hence, ,i4 it El 13, whence M bk Ei a A op, as^required to show that F k (0 a A0(3)--> el(a A(3) .^■Chapter 3^ 51Since every point in F's universe is related to an infinity of points, no point in F'suniverse is the unique successor of any point in F's universe. It follows that no point indom(Rx) bears Rx to any point which is the unique R x-successor of some point indom(Rx). Thus, F fails to satisfy first order principle 8.Note that the correspondences proven in this chapter are purely model-theoretic, thatis, they deal with a notion of definability for classes of ternary relational structures which iscompletely independent of proof-theoretic considerations. The determination results tocome in Chapter 4 provide for the proof-theoretic characterization of many these classes ofstructures.Chapter 4^ 52Chapter 4: Prestudy For Model Constructions.In Chapter 1 we saw how the construction of "universal" models for JS 5 consistentsets of formulae seemed to require a universe somewhat larger than the Lemmon-Scottcanonical universe of maximally consisitent sets. In particular, we had the misfortune ofwitnessing a rather ugly "coloring" scheme for expanding MAXjs 5 by adding multiple"copies" of certain JS5 maxi-sets. In the next chapter, we present a far more elegantconstruction technique which offers a high degree of uniformity in modelling extensions ofJK. In chapter 6, the construction is tailored to model dyadic logics that contain the schemaof strong transitivity [STR].The universes of the models presented in the next two chapters are constructed "on topof" the canonical universe of maximally consistent sets. In preparation, we devote thepresent chapter to the development of some theory which plays the same role for normaldyadic logic as the study of Henkin sets play in the canonical construction. In this and thenext two chapters, the standard results concerning the properties of maximal consistent sets(presented in Chapter 0, pp. 12-13) will be assumed and used without special mention.For the rest of this chapter, let A be a normal dyadic logic. Let w be an element ofMA X A. In general, we will use 'u' , ,'x' , . . . (and, of course, 'w') to denoteelements of MAXA.Weak Separation Lemma (4.0): Let a, be formulae such that a> 13 w. LetF = { S I (3y)(5>ye w & 1-Ay--0) }Then there is a u E MAXA with ^(w) g u such that cce u and Fnu = 0.Proof: Suppose that a> [3o w and, towards a contradiction, for all u OW, a E UFnu #0. By the definition of deducibility, there are nO and 51,^, On E F s.t.Chapter 4^ 53^ (w) FA a-(81 v...v 8n).Let Eon = Oi v...v ön. Then by Scott's Rule,(*)^w FA 0(a —*811).Let yi,...,yn be the formulae given by the definition of r s.t. 8i> yi E w and FAyi .—> 3(1 <_i <_n). Let 14 = yi v...v yn. Repeated applications of [DS] and [RPL] yield(#)^FA ((81>1+i) A—A (8n>711)) -- (Sn>in ) •By [RPL], F A y;> yn , SO [RMT] yields F A (8i> yi) -- (8i> yn), whence 8i> yi€ wgives 81> yn E W (1 5 i 5 n). Then (51> yn) A . . . A (8n > yn) e w , whence (#) yields5n> yre e w .Now, FA yn --) 0 by the choice of the yi , so [RMi] yieldsI-A(a>r) ---> (a>(3).But by [1M], (*) yieldsw F A (8n>'yn) -4 (a>yn) ,SOw F A (8/2>r) -4 (a>(3),whence 8n > y)E w gives a> 0 E w, contrary to the hypothesis of the lemma. ■Corollary: Let a, 13 be formulae such that a>00 w. Then there is a u E MAXA with^ (w) c u such that a EU and 8 0 u for all 8 such that 5> [3 E w.Chapter 4^ 54Proof: Let u be given by the Lemma and 8 a formula such that 8>(3E w. Since F A 13 —> 13,it follows from the Lemma that Se u.^ ■As in the model construction of Chapter 1, the "canonical" universe of the modelsconstructed in Chapters 5, 6, and 7 will be populated by pairs whose first element is amaximal consistent set of formulae. However, the second element of one of our "pairworlds" will be a set of formulae which bears an intimate logical relationship to the firstelement.When considering pairs X of subsets of Fma(0), we again use the "projectionoperators" L(_), RL) so that X .(L(X),R(X)). Let X be a pair of subsets of Fma(0)such that L(X)E MAXADefinition: X is a cut around w iff(CO) a>EtnE w^(aE L(X)^{8i 115.i Srz)) 4 R(X)) (n> 0),where 8/1 is the n-termed disjunction 81v...v 8n . If in addition X satisfies the condition:(C1)^_LE R(X),then X is said to be initial. Let Cut(w) be the set of all cuts around w.Note that satisfaction of (CO) is equivalent to satisfaction of the condition(CO') F A 13 ----> (81 v. . .v 8n) & a>13 E W & 81,^, 8n E R(X)^coz L(X) (n >0)because of [RMi]: Assume X satisfies (CO) and let n> 0 such that X satisfies theantecedent of (C0'). Then F A 13 --> (81v...v 8n) plus a>13 E w yieldsa> (81 v. . .v 8n) E wChapter 4^ 55by [RMT]. So the desired result that ae L(X) follows from (CO). Conversely, assumeX satisfies (CO') and let n > 0 and a, 81, ... , 8n E Fma(1) such that X satisfies theantecedent of (CO) and f si 11 5.i n) } c R(X). By [RPL],1- A (81v. . .v 8n) --) (81v.. .v 8n),so (CO') plus a>(,,Riv...v8n)e w yields ao L(X) as required.Following Lewis [15], I'll write "Sin S2" for "Si nS2# 0" (Si,S2 g MAXA).Lemma 4.1: Let a> 0 E w and X E Cut(w) with 0(w) c L(X). Thenae L(X)^10 1 6) I -1[R00]1.Proof: Assume the hypothesis and that 1[31 nI -i[R(X)]I=0. Then there are n. 0 and81,..., NE R(X) such thatFA 11—) (81v...v8n) •If n =0, then [RMi] yields a>_LE w, whence ^(w) g L(X) gives a€ L(X), as requiredto establish the contrapositive of the Lemma. On the other hand, if n > 0, then a> (3 E Wyields ae L(X) by condition (C0'). In either case, the contrapositive of the Lemma isestablished. ■Corollary: Let a>13€ w and X E Cut(w) with ^(w) g L(X). Then, 1 -1[R(X)] I isnonempty.Proof: Since A is normal, A contains [N*] by def. normal. Hence, T> T E W. Since TE L(X), Lemma 4.1 yields I TI rz.) 1 -1 [R(X)] I. That is, I n [R(X)] i is nonempty, asrequired. ■Chapter 4^ 56Lemma 4.2: Let a> (3 0 w . Then there is an initial XE Cut(w) such that ae L(X) and [3E R(X).Proof: Suppose that a> (3 e w. Let xe MAXA be given by Weak Separation such that0(w) gx, a E x and ye x for all y such that y>13e w . Let X= (x,{1,13}) .Claim: X is an initial cut around w. Pf.: (Cl) is satisfied by the definition of R(X).To see that X satisfies (CO), let ye Fma(0), n > 0 and 81, ... , S n e R(X) such thatY> (Si v• • •v 8n)e w. Since {St, • • • , 8,) c {1 , 0), by [RE], we have either y>le w ory> (3 E w. In the first case, ye x by the choice of x, that is, by 0(w) gx. In the secondcase, y> [3 E w, so again yo x by the choice of x. This establishes the Claim.From the Claim, we have XE Cut(w) with the desired properties.^■Let XE Cut(w). Say X is maximal at w, or maximal@ w, iff for all sets F offormulae properly extending R(X), (L(X),F) is not a cut around w. Perhaps moreexplicitly, iff:F D R(X)^(L(X), no Cut(w)^(F c Fma(0)).X will sometimes be called a w-point if it is maximal at w. LetMCut(w) =df { XE Cut(w)I X is maximal@w}.That is, MCut(w) is the set of all w-points.4.3 (Extension Lemma): Let X1E Cut(w). Then there is an X2E MCut(w) withL(X2)=L(X1) and R(Xi) g R(X2)•Proof: X2 is obtained by simply closing R(X1) under (CO). However, its useful to laydown a uniform procedure for doing this: Recall that 4  denotes the ith formulae in thestandard enumeration of Fma(4)) assumed in Chapter 0. Let X2 be (L(X1), F) where FChapter 4^ 57is defined as the union of the sequence { Fi I i < w } of subsets of Fma(0) giveninductively by:Kt) ro =^R (Xi )(1)^= rl u^if for all n 0, 81, , On e Fi and all ae Fma(0),a>(41 v Siv ...v On) E W^L(X1).otherwise.By assumption, (L(X1), F0) is a cut around w. And the set of XE Cut(w) with L(X) =L(Xi) is closed under (1). So (L(Xi), Fi)e Cut(w) for all Fi in {Fi I i< co }. To seethat X2 is a cut around w, suppose (L(Xi), F) fails to satisfy (CO). Then there aren>0, 01, ..., On e r and a€ Fma(0) such that a> (Si v...v 8n) E w and a E L(Xi).Let m< co be the least number such that all of Si, ..., O ne Fm . Then (L(Xi), Fm) fails{ 1), contrary to the above. To see that X2 is maximal@w, let r CFma(0) such thatD F. Let j< co such that (1:0i E r'— r. Since (1:•jo rp. i , by { 1) there are n>_ 0, 81 ..... OnE rj , and a E Fma(0), such that a> (4)i v Si- v...v Sn)E w but a e L(X1). Sincericr, we have {4)j, 81, • • On C F'. Then (L(Xi), I-) fails (CO), whence (L(X1), r)Cut(w).^ ■Corollary 1: Let x E MAXA. Then there is an X = , R(X)) in MCut(w).Proof: X1= (x, 0) is a cut around w. Then the Extension Lemma (4.3) guarantees amaximal@w X2 = (x , R(X2)) in Cut(w).^ ■Corollary 2: Let ^(w) c x. Then there is an initial X=(x, R(X)) in MCut(w).Proof: ^(w) C x ensures that X1= (x , {I}) is a cut around w. Then the ExtensionLemma (4.3) guarantees an X2=(x , R(X2)) in MCut(w) with {1} c R(X2). So X2is initial. ■Chapter 4^ 58Lemma 4.4: Let X= (x, R(X)) in MCut(w) with ^(w) cx. Then Xis initial.Proof: Towards a contradiction, suppose _Le R(X). Then R(X) u { I) properly extendsR(X), whence X maximal@w entails that (L(X), R(X)u { 1) Cut(w). In other words,(L(X1), R(X)u {11) fails (CO). So, there are n.0, 81, ... , 8n E R(X) and a aeFma((k)s.t. :a>(1v 81v...v8n)e w and aex.If n=0, then a>_LE w, whence ^(w) cx contradicts aex. If, on the other hand, n>0,then [RMT] yields a>(8,1 v...v 8n) E w, whence (CO) contradicts ae x. This completes theproof of the Lemma. ■Lemma 4.5: Let XE MCut(w), and let a, Pe Fma(0) such that FA a-+ P. Then13E R(X)^a e R(X).Proof: Assume the hypothesis and ae R(X). Since XE Cut(w) is maximal@w, there areye L(X), n>0, and 81, ... , On e R(X) such that(*)^y>(av81v...v8n)e w,by (CO). Since 1- A a -4 0, we have F A (a v 81 v. . . v 8n ) -4 ((3 v Si v. . . v 8n ) by[RPL], whence (*) yields y>(13v. Si v. . v8n )e w by [RMT]. Then fle R(X) by (CO),as required. ■Corollary: Let XE MCut(w), and let a, 0 E Fma(0) such that FA a<---> P. Then13 E R(X)^4:=>^a E R(X).Proof: By Lemma 4.5.^ ■Chapter 4^ 59The definition of a cut around(w) may be simplified by taking n to be 1 always inthe special case of transparent dyadic logics. This fact is expressed as the following:Lemma 4.6 (Transparency Lemma): Let A be transparent, that is, let A includeLewis' schema[DIS] (a>([3vy)) ((a>p) v (a>7))•Let X be a pair of subsets of Fma(0). Then X satisfies (CO) just in case it satisfies thecondition(COT)^a>8€ w & Se R(X) .^ae L(X).Proof: Since (COT) is a special case of (CO), satisfaction of the latter implies satisfactionof the former. Conversely, asume that X satisfies (COT) and the antecedent of (CO). Leta E Fma(0), n > 0 and Si, R(X) such thata>(Siv^v8n)E W.Repeated applications of [DIS] yield(a>81) v v (a>812)e w,whence a>81€ w for some 1 S i . tz. Then (COT) yields ae L(X), as required. ■Lemma 4.7: Let A be transparent, X1€ Cut(w) and= V (R(X) I XE Cut(w) & L(X)=L(X1)}.Then (L(X1), 1")E Cut(w).Chapter 4^ 60Proof: By the Transparency Lemma, it suffices to show that (L(Xi), F) satisfies (COT):Let ae Fma(0) and Se I' such that (a>5)e w. Then there is a XE Cut(w) with L(X) =L(Xi) and SE R(X). Then (COT) yields ae L(X)=L(Xi), as required. ■Lemma 4.8: Let A be transparent and Xie MCut(w). LetEXT(Xi) = R(X) I XE Cut(w) & L(X)=L(X1)).Then R(X1) = EXT(X1).Proof: (L(Xi.), EXT(X1))E Cut(w) by Lemma 4.7, so by definition EXT(Xi) includesR(X1). Conversely, let yE EXT(X1). Then there is an XE Cut(w) with L(X) = 1-(Xi)and yE R(X).Claim: ye R(X1). K.: Suppose not. Then R(Xi)u Y} properly extends R(Xi),whence Xi maximal@w gives (UX1),R(Xi)u {Y})e Cut(w). In other words, (L(Xi),R(Xi)u {y)) fails (CO). Then, A being transparent, (L(Xi), R(Xi)u {y}) fails (COT) bythe Transparency Lemma (4.6), that is, there is an a> Se w such that Se R(Xi) u tyl buta E L(Xi). Now, 6e R(X1), since otherwise a> Se w with ae L(Xi) entails that Xi fails(COT), and hence, by the Transparency Lemma, (CO), contrary to Xi E Cut(w). So, 5 = y.But since XE Cut(w), a>ye w and ye R(X), we have oce L00= L(Xi) by (CO). Thiscontradiction establishes the Claim.By the Claim, EXT(Xi) a R(Xi.), as required to establish the Lemma. ■Corollary 1: Let A be transparent and Xi,X2E MCut(w) such that L(X1)=1-(X2).Then Xi = X2.Proof: Immediately from Lemma 4.8.^ ■Chapter 4^ 61Corollary 2: Let A be transparent and XE MAXA. Then there is a unique XE MCut(w)such that L(X)=x.Proof: By Corollary 1 to the Extension Lemma (4.3) and Corollary 1 to 4.8.^■Let F g Fma(0). Say that F is w-closed iff^3>(Yi v • •.v YOE w & Il , • • - Yn E r .. 13E r^(n >0).Lemma 4.9 (Lemma on w-closure): Let A be transparent and let XE MCut(w). Letr be w-closed and either a) F g n[L(X)] or b) --i[F] c L(X). Then r cR(X).Proof: Assume the hypothesis of the lemma. Let ye r. To see that yE R(X), supposeotherwise. Then R(X) u {y} properly extends R(X), whence X maximal@w entails that(L(X),R(X)u {T})O Cut(w), i.e., (L(X1), R(X)u (11 }) fails (CO). Then, by theTransparency Lemma (4.6), (L(X), R(X) u { y} ) fails (COT), that is, there is an a> 5 E Wsuch that SE R(X)u {y} but a € L(X). Now, So R(X), since otherwise cc>5 E w witha E L(X) entails that X fails (COT), and hence, by the Transparency Lemma, (CO),contrary to XE Cut(w). So, 8 = 'y. Hence, both (a> y)E w and a E L(X). Since yE F,the assumption that r is w-closed yields aE F. In case a), then, a= -113 for some f3E L(X),whence ao L(X) since L(X) is A-consisitent, and in case b), iaE L(X), so once again,ao L(X). In both cases, we have a contradiction.^■Lemma 4.10 (Lemma on Right Closure): Let A contain the schema of generaltransitivity[GTR]^(a> (0 vy)) --. (ps .-4. oc>(Svy))•Let XE MCut(w). Then R(X) is w-closed.Proof: Let f3E Fma(0), m >0 and yi, • • •• I'M E R(X) such thatChapter 4^ 620>(yi V...Vym)E WTo see that 13E R(X), suppose otherwise. Then R(X) L.) {13} properly extends R(X),whence (L(X1), ROOL) {y} ) fails (CO), since X maximal@w. It follows that there areOGG L(X), n _1:1 and Si, , SnE R(X) u DI such that a> (Si v...v 8n)e w. We mayassume that [1E [8 1 ..... sn } since otherwise { 81, , On} c R(X), whence X fails (CO),contrary to XE Cut(w). Then, by [RE], there is no loss in generality in assuming that (3 =Hence, we have a>((3 v 82v...vOn)E w. Then by [GTR], we havea>(yiv...vym v 82v...v 8n)E w.Since { yi, , ym , 82,^, Sn g R(X) and XE Cut(w), by (CO) we have coz L(X),contrary to OCE L(X) from above (that is, by devine intervention). Q.E.D. Lemma. ■Lemma 4.11: Let Ti CFma(0) such that –I[Fi] is A-consistent and let r2 g r i suchthat I-2 is w-closed. Then there is an XE MCut(w) with n[rd S L(X) and F2 c R(X).Proof: Assume the hypothesis. Since –1[r1] is A-consistent, there is a ze MAXA withg z.Claim: (z, T2)E Cut(w). Pf.: We need to check that (z, 1-2) satisfies (CO). LetOCE Fma(0), n >0 and Si— sn E r2 such thata>(Oiv ...v5n)e w.Since F2 is w-closed, it follows that a E r2 c F 1 . Since n[1-1] g_ z, the desired resultthat ow z follows immediately. Hence, (z, r2)E Cut(x). Q.E.D. Claim.From the Claim, the Extension Lemma (4.3) gives an XE MCut(w) with z = L(X) andr2 C R(X). Hence, we have our XE MCut(w) with the desired properties.^■Chapter 4^ 63Lemma 4.12: Let A be natural, i.e., contain [MI]. Let XE MCut(w) initial. Then{131f3>IE w}R(X).Proof: Assume the hypothesis. Towards a contradiction, let 13e Fma(() such that 0> 1E w but Pe R(X). Since X is maximal@w, there are n 0, 81, , 5n E R(X) and ana eFma((h) such thata>((3 v s i v...v 5n) E W and a€L(X).Recall that since [MT] s A, all members of[NE] FA (a>((3v8) .A. (3>1) --> (a>8)are also members of A. Hence PIE w yields a> (Si v...v 8n)e w. Then, if n = 0, wehave w, whence 0(w) S L(X) yields asp L(X), a contradiction. If, on the otherhand, n > 0, then a E L(X) means that X fails (CO), contrary to assumption thatX E Cut(w). This establishes the Lemma. ■Lemma 4.13: Let A contain the schema[PS]^0(a-4 (3) -4 (cc> (3)and let XE Cut(w). Then -1 [R(X)] S L(X).Proof: Let -iaE --i[R(X)]. Then, by [WR], equivalent to [PS] given (pre)normality, wehave (a>a)E w. Then ocE R(X) gives ae L(X) by (CO), so -Tee L(X), as requiredto establish the Lemma. ■The proofs of 4.14 - 4.16 are aided by the following observations: Let A, r be sets offormulae.Chapter 4^ 64Observation 1:(i) -1(r)v-i[r]CA^r g -1(e)u -i[A], and(ii) AD-1(r)U-1[11^-I(A)Un[A]DF.To see (i), suppose --i(r)un[r] g A and let aE r. Then -la belongs to -1 [r ], andhence to A. Then a e , (A ), whence a E -1(A ) u -1[A], as required to show that r c--1(e)u-i[e].To see (ii), suppose AD 1(r)u , [r]. Then by (i), r c --I (A ) u --I [A]. Hence, to show7 (A )u -i[A] Dr, it suffices to find a formula belonging to (n (A )L.)7 [A]) — r. Let a EA-(--i(r)u-i[r ] ). Since a e -1 (r), -men But -la E -1[A]. Hence, we have 7 a E(-I (A ) u-I [A]) - r, as required.Observation 2: If -1[A] is A-consistent, then n (A )u 7 [A] is.First, note thatae n (A )^na€ A^-1 -1 otE "i [A].Suppose n (A ) u n [A] is not A-consistent. Then there are ali..., an E -1(A ) such that[A] u { al, ... , an } is not A-consistent. Then by [RPL],-1[A]u{ -Ina', ... , -1-tan }is not A-consistent either. But by the above note, f -1 nal, ..., -1 n an 1 c 7 [A], whence-1[A] is not A-consistent.Lemma 4.14: Let A contain the schema of adjunctivity:[AD]^((a>13) A (a>y )) --> (a>03Ay))•Let XE MCut(w) be initial. Then n [R(X)] u -I (R(X))e MAXA.Chapter 4^ 65Proof: Since X is initial, we have ^(w) g R(X) by (CO). So by Lemma 4.1, -1 [R(X)]is A-consistent. Then by Observation 2 above, --1[R(X)] u (R(X)) is A-consistent.Claim: Let r_cFma(0) such that rD --1[R(x)]u (R(X)). Then r is not A-consistent. Pf.: By assumption there is a 13E r such that [3( -1[R(X)], -1(R(X)).Towards a contradiction, suppose F is A-consistent. Then -11-1e F. It follows that neither13 nor -Ifs belongs to R(X). Since X is maximal@w, by (C1) there are al, a2EL(X), m, n ?.0 and Si,•, 8m, , yn e R(X) such thata) cci > (0 v8m) E w^and b) cc2>( -1(3vyn) E W ,where 8m =df Si v ...v 8m and r =df Yi v v yn . Then by OK, we have(ai na2)> (0 v 5m), (aina2) >^v Tn) E w,whence [AD] yields(4 )^(al Aa2)>Q(3V8M)A(_1PVTn))  E W.Now, the formula ((3 v 5m) A (3 yr) is propositionally equivalent to the disjunction ofthe following three generalized disjuctionsV{Oinyil 15d Sm,^V{PAyil 1.jn}; V{ -113AS1 lNote that each generalized disjuction propositionally entails the formula Smvyn, whence(*) yields(#)^(ai a2)> (Snivr) E Wby [RMT]. Now, ai,a2€ L(X) means that ain a2E L(X). Then Si,yjE R(X) (1m , 1j.n) and (#) contradict the fact that XE Cut(x) satisfies (CO). Q.E.D. ClaimChapter 4^ 66From the Claim, we have -1[R(X)] kJ-1(R(X)) maximally A-consistent, as required. ■Lemma 4.15: Let A contain the aggregation schema for[C*]^(Ela A 13)^1:1 03cA(3).Let XE Cut(w) be initial. Then there are u, z E MAXA such that (u, -1(z) u --i[z]) isinitial and belongs to MCut(w) and --i[R(X)] z.Proof: Recall from Chapter 0 that(w) =df{ aE Fma(0) IT>aE w}.Claim 1: El(w)u -I[R(X)} is A-consistent. Pf.: Suppose otherwise. Then there arem , n 0, al,^am E 0(w) and Si,^8nE R(X) such that(#)^FA(ain .A am) --> (81v .v8n).But^amE (w) yields El(cci A • • -A am)E w by repeated applications of [C*].So [RMT] yields Ei(81 v . . .v 8, 1)E w. But then 81, .., 8n E R(X) and (#) entail thatTE L(X) by (C0'). This contradicts L(X)E MAXA, and establishes the Claim.From Claim 1, let z E MAXA with 0(w) u [R(X)] c z. DefineF =df { aE Fma(0)1 (3 8)(80 z & a>SE w)}Claim 2: Let ae F and PE Fma(0) such that FA (3--* a. Then OE F. Pf.: By thedefinition of r, there is a So z s.t. a> 8 E W. Then F A --> a yields 13> 5E w b y[RMT], whence [3 E r by definition.Claim 3: To r. Pf.: TE r implies there is 80 z such that T> SE w, contrary tothe fact that El(w) c z by the choice of z.Chapter 4^ 67Claim 4: -1 [11 is A-consistent. Pf.: Suppose not. Then n 0, al, ..., an E Fsuch that(#)^I- A aiv ...van ,whence by def. of r there are 81 , ..., 8,1 0 z such that ai> Sie w (1 i n). Thislast yields ai> (Si v . . .v On) E w (1 5..i rt) by [RMT], whereby repeated applicationsof [DS] yield(*)Now, (#) yieldsby [RPL], so (*) gives(aiv ...van)>(Siv ...v8„)E w .F A T--->(ociv . ..van)T> (81v ...v8n)e wby [1.RM]. But 81, . . ., Sn 0 z means Si v . . .v Sne z (since ze MA XA), so T E Fby the definition of F, contrary to Claim 3. QED Claim 4.By Claim 4, let u E MAXA with -1[r] c u.Claim 5: ^(w) C u. Pf.: It suffices to show that ^(w) c --1 [F], for which it issufficient to show that:a>_Lew^a E F^(a E Fma(0)).So let aE Fma(0) with a>.I_E w. RecallF = [ cce Fma(0) I (38 e z) a> SE w } .Chapter 4^ 68Then the desired result follows from the fact that le z. QED Claim 5.Let u = (u, -1(z) u --1 [z]).Claim 6: u is an initial cut around w. Pf.: Since -11=1-4 1 E z, 1 E -1(Z) ..0 R(U)by def. --1(z). So U satisfies (C1), whence U is initial. To see that ti0 Cut(w), we needto check that U satisfies (CO). Towards this goal, let ae Fma((), n > 0 and Si, • • ., 8nE R(u) such that a> (S1 . . .v Sn )E w. Since Si, . . ., On e -1 (z) u --I [z] and z is A-consistent, we have Si, • .., On 0 z, whence Si v . • Ai 8,2 0 z, so (X E F by definition.Since -I[E] g u, the desired result that ao u follows immediately. QED Claim 6Claim 7: U is maximal@w. Pf.: Let A g Fma(0) s.t. AD -1(z) u -1 [z]. We needto show that (u, A)0 Cut(w). Towards a contradiction, suppose (u, A)e Cut(w). SinceA D -1(z) u -1 [z], by Observation 1 above, -1(A) u -I [A] DZ . Since z is maximally A -consistent, it follows that -1(A) u-1[A] is not A-consistent. Then by Observation 2 above,--I [A] is not A-consistent. Since D(w) g u, this contradicts the Corollary to Lemma 4.1.QED Claim 7.From Claims 6 and 7, Lie MCut(w) and is initial. And -1 [R(X)] g z by the choiceof z. This completes the proof of Lemma 4.15.^ •Lemma 4.16: Let A contain[II32]^oa--> Da .Let XE Cut(w) be initial. Then there is u E MAXA such that (u, -1 (L(X)) u 7 [L(X)])is initial and belongs to MCut(w).Proof: LetF = f ctE Fma(0) I (38)(80 WO & a> SE w)l-Chapter 4^ 69Claim 1: Let aE F and 3E Fma(0) such that 1-A(3—>a. Then PE F. Pf.: By thedefinition of F, there is a Se L(X) s.t. a>SE w . Then F AP-->a yields (3>SE w b y[RMT], whence pe r by def. F.Claim 2: –1[r] is A-consistent. Pf.: Suppose not. Then there are n ?_0, al, ...,an E Fsuch that(#)^FA aiv ...vanwhence by def. F there are Si, . . ., 8n 0 L(X) such that ai> SiE w (1 5_ i n). By[RivIt], we have ai>(81 v . . .v 8n)E w (1 _i5_ n), whence [DS] yields(*)^(al v . . .v an)>(8 1 v . . .vSn)e W .Now, (#) yieldsI-A T-4 (ai v . . .v an)by [RPL], so (*) yieldsT>(Siv ...vSn)E wby [.ARM]. Then [IB2] yields ^(Si v . . .v Sn)E w. But X initial gives ^(w) g L(X)by (C1), so Si v . . .V8nE L(X). This contradicts Si, ..., 5 n e L(X) and establishesClaim 2.From Claim 2, let u E MAXA with --I [r] c u.Claim 3: ^(w) g u. Pf.: It suffices to show that ^(w) g n[r], for which it is in turnsufficient to show that:a>1. E W^a E F^(a E Fma(0)).So let a E Fma(0) with a > 1E w. RecallChapter 4^ 70F = t cc€ Ftna(() I (38) (8o L(X) & a> Se w) } -Then the desired result follows from the fact that _Lo L(x). QED Claim 3Let u = (u, -1(1,(X)) —1[L(X)]).Claim 4: U is an initial cut around w. Pf.: Since L(X) is A-maximal, -11= 1 --->E L(X), whence le -0(X)), so U is initial. To see that U E Cut(w), we need to checkthat U satisfies (CO). So let ae Fma((), n > 0 and 51, ..., 8n E "[WO] {1} suchthata>(81v ...v5n)o w.Now, 51,^8n E 1 (L(X))^[WO] and L(X) E MAXA means that Si v . .v 8nL(X), so a e F by def. F. Since -1 [F] c u, the desired result that a u followsimmediately. QED Claim 4.Claim 5: u is maximal@w. Pf.: Let A c Fma(0) such that ADR(u). We need toshow that (u , A) Cut(w). Towards a contradiction, suppose (u, 0)E Cut(w). Since A(L(X)) L.) [L (X)] , by Observation 1 above, -I [A] u -1(A)DL(X). But L(X) ismaximally A-consistent, so --I [A] u -1(A) is not A-consistent. Then by Observation 2above, -1[A] is not A-consistent. Since Claim 3 ensures that ^(w) C u, this contradicts theCorollary to Lemma 4.1. QED Claim 7.From Claims 4 and 5, u = (u, -1(L(X))u-I[L(X)])e MCut(w) is initial, as requiredto complete the proof of Lemma 4.16.^ ■Lemma 4.17: Let A contain the schema[CONNEX]^(a>13) v ((3>a).and let X1,X2o Cut(w). Then either --i[R(Xi)] c L(X2) or -1[R(X2)] c L(X1).71Chapter 4Proof.: Towards a contradiction, suppose that neithera) -1[R(X1)] g L(X2)^nor^b) -i[R(X2)] c L(X1).Then there are formulae a and (3 such thati) aE R(X1) and nag L(X2)^(from a),ii) f3E R(X2) and -10 L(X1)^(from b).By [CONNEX], either a> f3 E w or p> a E w. Without loss of generality, assumea> (3E w. Then OE R(X2) from ii) yields ae L(X2) by (CO). This contradicts i),since L(X2) is complete. The other case is symmetric. This completes the proof ofLemma 4.17. ■Lemma 4.18: Let A be transparent, that is, let A include Lewis' schema[DIS]^(a> (13 v 7)) —* ((a> f3)v(a>7))and let X1,X2E MCut(w). Then either R(X1) g R(X2) or R(X2) g R(X1).Proof: Towards a contradiction, suppose that neither R(X1) g R(X2) nor R(X2) g R(X1).Then there are formulae a and 13 such that both(i) aE R(X1) and ag R(X2), and(ii) (3E R(x2) and 13 E R(x 1 ).Since X1, X2 are maximal@x, by the Transparency Lemma (4.6.) there are formulaea' and (3' such that both1) a'> aE x and a'E L(X2), (from (i)) , and72Chapter 42) 0'>13E X and f3'E L(Xi) (from (ii))-Then [RMT] yields a'> (a4), 13 1 >(av13) E X , whence [DS] yields(aivii')>(avf3) EX.It follows by [DIS] that either (a'v[3')> aE x or (a ' v (3 1 )> PE X. Assume, withoutloss of generality, that (a'vf3')> a E x. Then f3'>a E x by [.ARM], whence aE R(X1)from (i) above yields 134 L(Xi) by (CO). This contradicts 2) above, and, since theother case is symmetric, establishes Lemma 4.18. ■Lemma 4.19: Let A contain the schema[TRIV1]^(a--43)—>(a>0),and let XE Cut(w) initial. Then L(X)=w.Proof: Let az w. Since [TRIV1] yields the principle[Tc]^a—>Elawe know that ^aE w. Since Xis initial, ^(w) c L(X) by (CO), whence ae L(X). Wehave shown that w g L(X), so w, L(X)E MAXA yields w = L(X). QED 4.19. ■Lemma 4.20: Let A contain the schema[CP]^(occ-->0(3 )--“a>(3),and let XE Cut(w) initial. Then R(X) c {13 113>1E w } .Proof: Let 13€ Fma(0) such that p>10 w. Then we have 0 DE w, whence [RPL] yieldsoT -4o13Ew, whereby [CP] yields T> (3E w. But by (CO), X initial means thatChapter 4^ 73^(w) C L(X), so Lemma 4.1 gives 1131 r... I -1 { R ( -)0 ] I . Hence 130 R(X), as required toestablish the Lemma.^ ■This concludes our prestudy to the completeness constructions.Chapter 5^ 74Chapter 5: Model Construction for Normal Dyadic Logic.Let A be a normal dyadic logic. In this chapter, we construct a "canonical" model 4Afor A. The universe WA for „A4A is given by:WA = { Xe MCut(w)I wE MAXA .So, our canonical universe is populated by w-points for arbitrary w in MAXA.I will observe the convention that members X of WA are treated as "copies" of L(X)in MAXA. In particular, I'll think of a formula a as "true at" X just in case aE L(X).As demonstrated, I use 'X', 'X1', 'X2', etc., to range over the set of all cuts. However,I will use outlined lowercase variables: x , y , z ,..., etc., to range over WA,according to the following convention: When x, y, Z, ... in WA are given, 'x', 'y','z', ... denote the A-maximal sets of which x, y, z,... are respective copies. (Hence, theoutline notation encodes the left projection operator over w-points.)In accord with these conventions, I'll write 'ae x' just in case ae x (a E Fma(0)).Then we can extend the standard semantical definitions to apply to sets of "worlds" in WAin the obvious way. I will use the outline convention to take over previous notationwhenever possible. For example the canonical truth set of a in MA , denoted 0 a 0 A ,can be defined as (ye WA lye lal A l.Continuing our construction, letARx = { (y, z) I y,z E MCut(x) & y is initial & -i[R(y)] c L(z)} (xE WA),RA :^2wAxwA defined by: RA(x) =df RxA (X E WA) ,FA = (WA, RA) ,Chapter 5^ 75VA : Fma(0) ----> 2wA defined by:^VA(P) =df 11P0 A (/) E 0) ,M A = (WA , RA , vA) .AProposition 5.0: dom(Rx) = {X EMCut(x) I X is initial) (x E WA).Proof: Let xe WA. Then def. RxA ensures the inclusion of dom(RxA) in the set of initialx-points. Conversely, let XE MCut(x) initial. Then by the Corollary to Lemma 4.1 thereis a ze MAXA such that -1[R(X)] g z, whence Corollary 1 to the Extension Lemma gives aZ E MCut(x) with z =L(z). Hence, XE dom(RxA), as required.^■Proposition 5.1: IL(y) I y E dOM(RxA)) = I ^(x) I^(x E WA).Proof: Let x € WA and ye dom(RxA). Then y is initial by Proposition 5.0, whence^(x) cL(y) by (C1). Conversely, let 0(x) gy. Then there is an initial y= (y, R(y)EAMCut(x) by Corollary 1 to Lemma 4.3, whereby Proposition 5.0 yields y e dom(Rx ),as required.^ ■Lemma 5.2 (The Fundamental Theorem of Dyadic Logic):Let x E WA and a>13e Fma(0). Then,,a>13 E X^<=>^(Vy E dom(RxA ))[oce y^(3zE WA) (Pe Z& YR xA z)J •Proof:^. Let a>f3e x and y E dom(RxA) such that ae y. We need to find a Z E WAwith (3e z and yRxA z. Now, y E dom(RxA ) yields ^(x) c y by Proposition 5.1, whenceae y with a> (3 EX gives 1131 (6)1 "[WY)] I by Lemma 4.1. So there is a zE MAXA with{ (3) u-I[R(y)] c z. Let our desired z be given as (z, R(z))E MCut(x) by Corollary 1 tothe Extension Lemma (4.3). Since -1[R(y)] gL(z), the definition of R xA ensures thatAyR xz. Since f3e z, we are done.Chapter 5^ 76Let a>13 x. We need to show that there is a y e dom(RxA) with a e y but for allZ E WA, yR xAz implies 00 Z. By Lemma 4.2, a> 13 x yields an initial XE Cut(w)with ^(x) C L(X) such that aE L(X) and 13e R(X). By the Extension Lemma, we mayassume that Xis maximal@x. So XE MCut(x). Then by Proposition 5.0, XE dom(Rx ).So let X be our desired y. Clearly, ae y. Now let z E WA such that yR xAz. Then byAthe definition of Rx' -1 [R(y)] c z. But 13 E R(y), so 0* z, as required to complete theproof of Lemma 5.2.^ ■Having established the Fundamental Theorem for normal A, the way is now clear toshow that when A contains various combinations of the first degree dyadic principlespresented in Chapter 3, M A satisfies the associated first order sentences. However, letsfirst consider the strategy embodied in our construction of MA and its limitations. A briefstudy of right-to-left direction of the proof of The Fundamental Theorem will convince thereader that the purpose of populating WA with multiple copies of A-maximal sets is toensure that the domains of the canonical frame relations RR are "large enough" to allow forthe "falsification" of wedge statements not belonging to L(x).One limitation of this strategy is that dyadic principles whose first order correspondentsexpress the unique existence of certain kinds of relata, e.g., [AD], [C*], [IB1], etc., seemto require the auxiliary assumption of transparency in order for M A to meet thesestructural criteria. Its not hard to explain why this is the case.Take, for example, [AD], which was shown in Chapter 3 to correspond to the framerequirement that frame relations be functional. Now, it is interesting to look ahead toALemma 5.8 to see that, in the presence of [AD], the canonical frame relations Rx are indeedA"functional up to identity of left projections", i.e., any two R x -relata of a given point inWA are "copies" of the same A-maximal set. Hence, the strategy of allowing multiplecopies of a given A-maximal set, which is essential to giving the domains of canonicalChapter 5^ 77frame relations the right structure, frustrates our ablity to "control" the range of thoserelations. Now, by Corrollary 2 to Lemma 4.8, when A is transparent, the identity of theright element of a point in WA is uniquely determined by the choice of the left element.AThus, when A is assumed to be transparent, the canonical frame relations R R are genuinelyfunctional in the presence of [AD]. (Indeed, one advantage of our construction is thatwhen A is transparent, the canonical universe WA coincides, up to isomorphism, with thetraditional Lemmon-Scott canonical universe.) Similar remarks can be made for [C*] and[IB1].Now, one way to avoid relying on transparency would be to change the definiton ofARx so that for each A-maximal set y required to be the left element of a point in the rangeAof Rx' a unique representative be chosen (from among the points in WA having y as theirleft element) to play that role. This strategy is developed in Chapter 7.For the rest of this chapter, let xe WA.Lemma 5.3: Let A be natural. Then rng(RxA ) c dom(RxA).AProof: Let ze rng(Rx). Then z E MCut(x) and there is an initial yE MCut(x) suchAthat yRxz. Since y is initial, ^(x) cL(y) by (C1). Also, by Lemma 4.12, we have{13113>le x} C R(y).AClaim: z is initial. Pf.: We need to show that z satisfies (C1). Since yR xz ,-1[R(y)] c L(z). From Claim 1, { 0 I ((3> 1) e x } c R(y), whence ^(x) c L(z). Then byLemma 4.4, p. 58, z is initial, as required to complete the proof of the Claim.By the Corollary to Lemma 4.1, there is a ZE MAXA such that -1{R(z)) c z'. Let z ° =(z', R(z)) be given maximal@x by Corollary 1 to the Extension Lemma. Since the Claimgives z initial, we have (z,z°) ERA' whence z € dom(RxA), as required to complete thexproof of Lemma 5.3.^ ■78Chapter 5Lemma 5.4: Let A contain[CON]^--CI, equivalently, --1(T>1).AThen Rx is nonempty.Proof: Suppose that FA1(T>1). Then —1(T>1)E x yields a ye dom(RxA) by the right-to-left direction of Lemma 5.0. QED Lemma 5.4.^■Lemma 5.5: Let A contain[PS]^El(a -4 13) --> (a> 13) .A A^AThen Rx is reflexive on its domain, i.e., (VyE dom(Rx))yR x y .AProof: Let y Edom(Rx). Then y is initial. Since ye Cut(x), [R (y )] c L(y) by Lemma4.13. Hence, y initial ensures that yRxAy by def. RA . This completes the proof ofLemma 5.5.^ ■Lemma 5.6: Let A be transparent and contain the schema[PW]^(a> ) ^(oc -4 (3)AThen RxA  is "at most reflexive", i.e., (Vyi, y2) (If1Rx192^1y1 = y2).Proof: Let yi,y 2 E WA such that yiRxA y2. We need to show that yi= y2. SinceAyiE dom(Rx), we have ^(x) g L(y1) by Proposition 5.1.AClaim: Lcy2) g L(n). Pf.: Let 13E 142). Since yiRxy2, we know that --i[R(Y1)]g 1(1y2), whence I3e R(y1). Since A is transparent and yi is maximal@x, by (COT)there is ae L(y1) such that a>13E X. Then by [PW], we have0(a—d3)e x,Chapter 5^ 79whence 12(x)u { a} c 141) yields 13E L(y 1 ), as required to establish the Claim.Since L(Y1),L(Y2)E MAXA, the Claim yields uy2)=L(y1). Then then X11 =Y2 followsby Corollary 1 to Lemma 4.8 given the assumption that A is transparent. This completesthe proof of Lemma 5.6.^ ■Lemma 5.7: Let A be transparent, that is, let A include Lewis' schema[DIS]^(a> (13 v 7)) —, ((a> 0) v (a>7)).and contain and the schema[TRIV1]^(a .-413) -4 (a> p )Then, x E dom(RxA )^[xRxA x & (Vy)(y E dom(RxA^) ^y =x)] .Proof: Assume xE dom(RxA). Since [TRIV1] yields [WR], equivalently, [PS], we haveAxR xx by Lemma 5.5. So it suffices to establish(Vy)(yE dOM(RxA)^y=x).ATowards this goal, let ye dom(R x). Then y is initial by Proposition 5.0, whence L(y)=x by Lemma 4.19. Then the assumption that A is transparent yields x= y by Corollary 1to Lemma 4.8. This establishes Lemma 5.7. ■Lemma 5.8: Let A contain the schema of adjunctivity:[AD]^((a>13) A (a>7)) —> (a>(DAY))•A^A^ALet zi, z2 E WA and yE dom(Rx) such that yRxz i and yR xz2. Then L(z1)=L(z2).Chapter 5^ 80Proof: Since ye MCut(x) is initial, by Lemma 4.14 -1 [R(y)] u (R(y))E MAXA. Since--i[R(y)] g L(zi) and L(zi)E MAXA, it follows that "I[R(y)]u , (R(y)) g L(zi) (i= 1, 2).Hence L(z1), L(z2)E MAXA yields the desired result that L(z1)=1-(z2). ■Lemma 5.9: Let A be transparent and contain the schema [AD]. Then R )At is functional,i.e., (VyE dom(RxA ))(3! z)yR xA Z.Proof: Let z, z'e WA and ye dom(RxA ) such that yRxA z and yR Axz . We want to showthat z=z °. By Lemma 5.8, L(z)=L(e). Then transparency yields the desired result byCorollary 1 to Lemma 4.8. ■Lemma 5.10: Let A be transparent and contain the aggregation schema for[C*]^A (3) -5 ri(a A f3).Then every point in dom(RxA ) bears RxA to a point in WA which is the unique RxA-successorAof some point in dom(Rx). Symbolically,(VyE dom(Rx))(3 z)[YRAxz & (3 ue dOln(Rx))(Ve) (UR Axe <=> Z =z g )].A^AProof: Let ye dom(Rx). Then by def. Rx , y E MCut(x) is initial. By Lemma 4.15,there are u, z E MAXA such that u =(u, -1 (z)U -1 [z])E MCut(w) is initial and —1[R(y)] g z.ASince UE MCut(x) is initial, u E dom(Rx) by Proposition 5.0. Let z = (z, R(z)) begiven maximal@x by Corollary 1 to the Extension Lemma (4.3).Now, to establish the Lemma, we need to show that all of the following hold:A^A^, Aa) yRx z b) uRx z c) (Vz)(uRx z °^z =z°).ASince —1[R(y)] g z by the choice of z, it follows by def. that yR xz , whence a) isestablished.Chapter 5^ 81AFor b), it suffices by def. Rx to show -1[R(u)] g L(z). So assume a = -113E -1 [R(u)].Then 0 E R(u) = -1(z) u --1 [z]. If DE -1(z), then a E Z. On the other hand, if 13 E --I [z],then (3 = --ly for some yE z, whence again a. --rlye z., since z E MAXA. Hence, b) isestablished ).To show c), let z ae WA such that uRxz 0 . Then --1 [R(u)] g L(e) by the definition of RxA.Claim: L(z)=L(e). Pf.: Since L(z),L(z ° )E MAXA, it suffices to show that L(z)g L(z'). Now R(u). -1(z) k..) -1[z], so —I [z] g R(u), that is, --1[1.(z)] g R(u), whence-i[R(u)] g L(e) yields -1 -1[L(z)] gL(e). So, L(z°)E MAXA yields L(z) c L(z ° ), asrequired. QED Claim .From the Claim, we have z ° =z, by Corollary 1 to Lemma 4.8, as required to complete^the proof of Lemma 5.10.^ ■Lemma 5.11: Let A contain[IB1]^Da.--> Da .Then (Vy E dOM(RxA ))(3 Z E dOM(RxA )) yR Ax z .^A^ AProof: Let ye dom(Rx). Towards a contradiction, suppose that zE dom(R x) implies-1 [R(y)] ct L(z) (z e WA). By Proposition 5.2:{ L(y) I y E dOM(RxA)/ = I O(T)I.Then it follows thatEl(x) g z^—1 [R(Y)] '4 z ( ZE MAXA).That is, fl(x)ui[R(y)] is not A-consistent. So there are m, n< co , a 1, . . . , a m E ^(X)and Si_ Sn E R(y) such that82Chapter 5FA (al ...nam) —) (81v ... An) .Then by [RM]F A ^(a1 A ... Aam)^0(51V vOn) •Since al, , amE ^(x), [C] yields ^(ai ... na nd E x, whence^(81v vOn)e x.Then by [1131], 3 (81 V ... VOn)E X , i.e., T > (Si v^v 8n) e x. Then by Lemma 4.1,we have 1(8 1 v ... v8,01 6) I [R(y)] , contrary to 61,. Sne R(y). This completes theproof of Lemma 5.11.^ ■Lemma 5.12: Let A be transparent and contain[1132]^Cia- Oa .Then every point in dom(RxA ) is the unique R xA -successor of some point in dom(RxA).„^ ASymbolically, (V y E dOM(RxA ))(3 U E dOM(RxA ))(VZ)(URe a y =z)Proof: Let yE dom(RxA). Since y E Cut(x) is initial, there isu E MAXA such that u=(u, - (L(y)) L.) [L(y)DE MCut(w) initial by Lemma 4.16, whence u e dom(R xA-1^ ) byProposition 5.0. To establish the Lemma, we need to show thata) uRxAy^and b) (Vz)(uRAxz^y =z).A^ASince -i[R(u)] c L(y) by the choice of u, it follows by the definition of ; that uR x y .ASo we need only concern ourselves with b). Let z be any in WA such that uRxz. ThenA-I[R(u)] c L(z) by the definition of R.Chapter 5^ 83Claim: L(y)=L(z). Pf.: Since L(y),L(z)E MAXA, it suffices to show that L(y)L(z). Now, R(u)= - (L(y))u-1[1.(y)], whence --1[L(y)] c R(u). Since -i[R(u)] c L(z),-1 -1[L(y)] c L(z), whence L(z)E MAXA yields L(y) c L(z), as required. QED Claim.Since L(y)=L(z), we have y=z by Corollary 1 to Lemma 4.8, as required to completethe proof of Lemma 5.12.^ ■Lemma 5.13: Let A contain the schema[CP]^(o a o )^(a>13)A A ^AThen Rx is complete on its domain, i.e., (Vyi, y2E dOM(Rx))(y iR x y2) .Proof: Let y1,y2 E dom(RxA ). By def. RxA, it suffices to show that -1[R(Ifi)] c L(y2)•ASince yiE dom(Rx), yl is initial, whence R(yi).c {13 I (3> 1 E x} by Lemma 4.20.Then i[R(y1)] g ^(x). But Proposition 5.1 gives ^(x) g_ 142), so -I [R(yl)] g 1(y2),as required to complete the proof of Lemma 5.13. ■Lemma 5.14: Let A be transparent and contain the schema of strong transitivity:[STR]^a>((3 v 7)^((R>s) .—>. a>(Svy))•^A ^AThen RxA is transitive, i.e., eglyi, y2, y3) klf iR xA Y2 & y2R xy3^y1RxY3)•Proof: Let y i , y2, y3 e WA. Assume yiRxA y2 and y2R xA y3.Claim: R(y1) c R(y2). Pf.: Since yl E MCut(x), we have R(y1) x-closed by theLemma on Right Closure (4.10, p. 63). Since y1R Axy2, we have —1 [R(y1)] C 1-(Y2)•Then by Lemma 4.9, p. 63, R(y 1 ) g R(y2), as required.Chapter 5^ 84Since yiRxA y2 entails that yi is initial, to show that yiRxA y3, it suffices by def. R xA toshow that [R(y1)] g L(Y3). But from the Claim we have --i[R(Y1)] c -1 [R(Y2)].Moreover, y2RY3 gives -I [R(y2)] c 143). Hence, the desired result is immediate. ■Lemma 5.15: Let A contain the schema[CONNEX]^(a> (3) v ((3>a)AThen RxA is connected on its domain, i.e., (Vyi, y2€ dom(RxA )AY iR xA Y2^Y2R xY1)•AProof: Let y1,y2E dom(Rx). Since y1,y2E Cut(x), by Lemma 4.17, either -1[R(Y1)] cL(y2) or "I [R(y2)] g um. Since yi and y2 are both initial, the desired result that eitherAY1R02^Ay2R xyi follows immediately by the def. R.. This completes the proof ofLemma 5.15. ■ALemma 5.16: Let A be transparent. Then Rx is mutual over its domain, i.e.,(Vyi, y2 E dOM(R xA)) ((VZ)(Y1RxZ^y2Rxz) or ((Vz)(Y2R xZ^YiR xz))•Proof: Let y1,y2E dom(RxA). Since y1,y2E MCut(x), by Lemma 4.18, we have eitherR(y1) c R(y2) or R(y2) c R(y1). We need to show that eithera) (VZ)(YiRxA Z^y2RxAz) orA^Ab) (Vz)(Y2Rxz^yiRxz)holds. Assume, without loss of generality, that R(y 1 ) S R(y2). To see that b) follows, letZ E WA such that y2RxA z- Then [R(1172)] cL(z) by def. R xA, whence -1[R(Y1)] cL(z)A^Aby assumption. Since yi is initial, the definition of R x yields yiRxz, as required. Theother case yields a) in symmetric fashion.^■Chapter 5^ 85We are now in a good position to establish some determination results. But first, let'srecall from the introduction (and Chapter 0) the semantics of "relativised" generalizedinclusion. We extend valuations V for models ,A4 = (W, R) to assignments if E.A4 :Fma(0)--> 2Wx W by the usual inductive clauses for —> ,1 and, for the wedge,.A4[R>]^.1,, a>f3 <=>^(Vx€ dom(Rw))[xE [tam^(3yE III-311M ) x Rwy]•Now, VA is lifted to a valuation II E A of Fma(0) with the desired property that:5.17 (Truth Lemma): if a E A = {we WA I ae w} .Proof: As usual, by induction on the formation of a, using the definition of VA for thecase a=pE 1, the properties of maximal consistent sets for the the cases a=1, a =13—>y,and Lemma 5.2 for the case a = 0>y. ■Corollary: MA determines A, i.e., for all formulae a.MA a <=:, Fh a .Proof: FA a <=> a belongs to all members of MAXA <=> (by def. WA) for allw E WA, a e^<=> (by Lemma 5.17) if ca A= WA.^■Theorem 5.18 (Determination of JK): JK a if, and only if, a is valid in all g.i.frames.Proof: Soundness: For any frame F, EF = IpIF H3} is a normal dyadic logic, soA c EF , i.e.,pF c a^Fka.Completeness: If liK a then, by Corollary to the Truth Lemma, a is false on M K ,whence a is not valid in the frame FJK.^ ■Chapter 5^ 86Theorem 5.19: Let A be a normal logic.i) If A includes any combination of the schemata 0, 1, 2, 8, 9, 11, 13, 14, given inChapter 3, then A determines the class of frames which satisfy the associated combinationof first order principles.Proof: Soundness: By Theorem 3 and Lemma 3.1.Completeness: By Lemmata 5.3, 5.4, 5.5, 5.10, 5.11, 5.13, 5.15, 5.16. ■ii) Let A be transparent. Then, if A includes any combination of the schemata 0, 1, 2,3, 5, 7, 8, 9, 10, 11, 12, 13, 14. inclusive given in Chapter 3, then A determines the classof "mutual" frames which satisfy the associated combination of first order principles.Proof: Soundness: By Theorem 3.0 and Lemma 3.1.Completeness: By Lemmata 5.3, 5.4, 5.5, 5.6, 5.7, 5.9, 5.10, 5.11, 5.12, 5.13, 5.14,5.15, 5.16.^ ■This completes (no pun intended) our general study of classes of g.i framesdetermined by first degree extensions of JK. In the next chapter, we focus on a largesubclass of comparison frames, those determined by first degree extensions of JKSTR.87Chapter 6Chapter 6: Model Construction for Normal Logics Containing STR.In this chapter, we shall see that JK[STR] emerges as a natural base logic. Let I be anormal dyadic logic containing [STR]. Recall from Chapter 2 that this means that I isnatural, since [Mt] is a consequence of [STR].Let's now construct a "canonical" model ME for I. The universe WE for ,A4 E isgiven by:WE = { Xe MCut(w)I X is initial & w e MAXE} .Thus, unlike the construction of the previous chapter, our canonical I-universe ispopulated by initial w-points for arbitrary we MAXE.In the sequel, u, V. w, x, y, z range over WE. We shall observe theconventions of the previous chapter regarding the interpretation of cuts as "worlds".Set:ZRx = { (if , z)I y ,z E MCWX) & -I[R(y)j g L(z) & R(y) c R(z)} (XE WE),ERE : WE ---) 2wExwE defined by: RE(X) =dfRxFE= (WE , RE) ,(x e WE) ,VI : Fma(40) ---> 2wE defined by: V1(p) =df OpI E^(p E 0) ,ME_  (WE, RE, VE) •Proposition 6.0: dom(R xI) = { XE MCut(x) I X is initial }^(x E WE).IProof: Let XE WE. Clearly, dom(Rx ) g { XE MCut(x) IX is initial} by the definitionof WE. Conversely, let X1 E MCut(x) initial. We know that --1 [R(Xi)] is I-consistentChapter 6^ 88by the Corollary to Lemma 4.1. Also, since E contains [STR], R(X1) is x-closed by theLemma On Right Closure (4.10). Then by Lemma 4.11, there is an X2E MCut(w) with-1[R(X1)] c L(X2) and R(X1) c R(X2). Since J_E R(X1), we know that X2 is initial.z^E^ zThen the definition of Rx ensures that XiRxX2. Thus X1 E dom(Rx), as required. ■Proposition 6.1: {L(y) I y E dom(RxE)) = I ^(x) I^(x E WE).Proof: Similar to the proof of Proposition 5.1, using Proposition 6.0. in place of 5.0. ■Lemma 6.2: Let x E WE and a>f3E Fma(0). ThenE^ Ea>13€ X <=> (Vy e dom(RxMaE y^(3z E WE) (PE z & YR xZ)J •zProof: =. Let a> Pe x and ye dom(Rx) such that ae y. We need to find a zE WEEwith (3E z and yRxz. Now, R(y) is x-closed by the Lemma On Right Closure (4.10),Esince E contains [STR]. Also, since ye dom(Rx), by Proposition 6.1, ^(x) Cy,whence ae y with a>I3E x gives 1011 -1 [R(Y)] 1 by Lemma 4.1. So folu -i[R(y)]is E-consistent. Then by Lemma 4.11, there is an XE MCut(w) with -I [ { -1131 uR(y)]c L(X) and R(y) c R(X). Since y is initial, it follows that X is initial. So let X E WEbe our desired z . Clearly, --I [R(y)] c L(z); furthermore, R(y) c R(z). Then theEdefinition of Rx gives yRxz . Since -1 -1(3E L(X), (3E z, and we are done.E. Let oc>130 x. We need to show that there is a ye dom(Rx) with ae y but for all ZE^iE WE, yR xz mpl ies pe z. By Lemma 4.2, a>pex yields an initial XE Cut(w)with ^(x) c L(X) such that OCE L(X) and [3e R(X). By the Extension Lemma (4.3), wemay assume that X is maximal@x. Since XE MCut(x) initial, Proposition 6.0 ensuresXE dom(Rx). So let's take X as our desired y. Clearly, ae y. Now let ZE WE suchE^ zthat yRxz. Then by the definition of Rx , -i[R(y)] c z. But (3 E R(y), so 0 e z, asrequired to complete the proof of Lemma 6.2.^ ■Chapter 6^ 89For the rest of this chapter, let xE WE. Since we are here interested in modellingextensions of JK[STR], we need to show that „M E satisfies the structural conditioncorresponding to [STR] given in Chapter 3, viz., that1) the range of R is included in the domain of that relation, and2) Rx is transitive.Lemma 6.3: mg(Rx ) c dom(Rx ).Proof: Let Z E mg(Rx). Then Z E MC ut(x) initial, so by Proposition 6.0,Z E dom(Rx), as required.^ ■ELemma 6.4: Rx is transitive.Proof: Let yi,y2, y3 E WE. Assume that 0 Y1RxY2 and ii) y2Rxy3. To show thatZ,y 1R ^it suffices, by the definition of R x, to show that both of the following hold:a) -' [R(Y1)] c L(y3),^and^b) R(S91) c R(Y3).From i), the definition of Rx yields R(y 1 ) c R(y2), while from ii), Rx yields -1 [R(192)]c L(y3). Hence a) is immediate. Furthermore, ii) yields R(y2) c R()y3), whence b)follows. This completes the proof of Lemma 6.4. ■We now procceed to show that when E contains any combination of the first degreedyadic principles presented in Chapter 3, M E satisfies the associated combination of firstorder sentences.Lemma 6.5: Let E contain [CON]. Then R x is nonempty.Proof: Suppose that 1- E-C11. Then --i(T>1.)E x yields a pair (y, y°)E R x by theright-to-left direction of Lemma 6.0. This is sufficient.^ ■90Chapter 6Lemma 6.6: Let I contain[PS]^0(a--->(3 ) —> (a > (3) .EThen Rx is reflexive on its domain, i.e., (VyE dOM(RxI))yR zxy .EProof: Let ye dom(Rx). Since ye Cut(x), we have --I [R(y)] c L(y) from Lemma 4.13.E^zThen since ye MCut(x) initial and R(y) c R(y), we have yRxy by the def. Rx . ■Lemma 6.7: Let Z contain the schema[SI]^^(a —)(3) <—> (a> J3).E^zThen (thy E dom(Rx))(Vz)(YRxz <=> y =z).Proof: First we note that [SI] yields [AD], as follows. From [SI], [RPL] yieldsI- z ((a> 0) A (a>y)) .--->. ^(a —> 13) A 0(0C—yy) ,whence [C] yieldsFE ((a>I3) A (a>y)) --> D(a —> f3 .A. a--->Y)by [RPL], whereby [RE] yieldsFE ((a>f3)A (a>y)) —> ^(a—> (OAT))whence [SI] yields1-"z ((a>P) A (CE>Y)) --> (a>((3AY))Eby [RPL], as required. Now, to establish the Lemma, let yE dom(Rx). We need tozshow that: (Vz)(yRxz 4#› y =z ).91Chapter 6Since E is "adjunctive", Rx is functional by Lemma 6.7. Hence, it suffices to show thatyR xy. But [PS] is a consequence of [SI], so the desired result follows from Lemma6.6. ■Lemma 6.8: Let E be transparent, that is, let E include[DIS]^(a> vy)) ((a> (3) v (a> y)).Suppose further that E contains the schema[TRIV1]^(a---)(3)-->(a>p).Then x E dom(RxA )^[xRxA x & (Vy)(y € dom(RxA)^y=x)i .Proof: xe dom(RxA ). Since [TRIV1] yields [WR], equivalently, [PS], we have xRxAx byLemma 6.6. So it suffices to establish(Vy)(y e dom(R)d^y=x).ATowards this goal, let ye dom(Rx). Then y is initial by Proposition 6.0, whence L(y)=xby Lemma 4.19. Then the assumption that A is transparent yields x=y by Corollary 1 toLemma 4.8. ■Lemma 6.9: Let E contain the schema[TRIV]^(a>13)<-4 (a --)(3).Then (yR xz <=> x=y =z) (y, z E WE).Proof: Let y,z E WE. First we note that the assumption that E includes [TRIV] entailsthat E is transparent and includes [PS] and [TRIV1].92Chapter 6. Suppose yRxz. Since I includes [TRIV1], we have L(x)=L(y) by Lemma 4.19.Then, since I is transparent, we have x= yby Corollary 1 to Lemma 4.8. Hence, itsuffices to show that y=z, for which it in turn suffices by Corollary 1 of Lemma 4.8 toE^ Eshow that L(y)=L(z). Since yRxz we have -1 [R(y)] cL(z) by def. R x , and sinceL(z)e MAXE, we have:(#)^-i[R(y)]un(R(y)) c L(z).Since I includes [PS], we have --I [R(y)] gL(y) by Lemma 4.13, whence L(y)E MAXEyields(*)^-T[R(y)]un(R(y)) c L(y)•But since I contains [AD], -i[R(y)]u -1 (R(y)) e MAXE by Lemma 4.14. Then (#) and(*) yield the desired result that L(z) = L(y) by virtue of L(z), L(y)E MAXE.E=. It suffices to show that xR xx. Since x is initial and R(x) g R(x), it suffices by def.ERx to show that a) xE MCut(x) and b) -i [R(x)] c L(x). Now, b) follows from the factthat I includes [PS] by Lemma 4.13. So it suffices to show a).Claim 1: xE Cut(x). Pf.: Since I is transparent, it suffices to show that x satisfies(COT). Towards this goal, let ae Fma(0) and Se R(x) such that a>SE L(x). This lastyields a ---> SE L(x) by [TRIV1]. As we have seen, -I [R(x)] C L(x), whence SE R(x)yields n•SE L(x), whereby 'GEE L(x), i.e., a€ L(x), as required to complete the proof ofClaim 1.Given Claim 1, to prove a), it suffices to show that x is maximal@x. Since Xe WE,it follows from def. WE that x is initial and there is a UEMAXE such that xE MCut(u).EThen by Proposition 6.0, xE dom(RU ), whence XE ^(u) by Proposition 6.1. Now,observe that since I contains [TRIV], I also containsChapter 6^ 93[n]^0a4->a.Claim 2: Let a> E u. Then a>13e L(x). By assumption, since a> E u we have0(a>(3)e u by [n], whence xE 0(u) yields a>13E L(x), as required.Claim 3: x is maximal@x. Pf.: Let r g Fma(0) properly extend R(x). We need toshow that (L(x),^Cut(x). Since Z is transparent, it suffices to show that (L(x), F)fails (COT) with respect to x, i.e., that there is an otE L(x) and a SE R(x) such thata>(3 Ex. Now, since xE MCut(u), x is maximal@u, whence, by def. maximal@u,(L(x), r)f6 Cut(u). Then (L(x), F) fails (COT) with respect to u, i.e., there is an aE L(x)and a SE R(X) such that a> f3E u. But by Claim 2, then a> Ex, as required.From Claims 1 and 3, we have XE MCut(x), and a) is established. This completes theproof of Lemma 6.9.^ ■Lemma 6.10: Let E contain the schema of adjunctivity:[AD]^((a> 13) A (a>y)) —3 (a>(3Ay)).EThen Rx is functional.Proof: Let Zl,Z2 E WE and y E dom(R) such that yR:g1 and yRxz2. We want toshow that z1=Z2. By assumption, y, z 1, Z2 E MCut(x) initial with --1[R(y)] c L(zi) andR(y) c R(z1) (i =1, 2). Since y, z 1, Z2 E MCut(w) initial, we have(*)^—1[R(U)]U-1(R(U))E MAXE^E { y,z1,z2}by Lemma 4.14. It follows that if wl, w2 E MAXz such that -1 [R(y)] c wi (i =1, 2),then wi =w2. Suppose that -1[R(19)]C wi. Then WiE MAXz yields 7 (WY)) g Wi, sowe have -1 [R(y)]u (R(y)) c wi, whence wi = --1[R(y)] u (R(y)) (i = 1 , 2). Hence,(t3[C*]94chapter 6-1[R(Y)] c L(zi) (i =1,2) entails that L(z1)=L(z2). So we need only show that R(Z1) =R(z2).Now R(y) c R(zi), so we know that(#)^--I [R(y)] u --1 (R(y)) c --I [R(zi)] u -1 (R(zi))^(i =1,2).Then it follows from (*) and (#) that($)^--1 [R(y)] u n (R(y)) = n [R(z1)] u -1 (R(zi))^( i =1,2).Claim: R(z1)=R(z2). Pf.: Let aE R(z1). Then -la E -I [R(z2)]u 7 (R(z2)) by($), whence one of a, -1 -la belongs to R(z2). However, by the Corollary to Lemma4.5, we haveaE R(X)^<=>^-1 --1ccE R(X).Thus, ocER(z2). We have shown that R(z1) c R(z2). But symmetric reasoning alsoyields R(z2) c R(z1). Hence R(z1)=R(z2) , as required.So we have shown that zi =Z2. Hence, Lemma 6.10 is established.^■Lemma 6.11: Let I contain the aggregation schema for Elanci(3) -p Ei(an().z^z^ zThen every point in dom(Rx) bears Rx to a point in WE which is the unique R x-successorEof some point in dom(Rx). Symbolically,(VyE doril(RxE ))(3z)[yR Exz & (3LBE d0111(4))(Vz0(d14.Z ° <1=> Z =e)].Z^ zProof: Let yEdom(Rx). Then by the definition of R x , ye MCut(x) is initial. ByLemma 4A5, there areu, z E MAXE such that u= (U, 7 (Z) U 7 [Z]) is initial, belongs to95Chapter 6MCut(w) and --i[R(y)]cz. Since LAE MCut(x) initial, U E dom(Rx) by Proposition6.0. Let z = (z , -1(z) u -1[z]).Claim 1: ZE Malt(X) is initial. Pf.: Since _LE -1(z), we have _LE R(Z) by def. z.So z satisfies (C1). To see that z satisfies (CO) (and hence is an initial cut around x),let aE Fma(0), n>0 and 81, . . ., 8n E (-1(Z) Un[z]) such thata>(Siv...v8n)e x.Since I contains [STR] and uE MCut(x), we have that R(u) = -1(z) u -'[z] is x-closedby Lemma 4.10. Hence, a E i (z) u -1 [z] by the definition of x-closure. Sincez E MAX, it follows that cco z, as required to establish that z satisfies (CO). To see thatz is maximal@x, let A g Fma(0) s.t AD (-1(Z) U -1[Z]). We need to show that (z,A) 0Cut(x). Towards a contradiction, suppose (z, A)e Cut(x). Since AD -1(z), there is a PEA s.t. -100 z; thus, since ze MAXE, 13E z. But then A D n[z] yields -ilk A, whenceboth , 13, -1 -10E -1[i\]. So -1[0] is not I-consistent. Since -i(z)u n [z] is x-closed and.LE -7(z), it follows that [13113>J_Ex} g -1(z)u -I[z], whence 1:1(x)g z by the fact thatZ E MAXE. This contradicts the Corollary to Lemma 4.1 and establishes the Claim.Now, to establish the Lemma, we need to show that all of the following hold:E^Ea) yRxz b) uRxz^c) (Vz0(uRIxe^z =z°).We have ' [R(y)] c L(z) by the choice of z, so n (L(z)) c R(z) yields R(y) c R(z),Ewhence a) is established by def. Rx .To see that b) holds, recall that R(u) = -1(z) l..) 7 [Z] . Then -1[R(u)] c z =L(z), sinceAZ E MAXE. Hence, by def. Rx it suffices to show that R(u) c R(z). But R(u) = -1(z) L)[z] = R(z), so we have the desired result.Chapter 6^ 96To show c), let telii/ such that uR xEz ° . Then -i[R(u)] g L(e) and R(u) g R(V)by the definition of Rx .Claim 2: L(z) = L(z °). Pf.: Since L(z), L(z °)E MAXE, it suffices to show thatL(z) g L(z'). Now R(u)= (z)u --1[2], so -i[L(z)] c R(u), whence -1 [R(u)] g L(e)yields -1 -1[L(Z)] gL(e), whereby L(z °)E MAXI entails L(z) c L(e), as required.Claim 3: R(z') c R(u). Pf.: Towards a contradiction, suppose that ae R(z') but aR(u)=df-i(z)u -1[z]. The latter yields aE z (since ze MAXE), whence 'ae R(u),whereby R(u) g R(V) gives -1 ae R(e). Hence -1 oc,a E R(e), so -1 [R(z')] is notI-consistent . But z' is an initial cut around x, so ^(x) c z by (CO). This contradictsthe Corollary to Lemma 4.1 and establishes Claim 3.From Claim 3, R(u)g R(e) gives R(u)=R(e), whence R(z)=R(u) yields R(z)=R(z'). Then 1=z follows by Claim 2. This establishes c), as required to complete theproof of Lemma 6.11. ■Lemma 6.12: Let E be transparent and contain[IB2]^na—>^ .Then every point in dom(Rx) is the unique R x-successor of some point in dom(R x ).Symbolically, (fy E dOM(Rx ))(3U E dom(Rx))(Vz) (uR xz <=> y =z).Proof: Let yE dom(Rx/). Then y E Cut(x) is initial by Proposition 6.0, whence Lemma4.16 gives a u E MAXI such that u =(u, -1(14) [L(yD is initial and belongs toMCut(x). So uE dom(Rx) by Proposition 6.0, whence to establish Lemma 6.12 itsuffices to show thata) uRx y^and b) (Vz) (uRExz^y97Chapter 6Since i[R(u)] gL(y) by the choice of u, for a) it suffices by def.R to show that R(u)c R(y). Since u E MCut(x), R(u) is x-closed by the Lemma on Right Closure (4.10).Then by Lemma 4.9, we have the desired result that R(u) g R(y). To establish b), letZE WE such that uRxz. Then -, [R(u)] c L(z) by the definition of Rx .Claim: L(y)=L(z). Pf.: Since L(y),L(z)EMAXA, it suffices to show that L(y)L(z). Now R(u)--.dr(L(y)) u -1 [L(y)], so -1[L(y)] c R(u), whence n[R(1.1)] c L(z)yields -1-1[14)] c L(Z), whereby L(z) E MAXA entails L(y) g. L(z), as required.The Claim yields y= z by Corollary 1 to Lemma 4.8, as required to complete theproof of Lemma 6.12.^ ■Lemma 6.13: Let E contain the schema[CP]^(oa--><>0)--> (a>(3).\ zThen Rx is complete on its domain, i.e., (Vyi,y2E dOM(Rx)lkylR 02) •Proof: First, let us observe that the "Rule of Monotonicity for Diamond"[RMo]^F a—>13^I- °a -4 ois an easy consequence of [IRM] given [RPL] and the Df. 0 . Now, to prove 6.13, letY1, Y2 E dOM(Rx). It suffices to show that -1[R(191)] cL(y2) and R(y 1) R(y2) by def.REx•Claim 1: E includes [DIS]. Pf.: By [PD] we haveFE (ct>(13vy)) —> (oa —>o(13vy))Now, [RMO] yieldsChapter 6^ 981-z 0 (Pvy) ---* (013v oy),so by [RPL] we haveFE (cit>(13vy)) —* (occ--4 (0 Ovoy))•But 0 a --) (013v 0 y) is propositionally equivalent to (0 a--4 o(3)v(oa--)oy), so[RPL] and [CP] yieldFE (a>(Ov1)) --+ ((a>13) v (a>Y)),as required to establish Claim 1.From Lemma 4.20 we know that R(Y1) g (13 I PIE x ), i.e., -1 [R(Y1)] CI:7(x). ButProposition 6.1 gives ^(x) g L(y2), so -, [R(y1 )] gL(y2).Claim 2: R(y1) c R(y2). Pf.: Proposition 6.1 gives ^(x) g L(191), whence we knowfrom the Corollary to Lemma 4.1 that -1 [R(y1)] is E-consistent. Then, since E contains[STR], R(y1) is x-closed by the Lemma On Right Closure (4.10). Since -1[R(Y1)] cL(y2), it follows that R(y1) c "1 [L(y2)]. Since E is transparent by Claim 1, by theLemma on w-closure (4.9, p.61), we have the desired result that R(y 1 ) c R(192)•^This completes the proof of lemma 6.13.^ ■Lemma 6.14: Let E contain the schema[CONNEX]^(a>13)v (Pa)EThen Rx is connected on its domain, i.e.,E ^E^E(\iyi,y2E dom(Rx))(y1RxY2 or y2R xyl) •Chapter 6^ 99Proof: Let yi, y2 E dom(Rx). By Lemma 4. 14 either -i [R(y1)] c L(92) or -1 [R(Y2)]CL(yi). Suppose, without loss of generality, that -1[R(111)] cL(y2). I shall show thatE^ EyiRx y 2. Since y 1 , y2e MCut(x) initial, it suffices, by def.Rx' to show thatR(Y1)gR(Y2). Since I contains [STR], R(y1) is x-closed by the Lemma On RightClosure (4.10). Now, we know from Chapter 3 that I is transparent, since [CONNEX]and [STR] yield [DIS]. Then by the Lemma on w-closure (4.9), -i [R(y1)] c L(y2) yieldsthe desired result that R(y1) cR(y2). Since the case -I [R(y2)] gL(191) is treatedsymmetrically, this completes the proof of Lemma 6.14. ■ELemma 6.15: Let I be transparent. Then Rx is mutual over its domain, i.e.,E^E^E^E^E ,(gfy 1 ,y2 E dOM(Rx))0,Z)(Y1RxZ^y2Rxz) or ((Vz)(192R xz^YiR xz))•Proof: Let y1,y2E dom(Rx). We need to show that eitherE^Ea) (Vz)(YiRxZ^y2R xz) or b) (Vz)(Y2R xE Z^yiRxz)Eholds. By def. Rx , Y 1, Y2 E MCut(x), whence either R(y1) c R(y2) or R(y2) g R(Yi) byLemma 4.18. Assume, without loss of generality, that R(y1) c R(y2). To see that b)follows, let ZE WE such that y2Rxz. Then we havei) -1 [R(Y2)] c L(z)^and^ii) R(y2) g R(z)by the definition of Rx. Since R(yt) g R(y2), we have 7 [R(y1)] g L(z) by i) andE^ER(y1) c R(z) by ii). So by the definition of Rx , we have yiRxz, as required to establishb). In the case where R(y2) g R(y1), we obtain a) in symmetric fashion. This completesthe proof of Lemma 6.15.^ ■Now for some determination results. Again, we recall the truth condition for thewedge:Chapter 6^ 100[R>]^k a> 3 44. (Vx E dom(Rw))[xE ffa]A4^(3y e Q(3DA4) xR,, y ).wRecall also the definition of our model ME = (WE, RE, VI) at the beginning of thechapter. VE is canonically extended to a valuation IE II E of Fma(0) with the desiredproperty that:6.16 (Truth Lemma): if a D E= fwe WE I ocew).Proof: As usual, by induction on the formation of a, using the definition of VI for thecase a =p E 0, the properties of maximal consistent sets for the the cases a = 1 ,a = (3 -*y , and Lemma 6.2 for the case a= [3>y . ■Corollary: ME determines E, i.e., for all formulae a,,A4.E k cc^FE a .Proof: FE a <=> a belongs to all members of MAXE•=> (by def. WE) ae w^E WE)4* (by Lemma 6.16) Q a11 = WE.^ ■Theorem 6.17 ("Determination of JKSTR"):Let C be the class of g.i. frames F = (W, R) that are "pointwise serial" and "transitive",i.e., such that1) dom(Rw) c rng(Rw) (we W)2) Rw is transitive (WE IV).I-^a <=> C^a.jKsTRThen,101Chapter 6Proof: Soundness: For any frame FE C, X,F = 1131F k 13} is a natural dyadic logic.And by Lemma 12 of Theorem 3.0, EF includes [STR]. Hence, JKSTR .c ZF , i.e.,I-^a^F a .jKsTRCompleteness: If Iticsma then, by Corollary to the Truth Lemma, a is false on M ASTR ,whence a is not valid in the frame FJKSTR.^ ■Theorem 6.17: Let E be a normal dyadic logic with [STR]. Theni) If E includes any combination of the schemata 1, 2, 4, 6, 7, 8, 11, 13, 14 given inChapter 3, then E determines the class of transitive, pointwise serial frames which satisfythe associated combination of first order principles.Proof: Soundness: By Theorem 3.0 and Lemma 3.1.Completeness: By Lemmata 6.5, 6.6, 6.7, 6.9, 6.10, 6.11, 6.13, 6.14, 6.15,respectively.^ ■ii): If I is transparent and includes any of the schemata 1, 2, 4, 5, 6, 7, 8, 10, 11, 13given in Chapter 3, then E determines the class of mutual, transitive, and pointwise serialframes which satisfy to the associated combination of first order principles.Proof: Soundness: By Theorem 3.0 and Lemma 3.1.Completeness: By Lemma 6.15 and Lemmata 6.5, 6.6, 6.7, 6.8, 6.9, 6.10., 6.11, 6.12,6.13, 6.14, respectively.^ ■102Chapter 7Chapter 7: Model Construction for Natural Dyadic Logic.Let A be a natural dyadic logic. In this chapter, we construct a model MA of A whichwill afford us some determination results for natural logics which have so far eluded us.The model MA = (W, R, V) has universe W given by:W = {XE CUt(W)I W E MAXA } •Note that unlike the previous two constructions, MA has no maximality conditions placedon the cuts populating its universe. Let: x, y, z,... etc. range over W according to ourprevious conventions.Let w E MAXA and X1, X2€ Cut(w). I shall write 'X1 g r X2' wheneverL(X1) = L(X2) and R(X1) c R(X2).Recall from Chapter 4 that in the proof of the Extension Lemma (4.3) we presented auniform procedure which, for a given maximally A-consistent set w andXie Cut(w),produced an X2€ MCut(w) such that R(X1) c R(X2). Since X2 is uniquely determinedby the choice of w, X1 and the enumeration 4) of Fma((), and since we hold 4) fixed, wemay use the functional notation 'E w (X1) 1 to denote X2. Let z E MAXA with ^(w) g z.By the argument of Corollary 2 of the Extension Lemma (4.3), (z, {1.}) is a cut around w,and Ew((z , UWE MCut(w) is initial. LetE w((z, fl )))be denoted 'w[zr .The point here is that w[z] is an initial element of MCut(w) which is uniquelydetermined by the choice of ze MAXA.103Chapter 7Let: Rx = {(y,x[z]) I yE Cut(x) & Z E MAXA & -1[R(Ex(10)] c z^W),R : W —> 2WxW defined by: R(x) =dfRx^E W) ,F= (141 , R) ,V : Frna((b)^2W defined by:V(p) =cif 11P D A (p E^,M A = v R v) .Proposition 7.0: Let x,y E W. Let Z E MAXA such that -1 [R(Ex(Y))] -C z. ThenClaim 1: (13 I 13>lEx} cR(Ex(Y)). Pf.: Towards a contradiction, let Pe Fma(0)such that 13>lex but fie R(Ex(y)). Since Ex(Y) is maximal@x, there are n 0, 61,8n E R(Ex(Y)) and an aE Fma(0) s.t.a) a> ((3vR^-iv ...v 8n )E x^andRecall that owing to [MTh[NE] I- A (a> (8 v^.A. 13>i) --> (a>8).b) ae L(Ex(y)).Hence, a> (81 v...v^E X follows from a) and 13>1 E X. Then, if n = 0, we havea>_Le x, whence ^(x) c L(Ex(y)) yields a L(Ex(y)), a contradiction. If, on theother hand, n > 0, then E x(y) fails (CO) because of b), contrary to the fact thatEx(y)E Cut(x). This establishes Claim 1.Since by assumption -i[R(Ex(y))} g z, Claim 1 yields ^(x) c L(z), as required tocomplete the proof of Proposition 7.0.^ ■Chapter 7^ 104Proposition 7.1: dom(Rx) = {XE Cut(x) I Xis initial} (x E IV).Proof: Let xe W. Then the definition of W ensures the inclusion of dom(R x) in the setof initial cuts around x. Conversely, let X e Cut(x) initial. Then ^(x) c L(X) by (C1),whence ^(x) s L(Ex(X)). Then the Corollary to Lemma 4.1 gives a ze MAXA such thatn[R(Ex(X))) C z. Then (X,w[z])e Rx by def.Rx , so XE dom(Rx), as required. ■Proposition 7.2: { L(y) I y E dom(Rx) } = 1:1(41 (x E W).Proof: Let XE W and ye dom(R x). Then y is initial, so ^(x) c L(y) by (C1).Conversely, let y E MAXA such that ^(x) Cy. Then there is an initial y = (y, R(y))E Cut(x). By Proposition 7.1, yE dom(R x), as required. ■Lemma 7.3: Let XE W and a> 0 eFma(0). Thencc> 0 e (dye dom(Rx))[aE y (azE W) (Pe z and yRxz)].Proof: Let a> 0e x and ye dom(Rx) such that otE y. We need to find a ZE Wwith 0E Z and yR xz. Now, since yE dom(Rx), by Proposition 7.1, ^(x) CL(y),whence ^(x) cL(Ex(Y)). Then ote L(Ex(Y))with a>0 ex gives 101 (6) I i [R(Ex(y))]by Lemma 4.1. So there is a z E MAXA with { u [R(Ex(Y))] C z. Let our desiredz be x[z]. Since -1[R(Ex(Y))] c L(z), the definition of R x ensures that yRxz. SinceE Z, we have 0e z, as required.Let a>f3ex. We need to show that there is a yE dom(Rx) with aE y but for allZE W, YRxZ implies fle z. Since a>(3 x, there is an initial XECut(w) with^(x) CL(X) such that a€ L(X) and 0e R(X) by Lemma 4.2. Since X is initial, X Edom(Rx) by Proposition 7.1. X is our desired y. Clearly, cite y, so we need only showthat105Chapter 7yRxz^13 0 z^(z E W)So let zE W such that yR xz. Then by the definition of Rx , -I [R(Ex(Y))] g L(z). ButDe R(y) c R(Ex(y)), so 'OE L(z), whence 13e z, as required to complete the proofof Lemma 7.3. ■For the rest of this chapter, let xe W. Since we are here interested in modellingextensions of JICMT, we need to show that Alt A satisfies the structural conditioncorresponding to [MT] given in Chapter 3, viz., that the range of R x is included in thedomain of that relation:Lemma 7.4: rng(Rx) c dom(Rx).Proof: Let ze rng(Rx). Then ze Cut(x) initial, so by 7.1, ze dom(Rx).^■Lemma 7.5.: Let A contain[CON]^-ID I, equivalently, -1(T>1).Then Rx is nonempty.Proof: By Lemma 7.3.^ ■Lemma 7.6: Let A contain the schema of adjunctivity:[AD]^((a>13) A (a>y)) —> (a>([ A y))•Then Rx is functional, i.e., (VyE dom(Rx))(3!z) yR xz .Proof: Let z, ee W and ye dom(Rx) such that yRxz and yRxe. We want to showthat z= z ° . Since yRxz and yRxz ° , by def.Rx, we have n [R(Ex(y))] g L(z), L(z °).Claim: L(z) = L(z °). Pf: Since Ex(y)e MCut(w) is initial, we have■ElChapter 7(#) 106n [R(Ex(Y))] un (R(Ex(Y))e MAXAby Lemma 4 14. Since we have "[R(Ex(Y))1C L(zi) and L(zi) E AXA, it follows thatn [R(Ex(Y))1u "(R(Ex(Y)) c L(Zi) (i = 1, 2). Then (#) yields the desired result thatL(z)=L(e).From the Claim, we have x[L(z)] =x[L(z °)], whence the desired result that z= z °follows by def. Rx .Lemma 7.7: Let A contain the aggregation schema for[C*] an D13) --> el(a Al3).ElThen every point in dom(Rx) bears Rx to a point in W which is the unique Rx-successorof some point in dom(Rx). Symbolically,(VyE dom(Rx))(3 z)[yRxz & (3ue dom(Rx))(Vz°) (URxe .4* Z = Z °)]•Proof: Let ye dom(Rx). Since E x(y)E Cut(x) is initial, by Lemma 4.15, there areu,z E MAXA such that (u, -1(z)u -I [z])e MCut(x) initial and -1 [R(Ex(Y))] C z . Let U=df (14, —I (Z)U —I [Z]). By Proposition 7.1, u E dom(Rx). Let z =x[z]. Now, toestablish the Lemma, we need to show that all of the following hold:a) yRxz b) URxZ c) (gf z ° ) (URxz ° z =z ° ).-1[12(Ex(y))] g z, whence yRxzby def. Rx. Since R(u) = -1(z) u -1[z] and ze MAXA,we have --1[R(u)] g z =L(z). Hence, b) follows by def. Rx. To show c), let z ° E Wsuch that URxe. Then -1[R(u)] g L(z °) by def. Rx.107Chapter 7Claim: z c L(e). Pf: Let aE z. Since R(u) =1(z)u n [z], we have naE R(u).Then, since -1[R(u)] CL(Z 1), -1 -1 ae L(z'), whence ocE L(V) follows from L(z°)EMAXA, as required.Then z,L(e)E MAXA give z =L(e) by the Claim. But by def. Rx, z°=x[L(e)], i.e.,z ° =x[z]. Then it follows that e=x[z] = z, as required to complete the proof of theLemma 7.7. ■Lemma 7.8: Let A be transparent, that is, let A include Lewis' schema[DIS]^(a> (I3 v y)) -4 ((a> 13) v (a>y))•Then Rx is mutual over its domain, i.e.,(Vyi, y2E dom(Rx))((Vz)(YiRxz y2Rxz) or (Vz)(Y2RXZ YiRxz))•Proof: Let y1, y2 E dom(Rx). Now, Ex(n),Ex(Y2)E MCut(w), so by Lemma 4.18,we have that either R(Ex(Y1)) c R(E x(y2)) or R(Ex(y2)) g R(Ex(Y1)). To establishthe Lemma, we need to show that one ofa) (Vz)(YiRxZ y2Rxz)b) (Vz)(Y2Rx  yiRxz)holds. Assume, without loss of generality, that R(Ex(Y1)) g R(E x(y2)). To see that b)follows, let ZE W be such that y2Rxz. Then, by def. Rx, z =x[L(z)J andn [R(Ex(y2))] c L(z). Then by assumption, -' [R(Ex(Y1))1 g L(z). Then the definitionof Rx yields yiRxz, as required. The other case yields a) in symmetric fashion. Thiscompletes the proof of Lemma 7.8. ■As before, V is lifted to a valuation I 3] A of Fma(0) with the desired property that:Chapter 7^ 1087.9 (Truth Lemma): II a B A = {we W I ae w }Proof: As before, by induction on the formation of a, using the definition of V for thecase a = p E 0, the properties of maximal consistent sets for the the cases a =1, a =13 -4y, and Lemma 7.3 for the case a =13 > y. ■Corollary: MA determines A, i.e., for all formulae a,MA ka <=> Fla.Proof: I-Aa^a belongs to all members of MAXA<=> (by def. W) ae w (W E W)<=> (by Lemma 7.17) QaBA= W.^■Let C be the class of g.i. frames F = (W, R) that are "pointwise serial" ", i.e., such thatdom(Rw) c mg(Rw) (WE W). Then:Theorem 7.10: Let A be a natural logic.i) If A includes any combination of the schemata 1, 7, 8, 14, given in Chapter 3, then Adetermines the class of frames FE C such that F satisfies the associated combination of firstorder principles.Proof: Soundness: By Theorem 3.0 and Lemma 3.1.Completeness: By Lemmata 7.5, 7.6, 7.7, 7.8.^ ■This completes Chapter 7, and our completeness study.BibliographyBibliography.[0]^Äqvist, Lennart. An Introduction to Deontic Logic and the Theory of Normative Systems. Bibliopolis, Indices IV (Monographs in Philosophical Logic and FormalLinguistics), 1987.[1] Chellas, Brian, F. 'Basic Conditional Logic'. Journal of Philosophical Logic  4,(1975), 133-153.[2] Chellas, Brian, F. Modal Logic: An Introduction. Cambridge University Press,1980.[3] van. Fraassen, Bas C. 'The Logic of Conditional Obligation', Journal ofPhilosophical Logic 1 (1972), 417 - 438.[4] ^ 'Values and the Heart's Command', Journal of Philosophy (1973), 5 - 19.[5] Goldblatt, R. I. Logics of Time and Computation. CSLI Lecture Notes No. 7,Center for the Study of Language and Information, Stanford University, 1987.[6] Jennings, R.E., 'Utilitarian Semantics for Deontic Logic;', Journal of Philosophical Logic 3 (1974), 445 - 456.[7] 'Aspects of the Analysis of Entailment'. Unpublished monograph,1984.[8] Leibnizian Semantics: An Essay in Monotonic Modal Logic,  Unpublishedmonograph, 1984.109[9]   'The Natural Conditional'. Unpublished monograph, 1986.Bibliography[10] Kripke, S. 'A Completeness Theorem in Modal Logic', J. Symbolic Logic 24, 1-14.^ "Semantic Analysis of Modal Logic I. Normal Modal Calculi",Zeitschrift far Mathematische Logik and Grunglagen der Mathematike  9 (1963),67 - 96.[12] Leibniz, G. W. von. "First Truths" in Opuscules et Fragments Inëdit de Leibniz,ed. Louis Coutourat. Paris: Felix Alcan, 1903.[13] Lemmon, E. J. and Scott, Dana S. Intensional Logic, preliminary draft of initialchapters by E. J. Lemmon, 1966, Nowadays available as An Introduction to Modal Logic (edited by Krister Segerberg). American Philosophical QuarterlyMonograph No. 11, Blackwell, 1977.[14] ^ 'Completeness and Decidability of Three Logics of CounterfactualConditionals', Theoria 37 (1971), 74 - 85.[15] ^ Counterfactuals. Oxford: Blackwell, 1973.[16] Lewis, D.K., "Counterfactuals and Comparative Possibility". Journal of Philosophical  Logic 2 (1973), 418-446.[17] Nute, Donald, Topics in Conditional Logic, Reidel, Dordrecht, 1980.[18] 'Conditional Logic', in Handbook of Philosophical Logic II.  D. Gabbay and F.Guenthner, eds. (Synthese Library), Dordrecht and Boston. D. Reidel Publ. Co.(1984), 387- 439.110Bibliogaph.y_[19] Scott, D. 'Advice On Modal Logic', in Philosophical Problems in Logic, Some Recent Developments.  K. Lambert ed. (Synthese Library), Dordrecht andBoston. D. Reidel Publ. Co. (1971), 143-173.[20] Smith, T.V., and Marjorie Grene, eds. From Descartes to Kant. Chicago:University of Chicago, 1940.111

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0098835/manifest

Comment

Related Items