The subcommutativity preordering

Let G be a graph, then the vertices of the graph G can be preordered by adjacency, so that one element is greater then another if it is adjacent to every element that element is adjacent to. Two elements are adjacency equal if they are adjacent to all the same elements. In the same sense, we can get a preordering of a semigroup from the commuting graph. This forms the subcommutativity preordering, which is immensely useful in studies of commutativity. It tells us when one element is more commutative then another element.

Definition. an element a subcommutes with b if it is the case that $\forall x : (xa=ax) \implies (xb = bx)$.

Semigroups are sufficiently complicated that they have multiple preorderings defined on them. For the sake of clarity and formalism, we will also define the generator preordering on a semigroup. This preorder requires a positive integer for iteration, because a semigroup does not require an identity.

Definition. an element a is a generator of b if it is the case that there exists a positive integer $n$ such that $a^n = b$.

The main theorem that we will be considering today is that this generation preorder is a subpreorder of the commutativity preorder. This means that if b is generated by a, then b commutes with every element that a does.

Theorem. the subcommutativity preordering is a subpreordering of the generator preordering.

Proof. suppose that a generates b, then we know by definition that there exists a positive integer $n$ such that $b = a^n$. We will show that if $c$ commutes with $a$ then it commutes with $a^n$. If $n = 1$ then $a^n = a$ and since $a$ commutes with $c$ we know that $a^n$ commutes with $c$. By induction suppose that it holds for $n = k$ then if we have $a^(k+1)$ it is equal to $a * a^k$ so if we take $(a * a^k) * c$ we know that $a^k$ commutes with $c$ and by associativity we get $a(c*a^k)$ now since $c$ commutes with $a$ by associativity we get $c*(a*a^k)$ which equals $c*a^(k+1)$.

Basically, we can use the base case of commutativity, with the property of associativity iteratively to get commutativity for all generated elements. The importance of this theorem is that although there are multiple preorderings on a semigroup, they are not unrelated to one another. The different preorders can themselves be related to another by preordering. An important result of this, is that generation equality leads to commutativity equality. Generation equality occurs in cyclic subgroups, who have $\varphi(n)$ generators. Each order $n$ element in a subgroup, therefore has $\varphi(n)$ generation and commutativity equal elements.

1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8

This implies that non-trivial groups tend to have a lot of commutativity-equal elements. Therefore, it might be useful to take the equality-quotient of the commuting graph when studying the commuting graphs of groups. In fact, all non-binary finite groups have commutativity-equal elements. Even the symmetric group S3 which is the smallest non-commutative group has two elements that are commutativity equal : the two elements of order three. This commutativity-equality is preserved even if the non-binary group is embedded in a larger semigroup, as the parent semigroup preserves generation equality it must preserve commutativity-equality.

Maximal commuting cliques

One of the basic problems in semigroup theory is the relationship between subalgebras and commutativity. We will address this question by first considering commuting cliques of a semigroup. A commuting clique is a set of elements, each of which commutes with each other. In other words, a clique in the commuting graph of the semigroup. We will show that semigroup closure maps commuting cliques to commuting cliques.

Theorem. Let $S$ be a semigroup and let $C$ be a commuting clique of the semigroup. Then let $a,b$ be elements of $C$. The product $ab$ commutes with every element of $C$.

Proof. Let $c$ be any element of $C$. We will show that $(ab)c$ = $c(ab)$. By associativity we know that $(ab)c$ equals $a(bc)$. Then by the fact that $b,c$ are both elements of $C$ we know that they commute so $a(bc) = a(cb)$. By associativity we know that $a(cb)$ equals $(ac)b$. By the fact that $ac$ are both elements of $C$ we know this equals $(ca)b$ now finally by associativity this equals $c(ab)$. Applied iteratively this implies that semigroup closure maps commuting cliques to commuting cliques.

Corollary. the maximal commuting cliques of a semigroup form a subalgebra system

This follows from the fact that semigroup closure maps commuting cliques to commuting cliques. Suppose that $M$ is a maximal commuting clique, then by the fact that closure operations are extensive, the closure of $M$ must be greater then or equal to $M$ and by the fact that commuting cliques are mapped to commuting cliques, it must be mapped to a commuting clique greater then or equal to $M$. But $M$ is a maximal commuting clique by definition, so it must be mapped to itself. Therefore its closure must be equal to itself, so it must be a subsemigroup.

