Description 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.
Contents 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 handling.
7.10 Summary of chapter
8 Axiomatising
representable relation algebras and cylindric algebras.
8.1 The relation algebra case.
8.2 An axiomatisation using 'Q-operators'.
8.2.1 The new function symbols.
8.2.2 Equations using these function symbols.
8.2.3 Proof that the equations characterise
representability.
8.2.4 The Jonsson Q-operators.
8.3 Axiomatising RCA(d) for 3 d omega.
8.4 Axiomatising RCA(alpha) for
infinite alpha
9 Axiomatising pseudo-elementary classes.
9.1 Introduction.
9.2 Pseudo-elementary classes.
9.3 Examples.
9.4 Model theory of pseudo-elementary classes.
9.4.1 Alternative single-sorted view.
9.4.2 Equivalence of sorted and unsorted
approaches.
9.4.3 Survey of known results.
9.5 More explicit axioms.
9.5.1 The game.
9.5.2 The game characterises
K.
9.5.3 Short games.
9.5.4 Axioms for the short games.
9.5.5 The axioms define K.
9.5.6 Varieties and equations.
9.6 Axiomatising pseudo-elementary classes.
9.7 Generalised Q-operators
10 Game trees.
10.1 Trees, and games on them.
10.2 Strategies.
10.3 Examples.
10.3.1 The game Gn(Ia,A).
10.4 Formulas expressing a winning strategy.
10.5 Games
and non-finite axiomatisability.
10.5.1 Ultraproducts and games.
10.5.2 Countable, elementary subalgebra.
10.5.3 Non-finite
axiomatisability
11 Atomic networks.
11.1 Introduction.
11.2 Atomic networks and games.
11.3 Alternative views of
the game.
11.3.1 Relation to the game Gn of chapter 7.
11.3.2 Lyndon conditions.
11.3.3 Game tree view.
11.4 Atomic
games and complete representations.
11.5 Axioms for complete representability?
III Approximations.
12 Relational, cylindric,
and hyperbases.
12.1 Hypernetworks.
12.1.1 Definition of hypernetworks.
12.1.2 Comparing and altering hypernetworks.
12.2 Relational bases and hyperbases.
12.2.1 Relational bases.
12.2.2 Hyperbases.
12.3 Elementary properties of bases.
12.3.1 Symmetric bases.
12.3.2 Interpolation in hyperbases.
12.3.3 From hyperbasis to cylindric algebra.
12.3.4 Reducing
the dimension of a relational basis.
12.3.5 Reducing the dimension of a hyperbasis.
12.4 Games.
12.4.1 Game for relational
bases.
12.4.2 Game for hyperbases.
12.4.3 Expressing the games by game trees.
12.5 The variety RA(n).
12.6 Maddux's
bases.
12.6.1 Relational and cylindric bases.
12.6.2 Comparing cylindric bases with hyperbases.
12.7 Cylindric bases and
homogeneous representations
13 Approximations to RRA.
13.1 Representation theory.
13.1.1 Relativised semantics for L(A).
13.1.2 Square relativised representations.
13.1.3 Flat relativised representations.
13.1.4 Smooth relativised representations.
13.1.5 Links between the notions.
13.1.6 Elementary view.
13.2 From relativised representations to relation algebra reducts.
13.3 From reducts to relational bases.
13.4 From reducts to hyperbases.
13.4.1 Preliminary results on substitutions.
13.4.2 Finding the hyperbasis.
13.5 From bases to relativised representations.
13.6 From smooth to hyperbasis.
13.7 Summary
and discussion.
13.7.1 Atomic non-associative algebras.
13.7.2 Arbitrary non-associative algebras.
13.7.3 Three-dimensional
version of theorem 13.46.
13.7.4 Finite versions of theorem 13.46 (first part).
13.7.5 Finite versions of theorem 13.46 (second
part).
13.8 Equational axioms for RA(n) and SRaCA(n)
IV Constructing Relation Algebras.
14 Strongly representable relation
algebra atom structures 4.
14.1 Introduction.
14.2 SRAS is not an elementary class.
14.2.1 Graphs and colourings.
14.2.2 The construction.
14.2.3 SRAS is not elementary.
14.3 Consequences of the theorem.
14.3.1 Closure properties.
14.3.2 Related classes.
14.4 Maddux's construction.
14.4.1 The atom structures.
14.4.2 X(q) is strongly representable
15 Non-finite axiomatisability of SRaCA(n+1) over SRaCA(n).
15.1 Outline of chapter.
15.2 The algebras A(n,r) and C(r).
15.3 A(n,r) in SRaCA(n).
15.4 A(n,r) not in SRaCA(n+1).
15.5 E can win G(m,n+1;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
Books and book related electronic products are priced in US dollars (USD), euro (EUR), and Great Britain Pounds (GBP). USD prices apply to the Americas and Asia Pacific. EUR prices apply in Europe and the Middle East. GBP prices apply to the UK and all other countries.
Home | Elsevier Sites | Privacy Policy | Terms and Conditions | Feedback | Site Map | A Reed Elsevier Company