what are some examples of implicit operations in finite semigroups other than expressions involving $\omega$? Like $x^\omega y^\omega$ or $x^{\omega+1}$. By Reiterman's theorem, pseudovarieties of finite semigroups are given by a set of pseudoidentities, yet all the examples I've seen involve the $(-)^\omega$ operation. I haven't find anything, but I admit I don't know what's the best place to look for such things.

In case it's not standard notation: In finite semigroup $S$ and for any element $x\in S$ by $x^\omega$ we mean the unique idempotent in the subsemigroup generated by $x$.

  • $\begingroup$ I did not know that $x^\omega$ existed. Can you provide a link to a proof? Cheers! $\endgroup$ – Robert Lewis Sep 26 '18 at 15:47
  • 1
    $\begingroup$ @RobertLewis it exists in finite semigroups, I will edit it in. Since the semigroups is finite, there have to be two smallest exponents $l, n$ s.t. $x^l = x^{l+n}$, the cycle $x^l, x^{l+1}, \dots, x^{l+n-1}$ is a subgroup hence it contains only one idempotent, the neutral element of the group. I'm sure you can convince yourself of the details. $\endgroup$ – liczman Sep 26 '18 at 15:54
  • $\begingroup$ Yes, I think I can probably do that. Thanks. $\endgroup$ – Robert Lewis Sep 26 '18 at 15:56

First of all, the set of all implicit operations on finite semigroups (on a given alphabet $A$) can be identified with the free profinite monoid. This monoid is the completion of the free monoid $A^*$ for the profinite metric $d$, defined as follows.

A monoid morphism $f:A^* \rightarrow M$ separates two words $u$ and $v$ of $A^*$ if $f(u) \not= f(v)$. By extension, we say that a monoid $M$ separates two words if there is a morphism from $A^*$ onto $M$ that separates them. Given two words $u, v \in A^*$, we now set \begin{align*} r(u,v) &= \min \left\{|M| \mid \text{$M$ is a monoid that separates $u$ and $v$} \right\} \\ d(u,v) &= 2^{-r(u,v)} \end{align*} with the usual conventions $\min \emptyset = +\infty$ and $2^{-\infty} = 0$.

Then $d$ is a metric (it is even an ultrametric) and the completion $\widehat{A^*}$ of the metric space $(A^*, d)$ is a compact topological monoid. Indeed, one can show that the product is uniformly continuous on $A^*$ and hence extends by continuity to $\widehat{A^*}$.

The elements of $\widehat{A^*}$ are called profinite words. Given a word, or even a profinite word, one can show that the sequence $u^{n!}$ is Cauchy and hence converges to an element $u^\omega$. Moreover $u^\omega$ is an idempotent of $\widehat{A^*}$.

Since $A^*$ is countable, there are also countably many profinite words involving the $(-)^\omega$ operator. But as $\widehat{A^*}$ is uncountable, there are way more profinite words, but it is not so easy to give examples. Since $\widehat{A^*}$ is compact, one can extract a converging sequence from any sequence of words and its limit will be a profinite word. However, this does not give an explicit example.

First example. For each prime $p$, the sequence $u^{p^{n!}}$ is Cauchy and hence converges to an element denoted $u^{p^\omega}$.

Second example. Let us fix a total order on the alphabet $A$ and let $u_0, u_1, \ldots$ be the ordered sequence of all words of $A^*$ in the induced shortlex order. For instance, if $A = \{a, b \}$ with $a < b$, the first elements of this sequence would be $$ 1, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, \ldots $$ It is proved in [1, 2] that the sequence of words $(v_n)_{n \geq 0}$ defined by $$ v_0 = u_0 ,\ v_{n+1} = (v_nu_{n+1}v_n)^{(n+1)!} $$ converges to a profinite word $\rho_A$, which is idempotent and belongs to the minimal ideal of $\widehat{A^*}$.

[1] J. Almeida and M. V. Volkov, Profinite identities for finite semigroups whose subgroups belong to a given pseudovariety, J. Algebra Appl. 2,2 (2003), 137--163.

[2] N. R. Reilly and S. Zhang, Decomposition of the lattice of pseudovarieties of finite semigroups induced by bands, Algebra Universalis 44, 3-4 (2000), 217--239.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.