Games in Algebraic Logic: Axiomatisations and Beyond
Robin Hirsch, Ian Hodkinson · 2007
A classical problem in algebraic logic is to characterise classes of representable algebras. Taking the example of the representable Tarskian relation algebras, we will discuss how games can help with such problems, and how they lead to a deeper study of representability. Introduction A classical problem in algebraic logic is to characterise classes of representable algebras. Taking the example of the representable Tarskian relation algebras, we will discuss how games can help with such problems, and how they lead to a deeper study of representability. We will be able to use the games to help to explain some classical results in this area, and to discuss some more recent ones. 1 Algebras of relations Algebraic formalisation of unary relations began with Boole in the 19th century. It was very successful. The boolean algebra axioms are sound and We would like to thank the referee for helpful comments on a draft of this paper. The second author thanks the organisers for inviting him to speak at the conference. 158 Robin Hirsch and Ian Hodkinson complete: every boolean algebra is isomorphic to a field of sets [Sto036]. De Morgan proposed considering binary (and higher-arity) relations. Peirce and Schroder developed the theory and established hundreds of laws of binary relations (cf., e.g., [Sch895]). [Mad91] has an interesting discussion of the history. But Pierce lamented: The logic of relatives is highly multiform; it is characterized by innumerable immediate conclusions from the same set of premises. . . . The effect of these peculiarities is that this algebra cannot be subjected to hard and fast rules like those of the Boolian calculus; and all that can be done in this place is to give a general idea of the way of working with it. [Pei33, 3.342] In the 1940s, Tarski and his collaborators began to investigate binary relations with modern algebra. Tarski laid down the notion of a field of binary relations, by which he meant a subalgebra of a product of algebras of the form Re(X) = (℘(X ×X),∪, \, ∅, X ×X, IdX , , | ), for some set X, where IdX = {(x, x) : x ∈ X}, R = {(y, x) : (x, y) ∈ R}, R|S = {(x, y) : ∃z((x, z) ∈ R ∧ (z, y) ∈ S)}. He wanted to characterise the algebras isomorphic to fields of binary relations. Such algebras are called representable relation algebras, the class of them is denoted RRA, and the isomorphism is called a representation. It’s easily seen why Tarski wanted to admit subalgebras of Re(X). They are simply obtained by omitting some of the relations in Re(X), but they still contain ∅, X × X, and IdX , and are closed under the operations, so they can certainly be considered as algebras of binary relations. But why products? One could argue that if Xi (i ∈ I) are pairwise disjoint and have union X, the product ∏ i∈I Re(Xi) is isomorphic to the relativisation of Re(X) to the equivalence relation E = ⋃ i∈I(Xi × Xi) on X, defining ‘being in the same Xi’. Relations not contained in E are deleted, and the algebra operations are intersected with E: e.g., a ; b in the relativisation is defined to be c∩E, where c is a ; b evaluated in Re(X). Such a relativisation is some sort of algebra of binary relations, but maybe not the kind one would first think of considering. So perhaps a better answer is probably that under this ‘subalgebras of products’ definition, RRA is a variety — an equationally axiomatised class. This was proved by Tarski in [Tar55]. It follows from Birkhoff’s theorem [Bir35] that RRA is closed under subalgebras, products, and homomorphic images. Games in Algebraic Logic 159 An algebra is simple if it has no non-trivial proper homomorphic images. It can be shown that all simple representable relation algebras are isomorphic to subalgebras of Re(X) for some X: there is no need to consider products. For simplicity of exposition, we will generally restrict our attention here to simple algebras; but most of what we say is either true for arbitrary ones, or can easily be generalised to them. We also generally consider only non-degenerate relation algebras, satisfying 0 6= 1. (When 0 = 1, the algebra has only one element; it is isomorphic to Re(∅) and so is representable. This case is not interesting.) Relation algebras In [Tar41], Tarski proposed axioms to capture RRA. These axioms defined the class RA of ‘relation algebras’. Definition 1. A relation algebra is an algebra of the form A = (A,+,−, 0, 1, 1 , , , ; ) such that • (A,+,−, 0, 1) is a boolean algebra • (A, ; , 1 , ) is a monoid • ‘Peircean law’ (actually discovered by De Morgan): (a ; b) · c 6= 0 ⇐⇒ (a ; c) · b 6= 0 ⇐⇒ a · (c ; b) 6= 0 for all a, b, c ∈ A. As is standard, we use the notation +,−, 0, 1, 1 , , , ; for ‘abstract’ algebra operations corresponding to the ‘concrete’, set-theoretically defined operations ∪, \, ∅, X × X, IdX , , | (respectively) on algebras of binary relations. Considering triangles helps to make the point of the Peircean law clear: