A lgebraic R elativization AND A rrow Logic
ILLC Dissertation Series 1995-3
institute/orlogic,languageandcomputation
For further information about ILLC-publications, please contact Institute for Logic, Language and Computation Universiteit van Amsterdam Plantage Muidergracht 24 1018 TV Amsterdam phone: +31-20-5256090 fax: +31-20-5255101 e-mail:
[email protected]
A lgebraic R elativization and A rrow Logic
Academisch Proefschrift ter verkrijging van de graad van doctor aan de Universiteit van Amsterdam, op gezag van de Rector Magnificus Prof.dr P.W.M. de Meijer in het openbaar te verdedigen in de Aula der Universiteit (Oude Lutherse Kerk, ingang Singel 411, hoek Spui) op vrijdag 3 februari te 13.00 uur door
Maarten Johannes Marx geboren te Amsterdam.
Promotors:
Prof.dr. J.F.A.K. van Benthem Prof dr. I. Nemeti Co-promotor: Dr. J.M.F Masuch
CIP-GEGEVENS KONINKLUKE BEBLIOTHEEK, DEN HAAG Marx, Maarten Johannes Algebraic relativization and arrow logic / Maarten Johannes Marx. - Amsterdam : Institute for Logic, Language and Computation. - (ILLC dissertation series ; 1995-3) Proefschrift Universiteit van Amsterdam. - Met lit. opg., reg. ISBN 90-74795-15-3 N U G I811 Trefw.: algebra / logica.
Copyright © 1995 by Maarten Marx Cover: Saint Sebastian by Egon Schiele ISBN: 90-74795-15-3
C ontents
Acknowledgments
vii
Introduction
1
1 Main themes LI Arrow logic is the modal logic of tra n sitio n s...................... 1.2 Cylindric modal logic is the modal logic of assignm ents........................ 1.3 Relativization............................................................................................ 1.4 Fine structure of definability.................................................................... 1.5 BAO’s and general modal logic ...............................................................
5 5 7 10 10 11
2 The 2.1 2.2 2.3 2.4 2.5
13 13 18 23 25 36
Algebras and the Logics BAO’s, general modal logic and Kripke fram es....................................... Review of basic duality th eo ry .................................................................. Relativization and the logical co re............................................................ Relation algebras, arrow logic and arrow fra m e s .................................... Cylindric algebras, cylindric modal logic and alpha f r a m e s ..................
3 Decidability 3.1 Filtrations................................. 3.2 Relativized relation algebras . . 3.3 Relativized cylindric a lg e b r a s ........................ 3.4 Concluding remarks..........................................
.4 .5 .5 .5
4 Representation &: Axiomatization 4.1 Axiomatizing BAO’s by representing frames . . 4.2 Relativized relation algebras........................ ................................. 4.3 Reducts of relativized relation alg eb ras...... ................................. 4.4 Adding the difference operator................................................................. 4.5 Representing BAO’s as algebras of re la tio n s .......................................... 4.6 Concluding remarks.......................................................................... .. . . 5 Amalgamation & Interpolation 5.1 Amalgamation, interpolation and definability . . 5.2 Zigzag products.......................... . 104 5.3 Preservation................................ .1 1 0 5.4 Applications to relation and cylindric algeb ras............ 5.5 Concluding remarks......................................................... 5.6 Appendix: Reformulation of (S)AP with applications .
45 5 0 2 5 57 57 58 69 74 85 9