Relation Algebras by Games
North-Holland (Verlag)
978-0-444-50932-1 (ISBN)
- Titel ist leider vergriffen;
keine Neuauflage - Artikel merken
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.
Preface.Foreword.1Introduction.1.1History.1.2To the games.1.3Non-finite axiomatisability.1.4Approximations to representability.1.5Constructions of algebras.1.6Some remarks on methods.1.7Summary of contentsIAlgebras of Relations.2Preliminaries.2.1Foundations.2.2Model theory.2.2.1Syntax.2.2.2Semantics - structures.2.2.3Models, validity.2.2.4Homomorphisms, embeddings, substructures.2.2.5Generating sets.2.2.6Compactness, Lowenheim-Skolem-Tarski theorems.2.2.7Relativisation, interpretations, second-order logic.2.3Boolean algebras.2.3.1Definition and examples.2.3.2Atoms.2.3.3Dense sets.2.3.4Ideals, filters, ultrafilters.2.3.5Representations of boolean algebras.2.3.6Canonical extensions.2.3.7Infinite sums and products.2.3.8Complete representations.2.3.9Completions of boolean algebras.2.4Products and ultraproducts.2.4.1Products.2.4.2Ultraproducts, ultrapowers.2.5Boolean algebras with operators.2.5.1Definitions.2.5.2Homomorphisms and ideals.2.5.3Completely additive and conjugated algebras.2.5.4Completions of BAOs.2.6Varieties and quasi-varieties of BAOs.2.6.1Basic concepts.2.6.2HSP notation and Birkhoff's theorem.2.6.3Subdirect products.2.6.4Discriminator varieties.2.7Aspects of duality for BAOs.2.7.1Atom structures of BAOs.2.7.2Complex algebras.2.7.3Canonical (perfect) extensions of BAOs.2.7.4Axiomatising the atom structures of a variety.2.7.5Recovering a variety from its atom structures?2.7.6Sahlqvist varieties3Binary relations and relation algebra.3.1Algebraic logic.3.2Binary relations.3.2.1Proper relation algebras.3.2.2Square proper relation algebras.3.3Relation algebras.3.3.1Definition of relation algebras.3.3.2Peircean law.3.3.3RA is a completely additive variety of BAOs.3.3.4RA is a canonical variety.3.3.5RA is a discriminator variety.3.3.6Atom structures of relation algebras.3.3.7Consistent and forbidden triples of atoms.3.4Representations of relation algebras.3.4.1The class RRA.3.4.2Model-theoretic view of representations.3.4.3Saturation.3.4.4RRA is a canonical variety4Examples of relation algebras.4.1Set algebras.4.2Group relation algebras.4.3n-variable logic.4.4Examples.4.5The Lyndon algebras.5Relativisation and cylindric algebras.5.1Relativisation.5.1.1Relativised representations.5.1.2Non-associative algebras.5.1.3Weakly associative algebras.5.1.4Semi-associative algebras.5.1.5Basic facts about NA, WA, SA.5.2Weakly representable relation algebras.5.3Cylindric algebras.5.4Substitutions in cylindric algebras.5.4.1Basic facts about substitutions.5.4.2More valid substitution-cylindrification identities.5.5Relativised cylindric algebras.5.6Relation algebra reducts of cylindric algebras.5.6.1Neat reducts and relation algebra reducts.5.6.2Relation algebra reducts and canonical extensions.5.6.3Relation algebra reducts are relation algebras.5.6.4The classes SNr(beta)CA(alpha) and SRaCA(n).5.7Relation algebra reducts of other cylindric-type algebras.6Other approaches to algebras of relations.6.1Diagonal-free algebras.6.2Polyadic algebra.6.3Pinter's substitution algebras.6.4Finitisation problem.6.4.1Reducts, subreducts, generalised subreducts.6.4.2Expansions.6.4.3Special conditions for representability.6.5Decidability.6.6Amalgamation.6.7Technical innovations.6.8ApplicationsIIGames.7Games and networks.7.1Networks.7.2Refining networks.7.3All weakly associative algebras have relativised representations.7.4Games on relation algebra networks.7.5Strategies.7.6Games and representations of relation algebras.7.7Networks for cylindric algebras.7.8Games for cylindric algebra networks.7.9Games for temporal constraint handling.7.10Summary of chapter8Axiomatising representable relation algebras and cylindric algebras.8.1The relation algebra case.8.2An axiomatisation using 'Q-operators'.8.2.1The new function symbols.8.2.2Equations using these function symbols.8.2.3Proof that the equations characterise representability.8.2.4The Jonsson Q-operators.8.3Axiomatising RCA(d) for 3 d omega.8.4Axiomatising RCA(alpha) for infinite alpha 9Axiomatising pseudo-elementary classes.9.1Introduction.9.2Pseudo-elementary classes.9.3Examples.9.4Model theory of pseudo-elementary classes.9.4.1Alternative single-sorted view.9.4.2Equivalence of sorted and unsorted approaches.9.4.3Survey of known results.9.5More explicit axioms.9.5.1The game.9.5.2The game characterises K.9.5.3Short games.9.5.4Axioms for the short games.9.5.5The axioms define K.9.5.6Varieties and equations.9.6Axiomatising pseudo-elementary classes.9.7Generalised Q-operators10Game trees.10.1Trees, and games on them.10.2Strategies.10.3Examples.10.3.1The game Gn(Ia,A).10.4Formulas expressing a winning strategy.10.5Games and non-finite axiomatisability.10.5.1Ultraproducts and games.10.5.2Countable, elementary subalgebra.10.5.3Non-finite axiomatisability11Atomic networks.11.1Introduction.11.2Atomic networks and games.11.3Alternative views of the game.11.3.1Relation to the game Gn of chapter 7.11.3.2Lyndon conditions.11.3.3Game tree view.11.4Atomic games and complete representations.11.5Axioms for complete representability?IIIApproximations.12Relational, cylindric, and hyperbases.12.1Hypernetworks.12.1.1Definition of hypernetworks.12.1.2Comparing and altering hypernetworks.12.2Relational bases and hyperbases.12.2.1Relational bases.12.2.2Hyperbases.12.3Elementary properties of bases.12.3.1Symmetric bases.12.3.2Interpolation in hyperbases.12.3.3From hyperbasis to cylindric algebra.12.3.4Reducing the dimension of a relational basis.12.3.5Reducing the dimension of a hyperbasis.12.4Games.12.4.1Game for relational bases.12.4.2Game for hyperbases.12.4.3Expressing the games by game trees.12.5The variety RA(n).12.6Maddux's bases.12.6.1Relational and cylindric bases.12.6.2Comparing cylindric bases with hyperbases.12.7Cylindric bases and homogeneous representations13Approximations to RRA.13.1Representation theory.13.1.1Relativised semantics for L(A).13.1.2Square relativised representations.13.1.3Flat relativised representations.13.1.4Smooth relativised representations.13.1.5Links between the notions.13.1.6Elementary view.13.2From relativised representations to relation algebra reducts.13.3From reducts to relational bases.13.4From reducts to hyperbases.13.4.1Preliminary results on substitutions.13.4.2Finding the hyperbasis.13.5From bases to relativised representations.13.6From smooth to hyperbasis.13.7Summary and discussion.13.7.1Atomic non-associative algebras.13.7.2Arbitrary non-associative algebras.13.7.3Three-dimensional version of theorem 13.46.13.7.4Finite versions of theorem 13.46 (first part).13.7.5Finite versions of theorem 13.46 (second part).13.8Equational axioms for RA(n) and SRaCA(n)IVConstructing Relation Algebras.14Strongly representable relation algebra atom structures4.14.1Introduction.14.2SRAS is not an elementary class.14.2.1Graphs and colourings.14.2.2The construction.14.2.3SRAS is not elementary.14.3Consequences of the theorem.14.3.1Closure properties.14.3.2Related classes.14.4Maddux's construction.14.4.1The atom structures.14.4.2X(q) is strongly representable15Non-finite axiomatisability of SRaCA(n+1) over SRaCA(n).15.1Outline of chapter.15.2The algebras A(n,r) and C(r).15.3A(n,r) in SRaCA(n).15.4A(n,r) not in SRaCA(n+1).15.5E can win G(m,n+1;r)(A(n,r),L).15.6Non-finite axiomatisability.15.7Proof theory16The rainbow construction for relation algebras.16.1Ehrenfeucht-Fraisse `forth' games.16.1.1The standard Ehrenfeucht-Fraisse game.16.1.2The modified Ehrenfeucht-Fraisse game.16.2The rainbow algebra A(A,B).16.3How A can win G(A(A,B)).16.4How E can win G(A(A,B)).16.5Modifications to the rainbow algebra17Applying the rainbow construction.17.1Non-finite axiomatisability of RRA.17.2Complete representations.17.3There is no n-variable equational axiomatisation of RRA.17.4RA(n+1) is not finitely based over RA(n).17.5Infinite-dimensional bases and relativised representations.17.6Weakly representable relation algebras.17.7Completions.17.7.1The example.17.7.2Corollaries and problemsVDecidability.18Undecidability of the representation problem for finite algebras.18.1Introduction.18.2The tiling problem.18.3The definition of RA(t).18.4Games.18.5Winning E-strategy implies tiling18.6RA(t) in SRaCA(5) implies tiling18.7Tiling implies winning E-strategy18.7.1E's strategy for non-tile edges18.7.2Tile edges18.7.3Attached and linked tile edges18.7.4Inductive conditions T1, T2, T3 on N18.7.5Tiling functions and coordinates for A's tile edges18.7.6Tiling functions for E's new tile edges18.7.7Coordinates for E's new tile edges18.7.8Conditions T1, T2 hold for M18.7.9E's strategy for tile edges, T3, and consistency18.8Conclusion18.9Weak representability is undecidable18.10Undecidability of equational theories19Finite base property19.1Introduction19.2Guarded fragments19.2.1Loosely guarded fragment19.2.2Packed fragment19.2.3Clique-guarded fragment19.2.4Finite model property19.3The finite base property19.4Finite base property for WA19.5Finite algebra on finite base property for RA(n)19.6The finite algebra on finite base property for SRaCA(n)?VIEpilogue20Brief summary20.1Basic definitions20.2Games for representability20.3Relativised representations, bases, reducts20.3.1Relativised representations20.3.2Relational bases and hyperbases20.3.3Relation algebra reducts20.3.4Equivalences between the notions20.4The rainbow construction20.5Atom structures20.6Decidability20.7Summary of relations between the classes20.8Summary of properties of classes21ProblemsBibliographySymbol indexSubject index
| Erscheint lt. Verlag | 15.8.2002 |
|---|---|
| Reihe/Serie | Studies in Logic and the Foundations of Mathematics |
| Sprache | englisch |
| Maße | 156 x 234 mm |
| Gewicht | 1170 g |
| Themenwelt | Mathematik / Informatik ► Mathematik ► Algebra |
| ISBN-10 | 0-444-50932-1 / 0444509321 |
| ISBN-13 | 978-0-444-50932-1 / 9780444509321 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
