Canonical varieties with no canonical axiomatisation

Abstract:

We give a simple example of a variety $\mathbf {V}$ of modal algebras that is canonical but cannot be axiomatised by canonical equations or first-order sentences. We then show that the variety $\mathbf {RRA}$ of representable relation algebras, although canonical, has no canonical axiomatisation. Indeed, we show that every axiomatisation of these varieties involves infinitely many non-canonical sentences. Using probabilistic methods of Erdős, we construct an infinite sequence $G_0,G_1,\ldots$ of finite graphs with arbitrarily large chromatic number, such that each $G_n$ is a bounded morphic image of $G_{n+1}$ and has no odd cycles of length at most $n$. The inverse limit of the sequence is a graph with no odd cycles, and hence is 2-colourable. It follows that a modal algebra (respectively, a relation algebra) obtained from the $G_n$ satisfies arbitrarily many axioms from a certain axiomatisation of $\mathbf {V}\ (\mathbf {RRA})$, while its canonical extension satisfies only a bounded number of them. First-order compactness will now establish that $\mathbf {V}\ (\mathbf {RRA})$ has no canonical axiomatisation. A variant of this argument shows that all axiomatisations of these classes have infinitely many non-canonical sentences.