Relation Algebras by Games - Hirsch

. .

Résumé :
Relation algebras are algebras arising from the study of binary relations.They form a part of the field of algebraic logic, and have applications in proof theory, modal logic, and computer science. This research text uses combinatorial games to study the fundamental notion of representations of relation algebras. Games allow an intuitive and appealing approach to the subject, and permit substantial advances to be made. The book contains many new results and proofs not published elsewhere. It should be invaluable to graduate students and researchers interested in relation algebras and games.

After an introduction describing the authors' perspective on the material, the text proper has six parts. The lengthy first part is devoted to background material, including the formal definitions of relation algebras, cylindric algebras, their basic properties, and some connections between them. Examples are given. Part 1 ends with a short survey of other work beyond the scope of the book. In part 2, games are introduced, and used to axiomatise various classes of algebras. Part 3 discusses approximations to representability, using bases, relation algebra reducts, and relativised representations. Part 4 presents some constructions of relation algebras, including Monk algebras and the 'rainbow construction', and uses them to show that various classes of representable algebras are non-finitely axiomatisable or even non-elementary. Part 5 shows that the representability problem for finite relation algebras is undecidable, and then in contrast proves some finite base property results. Part 6 contains a condensed summary of the book, and a list of problems. There are more than 400 exercises.

The book is generally self-contained on relation algebras and on games, and introductory text is scattered throughout. Some familiarity with elementary aspects of first-order logic and set theory is assumed, though many of the definitions are given. Chapter 2 introduces the necessary universal algebra and model theory, and more specific model-theoretic ideas are explained as they arise....

Biographie:
r)(A(n,r),L). 15.6 Non-finite axiomatisability. 15.7 Proof theory

