## Representability is not decidable for finite relation algebras

HTML articles powered by AMS MathViewer

- by Robin Hirsch and Ian Hodkinson PDF
- Trans. Amer. Math. Soc.
**353**(2001), 1403-1425 Request permission

## Abstract:

We prove that there is no algorithm that decides whether a finite relation algebra is representable. Representability of a finite relation algebra $\mathcal A$ is determined by playing a certain two player game $G({\mathcal A})$ over ‘atomic $\mathcal A$-networks’. It can be shown that the second player in this game has a winning strategy if and only if $\mathcal A$ is representable. Let $\tau$ be a finite set of square tiles, where each edge of each tile has a colour. Suppose $\tau$ 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 $T \in \tau$ there is a tiling of the plane ${\mathbb Z}\times {\mathbb Z}$ using only tiles from $\tau$ in which edge colours of adjacent tiles match and with $T$ placed at $(0,0)$? It is not hard to show that this problem is undecidable. From an instance of this tiling problem $\tau$, we construct a finite relation algebra $RA(\tau )$ and show that the second player has a winning strategy in $G(RA(\tau ))$ if and only if $\tau$ is a yes-instance. This reduces the tiling problem to the representation problem and proves the latter’s undecidability.## References

- 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** - Robert Berger,
*The undecidability of the domino problem*, Mem. Amer. Math. Soc.**66**(1966), 72. MR**216954** - Robin Hirsch and Ian Hodkinson,
*Complete representations in algebraic logic*, J. Symbolic Logic**62**(1997), no. 3, 816–847. MR**1472125**, DOI 10.2307/2275574 - Robin Hirsch and Ian Hodkinson,
*Step by step—building representations in algebraic logic*, J. Symbolic Logic**62**(1997), no. 1, 225–279. MR**1450522**, DOI 10.2307/2275740 - Robin Hirsch,
*Completely representable relation algebras*, Bull. IGPL**3**(1995), no. 1, 77–91. MR**1330986** - Leon Henkin, J. Donald Monk, and Alfred Tarski,
*Cylindric algebras. Part I*, Studies in Logic and the Foundations of Mathematics, vol. 64, North-Holland Publishing Co., Amsterdam, 1985. With an introductory chapter: General theory of algebras; Reprint of the 1971 original. MR**781929** - I. Hodkinson. Atom structures of cylindric algebras and relation algebras.
*Ann. Pure Appl. Logic,*89(2–3):117–148, 1997. - B. Jónsson and A. Tarski. Representation problems for relation algebras.
*Bulletin of the American Mathematical Society*, 54, pp. 80 and 1192, 1948. - C. J. Everett Jr.,
*Annihilator ideals and representation iteration for abstract rings*, Duke Math. J.**5**(1939), 623–627. MR**13** - Charles Hopkins,
*Rings with minimal condition for left ideals*, Ann. of Math. (2)**40**(1939), 712–730. MR**12**, DOI 10.2307/1968951 - Cahit Arf,
*Untersuchungen über reinverzweigte Erweiterungen diskret bewerteter perfekter Körper*, J. Reine Angew. Math.**181**(1939), 1–44 (German). MR**18**, DOI 10.1515/crll.1940.181.1 - Roger Maddux,
*Some varieties containing relation algebras*, Trans. Amer. Math. Soc.**272**(1982), no. 2, 501–526. MR**662049**, DOI 10.1090/S0002-9947-1982-0662049-7 - 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** - 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** - Roger D. Maddux,
*A perspective on the theory of relation algebras*, Algebra Universalis**31**(1994), no. 3, 456–465. MR**1265356**, DOI 10.1007/BF01221799 - Donald Monk,
*On representable relation algebras*, Michigan Math. J.**11**(1964), 207–210. MR**172797** - I. Németi. A fine-structure analysis of first-order logic. In M. Marx, L. Pólos, and M. Masuch, editors,
*Arrow Logic and Multi-Modal Logic*, Studies in Logic, Language and Information, pages 221–247. CSLI Publications & FoLLI, 1996. - 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**, DOI 10.1090/coll/041

## 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
- 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.
- © Copyright 1999 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
**353**(2001), 1403-1425 - MSC (1991): Primary 03G15; Secondary 03G05, 06E25, 03D35
- DOI: https://doi.org/10.1090/S0002-9947-99-02264-3
- MathSciNet review: 1806735