Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society, the Transactions of the American Mathematical Society (TRAN) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Transactions of the American Mathematical Society is 1.43.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Canonical varieties with no canonical axiomatisation
HTML articles powered by AMS MathViewer

by Ian Hodkinson and Yde Venema PDF
Trans. Amer. Math. Soc. 357 (2005), 4579-4605 Request permission

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
Similar Articles
Additional Information
  • Ian Hodkinson
  • Affiliation: Department of Computing, Imperial College London, South Kensington Campus, London SW7 2AZ, United Kingdom
  • Email: imh@doc.ic.ac.uk
  • Yde Venema
  • Affiliation: Institute for Logic, Language and Computation, University of Amsterdam, Plantage Muidergracht 24, 1018 TV Amsterdam, The Netherlands
  • Email: yde@science.uva.nl
  • 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.
  • © Copyright 2004 American Mathematical Society
    The copyright for this article reverts to public domain 28 years after publication.
  • Journal: Trans. Amer. Math. Soc. 357 (2005), 4579-4605
  • MSC (2000): Primary 03G15, 08B99; Secondary 03B45, 03C05, 05C15, 05C38, 05C80, 06E15, 91A43
  • DOI: https://doi.org/10.1090/S0002-9947-04-03743-2
  • MathSciNet review: 2156722