Canonical varieties with no canonical axiomatisation
Ian Hodkinson, Yde Venema · Transactions of the American Mathematical Society · 2004
We give a simple example of a variety V \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 R R A \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 , … G_0,G_1,\ldots of finite graphs with arbitrarily large chromatic number, such that each G n G_n is a bounded morphic image of G n + 1 G_{n+1} and has no odd cycles of length at most n 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 G_n satisfies arbitrarily many axioms from a certain axiomatisation of V ( R R A ) \mathbf {V}\ (\mathbf {RRA}) , while its canonical extension satisfies only a bounded number of them. First-order compactness will now establish that V ( R R A ) \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.