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 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.**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**, 10.1016/S0168-0072(97)00027-4**2.**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****3.**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****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**0102081****6.**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****7.**Robert Goldblatt,*Varieties of complex algebras*, Ann. Pure Appl. Logic**44**(1989), no. 3, 173–242. MR**1020344**, 10.1016/0168-0072(89)90032-8**8.**Leon Henkin, J. Donald Monk, and Alfred Tarski,*Cylindric algebras. Part II*, Studies in Logic and the Foundations of Mathematics, vol. 115, North-Holland Publishing Co., Amsterdam, 1985. MR**781930****9.**Robin Hirsch and Ian Hodkinson,*Complete representations in algebraic logic*, J. Symbolic Logic**62**(1997), no. 3, 816–847. MR**1472125**, 10.2307/2275574**10.**Robin Hirsch and Ian Hodkinson,*Step by step—building representations in algebraic logic*, J. Symbolic Logic**62**(1997), no. 1, 225–279. MR**1450522**, 10.2307/2275740**11.**-,*Representability is not decidable for finite relation algebras*, Trans. Amer. Math. Soc.**353**(2001), 1403-1425. CMP**2001:06****12.**Ian Hodkinson,*Atom structures of cylindric algebras and relation algebras*, Ann. Pure Appl. Logic**89**(1997), no. 2-3, 117–148. MR**1490103**, 10.1016/S0168-0072(97)00015-8**13.**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****14.**Roger C. Lyndon,*The representation of relational algebras*, Ann. of Math. (2)**51**(1950), 707–729. MR**0037278****15.**Roger C. Lyndon,*The representation of relation algebras. II*, Ann. of Math. (2)**63**(1956), 294–307. MR**0079570****16.**R. Maddux,*Topics in relation algebra*, Ph.D. thesis, University of California, Berkeley, 1978.**17.**Roger Maddux,*Some varieties containing relation algebras*, Trans. Amer. Math. Soc.**272**(1982), no. 2, 501–526. MR**662049**, 10.1090/S0002-9947-1982-0662049-7**18.**Roger Maddux,*A sequent calculus for relation algebras*, Ann. Pure Appl. Logic**25**(1983), no. 1, 73–101. MR**722170**, 10.1016/0168-0072(83)90055-6**19.**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****20.**Roger D. Maddux,*Nonfinite axiomatizability results for cylindric and relation algebras*, J. Symbolic Logic**54**(1989), no. 3, 951–974. MR**1011183**, 10.2307/2274756**21.**Donald Monk,*On representable relation algebras*, Michigan Math. J.**11**(1964), 207–210. MR**0172797****22.**J. Donald Monk,*Nonfinitizability of classes of representable cylindric algebras*, J. Symbolic Logic**34**(1969), 331–343. MR**0256861****23.**Saharon Shelah,*Every two elementarily equivalent models have isomorphic ultrapowers*, Israel J. Math.**10**(1971), 224–233. MR**0297554****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.**Y. Venema,*Atom structures and Sahlqvist equations*, Algebra Universalis**38**(1997), no. 2, 185–199. MR**1609043**, 10.1007/s000120050047

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:
http://dx.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