Tue, 19 Oct 2021, 1 pm MDT
It is well-known and easy to prove that the variety of groups abstractly captures algebras of permutations under composition and inverse, that the variety of inverse semigroups capture algebras of partial injective functions under composition and inverse, and that the variety of semigroups abstractly capture the algebras of any of total functions, partial functions or binary relations under the operation of composition. In contrast to this, a landmark result of Hirsch and Hodkinson showing the undecidability of determining when a finite algebra is isomorphic to an algebra of binary relations under Tarski's signature: the usual set theoretic Boolean operations, composition, converse and identity. This is a very rich signature, and it has subsequently been discovered that undecidability of representability begins in weaker signatures.
This talk will survey some of the very extensive literature in this area, and an overview of the approaches to undecidability, possibly touching on some new results for one of the weakest known algebraic signature to experience undecidability of representability as binary relations.
[video]