Isotone analogs of results
by Mal'tsev and Rosenberg

Benoit Larose

Abstract: We prove an analog of a lemma by Mal'tsev and deduce the following analog of a result of Rosenberg [R]: let $Q$ be a finite poset with $n$ elements, let $\k$ denote the $k$-element chain, and let $h$ be an integer such that $2\leq h n\leq k$. Consider the set of all order-preserving maps from $Q$ to $\k$ whose image contains at most $h$ elements, viewed as an $n$-ary relation $\mu_{Q,h}$ on $\k$. Then an $l$-ary order-preserving operation $f$ on $\k$ preserves this relation if and only if it is either (i) essentially unary or (ii) the cardinality of $f(e(Q))$ is at most $h$ for every isotone map $e:Q\rightarrow \k^l$. In other words, if an increasing $k$-colouring of the grid $\k^l$ assigns more than $h$ colours to a homomorphic image of the poset $Q$, then there is such an image that lies in a subgrid $G_1 \times \dots \times G_l$ where each $G_i$ has size at most $h$, or otherwise the colouring depends only on one variable.

[R] Rosenberg, I. G.: Completeness properties of multiple-valued logic algebras. Computer Science and Multiple-Valued Logic, Theory and Applications, D. C. Rine (ed.), North-Holland 1977, 142--186.

Keywords: Order-preserving operation, chain, clone

Classification (MSC2000): 06A11, 08A99, 08B05

Full text of the article:

• Compressed PostScript file (76 kilobytes)
• PDF file (160 kilobytes)