Complete reducibility of systems of equations with respect to \(\mathbf R\). (Q2479751): Difference between revisions

It is shown that the pseudovariety \(\mathbf R\) of all finite \(\mathcal R\)-trivial semigroups is completely reducible with respect the canonical signature. A pseudoword is an element of the \(A\)-generated free profinite semigroup \(\overline\Omega_AS\), where \(A\) is a finite alphabet and \(S\) is a semigroup. A semigroup \(S\) satisfies the pseudoidentity \(u=v\), if \(\varphi(u)=\varphi(v)\) for any continuous morphism \(\varphi\colon\overline\Omega_AS\to S\). Let \(\sigma\) be a set of pseudowords, called an implicit signature. The pseudovariety \(\mathbf V\) is \(\sigma\)-reducible for a class of equation systems if the existence of a solution modulo \(\mathbf V\) of any system in the class entails the existence of a solution in \(\sigma\)-terms. The signature \(\sigma\) should also possess reasonable algorithmic properties, (1) as a set, \(\sigma\) should be recursively enumerable; (2) as implicit operations, the elements of \(\sigma\) should be effectively computable in finite semigroups; (3) the word problem for the free \(\sigma\)-algebra in the variety generated by \(\mathbf V\) should be decidable. A pseudovariety is completely \(\sigma\)-reducible if it is \(\sigma\)-reducible for all finite systems of pseudoword equations in which the pseudowords that define the equations are given by \(\sigma\)-terms. The implicit signature most often consists of just two pseudowords: \(ab\), representing semigroup multiplication, and \(a^{\omega-1}\), the unary pseudoinverse. This signature is called canonical and denoted by \(\kappa\). The main result: The pseudovariety \(\mathbf R\) is completely \(\kappa\)-reducible.