Triviality of promise polymorphisms

Abstract

Given two $m$-ary predicates $P,Q$, an $n$-ary polymorphism is a tuple $(f_1,\dots ,f_m)$ of functions such that $x^{(1)},\dots ,x^{(n)}\in P$ implies $(f_1(y_1),\dots ,f_m(y_m))\in Q$, where $y_i=(x_i^{(1)},\dots ,x_i^{(m)})$. This generalizes the usual definition in universal algebra, in which $P=Q$ and $f_1=\cdots =f_m$. In earlier work, we studied when all polymorphisms of a single predicate are "trivial": either all depend on a single coordinate (common to all of them), or they constitute a "certificate" for the predicate. We showed that it suffices to check this condition for $2$-ary polymorphisms, and even for $1$-ary polymorphisms, modulo an explicit list of obstructions. In this paper we generalize the first result to the $P,Q$ setting, for a relaxed notion of certificate. We also generalize the second result in the promise setting, in which $P,Q$ range over the same alphabets and $P\subseteq Q$.

14 pages

Topics & keywords