Relation Algebras by Games (eBook)

Robin Hirsch, Ian Hodkinson (Autoren)

eBook Download: PDF

2002 | 1. Auflage
710 Seiten
Elsevier Science (Verlag)
978-0-08-054045-0 (ISBN)

Infos

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.

Inhalt

Cover 1
Contents 10
Preface 6
Foreword 8
Chapter 1. Introduction 20
1.1 History 20
1.2 To the games 28
1.3 Non-finite axiomatisability 32
1.4 Approximations to representability 34
1.5 Constructions of algebras 36
1.6 Some remarks on methods 38
1.7 Summary of contents 39
Part I: Algebras of Relations 42
Chapter 2. Preliminaries 44
2.1 Foundations 44
2.2 Model theory 50
2.3 Boolean algebras 57
2.4 Products and ultraproducts 75
2.5 Boolean algebras with operators 79
2.6 Varieties and quasi-varieties of BAOs 86
2.7 Aspects of duality for BAOs 96
Chapter 3. Binary relations and relation algebra 118
3.1 Algebraic logic 118
3.2 Binary relations 120
3.3 Relation algebras 124
3.4 Representations of relation algebras 137
Chapter 4. Examples of relation algebras 152
4.1 Set algebras 152
4.2 Group relation algebras 153
4.3 n-variable logic 155
4.4 Examples 156
4.5 The Lyndon algebras 163
Chapter 5. Relativisation and cylindric algebras 170
5.1 Relativisation 171
5.2 Weakly representable relation algebras 182
5.3 Cylindric algebras 185
5.4 Substitutions in cylindric algebras 189
5.5 Relativised cylindric algebras 199
5.6 Relation algebra reducts of cylindric algebras 205
5.7 Relation algebra reducts of other cylindric-type algebras 213
Chapter 6. Other approaches to algebras of relations 218
6.1 Diagonal-free algebras 218
6.2 Polyadic algebra 220
6.3 Pinter's substitution algebras 223
6.4 Finitisation problem 224
6.5 Decidability 229
6.6 Amalgamation 229
6.7 Technical innovations 230
6.8 Applications 231
Part II: Games 232
Chapter 7. Games and networks 236
7.1 Networks 236
7.2 Refining networks 241
7.3 All weakly associative algebras have relativised representations 244
7.4 Games on relation algebra networks 252
7.5 Strategies 255
7.6 Games and representations of relation algebras 258
7.7 Networks for cylindric algebras 267
7.8 Games for cylindric algebra networks 268
7.9 Games for temporal constraint handling 271
7.10 Summary of chapter 277
Chapter 8. Axiomatising representable relation algebras and cylindric algebras 280
8.1 The relation algebra case 281
8.2 An axiomatisation using 'Q-operators' 283
8.3 Axiomatising RCAd for 3 < = d <
8.4 Axiomatising RCA a for infinite a 290
Chapter 9. Axiomatising pseudo-elementary classes 292
9.1 Introduction 292
9.2 Pseudo-elementary classes 296
9.3 Examples 297
9.4 Model theory of pseudo-elementary classes 303
9.5 More explicit axioms 311
9.6 Axiomatising pseudo-elementary classes 321
9.7 Generalised Q-operators 325
Chapter 10. Game trees 328
10.1 Trees, and games on them 329
10.2 Strategies 333
10.3 Examples 337
10.4 Formulas expressing a winning strategy 340
10.5 Games and non-finite axiomatisability 344
Chapter 11. Atomic networks 354
11.1 Introduction 354
11.2 Atomic networks and games 357
11.3 Alternative views of the game 359
11.4 Atomic games and complete representations 366
11.5 Axioms for complete representability? 368
Part III: Approximations 372
Chapter 12. Relational, cylindric, and hyperbases 382
12.1 Hypernetworks 382
12.2 Relational bases and hyperbases 385
12.3 Elementary properties of bases 388
12.4 Games 395
12.5 The variety RAn 403
12.6 Maddux's bases 407
12.7 Cylindric bases and homogeneous representations 414
Chapter 13. Approximations to RRA 418
13.1 Representation theory 418
13.2 From relativised representations to relation algebra reducts 427
13.3 From reducts to relational bases 431
13.4 From reducts to hyperbases 435
13.5 From bases to relativised representations 440
13.6 From smooth to hyperbasis 446
13.7 Summary and discussion 447
13.8 Equational axioms for RAn and SRaCAn 456
Part IV: Constructing Relation Algebras 458
Chapter 14. Strongly representable relation algebra atom structures 464
14.1 Introduction 464
14.2 SRAS is not an elementary class 466
14.3 Consequences of the theorem 473
14.4 Maddux's construction 478
Chapter 15. Non-finite axiomatisability of SRaCAn+1 over SRaCAn 482
15.1 Outline of chapter 482
15.2 The algebras u(n,r) and Cr 485
15.3 u(n,r) e SRaCAn 486
15.4 u(n,r) e/ SRaCAn+1 488
15.5 3 can win Gr m,n+1 (u(n, r), .) 495
15.6 Non-finite axiomatisability 503
15.7 Proof theory 505
Chapter 16. The rainbow construction for relation algebras 510
16.1 Ehrenfeucht-Fraissé ‘forth’ games 511
16.2 The rainbow algebra AA,B 513
16.3 How V can win G(AA,8) 515
16.4 How 3 can win G(AA,8) 519
16.5 Modifications to the rainbow algebra 528
Chapter 17. Applying the rainbow construction 532
17.1 Non-finite axiomatisability of RRA 533
17.2 Complete representations 534
17.3 There is no n-variable equational axiomatisation of RRA 536
17.4 RAn+l is not finitely based over RAn 539
17.5 Infinite-dimensional bases and relativised representations 544
17.6 Weakly representable relation algebras 547
17.7 Completions 550
Part V: Decidability 556
Chapter 18. Undecidability of the representation problem for finite algebras 558
18.1 Introduction 558
18.2 The tiling problem 560
18.3 The definition of RA(t) 562
18.4 Games 565
18.5 Winning 3-strategy implies tiling 565
18.6 RA(t) e SRtCA5 implies tiling 567
18.7 Tiling implies winning 3-strategy 570
18.8 Conclusion 588
18.9 Weak representability is undecidable 590
18.10 Undecidability of equational theories 596
Chapter 19. Finite base property 600
19.1 Introduction 600
19.2 Guarded fragments 605
19.3 The finite base property 609
19.4 Finite base property for WA 614
19.5 Finite algebra on finite base property for RAn 620
19.6 The finite algebra on finite base property for SRaCAn? 621
Part VI: Epilogue 626
Chapter 20. Brief summary 628
20.1 Basic definitions 628
20.2 Games for representability 630
20.3 Relativised representations, bases, reducts 632
20.4 The rainbow construction 637
20.5 Atom structures 639
20.6 Decidability 640
20.7 Summary of relations between the classes 640
20.8 Summary of properties of classes 641
Chapter 21. Problems 644
Bibliography 648
Symbol index 674
Subject index 686

