Atom structures, completions

Go to home page

Algebraic logic is the study of algebraic theories corresponding to logical systems. Perhaps the oldest case is boolean algebra, which corresponds closely to propositional logic, or the logic of unary relations. The analogous systems for n-ary relations are n-dimensional cylindric algebras. As with boolean algebra, the notion of a cylindric algebra is defined axiomatically. The task is then to show (if possible) that any model of these axioms is isomorphic to a genuine algebra of n-ary relations. This is known as the representation problem: a general model of the axioms is a cylindric algebra, and one isomorphic to a concrete algebra is called a representable cylindric algebra, the isomorphism itself being a representation. The logical analogue of an algebraic representation result is a completeness theorem.

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.

Atom structures of cylindric algebras and relation algebras

I. Hodkinson
Annals of Pure and Applied Logic 89 (1997) 117-148
Publisher's website   Digital Object Identifier (DOI)
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 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.

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, in: `Advances in Modal Logic', Berlin, 1996, M. Kracht, M. de Rijke, H. Wansing, eds.

Strongly representable atom structures of relation algebras

R Hirsch and I Hodkinson
Proc. Amer. Math. Soc. 130 (2002) 1819-1831.
A relation algebra atom structure S is said to be strongly representable if all atomic relation algebras with that atom structure are representable.  This is equivalent to saying that the complex algebra over S is a representable relation algebra.  We show that the class of all strongly representable relation algebra atom structures is not closed under ultraproducts and is therefore not elementary.   This answers a question of Maddux (1982).

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.

Strongly representable atom structures of cylindric algebras

Robin Hirsch and Ian Hodkinson
J. Symbolic Logic 74 (2009) 811-828.
We show that for any finite n at least 3, the class of all strongly representable n-dimensional cylindric algebra atom structures is not closed under ultraproducts and is therefore not elementary.  Our proof is based on the following construction.  From an arbitrary undirected, loop-free graph G, we construct an n-dimensional atom structure E(G), and prove, for infinite G, that E(G) is a strongly representable cylindric algebra atom structure if and only if the chromatic number of G is infinite.  By Erdös's result above, there are graphs Gk (for each finite k) with infinite chromatic number, but having a non-principal ultraproduct G whose chromatic number is just two.  It follows that each E(Gk) is strongly representable but their ultraproduct is not.

On canonicity and completions of weakly representable relation algebras

Ian Hodkinson and Szabolcs Mikulás
J. Symbolic Logic, to appear.
We show that the variety of weakly representable relation algebras is not canonical, nor closed under Monk completions.

Preservation of Sahlqvist fixed point equations in completions of relativized fixed point BAOs

Nick Bezhanishvili and Ian Hodkinson
Algebra Universalis 68 (2012) 43-56.
We define Sahlqvist fixed point equations and relativized fixed point Boolean algebras with operators (relativized fixed point BAOs). We show that every Sahlqvist fixed point equation is preserved under completions of conjugated relativized fixed point BAOs. This extends the result of Givant and Venema (1999) to the setting of relativized fixed point BAOs.

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

Tangled closure algebras

Robert Goldblatt and Ian Hodkinson
Categories and General Algebraic Structures with Applications 7 (2017) 9-31.
The tangled closure of a collection of subsets of a topological space is the largest subset in which each member of the collection is dense. This operation models a logical 'tangle modality' connective, of significance in finite model theory. Here we study an abstract equational algebraic formulation of the operation which generalises the McKinsey-Tarski theory of closure algebras. We show that any dissectable tangled closure algebra, such as the algebra of subsets of any metric space without isolated points, contains copies of every finite tangled closure algebra. We then exhibit an example of a tangled closure algebra that cannot be embedded into any complete tangled closure algebra, so it has no MacNeille completion and no spatial representation.

On the variety generated by completions of representable relation algebras

Ian Hodkinson
Algebra Universalis 81:10 (2020)
Maddux recently defined the variety V generated by the completions of representable relation algebras. In this note, we observe that V is canonical, answering Maddux's problem 1.1(3), and show that the variety of representable relation algebras is not finitely axiomatisable over V .

Non-representable relation algebras from vector spaces

Ian Hodkinson
Australasian Journal of Logic 17 (2020) 82-109
Extending a construction of Andréka, Givant, and Németi (2019), we construct some finite vector spaces and use them to build finite non-representable relation algebras. They are simple, measurable, and persistently finite, and they validate arbitrary finite sets of equations that are valid in the variety RRA of representable relation algebras. It follows that there is no finitely axiomatisable class of relation algebras that contains RRA and validates every equation that is both valid in RRA and preserved by completions of relation algebras. Consequently, the variety generated by the completions of representable relation algebras is not finitely axiomatisable. This answers a question of Maddux (2018).