Strongly representable atom structures of relation algebras
HTML articles powered by AMS MathViewer
- by Robin Hirsch and Ian Hodkinson PDF
- Proc. Amer. Math. Soc. 130 (2002), 1819-1831 Request permission
Abstract:
A relation algebra atom structure $\alpha$ is said to be strongly representable if all atomic relation algebras with that atom structure are representable. This is equivalent to saying that the complex algebra $\mathfrak {Cm} \alpha$ is a representable relation algebra. We show that the class of all strongly representable relation algebra atom structures is not closed under ultraproducts and is therefore not elementary. This answers a question of Maddux (1982). Our proof is based on the following construction. From an arbitrary undirected, loop-free graph $\Gamma$, we construct a relation algebra atom structure $\alpha (\Gamma )$ and prove, for infinite $\Gamma$, that $\alpha (\Gamma )$ is strongly representable if and only if the chromatic number of $\Gamma$ is infinite. A construction of Erdös shows that there are graphs $\Gamma _r$ ($r<\omega$) with infinite chromatic number, with a non-principal ultraproduct $\prod _D\Gamma _r$ whose chromatic number is just two. It follows that $\alpha (\Gamma _r)$ is strongly representable (each $r<\omega$) but $\prod _D(\alpha (\Gamma _r))$ is not.References
- Hajnal Andréka, Complexity of equations valid in algebras of relations. I. Strong non-finitizability, Ann. Pure Appl. Logic 89 (1997), no. 2-3, 149–209. MR 1490104, DOI 10.1016/S0168-0072(97)00027-4
- 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
- C. C. Chang and H. J. Keisler, Model theory, 3rd ed., Studies in Logic and the Foundations of Mathematics, vol. 73, North-Holland Publishing Co., Amsterdam, 1990. MR 1059055
- R. Diestel, Graph theory, Graduate Texts in Mathematics, vol. 173, Springer-Verlag, Berlin, 1997.
- P. Erdős, Graph theory and probability, Canadian J. Math. 11 (1959), 34–38. MR 102081, DOI 10.4153/CJM-1959-003-9
- P. Hebroni, Sur les inverses des éléments dérivables dans un anneau abstrait, C. R. Acad. Sci. Paris 209 (1939), 285–287 (French). MR 14
- 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
- Leon Henkin, J. Donald Monk, and Alfred Tarski, Cylindric algebras. Part I, Studies in Logic and the Foundations of Mathematics, vol. 64, North-Holland Publishing Co., Amsterdam, 1985. With an introductory chapter: General theory of algebras; Reprint of the 1971 original. MR 781929
- Robin Hirsch and Ian Hodkinson, Complete representations in algebraic logic, J. Symbolic Logic 62 (1997), no. 3, 816–847. MR 1472125, DOI 10.2307/2275574
- 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
- —, Representability is not decidable for finite relation algebras, Trans. Amer. Math. Soc. 353 (2001), 1403–1425.
- 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
- 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
- Charles Hopkins, Rings with minimal condition for left ideals, Ann. of Math. (2) 40 (1939), 712–730. MR 12, DOI 10.2307/1968951
- Cahit Arf, Untersuchungen über reinverzweigte Erweiterungen diskret bewerteter perfekter Körper, J. Reine Angew. Math. 181 (1939), 1–44 (German). MR 18, DOI 10.1515/crll.1940.181.1
- R. Maddux, Topics in relation algebra, Ph.D. thesis, University of California, Berkeley, 1978.
- Roger Maddux, Some varieties containing relation algebras, Trans. Amer. Math. Soc. 272 (1982), no. 2, 501–526. MR 662049, DOI 10.1090/S0002-9947-1982-0662049-7
- 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
- Roger D. Maddux, Nonfinite axiomatizability results for cylindric and relation algebras, J. Symbolic Logic 54 (1989), no. 3, 951–974. MR 1011183, DOI 10.2307/2274756
- Donald Monk, On representable relation algebras, Michigan Math. J. 11 (1964), 207–210. MR 172797
- J. Donald Monk, Nonfinitizability of classes of representable cylindric algebras, J. Symbolic Logic 34 (1969), 331–343. MR 256861, DOI 10.2307/2270900
- Saharon Shelah, Every two elementarily equivalent models have isomorphic ultrapowers, Israel J. Math. 10 (1971), 224–233. MR 297554, DOI 10.1007/BF02771574
- Y. Venema, Atom structures, Advances in Modal Logic ’96 (M. Kracht, M. de Rijke, H. Wansing, and M. Zakharyaschev, eds.), CSLI Publications, Stanford, 1997, pp. 291–305.
- Y. Venema, Atom structures and Sahlqvist equations, Algebra Universalis 38 (1997), no. 2, 185–199. MR 1609043, DOI 10.1007/s000120050047
Additional Information
- Robin Hirsch
- Affiliation: Department of Computer Science, University College, Gower Street, London WC1E 6BT, United Kingdom
- Email: r.hirsch@cs.ucl.ac.uk
- Ian Hodkinson
- Affiliation: Department of Computing, Imperial College, Queen’s Gate, London SW7 2BZ, United Kingdom
- Email: imh@doc.ic.ac.uk
- Received by editor(s): October 20, 2000
- Received by editor(s) in revised form: November 27, 2000
- Published electronically: May 23, 2001
- Additional Notes: This research was partially supported by UK EPSRC grants GR/L85961, GR/K54946, GR/L85978. Thanks to Rob Goldblatt for valuable additions and suggestions, and Imre Leader for a helpful discussion about the graph-theoretic aspects. Thanks also to the referee for suggesting useful improvements to the paper.
- Communicated by: Carl G. Jockusch, Jr.
- © Copyright 2001 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 130 (2002), 1819-1831
- MSC (2000): Primary 03G15; Secondary 03C05, 05C80
- DOI: https://doi.org/10.1090/S0002-9939-01-06232-3
- MathSciNet review: 1887031