Generating primitive positive clones (Q1866838): Difference between revisions

A primitive positive formula is a first-order formula of the form \(\exists \;\wedge \) (atomic). A clone \(C\) on a set \(A\) is a primitive positive clone if every operation on \(A\) defined from operations in \(C\) using a primitive positive formula is again in \(C\). \textit{S. Burris} and \textit{R. Willard} [Proc. Am. Math. Soc. 101, 427-430 (1987; Zbl 0656.08002)] proved that there are finitely many primitive positive clones on any finite set. They conjectured that every such primitive positive clone is actually generated from its members of rank \(|A|\) if \(A\) has more than two elements. Suppose that for a finite algebra \textbf{A}, PPC\# (\textbf{A}) is the smallest number \(n\) for which PPC(Clo\textbf{A}), the primitive positive clone generated by Clo\textbf{A}, is equal to PPC(Clo\(_n\)\textbf{A}). In the paper the author discusses the problem how large PPC\# (\textbf{A}) can be when special conditions are assumed for the finite algebra \textbf{A}. It is shown that PPC\# (\textbf{A})\(\leq |A|+2\) if \textbf{A} generates a congruence permutable variety and every subalgebra of \textbf{A} is the product of a congruence neutral algebra and an Abelian algebra. PPC\# (\textbf{A})\(\leq |A|\) holds when the variety generated by \textbf{A} is congruence distributive, Abelian or decidable. Furthermore, an example is given for which PPC\# (\textbf{A})\(\geq (|A|-1)^2.\)