Algebraic Relativization And Arrow Logic [phd Thesis]


E-Book Content

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
You might also like

Mathematical Models In Biology: Solution Manual
Authors: Elizabeth S. Allman , John A. Rhodes    247    0


Introduction To Mathematical Methods In Bioinformatics
Authors: Alexander Isaev    169    0


Modular Algorithms In Symbolic Summation And Symbolic Integration
Authors: Jürgen Gerhard (auth.)    175    0


Comprehensive Mathematics For Computer Scientists
Authors: Guerino Mazzola , Gérard Milmeister , Jody Weissmann    189    0


Algebra. Abstract And Concrete
Authors: Frederick M. Goodman    221    0


Abstract Algebra
Authors: Pierre Antoine Grillet (auth.)    250    0


The Book Of Involutions
Authors: Alexander Merkurjev , Markus Rost , and Jean-Pierre Tignol Max-Albert Knus , Max-Albert Knus    240    0


Combinatorics Of Permutations
Authors: Miklos Bona    175    0


Topics In Discrete Mathematics: Dedicated To Jarik Nešetřil On The Occasion Of His 60th Birthday
Authors: Michael E. Adams , Aleš Pultr (auth.) , Martin Klazar , Jan Kratochvíl , Martin Loebl , Jiří Matoušek , Pavel Valtr , Robin Thomas (eds.)    157    0


Introduction To Hyperplane Arrangements
Authors: Stanley R.P.    214    0