Relative completeness (Q2763578)

Let \(P_k\) denote the set of all maps \(E_k^n \longrightarrow E_k\), for all \(n \in N\), where \(E_k = \{1,\dots,k\}\). A clone on \(E_k\) is a subset of \(P_k\) which contains all the projections \(f(x_1,\dots,x_n) = x_i\), and which is closed w.r.t. superpositions. Given a clone \(C\), a subset \(F\) of \(P_k\) is \(C\)-complete if the clone generated by \(P \cup C\) is equal to \(P_k\). It is known that \(F\) is \(C\)-complete iff \(F\) contains at least one mapping outside \(M_i\), where \(M_i\) is an arbitrary maximal clone containing \(C\). Six special sets of relations, denoted \(R_1,\dots,R_6\), are known to be sufficient for characterization of maximal clones.NEWLINENEWLINENEWLINE\(C\)-completeness w.r.t. four specified clones \(C\) (which were found to be of particular interest) is considered. These clones are generated by minimum and complement, by two negations, by transpositions, and by two unary functions, respectively. In each case, maximal clones containing \(C\) are detected by investigating relationships between the elements of \(C\) and the sets \(R_1,\dots,R_6\).NEWLINENEWLINENEWLINEThe paper consists of an extensive list of statements (64 statements are listed on less than five pages) without proofs, related to the established relationships of the above type.NEWLINENEWLINEFor the entire collection see [Zbl 0977.00022].