Descending chains and antichains of the unary, linear, and monotone subfunction relations (Q862976): Difference between revisions

Let \(C\) be a set of finitary functions on a fixed nonempty finite base set \(A\). Then an \(n\)-ary function \(f\) on \(A\) is called a \(C\)-subfunction of an \(m\)-ary function \(g\) on \(A\) if there exist \(n\)-ary functions \(h_1, \dots,h_m\in C\) such that \(f=g(h_1,\dots,h_m)\). This \(C\)-subfunction relation is a preorder (i.e., reflexive and transitive) if and only if \(C\) is a clone on \(A\). If \(f\) and \(g\) are \(C\)-subfunctions of each other, then they are called \(C\)-equivalent. For a clone \(C\), we obtain an equivalence relation and a partial order on the corresponding quotient set. In the present paper, this partial order is studied for the following clones on \(A\): (i) the clone of all functions; (ii) clones of essentially unary functions; (iii) clones of linear functions (with respect to a field structure on \(A)\); (iv) clones of monotone functions (with respect to any partial order on \(A)\). In particular, the existence of infinite descending chains and infinite antichains is investigated. It is shown that in the cases (i), (ii) and (iii) there exist no infinite descending chains, whereas in all non-trivial cases (iv) infinite descending chains exist. Furthermore, it is shown that in case (i) there exists no infinite antichain, whereas in all other non-trivial cases (ii), (iii) and (iv), infinite antichains exist.