Undecidability of RRA
Go to home page | Decidability
in modal logic
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.
Ian Hodkinson
Algebra Universalis, to appear.
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.