Descending chains and antichains of the unary, linear, and monotone subfunction relations (Q862976): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 02:26, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Descending chains and antichains of the unary, linear, and monotone subfunction relations |
scientific article |
Statements
Descending chains and antichains of the unary, linear, and monotone subfunction relations (English)
0 references
25 January 2007
0 references
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.
0 references
clones
0 references
partial orders
0 references
linear functions
0 references
monotone functions
0 references
Menger systems
0 references
Green's relations
0 references