A complete classification of endomorphisms of Kiselman’s semigroup
Luka Andrenšek · 2025
Read A complete classification of endomorphisms of Kiselman’s semigroup by Luka Andrenšek (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-03604.txt.
Introduction
Luka Andrenšek settles a standing question by sorting all endomorphisms of Kiselman's semigroup. The paper from twenty twenty-five closes a problem posed by Kudryavtseva and Mazorchuk. Endomorphisms are maps from the semigroup to itself that keep its product rule. A full census of them was missing. Andrenšek supplies it in complete form.
The classification pins down every such map by type. A Boolean matrix monoid is then exhibited that mirrors the endomorphism set exactly. That mirror gives the abstract census a concrete face: matrix moves stand in for semigroup maps. The result is short and final in flavor, a classification theorem rather than a method. It serves semigroup theory, where Kiselman's example is a standard test object.
Catalog record
| CREATOR | Luka Andrenšek |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 15 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-03604
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A complete classification of endomorphisms of Kiselman’s semigroup Luka Andrenšek Abstract . Let K n K_{n} denote Kiselman’s semigroup. It was thoroughly studied in Kudryavtseva and Mazorchuk’s paper On Kiselman’s semigroup. The authors in that paper pose a question, whether is it possible to classify all endomorphisms of K n K_{n} (Question 21). In this paper we give a complete classification and provide a boolean matrix semigroup that is isomorphic to End ( K n ) \text{End}(K_{n}) . 1. Introduction Kiselman’s semigroup was first introduced in [ 2 ] , having roots in convexity theory. It was later generalized and studied in [ 1 ] . It admits interesting combinatorial properties and is related to some graph dynamical systems [ 3 ] . In [ 1 ] the authors show that the only automorphism which K_{n} admits is the identity and the only antiautomorphism is the unique extension of the map a_{i}\mapsto a_{n-i+1} . They leave the question regarding the classification of endomorphisms open and has to date not been conclusively answered. 2. Main result In the present paper we show that the monoid \text{End}(K_{n}) is isomorphic to the following boolean matrix semigroup, equipped with the usual boolean matrix multiplication. We denote this monoid by D_{n} . \displaystyle D_{n}=\{M\in\{0,1\}^{n\times n}\mid\forall i,j\in\{1,2,\dots,n\}.\hskip 2.84526ptj>i\Rightarrow(M_{xj}=1,M_{xi}=0,M_{yj}=0,M_{yi}=1\Rightarrow x>y)\} Where M_{kl} denotes the entry in the matrix M in the k -th row and l -th column. In plain language, this is the set of boolean n\times n matrices which do not admit the following 2\times 2 submatrix (pattern) \displaystyle\begin{bmatrix}0&1\\ 1&0\end{bmatrix} 3. Preliminaries Let \mathcal{A}=\{a_{1},a_{2},\dots,a_{n}\} be a finite alphabet. We define K_{n} by \displaystyle K_{n}=\langle a_{1},a_{2},\dots,a_{n}\mid a_{i}^{2}=a_{i},\hskip 2.84526pta_{i}a_{j}a_{i}=a_{j}a_{i}a_{j}=a_{j}a_{i},\hskip 2.84526pt1\leq i<j\leq n\rangle. Let X\subset\{1,2,\dots,n\} . If X=\emptyset put e_{X}=e , the unit element in K_{n} . Otherwise, assume X=\{i_{1},i_{2},\dots,i_{k}\} , where i_{1}>i_{2}>\dots>i_{k} . Then put e_{X}=a_{i_{1}}a_{i_{2}}\dots a_{i_{k}} . Now put E_{n}=\{e_{X}\mid X\subset\{1,2,\dots,n\}\} . In [ 1 ] it is shown that every element of E_{n} is an idempotent, they are all distinct, and every idempotent is of the form e_{X} , for some X\subset\{1,2,\dots,n\} . Consequently, the number of idempotents in K_{n} is precisely 2^{n} . Furthermore, in [ 1 ] the following proposition is proven. Proposition 3.1 . Let X,Y\subset\{1,2,\dots,n\} . Then the following conditions are equivalent. (1) e_{X}e_{Y} is an idempotent (2) e_{X}e_{Y}=e_{X\cup Y} (3) \forall x\in X\setminus Y.\hskip 2.84526pt\forall y\in Y\setminus X.\hskip 2.84526ptx>y Also define the content map c:K_{n}\rightarrow 2^{\{1,2,\dots,n\}} , where c(a) is the set of all i ’s, for which a_{i} appears in a . In [ 1 ] it is shown that this map is indeed well defined. Furthermore the following proposition holds. Proposition 3.2 . The map c is an epimorphism from K_{n} to the semigroup (2^{\{1,2,\dots,n\}},\cup) . 4. The braid relation for idempotents We prove the following lemma. Lemma 4.1 . Let X,Y\subset\{1,2,\dots,n\} . The following two conditions are equivalent. (1) \forall x\in X\setminus Y.\hskip 2.84526pt\forall y\in Y\setminus X.\hskip 2.84526ptx>y (2) e_{X}e_{Y} is an idempotent and e_{X}e_{Y}e_{X}=e_{Y}e_{X}e_{Y}=e_{X}e_{Y} Proof. (2)\Rightarrow(1) is immediate from ( 3.1 ). (1)\Rightarrow(2) Because of ( 3.1 ) we only need to show the equalities e_{X}e_{Y}e_{X}=e_{Y}e_{X}e_{Y}=e_{X}e_{Y} . Since e_{X}e_{Y} is an idempotent, it is equal to e_{X\cup Y} . Notice condition (3) from ( 3.1 ) holds for the pairs of sets X\cup Y,X and Y,X\cup Y respectively. It follows that \displaystyle e_{X}e_{Y}e_{X}=(e_{X}e_{Y})e_{X}=e_{X\cup Y}e_{X}=e_{(X\cup Y)\cup X}=e_{X\cup Y}=e_{X}e_{Y} and furthermore \displaystyle e_{Y}e_{X}e_{Y}=e_{Y}(e_{X}e_{Y})=e_{Y}e_{X\cup Y}=e_{Y\cup(X\cup Y)}=e_{X\cup Y}=e_{X}e_{Y} This concludes the proof. ∎ 5. Isomorphism to monotone sets In this section, we will construct an isomorphism from \text{End}(K_{n}) to a set of sets, satisfying the monotonicity condition. Definition 5.1 . Let \mathbf{X}=(X_{1},X_{2},\dots,X_{n}) be a sequence of sets, where X_{i}\subset\{1,2,\dots,n\} for 1\leq i\leq n . \mathbf{X} is said to be monotone, if \displaystyle\forall i,j\in\{1,2,\dots n\}.j>i\Rightarrow\hskip 2.84526pt\forall x\in X_{j}\setminus X_{i}.\hskip 2.84526pt\forall y\in X_{i}\setminus X_{j}.\hskip 2.84526ptx>y We denote by M_{n}=\{(X_{1},X_{2},\dots,X_{n})\mid(X_{1},X_{2},\dots,X_{n})\hskip 2.84526pt\text{is monotone}\} . On the set M_{n} we define a binary operation \ast in the following way. Let \mathbf{X}=(X_{1},X_{2},\dots,X_{n}) and \mathbf{Y}=(Y_{1},Y_{2},\dots,Y_{n}) be elements in M_{n} . We put \mathbf{Z}=\mathbf{X}\ast\mathbf{Y} , where \displaystyle Z_{i}=\bigcup\limits_{j\in Y_{i}}X_{j} One can easily show that (M_{n},\ast) is a monoid, with its unit element being the sequence (\{1\},\{2\},\dots,\{n\}) . The following theorem holds. Theorem 5.2 . The map \Phi:\operatorname{End}(K_{n})\rightarrow M_{n} , defined as \displaystyle\Phi(\varphi)=(c(\varphi(a_{1})),c(\varphi(a_{2})),\dots c(\varphi(a_{n}))) is an isomorphism of monoids (\operatorname{End}(K_{n}),\circ) and (M_{n},\ast) . Proof. First we must prove, that for each \varphi\in\operatorname{End}(K_{n}) , \Phi(\varphi) lies in M_{n} . Therefore, let \varphi\in\operatorname{End}(K_{n}) . Since \varphi is a homomorphism, \varphi(a) is an idempotent, whenever a is an idempotent. Hence, \varphi(a_{i}) is an idempotent for 1\leq i\leq n . It follows that there exists a sequence (X_{1},X_{2},\dots,X_{n}) of subsets of \{1,2,\dots,n\} , for which \displaystyle\varphi(a_{i})=e_{X_{i}} for 1\leq i\leq n and thus we have \Phi(\varphi)=(X_{1},X_{2},\dots,X_{n}) . Now notice that a_{j}a_{i} is an idempotent, whenever j>i , in which case we ofcourse also have a_{j}a_{i}a_{j}=a_{i}a_{j}a_{i}=a_{j}a_{i} . Apply \varphi to these equalities and again use the fact that \varphi must preserve idempotents, it follows \displaystyle e_{X_{j}}e_{X_{i}}\hskip 2.84526pt is an idempotent and \displaystyle e_{X_{j}}e_{X_{i}}e_{X_{j}}=e_{X_{i}}e_{X_{j}}e_{X_{i}}=e_{X_{j}}e_{X_{i}} whenever j>i . From ( 4.1 ) it follows that whenever j>i , the condition \displaystyle\forall x\in X_{j}\setminus X_{i}.\hskip 2.84526pt\forall y\in X_{i}\setminus X_{j}.\hskip 2.84526ptx>y must be satisfied. This implies the monotinicity of (X_{1},X_{2},\dots,X_{n}) and hence \Phi(\varphi)\in M_{n} . The fact that \Phi is injective follows easily, since for any endomorphism, its images of the generators are of the form e_{X_{i}} for some X_{i}\subset\{1,2,\dots,n\} . Notice also that an idempotent in K_{n} is uniquely defined by its content. And thus if two endomorphisms coincide on the generators, they must be the same. Now we prove surjectivity. Let \mathbf{X}=(X_{1},X_{2},\dots,X_{n})\in M_{n} . Define a map \psi:\{a_{1},a_{2},\dots,a_{n}\}\rightarrow K_{n} by \displaystyle\psi(a_{i})=e_{X_{i}} Put b_{i} = \psi(a_{i}) for 1\leq i\leq n . It is apparent that b_{i} are idempotents. Furthermore let j>i . Then because of 4.1 and the monotinicity condition imposed on (X_{1},X_{2},\dots,X_{n}) it must follow that \displaystyle b_{j}b_{i}b_{j}=b_{i}b_{j}b_{i}=b_{j}b_{i} Thus elements \{b_{1},b_{2},\dots,b_{n}\} follow the defining relations of K_{n} , therefore we can uniquely extend \psi to an endomorphism of K_{n} . By construction it follows \Phi(\psi)=\mathbf{X} . Now we prove that \Phi is indeed a homomorphism. Let \psi,\varphi\in\operatorname{End}(K_{n}) . Let \psi(a_{j})=e_{Y_{j}} and \varphi(a_{j})=e_{X_{j}} for 1\leq j\leq n . Also put e_{X_{i}}=a_{m_{l}}a_{m_{l-1}}\dots a_{m_{1}} . In particular X_{i}=\{m_{l},m_{l-1},\dots,m_{1}\} and m_{l}>m_{l-1}>\dots>m_{1} . We compute \displaystyle(\psi\circ\varphi)(a_{i}) \displaystyle=\psi(e_{X_{i}}) \displaystyle=\psi(a_{m_{l}}a_{m_{l-1}}\dots a_{m_{2}}a_{m_{1}}) \displaystyle=\psi(a_{m_{l}})\psi(a_{m_{l-1}})\dots\psi(a_{m_{2}})\psi(a_{m_{1}}) \displaystyle=e_{Y_{m_{l}}}e_{Y_{m_{l-1}}}\dots e_{Y_{m_{2}}}e_{Y_{m_{1}}} \displaystyle=e_{\cup_{1\leq k\leq l}Y_{m_{k}}} The last equality holds because (\psi\circ\varphi)(a_{i}) is an idempotent and because of ( 3.1 ). Now if we denote by (\Phi(\psi\circ\varphi))_{i} the i -th component of the sequence of sets \Phi(\psi\circ\varphi) , we get \displaystyle(\Phi(\psi\circ\phi))_{i} \displaystyle=c((\psi\circ\varphi)(a_{i})) \displaystyle=c(e_{\cup_{1\leq k\leq l}Y_{m_{k}}}) \displaystyle=\bigcup\limits_{k=1}^{l}Y_{m_{k}} \displaystyle=\bigcup\limits_{j\in X_{i}}Y_{j} Since X_{i}=\{m_{l},m_{l-1},\dots,m_{1}\} . On the other hand, one has \displaystyle(\Phi(\psi)\ast\Phi(\varphi))_{i} \displaystyle=((c(\psi(a_{1})),c(\psi(a_{2})),\dots c(\psi(a_{n}))) \displaystyle\ast(c(\varphi(a_{1})),c(\varphi(a_{2})),\dots c(\varphi(a_{n}))))_{i} \displaystyle=((Y_{1},Y_{2},\dots Y_{n})\ast(X_{1},X_{2},\dots X_{n}))_{i} \displaystyle=\bigcup\limits_{j\in X_{i}}Y_{j} Since i was chosen arbitrarily, we indeed have \displaystyle\Phi(\psi\circ\varphi)=\Phi(\psi)\ast\Phi(\varphi) And since the identity map is the unit of \operatorname{End}(K_{n}) , it follows \displaystyle\Phi(\operatorname{id}_{K_{n}})=(\{1\},\{2\},\dots,\{n\}) This concludes the proof. ∎ 6. Isomorphism to a boolean matrix monoid Definition 6.1 . Let n\in\mathbb{N} . Denote by D_{n} the following set \displaystyle D_{n}=\{M\in\{0,1\}^{n\times n}\mid\forall i,j\in\{1,2,\dots,n\}.\hskip 2.84526ptj>i\Rightarrow(M_{xj}=1,M_{xi}=0,M_{yj}=0,M_{yi}=1\Rightarrow x>y)\} In plain language, D_{n} is the set of boolean n\times n matrices which do not admit the following 2\times 2 submatrix: (1) \displaystyle\begin{bmatrix}0&1\\ 1&0\end{bmatrix} On the set D_{n} we define a binary operation \cdot as follows. Let A,B\in D_{n} , A=(a_{ij}) and B=(b_{ij}) . Then C=A\cdot B , where C=(c_{ij}) and \displaystyle