Equivalence of operations with respect to discriminator clones (Q1011699): Difference between revisions

Let \(A\) be a set, \({\mathcal O}_A\) the set of all finitary operations on \(A\), and \(\mathcal C\) a clone on \(A\). For every \(f,g\in{\mathcal O}_A\), one says that \(f\) is a \(\mathcal C\)-minor of \(g\), in symbols \(f\leq_{{\mathcal C}}g\), if \(f\) can be obtained from \(g\) by substituting operations from \(\mathcal C\) for the variables of \(g\); \(f\) and \(g\) are \({\mathcal C}\)-equivalent, in symbols \(f\equiv{{\mathcal C}}g\), if \(f\leq_{{\mathcal C}}g\) and \(g\leq_{{\mathcal C}}f\). This concept, due to the first author, generalizes, e.g., Boolean minors and Green's relation. The discriminator function on \(A\) is \(t\in{\mathcal O}_A\) defined by \(t(x,y,z)=\) if \(x=y\) then \(z\), else \(x\). Then \(\mathcal C\) is called a discriminator clone if it contains \(t\), and locally closed if every \(f\in{\mathcal O}_A\) has the property that for every finite subset \(U\subseteq A^n\), where \(n\) is the arity of \(f\), there is \(g\in{\mathcal C}\) such that \(f(u)=g(u)\) for all \(u\in U\). Theorem 3.3 characterizes the relation \(\leq_{{\mathcal C}}\) for a locally closed discriminator clone. Then it is proved that if \(A\) is a finite set of cardinality \(\geq 2\) then for each discriminator clone \(\mathcal C\) the equivalence \(\equiv_{{\mathcal C}}\) has finite index in \({\mathcal O}_A\). The converse holds in any two-element set, but not in sets of cardinality \(>2\). The clone \(\mathcal D\) generated by the discriminator function \(t\) is minimal with the property that \(\equiv_{{\mathcal D}}\) is of finite index. The last theorem characterizes the relation \(\leq_{{\mathcal C}}\) for any of the six discriminator clones of Boolean functions.