Papers on atom structures

    Atom structures of cylindric algebras and relation algebras

    I. Hodkinson

    Annals Pure Appl. Logic 89 (1997) 117-148.

    For any finite n (at least 3), there are two atomic n-dimensional cylindric algebras with the same atom structure, with one representable, the other, not.

    Hence, the complex algebra of the atom structure of a representable atomic cylindric algebra is not always representable, so that the class RCA_n 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 RCA_n 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.

    This paper is now copyright Elsevier Science BV and I am no longer allowed to make it available on this server for downloading. (I am, however, allowed to send copies to individuals for their own personal use.)

    Atom structures of relation algebras

    I. Hodkinson

    An earlier version of the above, now superseded. 37 pages.

    We study atom structures of relation algebras. We prove that the class of atom structures that arise from representable atomic relation algebras is elementary*, but is not definable in the infinitary logic $L^\omega_{\infty\omega}$ (the fragment of $L_{\infty\omega}$ consisting of formulas using finitely many variables). Hence it is not finitely axiomatisable in first-order logic.

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