A construction of cylindric and polyadic algebras from atomic relation algebras
Ian Hodkinson · Algebra Universalis · 2012
Given a simple atomic relation algebra $${\mathcal{A}}$$ and a finite n ≥ 3, we construct effectively an atomic n-dimensional polyadic equality-type algebra $${\mathcal{P}}$$ such that for any subsignature L of the signature of $${\mathcal{P}}$$ that contains the boolean operations and cylindrifications, the L-reduct of $${\mathcal{P}}$$ is completely representable if and only if $${\mathcal{A}}$$ is completely representable. If $${\mathcal{A}}$$ is finite then so is $${\mathcal{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.