Group-symmetric semigroups

In the previous post the nature of Clifford semigroups was briefly discussed. We noticed that Clifford semigroups are divisibility commutative (because L=R). But due to complete regularity the Green's relations of Clifford semigroups have the further property that all non-trivial H classes form subgroups. We can therefore form a special subclass of the class of divisibility commutative semigroups that captures the divisibility properties of Clifford semigroups.

Definition. a semigroup is called group-symmetric if it is divisibility commutative and there are no non-trivial H classes that do not form groups.

The reason that I call these semigroups "group-symmetric" is that all the non-trivial components of the factorization preordering are a result of subgroups. Since subgroups are responsible for all factorization symmetry, antisymmetry is equivalent to aperiodicity. Here are three basic theorems about these semigroups:

• Clifford semigroups are group-symmetric
• All commutative semigroups of order four or less are group-symmetric
• Finite monogenic semigroups are group-symmetric

To see (1) first recall that Clifford semigroups are divisibility commutative by a previous theorem. Then by complete relugarity all H classes form subgroups, so there are no non-trivial H classes that do not form groups. To see (2) consider that Green's theorem demonstrates that a non-trivial H class that does not contain an idempotent must not contain the iterations of any of its own elements, so there must be a third element that is an element of these two. Additionally, the semigroup cannot be aperiodic because then it would be H-trivial since it is finite. So there needs to be a group which means at least two other elements need to exist to contain the group leading to a minimum of five elements. To see (3) compute the H classes of the finite monogenic semigroup. Clearly there is an H class containing the idempotent, but then every other element is H-trivial because a lesser iterate cannot be obtained from a larger one outside the group.

Starting with order five, there are commutative semigroups which are not group-symmetric. But these semigroups are not group-free because it is proven that all finite commutative aperiodic semigroups are antisymmetric and hence trivially group-symmetric. So even in those cases the symmetry in the semigroup is because of some subgroup. Those non-trivial H classes that are not subgroups are externally symmetric because they emerge from some group outside of themselves which operates on them to create some symmetry in the semigroup, which absent everything else would be antisymmetric like a finite commutative aperiodic semigroup.

Definition. the group elements of a semigroup are all those that are contained in some subgroup and the non-group elements are all those elements are not contained in a subgroup

The order of any finite semigroup is equal to the sum of the group elements count and the non-group elements count. So for example, example monogenic semigroups are classified by their period and index. The only difference is that their sum doesn't equal to the order of the semigroup because the index is never zero even for cyclic groups. So the non-group elements count is equal to the index minus one. The non-group elements count determines how far the semigroup is from being completely regular, and therefore in the group-symmetric case from being Clifford.

We saw how, particularly in the finite case, J-trivial semigroups generalize semilattices. Group-symmetric semigroups allow us to do the same thing for Clifford semigroups, which are often called semilattices of groups. So for example, given a group-symmetric semigroup we can form a Clifford semigroup from it which contains its ordered group structure. In the opposite direction, given a semilattice of groups we can form different group-symmetric semigroups which maintain the Cliffordic structure of that semigroup.

Clifford semigroups

Clifford semigroups are completely regular, inverse, divisibility commutative semigroups. Clifford semigroups are useful in the study of divisibility commutative semigroups (semigroups for which L=R). They are a little known class of semigroups with a suprisingly elegant theory. For the purposes of this discussion, we will focus on Clifford semigroups of finite order.

Cycle notation

The elements of an inverse semigroup can be represented as charts, or partial symmetries. These are the binary relations that are one to one in the sense that both the inputs and the outputs have no repetitions among themselves. The composition operation then is the composition of binary relations which is defined so that if a relation does not have an element as an input then that element goes to nothing. The empty binary relation therefore is a zero element of relation composition, because anything composed with the empty relation is the empty relation.

In the general case, partial symmetries need not have the same inputs and outputs. When they have the same inputs and outputs then they are partial permutations and not simply partial symmetries. The common set of inputs and outputs is simply the domain of the partial permutation. If a partial symmetry has different inputs and outputs, then after a single composition some of the inputs will vanish and the element will never be able to return to itself under composition. Therefore, it clearly cannot be part of a completely regular semigroup. Clifford semigroups are the semigroups of partial permutations so defined.

