Orbit-finite 0-simple semigroups

We ask the question of how the Rees-Suskevitch theorem should be generalised to provide representations of orbit-finite 0-simple semigroups. We believe that orbit-finite groupoids will be useful for this.

Semigroups

A semigroup is a set $S$ associated with an associative operation $S\times S\to S$ . By $S^1$ we denote the monoid obtained by adjoining $S$ with a neutral element. We say that:

$x$ is a prefix of $y$ if $y=xs$ for some $s\in S^1$ ,
$x$ is a suffix of $y$ if $y=sx$ for some $t\in S^1$ ,
$x$ is an infix of $y$ if $y=sxt$ for some $t\in S^1$ .

These three relations define preorders on $S$ . We call the corresponding equivalence relations prefix equivalence, suffix equivalence and similarity. We also define bi-equivalence to be the intersection of prefix and suffix equivalence, i.e., $x$ and $y$ are bi-equivalent if they are both prefix and suffix equivalent.

We call the equivalence classes of these relations, respectively, prefix classes, suffix classes, similarity classes and bi-classes.

Remark. In semigroup theory, those equivalence relations are denoted $\mathcal R, \mathcal L,\mathcal J,\mathcal H$ , respectively, and are called Green’s relations.

Semigroups from groupoids

Every groupoid (see the previous post) $M$ defines a semigroup, whose elements are the arrows of $M$ together with an additional element $0$ , and $f\cdot g=f;g$ if the composition $f;g$ is defined and $0$ otherwise.

Example 1. Consider the semigroup $S$ associated to a groupoid $M$ . Let $s,t$ be two nonzero elements in $S$ , i.e., two arrows in $M$ . They are similar iff $s$ factorizes through $t$ and vice-versa. They are prefix-equivalent iff they have the same source, suffix-equivalent iff they have the same target, and are bi-equivalent iff they have both the same source and targets. Bi-classes are of the form $M(x,y)$ , where $x,y$ are objects of $M$ . All bi-classes of similar elements are in bijection, by Lemma 1.

0-simple semigroups

The semigroup $S$ associated to a connected groupoid $M$ has several special properties:

It is has a zero element, i.e., an element $0$ such that $0\cdot s=s\cdot 0=0$ for all elements $s\in S$ ,
It is a $0$ -simple semigroup, i.e., all non-zero elements are similar.

Below is another example of a $0$ -simple semigroup.

Example 2. Fix two sets $I,J$ and a group $G$ . Let $m:J\times I\to G\cup \set{\bot}$ be a fixed mapping. We define a semigroup structure on $I\times G\times J\cup\set{\bot}$ as follows:

$\!\!\!\!\!\!(i,g,j)\cdot (i',g',j')=\\\begin{cases}(i,g\cdot m(j,i')\cdot g',j')&\text{if }m(j,i')\neq \bot}\\\bot&\text{otherwise}.$

We denote this semigroup by $R(I,J,m)$ . This is a $0$ -simple semigroup. Note that two elements are prefix equivalent iff their first coordinate agrees and are suffix equivalent iff their last coordinate agrees.

Theorem (Rees-Suskevitch). Let $S$ be a finite $0$ -simple semigroup. Then $S$ is isomorphic to a semigroup of the form $R(I,J,m)$ , where $I$ is the set of prefix-classes of $S$ , $J$ is the set of suffix classes of $S$ , $G$ is some group and $m:J\times I\to G\cup\set{\bot}$ is some function.

The finiteness assumption in the theorem can be replaced by the assumption that the semigroup is completely $0$ -simple (has a minimal left ideal and a minimal right ideal), which is the case in all orbit-finite semigroups.

Example 3. Consider the set $S$ of all partial bijections of $\atoms$ whose domain and range have exactly two elements, extended by the element $\bot$ . This forms a semigroup:

$f\cdot g=\begin{cases} f;g&\text{if \textrm{rg}(f)=\textrm{dom}(f)}\\\bot&\text{otherwise}.$

The semigroup $S$ is $0$ -simple, and in fact is isomorphic to the semigroup associated to the groupoid $\textrm{Iso}_{A}$ (see previous post) where $A$ is the alphabet consisting of unordered pairs of atoms.

To represent the semigroup $S$ as a semigroup of the form $R(I,J,m)$ , set $I=J=P_2(\atoms)$ , $G=\mathbb Z_2$ , and $m(j,i)=0$ for all $j\in J,i\in I$ . The isomorphism between $S$ and $R(I,J,m)$ is not finitely supported.

The problem we would like to resolve is:

Problem: Find a generalization of the Rees-Suskevitch theorem which provides an equivariant representation of an equivariant $0$ -simple semigroup.

We believe that orbit-finite groupoids will be useful for obtaining such a result. Below is an example where it is unclear how a representation might look like.

Example 4. Let $X$ be the set consisting of all sets of the form $\bar \alpha=\set{\alpha_1,\alpha_2,\alpha_3}$ , (the number $3$ is irrelevant here) where $\alpha_1,\alpha_2,\alpha_3$ are bijections between two-element sets of atoms, all with the same range but pairwise-distinct domains. Define $\set{\alpha_1,\alpha_2,\alpha_3}\cdot \set{\beta_1,\beta_2,\beta_3}$ to be equal to $\set{\alpha_1;\beta_i, \alpha_2;\beta_i, \alpha_3;\beta_i,}$ if the range of $\alpha_1,\alpha_2,\alpha_3$ is equal to the domain of $\beta_i$ , and $\bot$ otherwise. This forms a $0$ -simple semigroup. The suffix class of $\set{\alpha_1,\alpha_2,\alpha_3}$ is identified by the common range of the three mappings. The prefix class, on the other hand, is identified by the set of mappings $\set{\alpha_i;\alpha_j^{-1}: 1\le i<j\le 3}$ .

Schützenberger groupoids

One way to obtain a groupoid from a 0-simple semigroup $S$ is as follows. For $s\in S$ , denote by $\rho_s:S\to S$ the mapping defined by $\rho_s(t)=t\cdot s$ , and by $\lambda_s:S\to S$ the mapping defined by $\lambda_s(t)=s\cdot t$ .

Denote by $G_R$ the following category:

The objects are bi-classes of $S$
The arrows are of the form $H_1\stackrel {f} \rightarrow H_2$ , where $f:H_1\to H_2$ is the restriction of a mapping $\rho_s$ to $H_1$ for some $s$ such that $\rho_s(H_1)\subset H_2$ , i.e., $H_1\cdot s\subseteq H_2$ .

Lemma. The category $G_R$ is a groupoid. Its connected components are the prefix-classes of $S$ .

We call $G_R$ the (right) Schützenberger groupoid associated to $S$ . The left one is defined symmetrically, using $\lambda_s$ instead of $\rho_s$ , and is denoted $G_L$ , and its connected components are the suffix classes of $S$ .

Lemma. Let $x,y$ be bi-classes of $S$ . The groups $G_R(x,x)$ and $G_L(y,y)$ are anti-isomorphic.

Note that the groupoids $G_R$ and $G_L$ are usually not anti-isomorphic as they have different sets of connected components.The group $G_L(x,x)$ is (isomorphic to) the group $G$ which appears in the Rees-Suskevitch theorem.

This will be studied in detail in the folowing post.

Atompress

Orbit-finite 0-simple semigroups

Semigroups

Semigroups from groupoids

0-simple semigroups

Schützenberger groupoids

Leave a Reply Cancel reply

Computation with atoms