16 The rainbow construction for relation algebras.16.1 Ehrenfeucht-Fraisse `forth' games. 16.1.1 The standard Ehrenfeucht-Fraisse game. 16.1.2 The modified Ehrenfeucht-Fraisse game. 16.2 The rainbow algebra A(A,B). 16.3 How A can win G(A(A,B)). 16.4 How E can win G(A(A,B)). 16.5 Modifications to the rainbow algebra

17 Applying the rainbow construction. 17.1 Non-finite axiomatisability of RRA. 17.2 Complete representations. 17.3 There is no n-variable equational axiomatisation of RRA. 17.4 RA(n+1) is not finitely based over RA(n). 17.5 Infinite-dimensional bases and relativised representations. 17.6 Weakly representable relation algebras. 17.7 Completions. 17.7.1 The example. 17.7.2 Corollaries and problems

V Decidability. 18 Undecidability of the representation problem for finite algebras. 18.1 Introduction. 18.2 The tiling problem. 18.3 The definition of RA(t). 18.4 Games. 18.5 Winning E-strategy implies tiling 18.6 RA(t) in SRaCA(5) implies tiling 18.7 Tiling implies winning E-strategy 18.7.1 E's strategy for non-tile edges 18.7.2 Tile edges 18.7.3 Attached and linked tile edges 18.7.4 Inductive conditions T1, T2, T3 on N 18.7.5 Tiling functions and coordinates for A's tile edges 18.7.6 Tiling functions for E's new tile edges 18.7.7 Coordinates for E's new tile edges 18.7.8 Conditions T1, T2 hold for M 18.7.9 E's strategy for tile edges, T3, and consistency 18.8 Conclusion 18.9 Weak representability is undecidable 18.10 Undecidability of equational theories 19 Finite base property 19.1 Introduction 19.2 Guarded fragments 19.2.1 Loosely guarded fragment 19.2.2 Packed fragment 19.2.3 Clique-guarded fragment 19.2.4 Finite model property 19.3 The finite base property 19.4 Finite base property for WA 19.5 Finite algebra on finite base property for RA(n) 19.6 The finite algebra on finite base property for SRaCA(n)? VI Epilogue 20 Brief summary 20.1 Basic definitions 20.2 Games for representability 20.3 Relativised representations, bases, reducts 20.3.1 Relativised representations 20.3.2 Relational bases and hyperbases 20.3.3 Relation algebra reducts 20.3.4 Equivalences between the notions 20.4 The rainbow construction 20.5 Atom structures 20.6 Decidability 20.7 Summary of relations between the classes 20.8 Summary of properties of classes 21 Problems Bibliography Symbol index Subject index...

Sommaire:
Preface.Foreword.

1 Introduction.1.1 History. 1.2 To the games.1.3 Non-finite axiomatisability. 1.4 Approximations to representability. 1.5 Constructions of algebras.1.6 Some remarks on methods. 1.7 Summary of contents

I Algebras of Relations.2 Preliminaries. 2.1 Foundations. 2.2 Model theory.2.2.1 Syntax. 2.2.2 Semantics - structures. 2.2.3 Models, validity. 2.2.4 Homomorphisms, embeddings, substructures. 2.2.5 Generating sets.2.2.6 Compactness, Lowenheim-Skolem-Tarski theorems. 2.2.7 Relativisation, interpretations, second-order logic. 2.3 Boolean algebras. 2.3.1 Definition and examples. 2.3.2 Atoms.2.3.3 Dense sets. 2.3.4 Ideals, filters, ultrafilters. 2.3.5 Representations of boolean algebras. 2.3.6 Canonical extensions. 2.3.7 Infinite sums and products. 2.3.8 Complete representations. 2.3.9 Completions of boolean algebras. 2.4 Products and ultraproducts. 2.4.1 Products.2.4.2 Ultraproducts, ultrapowers. 2.5 Boolean algebras with operators. 2.5.1 Definitions. 2.5.2 Homomorphisms and ideals. 2.5.3 Completely additive and conjugated algebras. 2.5.4 Completions of BAOs. 2.6 Varieties and quasi-varieties of BAOs. 2.6.1 Basic concepts. 2.6.2 HSP notation and Birkhoff's theorem. 2.6.3 Subdirect products. 2.6.4 Discriminator varieties. 2.7 Aspects of duality for BAOs. 2.7.1 Atom structures of BAOs. 2.7.2 Complex algebras. 2.7.3 Canonical (perfect) extensions of BAOs. 2.7.4 Axiomatising the atom structures of a variety. 2.7.5 Recovering a variety from its atom structures? 2.7.6 Sahlqvist varieties

3 Binary relations and relation algebra. 3.1 Algebraic logic. 3.2 Binary relations. 3.2.1 Proper relation algebras. 3.2.2 Square proper relation algebras. 3.3 Relation algebras. 3.3.1 Definition of relation algebras. 3.3.2 Peircean law.3.3.3 RA is a completely additive variety of BAOs. 3.3.4 RA is a canonical variety. 3.3.5 RA is a discriminator variety. 3.3.6 Atom structures of relation algebras.3.3.7 Consistent and forbidden triples of atoms. 3.4 Representations of relation algebras. 3.4.1 The class RRA. 3.4.2 Model-theoretic view of representations. 3.4.3 Saturation. 3.4.4 RRA is a canonical variety

4 Examples of relation algebras. 4.1 Set algebras. 4.2 Group relation algebras.4.3 n-variable logic.4.4 Examples. 4.5 The Lyndon algebras.

5 Relativisation and cylindric algebras. 5.1 Relativisation. 5.1.1 Relativised representations. 5.1.2 Non-associative algebras. 5.1.3 Weakly associative algebras. 5.1.4 Semi-associative algebras. 5.1.5 Basic facts about NA, WA, SA. 5.2 Weakly representable relation algebras. 5.3 Cylindric algebras. 5.4 Substitutions in cylindric algebras. 5.4.1 Basic facts about substitutions. 5.4.2 More valid substitution-cylindrification identities. 5.5 Relativised cylindric algebras. 5.6 Relation algebra reducts of cylindric algebras. 5.6.1 Neat reducts and relation algebra reducts.5.6.2 Relation algebra reducts and canonical extensions. 5.6.3 Relation algebra reducts are relation algebras. 5.6.4 The classes SNr(beta)CA(alpha) and SRaCA(n). 5.7 Relation algebra reducts of other cylindric-type algebras

.6 Other approaches to algebras of relations.6.1 Diagonal-free algebras.6.2 Polyadic algebra. 6.3 Pinter's substitution algebras. 6.4 Finitisation problem. 6.4.1 Reducts, subreducts, generalised subreducts. 6.4.2 Expansions. 6.4.3 Special conditions for representability. 6.5 Decidability. 6.6 Amalgamation. 6.7 Technical innovations. 6.8 Applications

II Games. 7 Games and networks. 7.1 Networks. 7.2 Refining networks. 7.3 All weakly associative algebras have relativised representations. 7.4 Games on relation algebra networks. 7.5 Strategies. 7.6 Games and representations of relation algebras. 7.7 Networks for cylindric algebras. 7.8 Games for cylindric algebra networks. 7.9 Games for temporal constraint han...