Equivalence of operations with respect to discriminator clones

Abstract: For each clone C on a set A there is an associated equivalence relation, called C-equivalence, on the set of all operations on A, which relates two operations iff each one is a substitution instance of the other using operations from C. In this paper we prove that if C is a discriminator clone on a finite set, then there are only finitely many C-equivalence classes. Moreover, we show that the smallest discriminator clone is minimal with respect to this finiteness property. For discriminator clones of Boolean functions we explicitly describe the associated equivalence relations.

Review text

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.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Equivalence of operations with respect to discriminator clones

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1011699)