Strongly representable atom structures of relation algebras
Authors:
Robin Hirsch and Ian Hodkinson
Journal:
Proc. Amer. Math. Soc. 130 (2002), 18191831
MSC (2000):
Primary 03G15; Secondary 03C05, 05C80
Published electronically:
May 23, 2001
MathSciNet review:
1887031
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: 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, loopfree 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 nonprincipal 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 nonfinitizability, Ann. Pure Appl. Logic
89 (1997), no. 23, 149–209. MR 1490104
(99b:03078), http://dx.doi.org/10.1016/S01680072(97)000274
 2.
H.
Andréka, J.
D. Monk, and I.
Németi (eds.), Algebraic logic, Colloquia Mathematica
Societatis János Bolyai, vol. 54, NorthHolland Publishing Co.,
Amsterdam, 1991. Papers from the colloquium held in Budapest, August
8–14, 1988. MR 1153415
(92m:03003)
 3.
C.
C. Chang and H.
J. Keisler, Model theory, 3rd ed., Studies in Logic and the
Foundations of Mathematics, vol. 73, NorthHolland Publishing Co.,
Amsterdam, 1990. MR 1059055
(91c:03026)
 4.
R. Diestel, Graph theory, Graduate Texts in Mathematics, vol. 173, SpringerVerlag, Berlin, 1997. CMP 97:12
 5.
