Dominions and Primitive Positive Functions

Abstract

Let A <= B be structures, and K a class of structures. An element b in B isdominated by A relative to K if for all C in K and all homomorphisms g,g´ : B -> C such that g and g´ agree on A, we have g = g´. Our main theorem states that if K is closed under ultraproducts, then A dominates b relative to K if and only if there is a partial function F definable by a primitive positive formula in K such that F(a1 ,...,an) = b for some a1,...,an in A. Applying this result we show that a quasivariety of algebras Q with an n-ary near-unanimity term has surjective epimorphisms if and only if SPPu(Q_RSI) has surjective epimorphisms. It follows that if F is a finite set of finite algebras with a common near-unanimity term, then it is decidable whether the (quasi)variety generated by F has surjective epimorphisms.