Undecidability of representability as binary relations

Abstract: 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.

computational complexitycategory theorylogic

Audience: researchers in the topic

PALS Panglobal Algebra and Logic Seminar

Series comments: The PALS seminar is a research and learning seminar organized by the algebra and logic research group of the Department of Mathematics at the University of Colorado at Boulder. The scope of the seminar includes all topics with links to algebra, logic, or their applications, like general algebra, logic, model theory, category theory, set theory, set-theoretic topology, or theoretical computer science. Please contact one of the organizers for the Zoom password, to join the mailing list or if you want to speak.