Deciding some embeddability problems for semigroups of mappings
In the paper the authors give a simple way of showing that the problem of embeddability into finite inverse semigroups and finite semigroups of order-preserving mappings is decidable. The authors write \(S\leqslant T\) to indicate that \(S\) is a subsemigroup of a semigroup \(T\), and \(|A|\) to denote the cardinality of a set \(A\). Also they denote by \(PT(X)\) the semigroup of all partial mappings on \(X\) under composition.NEWLINENEWLINENEWLINEIn the paper the authors prove the following Embedding Theorem. Let \(S\leqslant T\), where \(T\leqslant PT(X)\) is closed under restrictions and \(S\) is a semigroup of finite cardinality \(n\). Then \(S\) embeds in the subsemigroup \(T\cap PT(Y)\) for some subset \(Y\) of \(X\) with \(|Y|\leq(\tfrac n2+1)^2\). As a corollary of this theorem the authors obtain the statement, that the question of whether or not a finite semigroup can be embedded into a finite inverse semigroup, or a finite semigroup of partial order-preserving mappings, or a semigroup of total order-preserving mappings, is decidable.NEWLINENEWLINENEWLINEAlso examples of left zero semigroups of order \(n\) suitable embedded into certain partial transformation semigroups \(PT(Y)\) for which the bound \(|Y|\leq(\tfrac n2+1)^2\) is best possible are constructed. The final result of the paper states that for a finite group \(G\) the set \(Y\) from the Embedding Theorem can be chosen so that \(|Y|\leq n\).NEWLINENEWLINEFor the entire collection see [Zbl 0954.00028].
- Deciding embeddability of partial groupoids into semigroups
- Some undecidable embedding problems for finite semigroups
- scientific article; zbMATH DE number 4093772
- An embedding theorem for semigroups of continuous selfmaps
- On some conditions for the embeddability of semigroups in groups
- scientific article; zbMATH DE number 848029
- On the question of embedding a semigroup into a semiband.
- scientific article; zbMATH DE number 3882594
- Embedding semigroups in \({\mathcal D}\)-trivial semigroups
- scientific article; zbMATH DE number 2202596
- Deciding embeddability of partial groupoids into semigroups
- scientific article; zbMATH DE number 3863478 (Why is no real title available?)
- scientific article; zbMATH DE number 4089808 (Why is no real title available?)
- scientific article; zbMATH DE number 17303 (Why is no real title available?)
- Some undecidable embedding problems for finite semigroups
- The Universal Theory of Ordered Equidecomposability Types Semigroups
- scientific article; zbMATH DE number 3998446 (Why is no real title available?)
- scientific article; zbMATH DE number 848029 (Why is no real title available?)
- On finite semigroups embeddable in inverse semigroups.
- On divisors of semigroups of order-preserving mappings of a finite chain.
This page was built for publication: Deciding some embeddability problems for semigroups of mappings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2709038)
