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

- H. Andréka, J. D. Monk, and I. Németi (eds.),
*Algebraic logic*, Colloquia Mathematica Societatis János Bolyai, vol. 54, North-Holland Publishing Co., Amsterdam, 1991. Papers from the colloquium held in Budapest, August 8–14, 1988. MR**1153415** - G. Birkhoff,
*On the structure of abstract algebras*, Proc. Cambr. Philos. Soc.**31**(1935), 433–454. - Patrick Blackburn, Maarten de Rijke, and Yde Venema,
*Modal logic*, Cambridge Tracts in Theoretical Computer Science, vol. 53, Cambridge University Press, Cambridge, 2001. MR**1837791**, DOI 10.1017/CBO9781107050884 - Alexander Chagrov and Michael Zakharyaschev,
*The undecidability of the disjunction property of propositional logics and other related problems*, J. Symbolic Logic**58**(1993), no. 3, 967–1002. MR**1242050**, DOI 10.2307/2275108 - Alexander Chagrov and Michael Zakharyaschev,
*Modal logic*, Oxford Logic Guides, vol. 35, The Clarendon Press, Oxford University Press, New York, 1997. Oxford Science Publications. MR**1464942** - L. A. Chagrova,
*An undecidable problem in correspondence theory*, J. Symbolic Logic**56**(1991), no. 4, 1261–1272. MR**1136455**, DOI 10.2307/2275473 - Reinhard Diestel,
*Graph theory*, Graduate Texts in Mathematics, vol. 173, Springer-Verlag, New York, 1997. Translated from the 1996 German original. MR**1448665** - P. Erdős,
*Graph theory and probability*, Canadian J. Math.**11**(1959), 34–38. MR**102081**, DOI 10.4153/CJM-1959-003-9 - David Gale and F. M. Stewart,
*Infinite games with perfect information*, Contributions to the theory of games, vol. 2, Annals of Mathematics Studies, no. 28, Princeton University Press, Princeton, N.J., 1953, pp. 245–266. MR**0054922** - George Goguadze, Carla Piazza, and Yde Venema,
*Simulating polyadic modal logics by monadic ones*, J. Symbolic Logic**68**(2003), no. 2, 419–462. MR**1976585**, DOI 10.2178/jsl/1052669058 - R. I. Goldblatt,
*Metamathematics of modal logic*, Rep. Math. Logic**6**(1976), 41–77. MR**536321** - Robert Goldblatt,
*Varieties of complex algebras*, Ann. Pure Appl. Logic**44**(1989), no. 3, 173–242. MR**1020344**, DOI 10.1016/0168-0072(89)90032-8 - R. E. Greenwood and A. M. Gleason,
*Combinatorial relations and chromatic graphs*, Canadian J. Math.**7**(1955), 1–7. MR**67467**, DOI 10.4153/CJM-1955-001-4 - Robin Hirsch and Ian Hodkinson,
*Step by step—building representations in algebraic logic*, J. Symbolic Logic**62**(1997), no. 1, 225–279. MR**1450522**, DOI 10.2307/2275740 - Robin Hirsch and Ian Hodkinson,
*Relation algebras by games*, Studies in Logic and the Foundations of Mathematics, vol. 147, North-Holland Publishing Co., Amsterdam, 2002. With a foreword by Wilfrid Hodges. MR**1935083** - Robin Hirsch and Ian Hodkinson,
*Strongly representable atom structures of relation algebras*, Proc. Amer. Math. Soc.**130**(2002), no. 6, 1819–1831. MR**1887031**, DOI 10.1090/S0002-9939-01-06232-3 - Ian Hodkinson,
*Atom structures of cylindric algebras and relation algebras*, Ann. Pure Appl. Logic**89**(1997), no. 2-3, 117–148. MR**1490103**, DOI 10.1016/S0168-0072(97)00015-8 - G. E. Hughes,
*Every world can see a reflexive world*, Studia Logica**49**(1990), no. 2, 175–181. MR**1094537**, DOI 10.1007/BF00935597 - Peter Jipsen,
*Discriminator varieties of Boolean algebras with residuated operators*, Algebraic methods in logic and in computer science (Warsaw, 1991) Banach Center Publ., vol. 28, Polish Acad. Sci. Inst. Math., Warsaw, 1993, pp. 239–252. MR**1446287** - Bjarni Jónsson,
*Representation of modular lattices and of relation algebras*, Trans. Amer. Math. Soc.**92**(1959), 449–464. MR**108459**, DOI 10.1090/S0002-9947-1959-0108459-5 - Bjarni Jónsson,
*The theory of binary relations*, Algebraic logic (Budapest, 1988) Colloq. Math. Soc. János Bolyai, vol. 54, North-Holland, Amsterdam, 1991, pp. 245–292. MR**1153429** - Bjarni Jónsson and Alfred Tarski,
*Boolean algebras with operators. I*, Amer. J. Math.**73**(1951), 891–939. MR**44502**, DOI 10.2307/2372123 - Marcus Kracht,
*Tools and techniques in modal logic*, Studies in Logic and the Foundations of Mathematics, vol. 142, North-Holland Publishing Co., Amsterdam, 1999. MR**1707315** - Marcus Kracht and Frank Wolter,
*Normal monomodal logics can simulate all others*, J. Symbolic Logic**64**(1999), no. 1, 99–138. MR**1683898**, DOI 10.2307/2586754 - Roger C. Lyndon,
*The representation of relational algebras*, Ann. of Math. (2)**51**(1950), 707–729. MR**37278**, DOI 10.2307/1969375 - Roger C. Lyndon,
*The representation of relation algebras. II*, Ann. of Math. (2)**63**(1956), 294–307. MR**79570**, DOI 10.2307/1969611 - R. C. Lyndon,
*Relation algebras and projective geometries*, Michigan Math. J.**8**(1961), 21–28. MR**122743**, DOI 10.1307/mmj/1028998510 - Roger Maddux,
*A sequent calculus for relation algebras*, Ann. Pure Appl. Logic**25**(1983), no. 1, 73–101. MR**722170**, DOI 10.1016/0168-0072(83)90055-6 - Roger D. Maddux,
*Introductory course on relation algebras, finite-dimensional cylindric algebras, and their interconnections*, Algebraic logic (Budapest, 1988) Colloq. Math. Soc. János Bolyai, vol. 54, North-Holland, Amsterdam, 1991, pp. 361–392. MR**1153432** - R. McKenzie,
*The representation of relation algebras*, Ph.D. thesis, University of Colorado at Boulder, 1966. - Donald Monk,
*On representable relation algebras*, Michigan Math. J.**11**(1964), 207–210. MR**172797** - Cecylia Rauszer (ed.),
*Algebraic methods in logic and in computer science*, Banach Center Publications, vol. 28, Polish Academy of Sciences, Institute of Mathematics, Warsaw, 1993. Papers from the 38th Semester held in Warsaw, September 15–December 15, 1991. MR**1446270** - M. H. Stone,
*The theory of representations for Boolean algebras*, Trans. Amer. Math. Soc.**40**(1936), no. 1, 37–111. MR**1501865**, DOI 10.1090/S0002-9947-1936-1501865-8 - Alfred Tarski,
*On the calculus of relations*, J. Symbolic Logic**6**(1941), 73–89. MR**5280**, DOI 10.2307/2268577 - Alfred Tarski,
*Contributions to the theory of models. III*, Nederl. Akad. Wetensch. Proc. Ser. A.**58**(1955), 56–64 = Indagationes Math. 17, 56–64 (1955). MR**0066303**, DOI 10.1016/S1385-7258(55)50009-6 - S. K. Thomason,
*Undecidability of the completeness problem of modal logic*, Universal algebra and applications (Warsaw, 1978) Banach Center Publ., vol. 9, PWN, Warsaw, 1982, pp. 341–345. MR**738827** - Y. Venema,
*Atom structures and Sahlqvist equations*, Algebra Universalis**38**(1997), no. 2, 185–199. MR**1609043**, DOI 10.1007/s000120050047 - Yde Venema,
*Canonical pseudo-correspondence*, Advances in modal logic, Vol. 2 (Uppsala, 1998) CSLI Lecture Notes, vol. 119, CSLI Publ., Stanford, CA, 2001, pp. 421–430. MR**1838261** - Yde Venema,
*Atomless varieties*, J. Symbolic Logic**68**(2003), no. 2, 607–614. MR**1976593**, DOI 10.2178/jsl/1052669066 - Michael Zakharyaschev, Krister Segerberg, Maarten de Rijke, and Heinrich Wansing (eds.),
*Advances in modal logic. Vol. 2*, CSLI Lecture Notes, vol. 119, CSLI Publications, Stanford, CA, 2001. Selected papers from the 2nd International Workshop (AiML’98) held at Uppsala University, Uppsala, October 16–18, 1998. MR**1838243**

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