See discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/38383951
Review: Maarten Marx, Laszlo Polos, Michael Masuch, Arrow Logic and Multi-Modal Logic ARTICLE in JOURNAL OF SYMBOLIC LOGIC · JANUARY 1998 Impact Factor: 0.54 · Source: OAI
READS
11
1 AUTHOR: Roger D. Maddux Iowa State University 83 PUBLICATIONS 1,145 CITATIONS SEE PROFILE
Available from: Roger D. Maddux Retrieved on: 05 February 2016
Review: [untitled] Author(s): Roger Maddux Source: The Journal of Symbolic Logic, Vol. 63, No. 1 (Mar., 1998), pp. 333-336 Published by: Association for Symbolic Logic Stable URL: http://www.jstor.org/stable/2586609 . Accessed: 24/02/2011 15:18 Your use of the JSTOR archive indicates your acceptance of JSTOR's Terms and Conditions of Use, available at . http://www.jstor.org/page/info/about/policies/terms.jsp. JSTOR's Terms and Conditions of Use provides, in part, that unless you have obtained prior permission, you may not download an entire issue of a journal or multiple copies of articles, and you may use content in the JSTOR archive only for your personal, non-commercial use. Please contact the publisher regarding any further use of this work. Publisher contact information may be obtained at . http://www.jstor.org/action/showPublisher?publisherCode=asl. . Each copy of any part of a JSTOR transmission must contain the same copyright notice that appears on the screen or printed page of such transmission. JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide range of content in a trusted digital archive. We use information technology and tools to increase productivity and facilitate new forms of scholarship. For more information about JSTOR, please contact
[email protected].
Association for Symbolic Logic is collaborating with JSTOR to digitize, preserve and extend access to The Journal of Symbolic Logic.
http://www.jstor.org
333
REVIEWS
Some corrections are needed to the exposition of Boole's MAL given in ?7 of Part 1 of the Editors' introduction. (i) On p. xxx we read: "For example, for the universal affirmative proposition, All Ys are Xs', symbolised as (1 - x)v = 0, he put forward v = vx (7.3) as 'the most general solution' (MAL, 25); but he should have noticed that x = 0 was missing from it, and that it did not hold if x = 0 and v was a class such that vy 74 0." Needed here in this last clause is an interchange of x and v, correcting it to .. . that y = 0 was missing from it, and that it did not hold if y = 0 and v was a class such that vx 740." One can disagree, however, with this (typographically corrected) conclusion. To say that y = vx is the general solution (for y) of (1 - x)y = 0, is to say that (1 - x)y = 0 if and only if there is a v such that y = vx. That is, one needs to establish the two conditionals (a) (1 - x)v = 0 -lv(y vx), and (1 - x)y = 0. Since the latter is equivalent to (b') Vv(v = vy - (1 - x)j, = 0), (b) "v(y = vx) one can establish (b) by showing that, for arbitrary v, y = vx implies (1 - x)y = 0. Note the essential presence of the existential quantifier in (a). The part of the argument in the text ("if y = 0 and v was a class such that vox74 0") illegitimately assumes that, with v = 0, v can be arbitrarilychosen so as to obtain for (a), (1 - x)0 --O
= vx, with vx 74 0.
(ii) Also on p. xxx: "In fact, in this case Boole realised that v = xy was a better version than (7.3)1: so did the Irish mathematician Charles Graves after reading [a portion of] MAL, and he told the Royal Irish Academy in a note 1850a." (This reference is absent from the book's bibliography.) While I have not checked the reference, there surely is an error here-indeed, a footnote on p. 45 of MAL reads in part [for the comparison interchange the roles of X and Y]: "Professor Graves suggests the employment of the equation x = vy for the primary expression of the Proposition All Xs are Ys, and remarks, that on multiplying both members by 1 - v, we obtain x (1 - y) = 0, the equation from which we set out in the text, and of which the previous one is a solution." (iii) On p. xxxi there is this passage illustrating Boole's method of solving logical equations by using his "expansions": "For example, (7.3)i [i.e., (1 - x)y = 0] was solved for y from (7.5) [Boole's general expansion of a So(x)] as 1 0 0 0 - x) = x +- (1(- x)' (7.8) x+ 0 with''' was [being?]explained as an alternative to 'v (p. 74), a quotient notation which was to feature prominently in LT." The equation that is given in (7.8) is in error and should be 0 0 0 l-x)= y=I Ix~ I These few corrections in a small part of the Editors' introductionshould not be taken as reflecting adversely on the achievements of the editors. Historians of logic will be indebted to them for making THEODORE HAILPERIN Boole's Nalchilassreadily available for study. Arrowv logic andmulti-modallogic, edited by Maarten Marx, Ldszl6 P6los, and Michael Masuch, Studies in logic, language and information, CSLI Publications, Stanford, and FoLLI, 1996, also distributed by Cambridge University Press, New York, xiv + 247 pp.-therein: A crash course in arrowtlogic. Pp. 3-34. YDE VENEMA. Investigations in arrowl7 MAARTEN MARX, SZABOLCS MIKULAS, ISTVAN NEMETI, and ILDIK6 SAIN. logic. Pp. 35-61. Causes and
HAJNAL ANDREKA, AGNES KURUCZ, ISTVAN NEMETI, ILDIK6 SAIN, and ANDRAS SIMON.
logics. Pp. 63-99. reinediesfor uindecidabilityin arrowtlogics and in mnulti-mnodal VIKTOR GYURIS. Associativity does not imply unclecidabilitywithout the axiomnof mnodaldistribution. Pp.101-107. MAARTEN MARX. Dycnamfic arrowvlogic. Pp.109-123. SZABOLCS MIKULAS. Complete calculuhs for conjutgatedarrolw logic. Pp.125-139. Pp. 141-187. Many-dinmensional arroii strutictutres.arrowi logics II. What is inodal logic? Pp. 191-202. Pp.203-219. JOHAN VAN BENTHEM. Content versus wrt7fapping.an essay in semantic complexity. A fine-stritctre analysis offirst-order logic. ISTVAN NEMETI. Pp.221-247. DIMITER VAKARELOV. MAARTEN DE RIJKE.
The
connection
between
J6nsson
and A. Tarski
a single
binary
relation
relations
in a two-part R on a set
and paper W.
Boolean
algebras
of subsets
in the early 1950's (XVIII 70). Let R*
be the operation
was
studied
intensively
For the simplest
on subsets
of
by B.
case, consider
W that
sends
each
334
REVIEWS
subset X to the image of X under R, namely R*(X) ={yi: Ex(x C X, xRjv)}. Then R* distributes over non-empty unions, and maps the empty set to the empty set. In other words, R* is a normal additive unary operator on eub( W), the Boolean algebra of all subsets of W. Suppose 1Bis a Boolean algebra. By Stone's representationtheorem, there is a set W such that 93 is isomorphic to a subalgebra of 5ub(W). The J6nsson-Tarski extension of Stone's theorem implies that if 0 is a normal additive unary operator on 93, then there is a set W and a binary relation R on W such that K93,0) is isomorphic to a subalgebra of K6ub(W), R*). Stone's theorem can be proved by taking W to be the set of ultrafiltersof 93, in which case the binary relation R should be the one that relates two ultrafilters if the image of the first ultrafilter under 0 is included in the second ultrafilter. The J6nsson-Tarski paper treats Boolean algebras with arbitrarily many operators of arbitrary finite rank, not simply those with a single unary operator, but their primary applications are to relation algebras and cylindric algebras, for which the theory was developed. The theory also has applications in the semantics of modal logics. About a decade later, S. Kripke (XXXI 120) independently initiated the (subsequently extensive) study of possible-world semantics, which, for a modal logic with a single unary modality, requires models consisting of a set W (the set of worlds) and a binary relation R c W2 (the accessibility relation, which relates two worlds if the first world is accessible from the second). If a proposition p holds at every world in X, a subset of W, then Op holds at every world in R* (X). The J6nsson-Tarski paper gave rise to a large literature in algebraic logic, encompassing relation algebras, cylindric algebras, polyadic algebras, and others. Kripke's paper had a similar effect in modal logic. The ten loosely linked papers in this collection exploit this connection, mixing the results, techniques, and viewpoints of algebraic logic with modal logic. Part I consists of seven papers on arrow logic. In Chapter 1, A crash course in arrowilogic, Yde Venema gives a general introduction. An arrowtfiamne is defined to be a structure )1 = (W, C, R, I) consisting of a set W, a ternary relation C C W3, a binary relation R C W2, and a subset I C W. The appropriate modal language and the appropriate semantical notions for this language are then defined in ways familiar from modal logic, followed by some is an arrowframem K ( KC,R, I) examples, motivation, and an algebraic point of view. A pair-faie a,b, c for which there is a base set U such that W C U2, C = w I {((a,c),(a,b),(b,c)): U}, R = w2 n {((a, b), (b, a)): a, b C U}, and I = {(a, a) : a C U}. (The third condition in the definition of pair-frame is incomplete; consult instead Definition 2.1 in Chapter 2.) A pair-frame is reflexive if I C W. syvmmetric if W is a symmetric relation, and transitive if W is transitive. Each arrow frame 9.1has its associated complex algebra: Cmnm = CmKW.C, R1I) = (K u b( W), C *, R *, I), where C * (X, Y) = x(x C X, y C Y.Czxv)} for all X, Y C W. The complex algebra of a reflexive, symmetric, transitive pair-frame is a complete atomic representablerelation algebra whose universe consists of all binary relations included in a particular equivalence relation. Conversely, every representablerelation algebra is isomorphic to a subalgebra of the complex algebra of a reflexive, symmetric, transitive pairframe. The modal language appropriatefor the frame m1consists of propositional logic augmented with a binary modality, unary modality, and a constant proposition. Each modal formula a in this language may also be interpretedas a term in the equational language appropriatefor the complex algebra m CZ, 9. so that a is (modal logically) valid in the frame 9Nif and only if the equation a = I is true in C9m Through this connection one may, for example, derive a finite set of modal formulas that are valid in an arrow frame ST if and only if its complex algebra Cm 91 is a relation algebra. The natural tendency to illustrate binary relations with pictures containing labeled arrows leads to the terms "arrowframe" and "arrowlogic." Chapter 2, Inviestigationsin arrow logic, by Maarten Marx, Szabolcs Mikulhs, Istvdn Nemeti, and Ildik6 Sain, has technical results involving classes of pair-frames. Let H be any list of properties of pair-framesselected from these three: reflexivity,symmetry, and transitivity. Let QH be the set of modal logical formulas that are valid in all pair-frames having the properties in H. If transitivity is included in H, then QH is not decidable, is not finitely axiomatizable, has neither the weak nor the strong Craig interpolation property, and does not have the Beth definability property. On the other hand, if transitivity is excluded from H, then f2H has all these properties."Thistheorem, the main result of the paper, summarizes and extends several results, some from the literature of algebraic logic. References are given for the original papers and proofs of certain parts. For instance, the negative results about logics and in inultidecidability are treated in Chapter 3, Calusesanldreinediesjbr wndecidabilityin arrowt. modal logics, by Hajnal Andr6ka, Agnes Kurucz, Istvdn Ndmeti, Ildik6 Sain, and Andrds Simon. This chapter starts with a review of modal logic and of the duality between modal logic and the equational logic of Boolean algebras with operators. It presents a wide variety of arrow logics that are undecidable 7
REVIEWS
335
(including an undecidable modal logic with only one binary associative modality satisfying two quite simple identities), plus many that are decidable. One of its themes is the responsibility of associativity for the axiom of mnodal undecidability, but in Chapter 4, Associatii'it!?does niotimply tndecidability wt.,ithout distribution,Viktor Gyuris reminds us that what the title says is true because, by a theorem of Pigozzi, a decidable equational theory is obtained if the one and only axiom involving both the Boolean and relative operators is omitted from a standard ten-identity axiomatization of relation algebras. Indeed, the resulting equational theory is essentiallyjust the "union" of two (decidable) equational theories, that of Boolean algebras and (what could be called) 'involuted monoids." The first half of Chapter 5, D'nainic arrowslogic, by Maarten Marx, has a general lemma concerning the addition of transitive closure to arrow logics. It yields several completeness and decidability results for arrow logics with transitive closure. In the second half, a finitely axiomatized, complete, decidable, two-sorted arrow logic is presented that corresponds algebraically to a class of two-sorted algebras that contains the representablePeirce algebras. Chapter 6, Complete caleuhis for conjugatedarroit'logic, by Szabolcs Mikulds, presents a complete finitely axiomatized inference system for a variant of arrowlogic having, besides the Boolean connectives, three binary modalities, for which the intended models are sets with a single ternary accessibility relation. The system is also shown to be decidable and to have the finite model property. The Introduction:.a short history of arrowt,logic, to Chapter 7, Mani'-clinmensional arrowt? structures. arrow logics II, by Dimiter Vakarelov, should be read right after the Prefrice. Vakarelov defines various kinds of frames and structures built on domains of points, arrows, or both. The defined objects are roughly equivalent, in that one can pass between them via canonical constructions. Appropriate firstorder and modal languages are constructed for each type of object, and these languages are shown to be equivalent in means of expression. Among the main results in the latter half of the chapter is a finitely axiomatized arrow logic for each finite nithat is decidable because it has the finite model property and complete with respect to models built from sets of ii-tuples. The class of Boolean algebras with operators corresponding to this arrow logic is the one containing every algebra obtainable from a full n-dimensional cylindric set algebra (one whose universe is the power set of the nth direct power of some base set) by relativizing to an arbitrary relation. Part II consists of three papers on multi-modal logic. The first two are nontechnical and discuss methodological issues. In Chapter 8, Whatis modal logic? Maarten de Rijke proposes that a modal logic is multi-sorted algebra with semantics subject to some mild restrictions. Connectives are the functions that operate within a given sort, while modalities are the functions that map between sorts. Some examples fitting this framework and a few new research topics are discussed. Johan van Benthem advocates In Chapter 9, Content versunsityrapping.:an essaYin senantic comiplexitY', systematic searches for alternative logical and semantic modelings in order to avoid complexity, such as undecidability or non-axiomatizability, and, through numerous examples and references, argues that this approach has already been fruitful. One of van Benthem's examples is Chapter 10, A fin~e-structure anall'sis of first-orderlogic, by Istvdn N6meti. The introduction begins with the observation that firstorder logic (with equality and binary relation symbols only) has its "expenses": the validities are undecidable, and the finite-variablefragments do not have the Beth definability property, nor the Craig interpolation property, nor are they finitely axiomatizable. Except for undecidability, these "expenses" are incurred only by passage to the finite-variable fragments (obtained by restricting the number of individual variables from the usual countable set down to a finite set), not by first-order logic itself. The main point of this paper (illustrating van Benthem's thesis) is that these "expenses"can be avoided by enlarging the class of models for first-order logic (and for its finite-variable fragments), thereby obtaining more restricted classes of logical validities, ones that turn out in many cases to be decidable and finitely axiomatizable (details are given), and to possess the Beth definability property and the Craig interpolation property (results are only summarized). The introduction contains a lucid description of the enlarged model class. A standard model for a first-order language (with equality and relation symbols only, possibly restricted to finitely many variables) has an underlying set, called the model's universe, together with a map that sends a relation symbol of rank n to an n-ary relation on the universe (and the equality symbol to the identity relation on the universe). The usual definition of satisfaction (of a formula in a standard model) makes use of the collection of all evaluations (functions from the set of variables to the universe of the model). If all (implicit or explicit) referencesto this class in the definition of satisfaction are instead relativized (restricted) to an arbitraryclass of evaluations, the result is one of the generalized models. A generalized model is thus obtained by specifying, in addition to a universe
336
REVIEWS
and a relation for each relation symbol, a class of evaluations. Several examples are given of logical identities that may fail in generalized models, such as the identity expressing the permutability of like quantifiers. Chapter 10 treats first-order logic from the perspective of modal logic (e.g. quantification with respect to a given variable is a modality added to propositional logic). It presents modal-logical versions of several theorems from algebraic logic that concern the existence of relative representations of finitely-axiomatized classes of Boolean algebras with operators, notably cylindric algebras and their variants. It includes some significant new results. For example, every finite weakly associative relation ROGERMADDUX algebra has a relative representation on a finite set.