P.
Erdős, Graph theory and probability, Canad. J. Math.
11 (1959), 34–38. MR 0102081
(21 #876)
 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
(14,999b)
 7.
Robert
Goldblatt, Varieties of complex algebras, Ann. Pure Appl.
Logic 44 (1989), no. 3, 173–242. MR 1020344
(91d:08005), http://dx.doi.org/10.1016/01680072(89)900328
 8.
Leon
Henkin, J.
Donald Monk, and Alfred
Tarski, Cylindric algebras. Part II, Studies in Logic and the
Foundations of Mathematics, vol. 115, NorthHolland Publishing Co.,
Amsterdam, 1985. MR 781930
(86m:03095b)
 9.
Robin
Hirsch and Ian
Hodkinson, Complete representations in algebraic logic, J.
Symbolic Logic 62 (1997), no. 3, 816–847. MR 1472125
(98m:03123), http://dx.doi.org/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
(98g:03145), http://dx.doi.org/10.2307/2275740
 11.
, Representability is not decidable for finite relation algebras, Trans. Amer. Math. Soc. 353 (2001), 14031425. CMP 2001:06
 12.
Ian
Hodkinson, Atom structures of cylindric algebras and relation
algebras, Ann. Pure Appl. Logic 89 (1997),
no. 23, 117–148. MR 1490103
(99c:03103), http://dx.doi.org/10.1016/S01680072(97)000158
 13.
Bjarni
Jónsson, The theory of binary relations, Algebraic
logic (Budapest, 1988) Colloq. Math. Soc. János Bolyai,
vol. 54, NorthHolland, Amsterdam, 1991, pp. 245–292. MR 1153429
(93b:03114)
 14.
Roger
C. Lyndon, The representation of relational algebras, Ann. of
Math. (2) 51 (1950), 707–729. MR 0037278
(12,237a)
 15.
Roger
C. Lyndon, The representation of relation algebras. II, Ann.
of Math. (2) 63 (1956), 294–307. MR 0079570
(18,106f)
 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 (84a:03079), http://dx.doi.org/10.1090/S00029947198206620497
 18.
Roger
Maddux, A sequent calculus for relation algebras, Ann. Pure
Appl. Logic 25 (1983), no. 1, 73–101. MR 722170
(85h:03067), http://dx.doi.org/10.1016/01680072(83)900556
 19.
Roger
D. Maddux, Introductory course on relation algebras,
finitedimensional cylindric algebras, and their interconnections,
Algebraic logic (Budapest, 1988) Colloq. Math. Soc. János Bolyai,
vol. 54, NorthHolland, Amsterdam, 1991, pp. 361–392. MR 1153432
(93c:03082)
 20.
Roger
D. Maddux, Nonfinite axiomatizability results for cylindric and
relation algebras, J. Symbolic Logic 54 (1989),
no. 3, 951–974. MR 1011183
(90f:03099), http://dx.doi.org/10.2307/2274756
 21.
Donald
Monk, On representable relation algebras, Michigan Math. J.
11 (1964), 207–210. MR 0172797
(30 #3016)
 22.
J.
Donald Monk, Nonfinitizability of classes of representable
cylindric algebras, J. Symbolic Logic 34 (1969),
331–343. MR 0256861
(41 #1517)
 23.
Saharon
Shelah, Every two elementarily equivalent models have isomorphic
ultrapowers, Israel J. Math. 10 (1971),
224–233. MR 0297554
(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. 291305. CMP 99:12
 25.
Y.
Venema, Atom structures and Sahlqvist equations, Algebra
Universalis 38 (1997), no. 2, 185–199. MR 1609043
(99g:06019), http://dx.doi.org/10.1007/s000120050047
 1.
 H. Andréka, Complexity of equations valid in algebras of relations, Part I: Strong nonfinitizability, Annals of Pure and Applied Logic 89 (1997), 149209. MR 99b:03078
 2.
 H. Andréka, J. D. Monk, and I. Németi (eds.), Algebraic logic, Colloq. Math. Soc. J. Bolyai, no. 54, NorthHolland, Amsterdam, 1991, Proc. Conf. Budapest, 1988. MR 92m:03003
 3.
 C. C. Chang and H. J. Keisler, Model theory, 3rd ed., NorthHolland, Amsterdam, 1990. MR 91c:03026
 4.
 R. Diestel, Graph theory, Graduate Texts in Mathematics, vol. 173, SpringerVerlag, Berlin, 1997. CMP 97:12
 5.
 P. Erdös, Graph theory and probability, Canad. J. Math. 11 (1959), 3438. 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), 291296. MR 14:999b
 7.
 R. Goldblatt, Varieties of complex algebras, Annals of Pure and Applied Logic 44 (1989), 173242. MR 91d:08005
 8.
 L. Henkin, J. D. Monk, and A. Tarski, Cylindric algebras part II, NorthHolland, 1985. MR 86m:03095b
 9.
 R. Hirsch and I. Hodkinson, Complete representations in algebraic logic, Journal of Symbolic Logic 62 (1997), 816847. MR 98m:03123
 10.
 , Step by step  building representations in algebraic logic, Journal of Symbolic Logic 62 (1997), 225279. MR 98g:03145
 11.
 , Representability is not decidable for finite relation algebras, Trans. Amer. Math. Soc. 353 (2001), 14031425. CMP 2001:06
 12.
 I. Hodkinson, Atom structures of cylindric algebras and relation algebras, Annals of Pure and Applied Logic 89 (1997), 117148. MR 99c:03103
 13.
 B. Jónsson, The theory of binary relations, In Andréka et. al. [2], pp. 245292. MR 93b:03114
 14.
 R. Lyndon, The representation of relational algebras, Annals of Mathematics 51 (1950), 707729. MR 12:237a
 15.
 , The representation of relation algebras, II, Annals of Mathematics 63 (1956), 294307. 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), 501526. MR 84a:03079
 18.
 , A sequent calculus for relation algebras, Annals of Pure and Applied Logic 25 (1983), 73101. MR 85h:03067
 19.
 , Introductory course on relation algebras, finitedimensional cylindric algebras, and their interconnections, In Andréka et. al. [2], pp. 361392. MR 93c:03082
 20.
 , Nonfinite axiomatizability results for cylindric and relation algebras, Journal of Symbolic Logic 54 (1989), 951974. MR 90f:03099
 21.
 J. D. Monk, On representable relation algebras, Michigan Mathematics Journal 11 (1964), 207210. MR 30:3016
 22.
 , Nonfinitizability of classes of representable cylindric algebras, Journal of Symbolic Logic 34 (1969), 331343. MR 41:1517
 23.
 S. Shelah, Every two elementarily equivalent models have isomorphic ultrapowers, Israel J. Math. 10 (1971), 224233. 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. 291305. CMP 99:12
 25.
 , Atom structures and Sahlqvist equations, Algebra Universalis 38 (1997), 185199. 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
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/S0002993901062323
PII:
S 00029939(01)062323
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 graphtheoretic 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
