Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Strongly representable atom structures of relation algebras

Authors: Robin Hirsch and Ian Hodkinson
Journal: Proc. Amer. Math. Soc. 130 (2002), 1819-1831
MSC (2000): Primary 03G15; Secondary 03C05, 05C80
Published electronically: May 23, 2001
MathSciNet review: 1887031
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information


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 $\mathop{\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 [Enhancements On Off] (What's this?)

  • 1. H. Andréka, Complexity of equations valid in algebras of relations, Part I: Strong non-finitizability, Annals of Pure and Applied Logic 89 (1997), 149-209. MR 99b:03078
  • 2. H. Andréka, J. D. Monk, and I. Németi (eds.), Algebraic logic, Colloq. Math. Soc. J. Bolyai, no. 54, North-Holland, Amsterdam, 1991, Proc. Conf. Budapest, 1988. MR 92m:03003
  • 3. C. C. Chang and H. J. Keisler, Model theory, 3rd ed., North-Holland, Amsterdam, 1990. MR 91c:03026
  • 4. R. Diestel, Graph theory, Graduate Texts in Mathematics, vol. 173, Springer-Verlag, Berlin, 1997. CMP 97:12
  • 5. P. Erdös, Graph theory and probability, Canad. J. Math. 11 (1959), 34-38. MR 21:876
  • 6. 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 14:999b
  • 7. R. Goldblatt, Varieties of complex algebras, Annals of Pure and Applied Logic 44 (1989), 173-242. MR 91d:08005
  • 8. L. Henkin, J. D. Monk, and A. Tarski, Cylindric algebras part II, North-Holland, 1985. MR 86m:03095b
  • 9. R. Hirsch and I. Hodkinson, Complete representations in algebraic logic, Journal of Symbolic Logic 62 (1997), 816-847. MR 98m:03123
  • 10. -, Step by step -- building representations in algebraic logic, Journal of Symbolic Logic 62 (1997), 225-279. MR 98g:03145
  • 11. -, Representability is not decidable for finite relation algebras, Trans. Amer. Math. Soc. 353 (2001), 1403-1425. CMP 2001:06
  • 12. I. Hodkinson, Atom structures of cylindric algebras and relation algebras, Annals of Pure and Applied Logic 89 (1997), 117-148. MR 99c:03103
  • 13. B. Jónsson, The theory of binary relations, In Andréka et. al. [2], pp. 245-292. MR 93b:03114
  • 14. R. Lyndon, The representation of relational algebras, Annals of Mathematics 51 (1950), 707-729. MR 12:237a
  • 15. -, The representation of relation algebras, II, Annals of Mathematics 63 (1956), 294-307. MR 18:106f
  • 16. R. Maddux, Topics in relation algebra, Ph.D. thesis, University of California, Berkeley, 1978.
  • 17. -, Some varieties containing relation algebras, Trans. Amer. Math. Soc. 272 (1982), 501-526. MR 84a:03079
  • 18. -, A sequent calculus for relation algebras, Annals of Pure and Applied Logic 25 (1983), 73-101. MR 85h:03067
  • 19. -, Introductory course on relation algebras, finite-dimensional cylindric algebras, and their interconnections, In Andréka et. al. [2], pp. 361-392. MR 93c:03082
  • 20. -, Non-finite axiomatizability results for cylindric and relation algebras, Journal of Symbolic Logic 54 (1989), 951-974. MR 90f:03099
  • 21. J. D. Monk, On representable relation algebras, Michigan Mathematics Journal 11 (1964), 207-210. MR 30:3016
  • 22. -, Nonfinitizability of classes of representable cylindric algebras, Journal of Symbolic Logic 34 (1969), 331-343. MR 41:1517
  • 23. S. Shelah, Every two elementarily equivalent models have isomorphic ultrapowers, Israel J. Math. 10 (1971), 224-233. MR 45:6608
  • 24. 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. CMP 99:12
  • 25. -, Atom structures and Sahlqvist equations, Algebra Universalis 38 (1997), 185-199. MR 99g:06019

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 03G15, 03C05, 05C80

Retrieve articles in all journals with MSC (2000): 03G15, 03C05, 05C80

Additional Information

Robin Hirsch
Affiliation: Department of Computer Science, University College, Gower Street, London WC1E 6BT, United Kingdom

Ian Hodkinson
Affiliation: Department of Computing, Imperial College, Queen’s Gate, London SW7 2BZ, United Kingdom

Keywords: Elementary class, complex algebra, relation algebra, representation
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.
Article copyright: © Copyright 2001 American Mathematical Society

American Mathematical Society