This produces an issue of notation. Group theorists are typically used to simply omitting the domain of permutations of permutation groups. The domain is assumed to come from the ground set of the group, but this doesn't work with Clifford semigroups where permutations can carry around different domains then one another. There are two different ways that we can denote a partial permutation: we can give each partial permutation a set or we can include all the one-cycles which would otherwise be omitted in the cycle notations. Since associating a set to every single permutation is potentially cumbersone, the later notation is preferred. That means that the cycle (0 1) on the domain #{0 1 2 3} is represented as the partial permutation (0 1) (2) (3) and the partial permutation (0 1) is the cycle on the smaller domain of only two elements.

Limits of composition:

The partial permutations that are composed together must match up in their common domains. So (0 1) composed in a last-first order with (1 2) is the binary relation {(2 0)} which is not a partial permutation because it has a set of inputs of {2} and a set of outputs of {0} which are clearly not equal as sets. On the other hand, (2 3) (0 1) composed with (0 1) (4 5) matches up because it produces the identity permutation (0) (1). Basically, the intersection domain of the two composed permutations must be a union of a subset of the connected components of the first permutation and the same for the second permutation. Otherwise, the partial permutations can produce elements outside of their domain.

This means that there is no symmetric clifford semigroup. In order to get something similar to that, it is necessary to go to the broader context of the symmetric inverse semigroup which consists of all partial symmetries without the limitation that they need to be permutations. But the symmetric inverse semigroup is not divisibility commutative except in the trivial case. Clifford semigroups can embedded within the symmetric inverse semigroup by taking certain completely regular subsets, but the join of two Clifford semigroups in the subsemigroups lattice of a symmetric inverse semigroup need not be Clifford.

The algebraic preorder:

Every single Clifford semigroup is associated with a natural algebraic preorder. An element x is less then a greater element y if there exists some c such that cx=y or xc=y or there exists c,d such that cxd=y. In other words, an element is less then another one if it can be used to express the greater element in some form in an expression. This completely matches up with the familiar algebraic preordering on commutative semigroups and because of divisibility commutative this is the only algebraic preorder that needs to be associated with the semigroup. Divisibility commutative allows us to treat certain non-commutative semigroups similarly to commutative ones.

Semilattices:
When we make the algebraic preorder antisymmetric we arrive semilattices. In a semilattice every element is idempotent, which means that as a partial permutation every element is going to be an identity permutation. The semilattice on the permutations {(), (0), (4), (5), (4)(5), (0)(1), (0)(2), (0)(3),(0)(1)(2)} is displayed below.



In these cases, the semigroup operation is simply the intersection of the domains of the identity permutations. So these are essentially intersection semilattices except that elements are represented as identity permutations rather then as sets.

Groups:
Clifford semigroups in which every partial permutation has the same domain are naturally permutation groups. The only difference is that the partial permutations include all their one cycles so that the full domain is specified. So for example, the Clifford semigroup {(0)(1)(2)(3),(0 1)(2)(3),(0)(1)(2 3),(0 1)(2 3)} forms a group because every partial permutation has the same domain. In that case, optionally we can ommit the single cycles and use the simpler group cycle notation. In a larger Clifford semigroup, it is easy to see that every identity permutation forms a subgroup around it. These maximal subgroups are clearly the H classes of the identity permutations, which are ensured to always form groups.

Examples

These exmaples will use the traditional table notation to denote semigroups. These semigroups can then be related to partial permutations that could generate them. The below semigroup is equivalent to the Clifford semigroup {(1)(2),(1 2),(1)(2)(3)(4),(1)(2)(3 4)}.

[ [ 1, 2, 1, 1 ], 
  [ 2, 1, 2, 2 ], 
  [ 1, 2, 3, 4 ], 
  [ 1, 2, 4, 3 ] ]

That semigroup is equally to the two cyclic groups ordinally summed together. The below semigroup also has two cyclic groups chained together in order, but they are chained together differently so it produces a semigroup. This can be seen from its partial permutations representation: {(1)(2),(1 2),(1)(2)(3)(4),(1 2)(3 4)}. The only difference is the partial permutation (1 2)(3 4) now has action on the cyclic subgroup above it.

