Key (critical) relations preserved by a weak near-unanimity function (Q522228)

An \(h\)-ary relation \(\rho\) is called a \(key\) \(relation\) if every \(h\)-tuple which is not from \(\rho\) can be mapped to a given \(h\)-tuple which is not in \(\rho\) by a vector-function preserving \(\rho\). This property seems to be profitable because it is a combinatorial property of a relation which does not involve any difficult objects (no clones, no relational clones, no primitive positive formulas). It is proved that all clones on finite sets can be defined by only key relations. The author presents a nice description of all key relations on a two-element set. It is shown that these are exactly the relations that can be defined as a disjunction of linear equations. However in general, key relations do not have such a nice description. Nevertheless, a nice characterization of all key relations preserved by a weak near-unanimity operation is obtained.