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
DOI: https://doi.org/10.1090/S0002-9947-04-03743-2
Published electronically: December 16, 2004
MathSciNet review: 2156722
Full-text PDF

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 Erdos, 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?)

  • 1. H. Andréka, J. D. Monk, and I. Németi (eds.), Algebraic logic, Colloq. Math. Soc. J. Bolyai, vol. 54, North-Holland, Amsterdam, 1991. MR 1153415 (92m:03003)
  • 2. G. Birkhoff, On the structure of abstract algebras, Proc. Cambr. Philos. Soc. 31 (1935), 433-454.
  • 3. P. Blackburn, M. de Rijke and Y. Venema, Modal Logic, Cambridge Tracts in Theoretical Computer Science, vol. 53, Cambridge University Press, Cambridge, UK, 2001. MR 1837791 (2003b:03001)
  • 4. A. Chagrov and M. Zakharyaschev, Undecidability of the disjunction property of propositional logics and other related problems, Journal of Symbolic Logic 58 (1993), 49-82. MR 1242050 (94i:03048)
  • 5. -, Modal logic, Oxford Logic Guides, vol. 35, Clarendon Press, Oxford, 1997. MR 1464942 (98e:03021)
  • 6. L. Chagrova, An undecidable problem in correspondence theory, Journal of Symbolic Logic 56 (1991), 1261-1272. MR 1136455 (93b:03075)
  • 7. R. Diestel, Graph theory, Graduate Texts in Mathematics, vol. 173, Springer-Verlag, Berlin, 1997. MR 1448665
  • 8. P. Erdos, Graph theory and probability, Canadian Journal of Mathematics 11 (1959), 34-38. MR 0102081 (21:876)
  • 9. D. Gale and F. Stewart, Infinite games with perfect information, Contributions to the theory of games II, Annals of mathematical studies 28 (1953), 291-296. MR 0054922 (14:999b)
  • 10. G. Goguadze, C. Piazza, and Y. Venema, Simulating polyadic modal logics by monadic ones, Journal of Symbolic Logic 68 (2003), 419-462. MR 1976585 (2004d:03036)
  • 11. R. Goldblatt, Metamathematics of modal logic, Reports on Math. Logic 6 (1976), 4-77. (Reprinted in: R. Goldblatt, Mathematics of modality, Lecture notes, vol. 43, CSLI Publications, Stanford, 1993). MR 0536321 (58:27331a)
  • 12. -, Varieties of complex algebras, Ann. Pure. Appl. Logic 44 (1989), 173-242. MR 1020344 (91d:08005)
  • 13. R. E. Greenwood and A. M. Gleason, Combinatorial relations and chromatic graphs, Canadian Journal of Mathematics 7 (1955), 1-7. MR 0067467 (16:733g)
  • 14. R. Hirsch and I. Hodkinson, Step by step -- building representations in algebraic logic, Journal of Symbolic Logic 62 (1997), no. 1, 225-279. MR 1450522 (98g:03145)
  • 15. -, Relation algebras by games, Studies in Logic and the Foundations of Mathematics, vol. 147, North-Holland, Amsterdam, 2002. MR 1935083 (2003m:03001)
  • 16. -, Strongly representable atom structures of relation algebras, Proc. Amer. Math. Soc. 130 (2002), 1819-1831. MR 1887031 (2002k:03113)
  • 17. I. Hodkinson, Atom structures of cylindric algebras and relation algebras, Annals of Pure and Applied Logic 89 (1997), 117-148. MR 1490103 (99c:03103)
  • 18. G. Hughes, Every world can see a reflexive world, Studia Logica 49 (1989), 175-181. MR 1094537 (91m:03016)
  • 19. P. Jipsen, Discriminator varieties of boolean algebras with residuated operators, In Rauszer [32], pp. 239-252.MR 1446287 (98b:06019)
  • 20. B. Jónsson, Representation of modular lattices and of relation algebras, Trans. Amer. Math. Soc. 92 (1959), 449-464. MR 0108459 (21:7175)
  • 21. -, The theory of binary relations, In Andréka et al. [1], pp. 245-292. MR 1153429 (93b:03114)
  • 22. B. Jónsson and A. Tarski, Boolean algebras with operators I, American Journal of Mathematics 73 (1951), 891-939. MR 0044502 (13:426c)
  • 23. M. Kracht, Tools and Techniques in Modal Logic, Studies in Logic and the Foundations of Mathematics, vol. 142, North-Holland, Amsterdam, 1999. MR 1707315 (2000h:03041)
  • 24. M. Kracht and F. Wolter, Normal modal logics can simulate all others, Journal of Symbolic Logic 64 (1999), pp. 99-138. MR 1683898 (2000g:03048)
  • 25. R. Lyndon, The representation of relational algebras, Annals of Mathematics 51 (1950), no. 3, 707-729. MR 0037278 (12:237a)
  • 26. -, The representation of relation algebras, II, Annals of Mathematics 63 (1956), no. 2, 294-307. MR 0079570 (18:106f)
  • 27. -, Relation algebras and projective geometries, Michigan Mathematics Journal 8 (1961), 207-210. MR 0122743 (23:A83)
  • 28. R. Maddux, A sequent calculus for relation algebras, Annals of Pure and Applied Logic 25 (1983), 73-101. MR 0722170 (85h:03067)
  • 29. -, Introductory course on relation algebras, finite-dimensional cylindric algebras, and their interconnections, In Andréka et al. [1], pp. 361-392. MR 1153432 (93c:03082)
  • 30. R. McKenzie, The representation of relation algebras, Ph.D. thesis, University of Colorado at Boulder, 1966.
  • 31. J. D. Monk, On representable relation algebras, Michigan Mathematics Journal 11 (1964), 207-210. MR 0172797 (30:3016)
  • 32. C. Rauszer (ed.), Algebraic Methods in Logic and Computer Science, volume 28 of Banach Center Publications, Polish Academy of Sciences, 1993. MR 1446270 (97k:03003)
  • 33. M. Stone, The theory of representations for boolean algebras, Trans. Amer. Math. Soc. 40 (1936), 37-111. MR 1501865
  • 34. A. Tarski, On the calculus of relations, Journal of Symbolic Logic 6 (1941), 73-89. MR 0005280 (3:130e)
  • 35. -, Contributions to the theory of models, III, Koninkl. Nederl. Akad. Wetensch Proc. 58 (= Indag. Math. 17) (1955), 56-64. MR 0066303 (16:554h)
  • 36. S. Thomason, Undecidability of the completeness problem of modal logic, Universal algebra and applications, Banach Center Publications, vol. 9, PNW-Polish Scientific Publishers, Warszawa, 1982, pp. 341-345. MR 0738827 (85e:03051)
  • 37. Y. Venema, Atom structures and Sahlqvist equations, Algebra Universalis 38 (1997), 185-199. MR 1609043 (99g:06019)
  • 38. -, Canonical pseudo-correspondence, In Zakharyaschev et al. [40], pages 439-448. MR 1838261 (2002c:03037)
  • 39. -, Atomless varieties, Journal of Symbolic Logic 68 (2003), 607-614. MR 1976593 (2004g:03108)
  • 40. M. Zakharyaschev, K. Segerberg, M. de Rijke, and H. Wansing (eds.), Advances in Modal Logic, Volume 2, CSLI Publications, Stanford, 2000. MR 1838243

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

DOI: https://doi.org/10.1090/S0002-9947-04-03743-2
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.

American Mathematical Society