Textauszug

Chapter 2

Preliminaries

Robin Hirsch    Department of Computer Science, University College Gower Street, London, WCIE 6BT United Kingdom

Ian Hodkinson    Department of Computing, Imperial College 180 Queen's Gate, London, SW7 2BZ United Kingdom

We do not want to assume any previous knowledge about algebraic logic, although a certain familiarity with mathematical concepts and notation is needed, and a background in formal logic will help. We have included this chapter in order to cover notions from outside algebraic logic that will be useful in later chapters. Most of them are from universal algebra — equational varieties and Birkhoff’s theorem, subdirectly irreducibles, conjugates, and discriminators. We also cover boolean algebras with operators and associated constructions such as atom structures, canonical embedding algebras, and completions. Some model theory will also be used in the book, and most of the later chapters are heavily influenced by model-theoretic ideas, but we use few specific model-theoretic theorems, so we confine ourselves here to the basic concepts and introduce the remaining ones, such as saturation, at the time of use. The chapter is intended to be selective and expository, and not a full or rigorous development of either universal algebra or model theory. References to universal algebra, which has historically been closely related to algebraic logic, include [Grät79, BurSan81, McKeMcN+87]. Standard texts on model theory, not so often seen as related to algebraic logic, include [ChaKei90, Hod93],

The reader who wishes to get straight into algebraic logic and the representation theory might be advised to run quickly through this preliminary chapter, or perhaps skip it altogether, and then refer back to it as the need arises.

2.1 Foundations

We assume a basic knowledge of sets, relations and functions, and other basic mathematical notions. In particular, the following concepts and notations will arise. Many of them are entire fields with many books devoted to them; we only want to give a handy reference for items used later.

Iff We often use ‘iff’ to abbreviate ‘if and only if’; this useful word was invented by Halmos. ‘⇔’ means the same; ‘⇒’ means ‘implies’, and ‘⇐’ means ‘is implied by’.

