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

DOI:
https://doi.org/10.1090/S0002-9939-01-06232-3

Published electronically:
May 23, 2001

MathSciNet review:
1887031

Full-text PDF

Abstract | References | Similar Articles | Additional Information

A relation algebra atom structure 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 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 , we construct a relation algebra atom structure and prove, for infinite , that is strongly representable if and only if the chromatic number of is infinite. A construction of Erdös shows that there are graphs () with infinite chromatic number, with a non-principal ultraproduct whose chromatic number is just two. It follows that is strongly representable (each ) but is not.

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

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

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

DOI:
https://doi.org/10.1090/S0002-9939-01-06232-3

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