This theorem immediately gives us a whole class of subalgebras that can be infered immediately from the commuting graph of the semigroup, without having to consider the semigroup itself. The maximal commuting cliques form a subalgebra system, that is to say a subset of Sub(A), they also form a set system. This set system forms a maximal cliques family, and the underlying graph is the commuting graph. Therefore, in the other direction, the subalgebra system consisting of all maximal commuting cliques fully determines the commuting graph.

Corollary. The maximal commuting cliques of a semigroup form a maximal cliques family and the underlying graph of this family is the commuting graph.

This follows directly from the definition of maximal clique families. We can now add the maximal commuting cliques to our list of subalgebra systems that form interesting set systems. The maximal subgroups for example are a pairwise disjoint set system. In general, most different types of set systems emerge at one point or another from subalgebras.

Lattices of subalgebras

Certain algebraic structures like semilattices have partial orders naturally defined on their elements, while a great many others like groups do not. In fact, groups do not have any natural ordering established on their elements at all. This means that to relate order theory to group theory, a different setting is required other then the elements. This is provided by sets, which are naturally partial ordered by inclusion. The condition of being closed under the operations of the algebraic structure provides for a set of sets of elements which forms a lattice called Sub(A).

Definition. let A be an algebraic structure with a set of n-ary operations defined on A then the set of subsets of the ground set of A that are closed under all the operations of A forms a lattice of sets called Sub(A).

The set of n-ary operations on A is the primary determinant of what Sub(A) will be. Groups have signature (0,1,2) consisting of an identity, inverse, and the group operation and semigroups have signature (2) consisting only of the semigroup operation. Groups as semigroups have strictly more operations but then semigroups but they have fewer subalgebras. This leads to the first deduction of universal algebra, which is that the set of operations of A is inversely proportional to the size of Sub(A).

The torsion-free additive group $(\mathbb{Z},+)$ can take at least three forms depending upon the signature. It can simply a group, a group-as-a-monoid, or a group-as-a-semigroup. Even though they are all defined by the same operation, it is ontologically important to distinguish between them in order to determine Sub(A). The positive integers $\mathbb{Z}+$ form a subsemigroup, the non-negative integers $\mathbb{N}$ form a submonoid, and the even integers $2\mathbb{Z}$ form a subgroup. In this case, the lattice of subsemigroups has strictly more elements then the lattice of submonoids, which in turn has strictly more elements then the lattice of subgroups.

It is not enough to consider the lattice of subalgebras Sub(A). When considering a partial order, one always needs to consider suborders. A set of subalgebras $S \subseteq A$ forms a subalgebra system. Chains of subalgebras are one type of subalgebra system. For example, solvability in groups is determined by a bounds-maintaing subnormal quotient-abelian chain of subgroups. Radical extensions in fields are determined by chains of field extensions such that consecutive filed extensions are formed by simple radicals. This leads to the definition of a subalgebra system.

Definition. let A be an algebraic structure. Then a set $S \subseteq Sub(A)$ of subalgebras of A is a subalgebra system.

Subalgebra systems are also set systems. Suppose, that S is a finite semigroup, then the set of maximal subgroups of S forms a pairwise disjoint sperner family by Green's theorem. The maximal proper subsemigroups of a finite semigroup form a sperner family, which is not necessarily disjoint. Sub(A) itself forms a Moore family as a set system. The closure operation associated with the Moore family can be used to define other sets that are not necessarily subalgebras like minimal generating sets, in the same manner typically done in set theory. Examples of subalgebra systems abound in abstract algebra.

Classes of divisibility commutative semigroups

Divisibility commutative semigroups are precisely the semigroups that have their L and R relations coincide. That is, they are the semigroups which act like commutative-semigroups with respect to divisibility, and they include all semigroups which are factorisation partially ordered. The consideration of these semigroups recently, as well as their specializations led to us to consider a number of subclasses of the class of divisibility commutative semigroups. An ontology of them is displayed below.

Clifford semigroups are particularly interesting because they are the most natural generalization of groups within the class of semigroups. In the theory of symmetric inverse semigroups, the Clifford semigroups are constructed entirely from charts that consist of only a permutation part and no nilpotent part. Clifford semigroups include both groups and semilattices as described above. We will now transition from our consideration of divisibility commutative semigroups to other generalisations of commutativity.

Strong divisibility commutative elements

