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?)

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