[ [ 1, 2, 1, 2 ], 
  [ 2, 1, 2, 1 ], 
  [ 1, 2, 3, 4 ], 
  [ 2, 1, 4, 3 ] ]
 

Groups can always be ordinally combined together in any order to get a semilattice of groups. The reason that Clifford semigroups are non-trivial is that they can be combined together in different ways as demonstrated above in the simplest case. The action of a lower group on an upper group chained together in order is always determined by the composition of the lower element with the upper identity, which produces the permutation representation in the upper group. So lower elements can subsume some of the role of upper elements.

Divisibility commmutative regular semigroups

Divisibility commutative regular semigroups will be examined. But before doing so, its worth stating Green's theorem and its corollaries which are necessary for the other results.

Green's theorem: the H class of every idempotent forms a subgroup of the semigroup. Since idempotents are unique in groups this means that H classes are idempotent separating.

A proof of this theorem is unnecessary as it is well known. The first theorem that we will prove ourselves is that divisibility commutative regular semigroups are completely regular. The second we will prove is that they are inverse.

Theorem: divisibility commutative regular semigroups are completely regular

Proof: A semigroup is completely regular if every elements is included in some subgroup of the semigroup. But this can be restated as the semigroup is completely regular if every H class contains an idempotent. In that case, by Green's theorem we know that each element is contained in a group which is the group of the idempotent of its H equivalence class. A semigroup is regular if each L class and each R class contain an idempotent. In a divisibility commutative semigroup H = L = R so it follows that H is equal to L and R which both contain idempotents in each of their equivalence classes. It follows that H contains idempotents in each of its equivalence classes. This makes it completely regular.

Theorem: divisibility commutative regular semigroups are inverse

Proof: an inverse semigroup can be stated as a regular semigroup such that L and R are both idempotent separating. Regular semigroups already guarantee that L and R classes have idempotents, but this condition ensures that the idempotent in each L and R class is unique. At the same time, we know from Green's theorem that the H classes of any semigroup are always idempotent separating. It follows that if we have divibisility commutative which means that H = L = R the property of being idempotent separating is shared with the L and R classes of the semigroup. This in turn means that the semigroup is inverse.

Theorem: completely regular inverse semigroups are divisibility commutative

Proof: from the fact that the semigroup is completely regular we know that each H class contains an idempotent. Let S be any L class or R class of the semigroup, then since the semigroup is inverse we know that must contain a unique idempotent. That unique idempotent has an H class containing it. If that H class is equal to S then we are done as that L/R class is equal to its H class which means that L = R = H. Suppose on the contrary, we have an L class or an R class that is not equal to the H class of its unique idempotent. Then there must be some element in the class S that is not in the H class of that idempotent. That element has its own distinct H class that it is contained in and that distinct H class and its distinct idempotent must be included in S. Therefore, we arrive at a class S with two different idempotents but that is not possible for an inverse semigroup so we arrive at a contradiction. As a result, we know that each L class and each R class is equal to a corresponding H class. This implies that L = R = H which means that the semigroup is divisibility commutative.

Conclusion: the three properties of being completely regular, inverse, and divisibility commutative form a perfect trinity where any of the two properties implies the other. The intersection of this triad is the class of Clifford semigroups. Clifford semigroups form a natural generalisation of semilattices and groups and they are one of the most basic classes of divisibility commutative semigroups.

Divisibility commutativity in the sense of green's relations

Given a commutative semigroup, then that semigroup has an associated preorder $a \le b$ if there exists a c such that $ac = b$. This is a preorder that defines all the ordering properties of a commutative semigroup in a singular standard way. The situation is not so simple in non-commutative semigroups as seen by the different green's relations. But suppose that L = R then we know that since D and H are defined by the meet and join of L and R in the partition lattice this means that all four are equal. \[ L = R = D = H \] In these cases, we can instead focus on a single preorder. Well there are different preorders on a non-commutative semigroup (the Green's preorders each have L,R,J,and H as partitions) these preorders are also equal in a divisibility commutative semigroup. That is, there is a sense that the semigroup has a singular order just like commutative semigroups. We already discussed J-trivial semigroups which are essentially just semigroups on total orders, well semigroups with a symmetric total preorder are essentially groups (which is proven in the finite case).

• Antisymmetric: J-trivial semigroups
• Symmetric: Groups

