Undecidability of RRA

Go to home page  |  Decidability in modal logic

Representability is not decidable for finite relation algebras

Robin Hirsch and Ian Hodkinson
Trans. Amer. Math. Soc. 353 (2001), 1403-1425
AMS page for the paper
We prove that it is not decidable whether a finite relation algebra is representable.  This confirms a conjecture of Maddux.
Representability of a finite relation algebra A is determined by playing a certain two-player game G(A) over 'atomic A-networks'.  It can be shown that the second player in this game has a winning strategy if and only if A is representable.
Let T be a finite set of square tiles, where each edge of each tile has a colour.  Suppose T 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 T, there is a tiling of the plane Z x Z (Z being the integers) 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 T, we construct a finite relation algebra RA(T), and show that the second player has a winning strategy in G(RA(T)) if and only if T is a yes-instance.  This reduces the tiling problem to the representation problem and proves the latter's undecidability.

An error in the proof is corrected in an appendix at the end of the paper.  An improved version of the proof without the error can be found in this book, where it is also shown that it is not decidable whether a finite relation algebra is in SRaCAn, for any n>4.  Related results on weakly representable relation algebras are also proved.

A construction of cylindric and polyadic algebras from atomic relation algebras

Ian Hodkinson
Algebra Universalis 68 (2012) 257-285, doi 10.1007/s00012-012-0202-3.
Abstract Given a simple atomic relation algebra A and a finite n at least 3, we construct effectively an atomic n-dimensional polyadic equality-type algebra P such that for any subsignature L of the signature of P that contains the boolean operations and cylindrifications, the L-reduct of P is completely representable if and only if A is completely representable. If A is finite then so is P.
It follows that there is no algorithm to determine whether a finite n-dimensional cylindric algebra, diagonal-free cylindric algebra, polyadic algebra, or polyadic equality algebra is representable (for diagonal-free algebras this was known). We also obtain a new proof that the classes of completely representable n-dimensional algebras of these types are non-elementary, a result that remains true for infinite dimensions if the diagonals are present, and also for infinite-dimensional diagonal-free cylindric algebras.

Undecidability of Algebras of Binary Relations

Robin Hirsch and Ian Hodkinson and Marcel Jackson
in: Hajnal Andréka and István Németi on Unity of Science - From Computing to Relativity Theory Through Algebraic Logic
Judit Madarász and Gergely Székely (Eds.),
Outstanding contributions to logic, vol 19, Springer, 2021, pp. 267-287.

Abstract Let S be a signature of operations and relations definable in relation algebra (e.g. converse, composition, containment, union, identity, etc.), let R(S) be the class of all S-structures isomorphic to concrete algebras of binary relations with concrete interpretations for symbols in S, and let F(S) be the class of S-structures isomorphic to concrete algebras of binary relations over a finite base. To prove that membership of R(S) or F(S) for finite S-structures is undecidable, we reduce from a known undecidable problem - here we use the tiling problem, the partial group embedding problem and the partial group finite embedding problem to prove undecidability of finite membership of R(S) or F(S) for various signatures S. It follows that the equational theory of R(S) is undecidable whenever S includes the boolean operators and composition. We give an exposition of the reduction from the tiling problem and the reduction from the group embedding problem, and summarize what we know about the undecidability of finite membership of R(S) and of F(S) for different signatures S.