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).
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.
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.
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