Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Canonical varieties with no canonical axiomatisation

Authors: Ian Hodkinson and Yde Venema
Journal: Trans. Amer. Math. Soc. 357 (2005), 4579-4605
MSC (2000): Primary 03G15, 08B99; Secondary 03B45, 03C05, 05C15, 05C38, 05C80, 06E15, 91A43
Published electronically: December 16, 2004
MathSciNet review: 2156722
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 03G15, 08B99, 03B45, 03C05, 05C15, 05C38, 05C80, 06E15, 91A43

Retrieve articles in all journals with MSC (2000): 03G15, 08B99, 03B45, 03C05, 05C15, 05C38, 05C80, 06E15, 91A43

Additional Information

Ian Hodkinson
Affiliation: Department of Computing, Imperial College London, South Kensington Campus, London SW7 2AZ, United Kingdom

Yde Venema
Affiliation: Institute for Logic, Language and Computation, University of Amsterdam, Plantage Muidergracht 24, 1018 TV Amsterdam, The Netherlands

Keywords: Canonical axiomatisation, canonical equation, canonical modal logic, canonical variety, canonicity, chromatic number, game, inverse system, random graph, relation algebra
Received by editor(s): May 23, 2003
Received by editor(s) in revised form: December 19, 2003
Published electronically: December 16, 2004
Additional Notes: The first author’s research was partially supported by grant GR/S19905/01 from the UK EPSRC. He gratefully thanks the members of ILLC of the University of Amsterdam for their warm hospitality during his visit in autumn 2002. The authors thank Robin Hirsch, Agi Kurucz, and Michael Zakharyaschev for valuable conversations, and the referee for helpful comments.
Article copyright: © Copyright 2004 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.