Representability of finite algebras of relations

Submission note: A thesis submitted in total fulfilment of the requirements for the degree of Doctor of Philosophy to the School of Engineering and Mathematical Sciences, College of Science, Health and Engineering, La Trobe University, Bundoora.

Cayley’s Theorem shows that groups correspond precisely to the isomorphism class of algebraic structures arising as systems of permutations on some set, under the operations of composition and inverse. This elementary fact underpins much of the application of group theory in modern mathematics: as algebras of symmetries. However, there are very many processes that cannot in general be faithfully reversed. We study situations such as this, in which the role of permutations is replaced by more general binary relations. We survey the representability of reducts of Tarski’s relation algebras as algebras of binary relations. In particular, we develop necessary conditions for the representability of semigroups as disjoint transformations. We also prove undecidable the problem of determining whether or not algebras in some reducts of Tarski’s signature are representable. Finally, we explore qualitative representability of nonassociative algebras. These are a broader class of algebras which includes Tarski’s relation algebras. We determine the constraint satisfaction properties of small nonassociative algebras and determine the representability of all nonassociative algebras on up to four atoms.