×

Canonical varieties with no canonical axiomatisation. (English) Zbl 1081.03062

Summary: 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.

MSC:

03G15 Cylindric and polyadic algebras; relation algebras
03C05 Equational classes, universal algebra in model theory
05C15 Coloring of graphs and hypergraphs
05C80 Random graphs (graph-theoretic aspects)
91A43 Games involving graphs
Full Text: DOI

References:

[1] H. Andréka, J. D. Monk, and I. Németi , 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.
[2] G. Birkhoff, On the structure of abstract algebras, Proc. Cambr. Philos. Soc. 31 (1935), 433-454. · Zbl 0013.00105
[3] Patrick Blackburn, Maarten de Rijke, and Yde Venema, Modal logic, Cambridge Tracts in Theoretical Computer Science, vol. 53, Cambridge University Press, Cambridge, 2001. · Zbl 0988.03006
[4] 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. · Zbl 0799.03009 · doi:10.2307/2275108
[5] Alexander Chagrov and Michael Zakharyaschev, Modal logic, Oxford Logic Guides, vol. 35, The Clarendon Press, Oxford University Press, New York, 1997. Oxford Science Publications. · Zbl 0871.03007
[6] L. A. Chagrova, An undecidable problem in correspondence theory, J. Symbolic Logic 56 (1991), no. 4, 1261 – 1272. · Zbl 0737.03018 · doi:10.2307/2275473
[7] Reinhard Diestel, Graph theory, Graduate Texts in Mathematics, vol. 173, Springer-Verlag, New York, 1997. Translated from the 1996 German original. · Zbl 0873.05001
[8] P. Erdős, Graph theory and probability, Canad. J. Math. 11 (1959), 34 – 38. · Zbl 0084.39602 · doi:10.4153/CJM-1959-003-9
[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. · Zbl 0050.14305
[10] George Goguadze, Carla Piazza, and Yde Venema, Simulating polyadic modal logics by monadic ones, J. Symbolic Logic 68 (2003), no. 2, 419 – 462. · Zbl 1059.03008 · doi:10.2178/jsl/1052669058
[11] R. I. Goldblatt, Metamathematics of modal logic, Rep. Math. Logic 6 (1976), 41 – 77. R. I. Goldblatt, Metamathematics of modal logic. II, Rep. Math. Logic 7 (1976), 21 – 52. · Zbl 0356.02016
[12] Robert Goldblatt, Varieties of complex algebras, Ann. Pure Appl. Logic 44 (1989), no. 3, 173 – 242. · Zbl 0722.08005 · doi:10.1016/0168-0072(89)90032-8
[13] R. E. Greenwood and A. M. Gleason, Combinatorial relations and chromatic graphs, Canad. J. Math. 7 (1955), 1 – 7. · Zbl 0064.17901 · doi:10.4153/CJM-1955-001-4
[14] Robin Hirsch and Ian Hodkinson, Step by step — building representations in algebraic logic, J. Symbolic Logic 62 (1997), no. 1, 225 – 279. · Zbl 0879.03018 · doi:10.2307/2275740
[15] 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. · Zbl 1018.03002
[16] Robin Hirsch and Ian Hodkinson, Strongly representable atom structures of relation algebras, Proc. Amer. Math. Soc. 130 (2002), no. 6, 1819 – 1831. · Zbl 1002.03054
[17] Ian Hodkinson, Atom structures of cylindric algebras and relation algebras, Ann. Pure Appl. Logic 89 (1997), no. 2-3, 117 – 148. · Zbl 0898.03025 · doi:10.1016/S0168-0072(97)00015-8
[18] G. E. Hughes, Every world can see a reflexive world, Studia Logica 49 (1990), no. 2, 175 – 181. · Zbl 0719.03010 · doi:10.1007/BF00935597
[19] 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. · Zbl 0794.06012
[20] Bjarni Jónsson, Representation of modular lattices and of relation algebras, Trans. Amer. Math. Soc. 92 (1959), 449 – 464. · Zbl 0105.25302
[21] 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. · Zbl 0760.03018
[22] Bjarni Jónsson and Alfred Tarski, Boolean algebras with operators. I, Amer. J. Math. 73 (1951), 891 – 939. · Zbl 0045.31505 · doi:10.2307/2372123
[23] Marcus Kracht, Tools and techniques in modal logic, Studies in Logic and the Foundations of Mathematics, vol. 142, North-Holland Publishing Co., Amsterdam, 1999. · Zbl 0938.03035
[24] Marcus Kracht and Frank Wolter, Normal monomodal logics can simulate all others, J. Symbolic Logic 64 (1999), no. 1, 99 – 138. · Zbl 0972.03019 · doi:10.2307/2586754
[25] Roger C. Lyndon, The representation of relational algebras, Ann. of Math. (2) 51 (1950), 707 – 729. · Zbl 0037.29302 · doi:10.2307/1969375
[26] Roger C. Lyndon, The representation of relation algebras. II, Ann. of Math. (2) 63 (1956), 294 – 307. · Zbl 0070.24601 · doi:10.2307/1969611
[27] R. C. Lyndon, Relation algebras and projective geometries, Michigan Math. J. 8 (1961), 21 – 28. · Zbl 0105.25303
[28] Roger Maddux, A sequent calculus for relation algebras, Ann. Pure Appl. Logic 25 (1983), no. 1, 73 – 101. · Zbl 0528.03016 · doi:10.1016/0168-0072(83)90055-6
[29] 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. · Zbl 0749.03048
[30] R. McKenzie, The representation of relation algebras, Ph.D. thesis, University of Colorado at Boulder, 1966.
[31] Donald Monk, On representable relation algebras, Michigan Math. J. 11 (1964), 207 – 210. · Zbl 0137.00603
[32] Cecylia Rauszer , 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. · Zbl 0747.03010
[33] M. H. Stone, The theory of representations for Boolean algebras, Trans. Amer. Math. Soc. 40 (1936), no. 1, 37 – 111. · Zbl 0014.34002
[34] Alfred Tarski, On the calculus of relations, J. Symbolic Logic 6 (1941), 73 – 89. · Zbl 0026.24401 · doi:10.2307/2268577
[35] 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). · Zbl 0058.24702
[36] 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.
[37] Y. Venema, Atom structures and Sahlqvist equations, Algebra Universalis 38 (1997), no. 2, 185 – 199. · Zbl 0913.06010 · doi:10.1007/s000120050047
[38] 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. · Zbl 0993.03022
[39] Yde Venema, Atomless varieties, J. Symbolic Logic 68 (2003), no. 2, 607 – 614. · Zbl 1059.03078 · doi:10.2178/jsl/1052669066
[40] Michael Zakharyaschev, Krister Segerberg, Maarten de Rijke, and Heinrich Wansing , 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. · Zbl 0994.03010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.