For boolean algebras, the representation problem found a successful solution in work of Stone. Given a boolean algebra A, Stone constructed a certain perfect or canonical extension B of it. B is isomorphic to a concrete algebra of unary relations, and so suffices to represent A, but it can be characterised abstractly up to isomorphism over A by its topological properties. It is complete (closed under arbitrary joins, or sums) and atomic.
For cylindric algebras, the representation problem is not so easily resolved. In 1951, Jónsson and Tarski extended the canonical extension construction to cylindric algebras (and to BAOs: boolean algebras enriched with arbitrary additive operators), but this could not be used to show that a cylindric algebra A was representable because its canonical extension B was only isomorphic to an algebra of unary relations, and not, perhaps, of n-ary ones. However, Monk did show later that the canonical extension of a representable algebra was also representable. For this and other reasons, canonical extensions became an important tool in algebraic logic and also in modal logic.
Another important kind of extension of an algebra A is its completion, which in essence is its smallest complete extension. Although the canonical extension of A is also complete, in general it is not the same as the completion of A. For example, the completion is only atomic when A is. Also, unlike canonical extensions, completions preserve all joins that exist in the original algebra. In 1970, Monk extended the known notion of completion of a boolean algebra to completely additive BAOs, including the cylindric algebras, and showed that the completion of a cylindric algebra is a cylindric algebra. However, the analogue for completions of the preservation of representability by canonical extensions remained open.
Hence, the complex algebra of the atom structure of a representable atomic cylindric algebra is not always representable, so that the class RCAn of representable n-dimensional cylindric algebras is not closed under completions. This answers a question of Monk.
Further, it follows by an argument of Venema that RCAn is not axiomatisable by Sahlqvist equations, nor by equations where negation can only occur in constant terms. This answers a question of Henkin, Monk, and Tarski.
Similar results hold for relation algebras.
We also show that representability of an atomic relation algebra is not determined by its atom structure, by exhibiting two (countable) relation algebras with the same atom structure, one representable, the other, not.
It is therefore of interest to study the class of atom structures C such that any atomic relation algebra with atom structure C is representable. This is the class of all atom structures whose complex algebra is representable. We show that this class includes any finite representable atom structure, any atom structure satisfying the Lyndon conditions, and more. We also prove that the class is not definable by any sentence of $L^\omega_{\infty\omega}$, even modulo the atom structures arising from representable atomic relation algebras. These results do not appear in the paper above.
* This result has been superseded
by one of Venema; see his
paper Atom structures, in: `Advances in
Modal Logic', Berlin, 1996, M. Kracht, M. de Rijke, H. Wansing, eds.
Our proof uses graphs G(r), based on ones discovered by Erdös,
that cannot be coloured with any finite number of colours but whose `small'
induced subgraphs of size <r can be coloured with just two colours.
From these graphs we build atom structures S(r). The fact that G(r)
cannot be coloured finitely is enough to prove that S(r) is strongly representable,
and the fact that small induced subgraphs of each G(r) can be two-coloured
is enough to prove that a non-principal ultraproduct of the S(r) can be
two-coloured, which suffices to show that this ultraproduct is not strongly
representable.