Some Undecidable Problems on Representability as Binary Relations
Robin Hirsch, Marcel Jackson · UCL Discovery (University College London) · 2012
We establish the undecidability of representability and of finite representability as algebras of binary relations in a wide range of signatures. In particular, representability and finite representability are undecidable for Boolean monoids and lattice ordered monoids, while representability is undecidable for J onsson's relation algebra. We also establish a number of undecidability results for representability as algebras of injective functions.