Sets We work implicitly in ZFC — Zermelo-Fraenkel set theory with the axiom of choice. For sets X,Y,X × Y denotes the set of all ordered pairs (x,y) (x ∈ X,y ∈ Y). (Formally, (x,y) = {{x}, {x,y}}.) For a whole number n ≥ 1, Xn denotes

×X×⋯×X;⏞ntimes

we think of this as the set of sequences {(x0, …, xn − 1): x0, …,xn − 1 ∈ X}. For a set ∪X and x∈Xx denote {y: y ∈ x for some x ∈ X}. For finite sets X, we simplify the notation, so that x∪ y denotes xy, etc. Similar conventions apply to ∩ when X ≠ Ø. The disjoint union of sets Xi (i ∈ I) is formally defined to be Xi×i:i∈I, though normally we think of it as the union of pairwise disjoint copies of the Xi. In the text, ⊆ will denote set or class inclusion (see any standard text on set theory for information about classes), or substructure or subalgebra (see section 2.2.4), as appropriate. ⊂ will be used to indicate that the inclusion is proper: X ⊂ Y iff X ⊆ Y and ≠Y.℘X denotes the power set (set of all subsets) of X. We write X / Y for the set {x ∈ X: x ∉ Y}.

Binary relations These are the main topic of the book; here we confine ourselves to their basic aspects. A binary relation R on a set X is a subset of X × X. Generally, X will be non-empty, but sometimes it is useful to allow empty X. We write R(x,y) or xRy as alternative notations for {x,y) ∈ R. The domain and range of R are {x: (x,y)’) ∈ R} and {y: (x,y) ∈ R}, respectively. R is said to be

reflexive, if xRx for all x ∈ X,

irreflexive, if xRx for no x ∈ X,

symmetric, if xRy implies yRx,

antisymmetric, if xRy and yRx imply x = y,

transitive, if xRy and yRz imply xRz.

The reflexive (or transitive) closure of R (with respect to X) is the smallest reflexive (respectively, transitive) binary relation on X containing R. The reflexive closure of R with respect to X is R ∪ {(x.x): x ∈ X}. Its transitive closure is the set of all pairs (x,y) such that there exist finite n > 0 and x0,…, xn ∈ X with x0 = x, xn = y, x0Rx1, x1Rx2, …, xn − 1 Rxn. That is, it is the intersection of all transitive relations on X containing R — or, the smallest such relation. Similarly, the reflexive transitive closure of R with respect to X is the smallest reflexive transitive relation containing R.

Equivalence relations An equivalence relation on a set X is a reflexive, symmetric, transitive binary relation E on X. An equivalence class of E is a subset of X of the form /E=defy∈X:yEx for some x ∈ X. We write X/E for the set of equivalence classes of E. The equivalence classes of E partition X: i.e., every element of X lies in exactly one of them.

The equivalence relation generated by a binary relation R on X is the smallest equivalence relation on X that contains R.

Orderings A pre-order is a set X endowed with a reflexive transitive binary relation ≤. A partial order or partial ordering is an antisymmetric pre-order. A partial order (X, ≤) is well-founded if every non-empty subset Y ⊆ X has a minimal element (there is y ∈ Y such that if z ∈ Y and z ≤ y then z = y), or equivalently, there is no infinite descending sequence of distinct elements x0 ≥ x1 ≥  in X. (X, ≤) is a linear order if x ≤ y or y ≤ x for all x,y ∈ X, and a well-order if it is well-founded and linear.

An irreflexive partial order on X is an irreflexive binary relation on X, usually written <, whose reflexive closure is a partial order on X. Similar definitions are made for irreflexive linear order, etc. If (X, ≤) is a given partial order, x < y denotes the binary relation on X given by x < y iff x ≤ y and x ≠ y. Then (X, <) is an irreflexive partial order. Conversely, for an irreflexive partial order (X, <), x < y denotes the binary relation on X given by x ≤ y iff x < y or x = y; then, (X, ≤) is a partial order.

Two linear orders are said to be...

Produkt-Details

• Erscheint lt. Verlag: 15.8.2002
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik ► Algebra
• Themenwelt: Mathematik / Informatik ► Mathematik ► Logik / Mengenlehre
• Themenwelt: Technik
• ISBN-10: 0-08-054045-7 / 0080540457
• ISBN-13: 978-0-08-054045-0 / 9780080540450