Games, axiomatisations

Go to home page

Games in algebraic logic

R. Hirsch and I. Hodkinson
Proc. 11th Amsterdam Colloquium, P Dekker, M Stokhof, Y Venema (eds), ILLC/Department of Philosophy, Universiteit van Amsterdam, 1997, pp. 7-12
A gentle survey of some of our work in this area.

Synthesising axioms by games

R. Hirsch and I. Hodkinson
In JFAK - a CD-ROM of essays dedicated to Johan van Benthem on the occasion of his 50th birthday.

This is a short account of (some of) the history of the axiomatisation problem in algebraic logic, together with an outline of a general method of axiomatising pseudo-elementary classes.  This covers probably all the axiomatisations given in the papers below, using games to obtain explicit axioms.  This is a discursive essay not intended as a technical paper; there are no formal proofs.

Step by step --- building representations in algebraic logic

R. Hirsch and I. Hodkinson
J. Symbolic Logic 62 (1997) 225-279
We consider the problem of finding and classifying representations in algebraic logic. This is approached by letting two players build a representation using a game. Homogeneous and universal representations are characterised according to the outcome of certain games. The 'Lyndon conditions' defining representable relation algebras (for the finite case) and a similar schema for cylindric algebras are derived. Finite relation algebras with homogeneous representations are characterised by first order formulas. Equivalence games are defined, and are used to establish whether an algebra is $\omega$-categorical. We have a simple proof that the perfect extension of a representable relation algebra is completely representable. Another two-player game is used to derive equational axiomatisations for the classes of all representable relation algebras and representable cylindric algebras.

Axiomatising various classes of relation and cylindric algebras

R. Hirsch and I. Hodkinson
Logic Journal of the IGPL vol. 5 no. 2 (1997) pp 209--229
We outline a simple approach to axiomatising the class of representable relation algebras, using games. We discuss generalisations of the method to cylindric algebras, homogeneous and complete representations, and atom structures of relation algebras.

Axiomatizing complex algebras by games

Ian  Hodkinson, Szabolcs Mikulás, and Yde Venema
Algebra Universalis, 46 (2001) 455-478
ILLC Prepublication series no. PP-2000-01
Given a variety V we provide an axiomatization P(V) of the class SCmV of complex algebras of algebras in V.  P(V) can be obtained effectively from the axiomatization of V; in fact, if this axiomatization is recursively enumerable, then P(V) is recursive.

Canonical varieties with no canonical axiomatisation

Ian Hodkinson and Yde Venema
Trans. Amer. Math. Soc. 357 (2005), 4579-4605.
We give a simple example of a variety V of modal algebras that is canonical but cannot be axiomatised by canonical equations or first-order sentences.  We then show that the variety RRA of representable relation algebras, although canonical, has no canonical axiomatisation.  Indeed, we show that every axiomatisation of these varieties involves infinitely many non-canonical sentences.

Using probabilistic methods of Erdös, we construct an infinite sequence G0, G1, ... of finite graphs with arbitrarily large chromatic number, such that each Gn is a bounded morphic image of Gn+1 and has no odd cycles of length at most n. The inverse limit of the sequence is a graph with no odd cycles and hence is 2-colourable. It follows that a modal algebra (respectively, a relation algebra) obtained from the Gn satisfies arbitrarily many axioms from a certain axiomatisation of V (RRA), while its canonical extension satisfies only a bounded number of them. It now follows by compactness that V (RRA) has no canonical axiomatisation. A variant of this argument shows that there is no axiomatisation using finitely many non-canonical sentences.

Survey talk on this paper.

Bare canonicity of representable cylindric and polyadic algebras

Jannis Bulian and Ian Hodkinson
Ann. Pure Appl. Logic 164 (2013) 884-906, doi 10.1016/j.apal.2013.04.002.
We show that for finite n at least 3, every first-order axiomatisation of the varieties of representable n-dimensional cylindric algebras, diagonal-free cylindric algebras, polyadic algebras, and polyadic equality algebras contains an infinite number of non-canonical formulas. We also show that the class of structures for each of these varieties is non-elementary. The proofs employ algebras derived from random graphs.