Endolocality meets homomorphism-homogeneity: a new approach in the study of relational algebras

Abstract

We study the problem of characterizing all relations that can be defined from the fundamental relations of a given relational structure using positive existential formulæ. The notion of κ-endolocality is introduced in order to measure the complexity of relational structures with respect to this task. The hierarchy of κ-endolocal structures is thoroughly analysed in algebraic and model-theoretic ways. Interesting cross-connections with homomorphism-homogeneous relational structures are revealed. The interrelations between endolocal relational structures and several model-theoretic notions are collected in the Main Theorem. This Main Theorem is demonstrated to be a useful tool for studying relational algebras and, in particular, weak Krasner algebras. For example, a short proof of F. Börners characterization of weak Krasner clones on a countable set is given.