Complete representatations

Go to home page

A complete representation of an algebra is one respecting infinitary meets and joins. Clearly, any representation of a finite algebra is complete. But this is not true for arbitrary algebras. The first example of a representable relation algebra with no complete representation appeared in a paper of Lyndon (1950), where it was (incorrectly) claimed not to be representable at all, because it did not satisfy certain first-order axioms a.k.a. the Lyndon conditions. Maddux constructed further examples in his PhD dissertation (1978).

Complete representations in algebraic logic

R. Hirsch and I. Hodkinson
J. Symbolic Logic 62 (1997) 816 - 847
A boolean algebra is shown to be completely representable if and only if it is atomic, whereas it is shown that neither the class of completely representable relation algebras nor the class of completely representable cylindric algebras of any fixed dimension >2 are elementary.

It is also shown that an atomic relation algebra satisfies the `Lyndon conditions' if and only if it is elementarily equivalent to a relation algebra with a complete representation.

A construction of cylindric and polyadic algebras from atomic relation algebras

Ian Hodkinson
Algebra Universalis, 2012, doi 10.1007/s00012-012-0202-3.
Abstract Given a simple atomic relation algebra A and a finite n at least 3, we construct effectively an atomic n-dimensional polyadic equality-type algebra P such that for any subsignature L of the signature of P that contains the boolean operations and cylindrifications, the L-reduct of P is completely representable if and only if A is completely representable. If A is finite then so is P.
It follows that there is no algorithm to determine whether a finite n-dimensional cylindric algebra, diagonal-free cylindric algebra, polyadic algebra, or polyadic equality algebra is representable (for diagonal-free algebras this was known). We also obtain a new proof that the classes of completely representable n-dimensional algebras of these types are non-elementary, a result that remains true for infinite dimensions if the diagonals are present, and also for infinite-dimensional diagonal-free cylindric algebras.

Completions and complete representations

Robin Hirsch and Ian Hodkinson
In: Cylindric-like Algebras and Algebraic Logic
H. Andréka, M. Ferenczi, I. Németi (eds.)
Bolyai Society Mathematical Studies, Vol. 22 (2013) pp. 61-89. ISBN 978-3-642-35024-5
doi 10.1007/978-3-642-35025-2_4