Representability is not decidable for finite relation algebras
Authors:
Robin Hirsch and Ian Hodkinson
Journal:
Trans. Amer. Math. Soc. 353 (2001), 14031425
MSC (1991):
Primary 03G15; Secondary 03G05, 06E25, 03D35
Published electronically:
April 23, 1999
MathSciNet review:
1806735
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We prove that there is no algorithm that decides whether a finite relation algebra is representable. Representability of a finite relation algebra is determined by playing a certain two player game over `atomic networks'. It can be shown that the second player in this game has a winning strategy if and only if is representable. Let be a finite set of square tiles, where each edge of each tile has a colour. Suppose includes a special tile whose four edges are all the same colour, a colour not used by any other tile. The tiling problem we use is this: is it the case that for each tile there is a tiling of the plane using only tiles from in which edge colours of adjacent tiles match and with placed at ? It is not hard to show that this problem is undecidable. From an instance of this tiling problem , we construct a finite relation algebra and show that the second player has a winning strategy in if and only if is a yesinstance. This reduces the tiling problem to the representation problem and proves the latter's undecidability.
 [AMN91]
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)
 [Ber66]
Robert
Berger, The undecidability of the domino problem, Mem. Amer.
Math. Soc. No. 66 (1966), 72. MR 0216954
(36 #49)
 [HH97a]
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
 [HH97b]
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
 [Hir95]
Robin
Hirsch, Completely representable relation algebras, Bull. IGPL
3 (1995), no. 1, 77–91. MR 1330986
(96d:03082)
 [HMT85]
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)
 [Hod97]
I. Hodkinson. Atom structures of cylindric algebras and relation algebras. Ann. Pure Appl. Logic, 89(23):117148, 1997. CMP 98:06
 [JT48]
B. Jónsson and A. Tarski. Representation problems for relation algebras. Bulletin of the American Mathematical Society, 54, pp. 80 and 1192, 1948.
 [JT52]
Bjarni
Jónsson and Alfred
Tarski, Boolean algebras with operators. II, Amer. J. Math.
74 (1952), 127–162. MR 0045086
(13,524g)
 [Lyn50]
Roger
C. Lyndon, The representation of relational algebras, Ann. of
Math. (2) 51 (1950), 707–729. MR 0037278
(12,237a)
 [Lyn56]
Roger
C. Lyndon, The representation of relation algebras. II, Ann.
of Math. (2) 63 (1956), 294–307. MR 0079570
(18,106f)
 [Ma82]
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
 [Ma91a]
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)
 [Ma91b]
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)
 [Ma94]
Roger
D. Maddux, A perspective on the theory of relation algebras,
Algebra Universalis 31 (1994), no. 3, 456–465.
MR
1265356 (95c:03143), http://dx.doi.org/10.1007/BF01221799
 [Mon64]
Donald
Monk, On representable relation algebras, Michigan Math. J.
11 (1964), 207–210. MR 0172797
(30 #3016)
 [Nem96]
I. Németi. A finestructure analysis of firstorder logic. In M. Marx, L. Pólos, and M. Masuch, editors, Arrow Logic and MultiModal Logic, Studies in Logic, Language and Information, pages 221247. CSLI Publications & FoLLI, 1996. CMP 97:09
 [TG87]
Alfred
Tarski and Steven
Givant, A formalization of set theory without variables,
American Mathematical Society Colloquium Publications, vol. 41,
American Mathematical Society, Providence, RI, 1987. MR 920815
(89g:03012)
 [AMN91]
 H. Andréka, J. D. Monk, and I. Németi. Algebraic Logic. Colloq. Math. Soc. J. Bolyai. NorthHolland, Amsterdam, 1991. Conference Proceedings, Budapest, 1988. MR 92m:03003
 [Ber66]
 R. Berger. The undecidability of the domino problem. Memoirs of the American Mathematical Society, vol. 66, 1966. MR 36:49
 [HH97a]
 R. Hirsch and I. Hodkinson. Complete representations in algebraic logic. Journal of Symbolic Logic, 1997. 62(3):816847, 1997. MR 98m:03123
 [HH97b]
 R. Hirsch and I. Hodkinson. Step by step  building representations in algebraic logic. Journal of Symbolic Logic. 62(1):225279, 1997. MR 98g:03145
 [Hir95]
 R. Hirsch. Completely representable relation algebras. Bulletin of the Interest Group in Propositional and Predicate Logics, 3(1):7791, 1995. MR 96d:03082
 [HMT85]
 L. Henkin, J. D. Monk, and A. Tarski. Cylindric Algebras. Part II. NorthHolland, 1985. MR 86m:03095b
 [Hod97]
 I. Hodkinson. Atom structures of cylindric algebras and relation algebras. Ann. Pure Appl. Logic, 89(23):117148, 1997. CMP 98:06
 [JT48]
 B. Jónsson and A. Tarski. Representation problems for relation algebras. Bulletin of the American Mathematical Society, 54, pp. 80 and 1192, 1948.
 [JT52]
 B. Jónsson and A. Tarski. Boolean algebras with operators. II. American Journal of Mathematics, 74:127  162, 1952. MR 13:524g
 [Lyn50]
 R. Lyndon. The representation of relational algebras. Annals of Mathematics, 51(3):707729, 1950. MR 12:237a
 [Lyn56]
 R. Lyndon. The representation of relation algebras, II. Annals of Mathematics, 63(2):294307, 1956. MR 18:106f
 [Ma82]
 R. Maddux. Some varieties containing relation algebras. Transactions of the American Mathematical Society, 272(2):501526, 1982. MR 84a:03079
 [Ma91a]
 R. Maddux. Introductory course on relation algebras, finitedimensional cylindric algebras, and their interconnections. In [AMN91], pages 361392. MR 93c:03082
 [Ma91b]
 R. Maddux. The origin of relation algebras in the development and axiomatization of the calculus of relations. Studia Logica, 5(34):421456, 1991. MR 93c:03082
 [Ma94]
 R. Maddux. A perspective on the theory of relation algebras. Algebra Universalis, 31:456465, 1994. MR 95c:03143
 [Mon64]
 J. D. Monk. On representable relation algebras. Michigan Mathematics Journal, 11:207210, 1964. MR 30:3016
 [Nem96]
 I. Németi. A finestructure analysis of firstorder logic. In M. Marx, L. Pólos, and M. Masuch, editors, Arrow Logic and MultiModal Logic, Studies in Logic, Language and Information, pages 221247. CSLI Publications & FoLLI, 1996. CMP 97:09
 [TG87]
 A. Tarski and S. R. Givant. A Formalization of Set Theory Without Variables. Number 41 in Colloquium Publications in Mathematics. American Mathematical Society, Providence, Rhode Island, 1987. MR 89g:03012
Similar Articles
Retrieve articles in Transactions of the American Mathematical Society
with MSC (1991):
03G15,
03G05,
06E25,
03D35
Retrieve articles in all journals
with MSC (1991):
03G15,
03G05,
06E25,
03D35
Additional Information
Robin Hirsch
Affiliation:
Department of Computer Science, University College, Gower Street, London WC1E 6BT, U.K.
Email:
r.hirsch@cs.ucl.ac.uk
Ian Hodkinson
Affiliation:
Department of Computing, Imperial College, Queen’s Gate, London SW7 2BZ, U.K.
Email:
imh@doc.ic.ac.uk
DOI:
http://dx.doi.org/10.1090/S0002994799022643
PII:
S 00029947(99)022643
Keywords:
Relation algebra,
representation,
undecidability,
tiling problem,
games,
algebraic logic
Received by editor(s):
April 2, 1997
Received by editor(s) in revised form:
November 11, 1997
Published electronically:
April 23, 1999
Additional Notes:
Research of the second author was partially supported by UK EPSRC grant GR/K54946. Many thanks to Peter Jipsen, Maarten Marx, Szabolcs Mikulás, Mark Reynolds, Yde Venema and the referee for useful comments and for pointing out serious errors in early drafts of this paper.
Article copyright:
© Copyright 1999 American Mathematical Society