It makes sense that groups are divisibility commutative, because everything can divide everything else in both directions. So we see that the two basic constituents of divisibility commutative semigroups are J-trivial semigroups and groups. J-trivial semigroups are aperiodic well groups are periodic respectively. This includes non-commutative groups as well, as their non-commutativity doesn't effect their divisibility. In general, divisibility commutative semigroups allow a restricted amount of non-commutativity so long as it doesn't effect divisibility.

The theory of J-trivial semigroups

Starting from partial orders, we can form semilattices from partial orders satisfying certain conditions. Semilattices are restricted to semigroups that are commutative and idempotent. Relaxing the restriction of idempotence, we arrived at finite commutative aperiodic semigroups. The next step, of relaxing commutativity, produces J-trivial semigroups. It can be proven that finite commutative aperiodic semigroups are J-trivial. We already described the simplest J-trivial semigroup that is not commutative, the T3 special combiner on a totally ordered set of three elements.

These non-commutative J-trivial semigroups produce upper bounds of elements in a partial order in an argument-dependent manner. This opens up a whole wide range of possibilities that were not available previously and it gives an approach to considering different upper bound producing functions on partial orders. Actually, J-trivial semigroups constitute all associative upper bound producing functions on partial orders. As we discussed previously, there are two types of non-monotonic behavior that can occur on J-trivial semigroups: chain non-monotonic behavior between comparable elements and antichain non-monotonic behavior on incomparable elements.

• Chain non-monotonic: non-monotonic products of comparable elements
• Antichain non-monotonic: non-monotonic products of comparable elements

We already demonstrated examples of chain non-monotonic and antichain non-monotonic behavior. These can occur argument-order dependently, essentially what this means is that given two elements which are either related to one another or not related to one another by the partial ordering comparability relation, these elements can produce a larger result in one argument order then in another argument order. This makes it so that one argument order is greater then another argument order.

In larger semigroups, smaller semigroups like the totally ordered T3 combiner can be combined in different directions, so they are not isomorphic even though they are antiisomorphic. In such semigroups for certain elements one argument order can be greater then another, well in other elements a greater result is produced between them by arguments in a different order. In other cases they can be combined in the same argument order. So these non-commutative J-trivial semigroups can either favor one argument order or another, it it can maximize them both equally. This is one thing that adds to the complexity of J-trivial semigroups.

Non-commutative version of the exceptional commutative semigroup

The exceptional small commutative semigroup of order four was defined primarily by the different product of its incomparable minimal elements. Rather then then producing the least upper bound it produced the maximal element of the partial order. Amongst the non-commutative semigroups there is a similar semigroup that produces either the maximum or the join depending upon the argument order.

[ [ 1, 1, 1, 1 ], 
  [ 1, 1, 1, 1 ], 
  [ 1, 1, 2, 1 ], 
  [ 1, 1, 2, 2 ] ]

So in total for the same indices and the same factorisation partial order there are three different types of behavior: the semilattice like behavior, the maximizing behavior, and the argument dependent half way case. All of these semigroups, just like the T3 special semigroup on three elements discussed previously are J-trivial. So we will be considering J-trivial semigroups which are associative bound-producing functions on partial orders.

Smallest non-commutative totally ordered semigroup

We considered commutative aperiodic semigroups such as semilattices upper bound functions on partial orders. We even considered how these upper bound functions can themselves be partially ordered by "how upper" their bounds are. Now we will move to the non-commutative case. Towards that end, we should consider the simplest case of a non-commutative upper bound function:

[[1 1 1]
 [1 1 1]
 [1 2 3]]

The first thing we notice is that this semigroup is actually totally ordered [3,2,1]. The second thing that we notice about this semigroup is that the middle element is index two. Therefore, the corresponding monotonic semigroup is M2,1 + identity or the index two aperiodic monogenic semigroup with an identity element adjoined to it.

We can learn about this semigroup by comparing it to its monotonic commutative aperiodic counterpart. The only difference is that 2*3=1 rather then 2 this means that the middle and minimal elements can either produce their least upper bound which is the middle element or the maximal element. Since this produces a greater upper bound then it would otherwise would among comparable elements I call this chain non-monotonic. This special T3 semigroup often appears in larger partially ordered semigroups as a subsemigroup.