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