We previously mentioned that semigroups can be strongly divisibility commutative. This occurs when the left and right principal ideals of the semigroup coincide for each element. In the case that the entire semigroup is not strongly divisibility commutative, there is a subset of the elements that are. So we will need to briefly examine strongly divisibility commutative elements and what they mean for Green's relations.

Definition. an element of a semigroup is strongly divisibility commutative if its left and right principal ideals coincide. The strong divisibility center consits of all elements that are strogly divisibility commutative.

It is trivial to see that central elements are strongly divisibility commutative, and therefore the center is a subset of the strongly divisibility center. Now consider the effect of strong divisibility upon the Green's relations. If two elements are strongly divisibility commutative, then they divisibility commute in the sense that L and R for the two elements are logically equivalent.

Theorem. if a and b are both strongly divisibility commutative then a L b is logically equivalent to a R b.

Proof. this will be proved by demonstrating implication in both directions. Suppose that a L b then we know that L(a) = L(b) but by strong divisibility commutative of elements we have R(a) = L(a) and L(b) = R(b) which implies R(a) = L(a) = L(b) = R(b) which by transitivity means that R(a) = R(b) which by definition means a R b. In the opposite direction a R b implies that R(a) = R(b) which implies that L(a) = R(a) = R(b) = L(b) which similarily implies L(a) = L(b) which by definition means a L b. So the proof of implication in both directions implies logical equivalence.

I managed to use this and Green's theorem to prove that idempotent-central semigropus (which include Clifford semigroups) are L,R idempotent separating. The H classes are also idempotent separating by Green's theorem, but there is no obvious way to get that the D classes are idempotent separating so we can't prove that.

Theorem. idempotent-central semigroups are L,R idempotent separating

Proof. let a and b be two idempotents of the semigroup, now a and b are both in the center by definition so they are strongly divisibility commutative. This implies that if a L b then a R b and that if a R b then a L b, so if idempotents are L related or R related then they are both L and R related, which would mean that they are H related. But by Green's theorem two idempotents cannot be H related, which would be a contradiction. So L and R must be idempotent separating.

Strongly divisibility commutative semigroups

We previously addressed the idea of divisibility commutative semigroups. These are semigroups in which the Green's L relation and the Green's R relation coincide. But it is apparent, even from the simplest case of the non-commutative divisibility commutative semigroup on three elements, that having the Green's L relation and the Green's R relation coincide does not imply that left and right principal ideals are going to be the same.

Definition. a semigroup is called strongly divisibility commutative if left and right ideals coincide.

The first thing is to prove that these strongly divisibility commutative semigroups are in fact divisibility commutative, for the sake of formality.

Theorem. strongly divisibility commutative semigroups are divisibility commutative

Proof. suppose that the L class of x and the L class of y are equal, then Sx = Sy, so since Sx = xS and Sy = yS we have that xS = Sx = Sy = yS which implies that xS = yS by the transitivity of multiplication. This means that x,y are in the same R class. In the reverse direction, if x,y are in the same R class then Sx = xS = yS = Sy implies that x,y are in the same L class. So R = L and the two Green's relations coincide when the principal ideals coincide.

It is trivial that commutative semigroups are strongly divisibility commutative. It is also the case that groups are strongly divisibility commutative. The interesting thing, is that there is a specific method to get the element that produces a given output element in the other principal ideal: namely conjugation of group elements.

Theorem. in a group if gx = yg is an element in both the left and right principal ideals of a given element g then x,y are conjugates of one another

Proof. if we take gx = yg and we multiply each side by g^(-1) to the front then we get x = g^(-1)yg which means that x is a conjugate of y. In the other direction, if we multiply each side by g^(-1) to the back we get gxg^(-1) = y and that means that x and y conjugates.

So conjugation in group theory actually is the basis of the strong divisibility commutativity. It is not hard to see then, why it is the case that self-conjugate elements are centered in groups, because conjugates are the elements that produce a given result in the opposite direction, and when this result is always the element must commute. It is known that in group theory, conjugates are directly related to commutativity in that for example the size of a conjugacy class is the order of the group divided by the commuting degree.

Previously we talked about Clifford semigroups, which are known to be the only divisibility commutative regular semigroups. According to the encyclopedia of mathematics, Clifford semigroups are strongly divisibility commutative as well because L and R classes coincide. I am willing to conjecture that since Clifford semigroups are completely regular, the element that produces a given output with respect to an element in the opposite argument order is the internal conjugate of that element in its H class. But I don't have a proof or a counter-example yet. The simpler case of groups is illuminating nonetheless.

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.