Semigroups of trivial charts

The elements of an inverse semigroup are called charts. Amongst the set of charts of an inverse semigroup, there are the charts containing no more then one element, which we call trivial. The non-empty semigroups constructed from these trivial charts are equivalent to the semigroups with zero of thin semigroupoids.

The complete Brandt semigroup of trivial charts:

Let $PS_n$ be the symmetric inverse semigroup on $n$ elements. Then the semigroup with zero of the complete thin groupoid $K_n + 0$ is a Brandt semigroup consisting of all trivial charts on $n$ elements. Chart representation makes $K_n + 0$ a subsemigroup of $PS_n$.

	$\emptyset$	(0,0)	(1,1)	(0,1)	(1,0)
$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$
(0,0)	$\emptyset$	(0,0)	$\emptyset$	(0,1)	$\emptyset$
(1,1)	$\emptyset$	$\emptyset$	(1,1)	$\emptyset$	(1,0)
(0,1)	$\emptyset$	$\emptyset$	(0,1)	$\emptyset$	(0,0)
(1,0)	$\emptyset$	(1,0)	$\emptyset$	(0,0)	$\emptyset$

The Brandt semigroup on five elements is the smallest non-commutative inverse semigroup, and it is the special case of the semigroup with zero of a category. The non-zero elements a complete Brandt semigroup of trivial charts are ordered pairs, and their inverses are the ordered pairs with elements reversed.

Definition. a semigroup of trivial charts is a subsemigroup of $K_n + 0$.

Theorem 1. subsemigroups of $K_n + 0$ are either trivial or they contain zero.

Proof. (1) in the trivial case we have the empty semigroup and the semigroups formed by any of the idempotents of $K_n + 0$. (2) if $S$ contains nilpotent charts then it must contain zero, so suppose that $S$ has no nilpotent charts and at least two non-zero elements. Then those non-trivial elements must be idempotents, but any two idempotents in $K_n + 0$ combine to produce zero, so a non-trivial subsemigroup must contain zero. $\square$

Theorem 2. let $S$ be a semigroupoid, then subsemigroupoids $Sub(S)$ are equivalent to zero-preserving subsemigroups of $Sub(S + 0)$.

Proof. (1) let $T$ be a subsemigroupoid of $S$. Then for all $a,b \in T$ either $ab \in T$ or $ab = 0$, it follows that $ab \in T + 0$. Suppose $X$ is a zero preserving subsemigroup of $S + 0$. Then $ab \in X-0$ or $ab = 0$. Let $T = X - 0$, then $T \subseteq S$ and forall $a,b$ either $ab \in T$ or $ab = 0$, so $ab$ is a subsemigroupoid of $S$. $\square$

Theorem 3. every non-empty semigroup of trivial charts is isomorphic to the semigroup with zero of a thin semigroupoid.

By theorem 1 a non-empty semigroup of trivial charts is equal to the trivial monoid with a single element. This is simply the semigroup with zero of the empty category. Then in the case that $S$ is non-trivial, by theorem one it is a zero-preserving subsemigroup of $K_n + 0$, which by theorem 2 is the semigroup with zero of a thin semigroupoid. $\square$

This allows us to create a direct correspondonce between a concept in semigroup theory and a concept in semigroupoid theory, so that thin semigroupoids can be studied by semigroups of trivial charts. Thin categories are simply a special case, and so they produce a special class of semigroups.

Proposition. a non-empty semigroup of trivial charts is the semigroup with zero of a thin category provided that every nilpotent chart absorbs two idempotents.

Proof. by theorem 3 every non-empty semigroup of trivial charts comes from a thin semigroupoid. There are two elements in a thin semigroupoid: nilpotents and idempotents corresponding to non-endofunctions and endofunctions respectively. In a thin category there are no non-identity idempotents to preserve, so all that is required is that each nilpotent morphism preserves two idempotents which are necessarily identities.

If $(a,b)$ is a morphism in a thin category, then the idempotents preserved by it are precisely the identities that it absorbs: $(a,a) \circ (a,b) = (a,b)$ and $(a,b) \circ (b,b) = (a,b)$ of which there can only be two. So if a nilpotent charts absorbs two different idempotents it preserves identities. $\square$

This is a purely semigroup theoretic characterization of thin categories. These are a very restricted class of semigroups, because concepts of semigroup theory most readily translates to semigroupoid theory rather then category theory. This correspondence forms the basis of the subject at hand.

We now need to characterize the Green's relations in the semigroup with zero of the complete thin groupoid $K_n + 0$ and prove that it is indeed in a Brandt semigroup. We have mentioned that $K_n + 0$ is a Brandt semigroup, and we can see this in the case of five elements by simple inspection, but we have not proved this result in general.

Lemma 1. let $K_n$ be a complete thin groupoid. Then the $L$ preorder on $K_n + 0$ has any ordered pair $(a,b)$ less then $0$ and any pair of ordered pairs are related if they have the same right elements. Dually, the right preorder $R$ has everything less then zero and it preserves left elements.

Proof. let $(a,b)$ be an ordered pair, then by left action $0(a,b) = 0$ so that $(a,b) \subseteq 0$. Then by left action with another ordered pair $(c,a)(a,b) = (c,b)$ two elements are left action related provided they have the same right elements. In other direction, $(a,b)0 = 0$ by right action and $(a,b)(b,c) = (a,c)$ so that ordered pairs are right action related provided they preserve the same left elements.

It follows that $K_n + 0$ has two $J$ classes: zero and all ordered pairs. It follows that $K_n + 0$ is a 0-simple semigroup. In the minimal $D$ class, $L$ and $R$ permute with one another (as is necessary in any $D$ class) and furthermore they form direct products of one another in the lattice of partitions (which is the quotient lattice of the topos of sets). Their direct product is the set of all ordered pairs. $\square$

Theorem 4. $K_n + 0$ is an H-trivial Brandt semigroup.

Proof. (1) let $a$, $b$ be idempotents in $K_n + 0$ then $a$ and $b$ can be represented as charts $(a,a)$ or $(b,b)$ so that $(a,a)(b,b) = 0$ which implies that $ab = 0$. Alternatively, $a = 0$ or $b = 0$ implies that $ab = 0$. As any two idempotents compose to zero, they commute. So that $K_n + 0$ is idempotent commutative.

(2) let $a$ be any element in $K_n = 0$. Then suppose that $a$ is equal to zero, then $a$ is idempotent which implies that it is a regular element. Suppose that $a$ is non-zero, then it is an ordered pair $(a,b)$ so it has an inverse $(b,a)$ then $(a,b)(b,a)(a,b) = (a,b)$ so that $a$ is a regular element.

(3) by lemma 1, $K_n + 0$ is 0-simple. Every trivial chart is periodic, so that every element in $K_n + 0$ is group bound. It follows that $K_n + 0$ is completely 0-simple. Every idempotent commutative regular semigroup is inverse, so by parts (1) and (2) it follows that $K_n + 0$ is an inverse semigroup. As it is a completely 0-simple inverse semigroup, it is a Brandt-semigroup. By lemma 1, the intersection of its L and R relations is trivial, so it is H-trivial. $\square$.

Proposition. $K_n + 0$ is a two-sided inverse subsemigroup ideal of the symetric inverse semigroup $PS(n)$.

Proof. $K_n + 0$ is closed under inverses, with $(a,b)^{-1} = (b,a)$ so it is an inverse subsemigroup of $PS(n)$. It is also a two-sided semigroup ideal because with respect to function composition for any $fg$ then $|fg| \leq |f|,|g|$, so function composition can only reduce the cardinality of partial transformations. It follows that composition can only make trivial charts smaller to become empty, which is included as a trivial chart. So that $K_n+0$ is a two sided semigroup ideal. $\square$

This demonstrates that the semigroup with zero of a thin category is a subsemigroup of an inverse semigroup, so among other things it is idempotent commutative. In general, every thin category embdes in a groupoid whose semigroup with zero is an inverse semigroup.

Zero divisor digraphs:

The zero divisor digraph $Z(S)$ is an important component in a number of constructions related to semigroups of trivial charts including the commuting graph $Com(S)$ and the construction of the underlying thin semigroupoid or category of the semigroup.

Definition. let $S$ be a semigroup, then the zero divisor digraph $Z(S)$ is the fiber of $0$. Then $(a,b) \in Z(S) \Leftrightarrow ab = 0$.

The zero divisor graph $Z(S)$ for a semigroup of trivial charts, can be described by the composition of trivial charts.

Proposition. let $S$ be a semigroup of trivial charts then $a,b \in S$ and $(a,b) \in Z(S)$ provided that $a = 0$, $b = 0$, or $a,b \not = 0$ and $a = (a_1,a_2), b = (b_1,b_2)$ with $a_2 \not= b_1$.

With this, we can show that the commuting graph of a semigroup of trivial charts is a subgraph of the zero divisor graph. As it is symmetric, it is naturally embedded in the symmetric component of the zero divisor graph. In fact it is equal to it, as we are about to show.

Theorem 5. let $S$ be a semigroup of trivial charts, then $Com(S) \subseteq Z(S)$.

Proof. the composition any elements with zero is zero, therefore in order for two elements to not be zero divisors of one another they must both be non-zero. Let $a,b$ be non-zero then by trivial chart representation they are $(a_1,a_2)$ and $(b_1,b_2)$ then if $(a_1,a_2)(b_1,b_2) = (a_1,b_2) = (b_1,a_2) = (b_1,b_2)(a_1,a_2)$ we have that $a_1 = a_2$ and $b_1 = b_2$ which implies that $(a_1,a_2) = (b_1,b_2)$. It follows that $a = b$ so the only non-zero elements that commute are equal. $\square$

We define a semigroupoid such as a category from a semigroup of trivial charts, not from the zero divisor graph but rather from its complement: the non-zero divisor graph. The domain of a semigroup is a complete binary relation, but the domain of a semigroupoid or a category is a non-zero divisor graph of a semigroup with zero.

Definition. let $S$ be the composition function of a non-empty semigroup of trivial charts. Then the underlying thin semigroupoid of $S$ is the subobject (in the topos of functions) of $S$ is the partial semigroup with domain equal to the non-zero divisor graph of $S$.

Corollary. the partial semigroup of a thin semigroupoid is anticommutative.

We have primarily studied thin semigroupoids in terms of their semigroups of trivial charts, which naturally emerge from their completions. But in the case of thin semigroupoids they are also anticommutative, which produces a special relationship with rectangular bands.

Theorem 6. let $\circ : R \to M$ with $R \subseteq M^2$ be a thin semigroupoid with object set $O$. Then $\circ$ is a subobject in the topos of functions of the composition function of a rectangular band.

Proof. the composition function of a thin semigoupoid has $(a,b)(c,d) = (a,d)$ when $b = c$. The composition function in a rectangular band has $(a,b)(c,d) = (a,d)$ no matter what. Let $O^2$ be the rectangular band of ordered pairs on $O$, this leads to a function $\cdot : (O^2)^2 \to O^2$. Then we can embed $\circ$ in $\cdot$ by an ordered pair of inclusion monomorphisms $(R \hookrightarrow (O^2)^2, M \hookrightarrow M)$. $\square$

This is of course a different kind of embedding of the composition function of a semigroup or category into a semigroup then we are used to, but this demonstrates a special relationship that exists between rectangular bands and thin categories. This is a consequence of the fact that thin categories are anticommutative.

Theorem 7. let $S$ be a semigroup of trivial charts and $a,b \in S$. If $ab \not= 0$ and $ba \not= 0$ then $a$ and $b$ are non-zero nilpotents and inverses of one another.

Proof. suppose that $a$ or $b$ are idempotent. Then $ab = 0$ and $ba = 0$ because idempotents always compose to zero. So that means $a$ and $b$ must both be non-idempotents and therefore non-zero nilpotent. Let $(a,b)$ and $(c,d)$ be their values then if they are composable then $b = c$ and $a = d$ which means that $(c,d) = (b,a)$ so that they are equal to $(a,b)$ and $(b,a)$ which are inverses of one another. $\square$

With this, we can get an important property of the zero divisors graphs of thin skeletal categories and semigroupoids arising from posets and strict orders.

Theorem 8. let $S$ be an antisymemtric thin semigroupoid. Then the zero divisor digraph of $S$ is total.

Proof. by theorem 7 in order for two elements to not compose to zero with one another they must be inverses of one another. An antisymmetric thin semigroupoid is inverse-free, so that for each $a,b \in S$ we have $ab = 0$ or $ba = 0$ which implies that the zero divisor digraph is total.

In particular, the semigroups with zero of thin categories always have at least one pair of elements compose to zero. Then same is true for the semigroups of trivial charts of strict orders.

Theorem 9. let $S$ be a commutative semigroup of trivial charts. Then $S$ is a maximum chain length two partially ordered commutative J-trivial semigroup, and all such commutative semigroups emerge in this way.

Proof. by the fact that the commuting graph of a semigroup of trivial charts is the symmetric component of the zero divisor graph, if $S$ is commutative this means that $ab = 0$ and $ba = 0$ for all $a,b$ with $a \not= b$. It follows that $S$ is a maximum chain length two J-trivial semigroup, with maximum chains equal to elements together with zero. In the other direction, every height two J-trivial commutative semigroup is classified by its set of idempontents and nilpotents. Idempotents can be represented by permutation charts and nilpotents by nilpotent charts, to get a trivial chart representation of the commutative semigroup. $\square$

Let $S$ be a semigroup with automorphism group $Aut(S)$ and suppose that $p \in Aut(S)$. Then if $ab = ba$ we have $p(ab) = p(ba)$ which implies that $p(a)p(b) = p(b)p(a)$ so that if $(a,b) \in Com(G)$ then $(p(a),p(b)) \in Com(G))$ so that automorphisms of a semigroup are automorphisms of its commuting graph.

Lemma. let $K_n + 0$ be a complete Brandt semigroup of trivial charts. Then let $f \in S_n$ be a permutation on the underlying set $n$. Then define $f' : K_n + 0 \to K_n + 0$ with $f'(0) = 0$ and $f'((a,b) = (f(a),f(b))$ then $f'$ is an automorphism.

Proof. let $ab \in K_n + 0$. Then suppose that $a = 0$ then $ab = 0$ and $f'(ab) = 0f'(b) = f'(0) = 0$ or if $b = 0$ then $f'(ab) = f'(a)0 = f'(0) = 0$. Suppose that $a \not = 0$ and $b \not= 0$ then \[ f'((a_1,a_2)(b_1,b_2)) = f'((a_1,b_2)) = (f(a_1),f(b_2)) \] \[ f'(a_1,a_2)f'(b_1,b_2)) = (f(a_1),f(a_2))(f(b_1),f(b_2)) = (f(a_1),f(b_2)) \] Then $f'((a_1,a_2)(b_1,b_2)) = (f(a_1),f(b_2)) = f'((a_1,a_2))f'((b_1,b_2))$. In the special case in which $a_2 \not = b_1$ then this implies that $f(a_2) \not= f(b_1)$ because $f$ reflects equality since its a permutation. So $f'$ preserves zeros. It follows that $f'$ is a semigroup automorphism.

Corollary. the Brand semigroup $K_n + 0$ has an automorphism group with there orbits: zero, non-zero idempotents, and non-zero nilpotents

We can use this result as an organizing principle in the theory of the centralizers of $K_n + 0$. By this result, we know that the centralizers belong into three classes. In the following theorem we will characterize all of them.

Theorem 10. let $K_n + 0$ be the complete semigroup of trivial charts, then the centralizers of $K_n + 0$ come in three forms:

1. The entire semigroup $K_n + 0$
2. $K_{n-1} + 0$ plus a side idempotent which has $(n-1)^2 + 1$ elements
3. A special case which has $(n-1)^2$ elements and a side nilpotent.

Proof. (1) let $0$ be the zero element of $K_n + 0$, then $0$ is a central element so its centralizer $C(a)$ is the entire semigroup $K_n + 0$.

(2) let $a$ be an idempotent non-zero element. Then it is equal to an element $(a,a)$ and so its centralizer is all elements disjoint from $(a,a)$ so besides $(a,a)$ it consits of the $D$ class of all $(x_1,x_2)$ with $x_1 \not = a$ and $x_2 \not = a$. The commuting graph is a subgraph of the zero divisor graph, so $ac = 0$ for any $c \in C(a)$ which implies that $a$ is a side idempotent.

(3) let $a$ be a non-zero nilpotent, then as before for any $c \in C(a)$ we have $ac = 0$ and $ca = 0$ so that $a$ is a side nilpotent element. Then let $(x_1,x_2)$ be the chart of $a$. Any idempotent element has the form $(y_1,y_2)$ with $x_2 \not= y_1$ and $x_1 \not= y_2$. These come in three forms $x_1 = y_1$, $x_2 = y_2$ and $x_1 \not= y_1$ and $x_2 \not= y_2$.

Those with $x_1 \not= y_1$ and $x_2 \not= y_2$ form a single D class with $L$ and $R$ classified by their components. Then those with $x_1 = y_1$ form a R-total D class and those with $x_2 = y_2$ form an L-total D class. Together, these constitute a complement set of J classes of $K_n + 0$. This results in a subsemigroup whose J class ordering has the form $[\{[1,\{1,1\}],1\},1]$. $\square$

The commuting graph of the Brandt semigroup on five elements is the cricket graph. In general, by theorem 10 we have that any commuting graph of a complete Brandt semigroup of trivial charts is a nearly-regular graph (in the sense that degrees can only differ by at most one) with a zero element adjoined.

Special cases:

We have defined semigroups of trivial charts by their embeddings in the partial inverse semigroup $PS(n)$ and its intermediary ideal $K_n + 0$, but we have not created a theory of recognising which semigroups of trivial charts without embeddings. We will now do that.

Theorem 11. let $S$ be a non-empty subsemigroup of $K_n+0$. Then $S$ has the following properties

1. $S$ is idempotent commutative, with a max height two semilattice of idempotents, and the idempotent action poset is 0-trivial, in the sense that non-zero elements form an antichain.
2. $S$ is group-free
3. $S$ is a semigroup with zero
4. The commuting graph of $S$ is a subgraph of its zero divisor graph
5. $S$ is max order two aperiodic.
6. Only elements that are inverses of one another are non-zero dividing as pairs

Proof. (1) as a subsemigroup of an inverse semigroup, $S$ is idempotent commutative. By theorem 9, the semilattice of idempotents of $S$ is max height two. Then for any idempotent $e$ and any element $x$ we have $ex = x$ or $ex = 0$, so that the idempotent action poset is 0-trivial. Furthermore, as a semigroup of trivial charts an inverse semigroup of trivial charts can only have a 0-trivial natural partial ordering.

(2) By theorem 4 $K_n + 0$ is H-trivial which by Green's theorem means it is group-free. So its subsemigroups are group-free as well.

(3) By theorem 1, $S$ is a semigroup with zero.

(4) By theorem 5, $Com(S) \subseteq Z(S)$ so that the only elements that commute are ones that both compose to zero.

(5) The charts in $K_n+0$ take two forms: they are idempotent or they are non-zero nilpotent. A non-zero nilpotent $(a,b)$ composed with itself is zero, so every non-zero nilpotent has index two. So $S$ is max index two as an aperiodic semigroup.

(6) By theorem 7, only inverses can be non-zero dividing as pairs. $\square$

The morphism preordering of a thin category $C$ is antisymmetric. This is translated into semigroup theoretic terms by the statement that $C+0$ is a J-trivial semigroup. This is encoded in the following theorem.

Theorem 12. a non-empty semigroup of trivial charts is J-trivial iff it comes from an antisymmetric thin semigroupoid.

Proof. (1) if $S$ is a thin semigroupoid with symmetric pair $(a,b)$ and $(b,a)$ then $(b,a)(a,a)(a,b) = (b,b)$ and $(a,b)(b,b)(b,a) = (a,a)$ so that $a$ and $b$ are in the same $J$ class. So if its semigroup $S + 0$ is J-trivial it must be antisymmetric.

(2) if it is antisymmetric then for $(a,b) \subseteq (c,d)$ then $c \subseteq a$ and $b \subseteq d$ and $(c,d) \subseteq (a,b)$ means $a \subseteq c$ and $d \subseteq b$. By antisymmetry if $a \subseteq b$ and $b \subseteq a$ then $a = b$ and if $c \subseteq d$ and $d \subseteq c$ then $c = d$ so that $(a,b) = (c,d)$ which implies that $S + 0$ is J-trivial. $\square$

Theorem 13. $S$ is a nilpotent semigroup iff it comes from a strict order.

Proof. every non-zero idempotent is of the form $(a,a)$. It follows that if $S$ is nilpotent, it must avoid every element of the form $(a,a)$ which means it is irreflexive. If $(a,b)$ and $(b,a)$ are in $S$ then $(a,b)(b,a) = (a,a)$ and $(b,a)(a,b) = (b,b)$ so that $(a,a)$ and $(b,b)$ are in $S$ it follows that irreflexive transitive are antisymmetric, in which case they are called strict orders. So only strict orders have nilpotent semigroups, and strict orders are nilpotent because they are irreflexive. $\square$

In theorem 9, we characterized from a semigroup perspective the commutative semigroups of charts. In the other direction, we can characterize the thin semigroupoids with commutative semigroup completions.

Theorem 14. let $S$ be a thin semigroupoid, then $S+0$ is commutative iff $S$ is a loop isolated maximum chain length two antisymmetric thin semigroupoid.

Proof. there are cases whereby two morphisms can be composable (1) if we have a loop and a non-loop edge $(a,a)(a,b)$ or $(a,b)(b,b)$ so to forbid this $S$ must be loop isolated (2) if we have two edges in a symmetric pair $(a,b)(b,a)$ which must be forbidden so that $S$ is antisymmetric (3) we have a chain of length three $(a,b)(b,c)$ which means that $S$ must be maximum chain length two. $\square$

Corollary. let $S$ be a thin semigroupoid, then $S+0$ is a null semigroup iff $S$ is a maximum chain length two strict order.

Proof. (1) by theorem 9 $S$ must have maximum chain length to be commutative and by theorem 13 it must be nilpotent, so to be a commutative nilpotent semigroup like a null semigroup it must be a maximu mchain length two strict order (2) by theorem 14 the fact that $S+0$ is commutative implies that $S$ is a maximum chain length two antisymmetric thin semigroupoid, and by theorem 13 we know it is irreflexive. So by combining the two $S$ is a maximum chain length two strict order. $\square$

Semilattices are an important special case in semigroup theory. By theorem 9, we know that every such semilattice is a maximum chain length two semilattice. So every semilattice associated to a thin category is isomorphic, it follows that in order to classify the thin semigroupoids associated with semilattices we need a class of semigroupoids classified by their cardinalities. These are precisely the discrete categories.

Theorem 15. let $S$ be a thin semigroupoid, then $S+0$ is a semilattice if $S$ is a discrete category.

Proof. if $S+0$ is a semilattice then every element of $S$ is an idempotent, which means it is a loop. It follows that $S$ is coreflexive, so that every element is a loop. The only thin semigroupoids that are coreflexive are the discrete categories, so $S$ is a discrete category. Then if $S+0$ is a semilattice, then every element of $S$ must still be idempotent, so that it must be a discrete category. $\square$

We started this discussion by considering the symmetric inverse semigroup $PS_n$ whose elements consist of charts on at most $n$ elements. These charts all have permutation and nilpotent parts, and they can be represented as sets of ordered pairs. If they have at most one ordered pair, they are trivial. So inverse semigroups have played an important role in this entire theory.

We return to the question of inverse semigroups. It remains to characterize which semigroups of trivial charts are indeed inverse semigroups. These are then inverse subsemigroups of the symmetric inverse semigroup $PS_n$. This is a fundamental relationship between groupoids and inverse semigroups.

Theorem 16. let $G$ be a thin groupoid, then $G+0$ is an inverse semigroup. Every inverse semigroup with zero of trivial charts emerges in this way.

Proof. let $(x,y)$ be an element of the thin groupoid, then $(y,x) \in G$ so that $(x,y)(y,x)(x,y) = (x,y)$. It follows that $G+0$ is a regular semigroup, and by theorem 11 it is idempotent commutative so it is an inverse semigroup. Then let $S+0$ be a semigroup with zero then every element $(x,y)$ has an inverse $(y,x)$ so that the underlying semigroupoid $S$ is a groupoid. $\square$

The semigroups of trivial charts are part of the basic relationship between category theory and semigroup theory, because the semigroup completion of any thin category is a semigroup of trivial charts. Further, if we generalize to the semigroup completion of any arbitrary category $C$, then hom class equivalence forms a congruence on $C+0$ whose quotient is a semigroup of trivial charts.

It follows that the theory of semigroups of trivial charts, like those dealt with in this post are part of the basic semigroup theory of categories. Properties of the semigroup completions of categories can be inferred from their quotient semigroups of trivial charts. This suggests a new direction to take the semigroup theory of categories in.

Completion of partial semigroups

A partial semigroup $f: R \to X$ with $R \subseteq X^2$ can be completed to form a total semigroup by adding a zero element, provided that it satisfies a number of conditions. These conditions are summarized in the following diagram presented below. The forbidden existence conditions are highlighted. Theorem 1. let $f: R \to X$ be a partial semigroup then adding a zero to $f$ completes it provided that:

1. If $(xy)z$ and $x(yz)$ both exist then $(xy)z = x(yz)$
2. $(xy)z$ exists is logically equivalent to $x(yz)$ existing (equivalently the four highlighted cases in the diagram above are forbidden)

Proof. there are three cases (1) they both exist in which case they both coincide by condition 1, (2) neither of them exist in which case they both produce zero and so they coincide, (3) one output exists and the other doesn't in which case they wouldn't coincide but condition 2 means this never happens. $\square$

Categories as partial semigroups:

A natural question is where do categories fit into this mathematical universe of semigroups and semirings? This is answered in two parts (1) categories are partial semigroups embedded in semigroups with zero (2) categories are certain types of idempotent semirings.

As this perspective on categories is not commonly dealt with (one mention the semigroup perspective on categories exists in stackoverflow), I want to make the exposition of this post as clear as possible. Most introductions to category theory don't mention that they are partial semigroups.

With so few mentions of the semigroup-theoretic perspective on categories, one might wonder if this perspective is even valid. I intend this post to be so simple and clear that there is no doubt that categories are indeed partial semigroups. If there is any doubt, you can always recheck the diagram at the start.

Theorem 2. Let $C$ be a category. The composition function $\circ$ of $C$ is a partial semigroup satisfying the conditions of theorem 1.

Proof. (1) by associativity $\circ$ satisfies condition 1 of theorem 1, (2) let $x,y,z$ be morphisms and suppose that $(xy)z$ exists. Then the output object of $xy$ and the output object of $y$ coincide, so that $(xy)z$ exists implies that $yz$ exists. Then the input object of $yz$ and $y$ coincide, so that $xy$ existing implies that $x(yz)$ exists, and vice versa. So $\circ$ satisfies condition 2 of theorem 1. $\square$

Then by the use of theorem 1 in combination with theorem 2, we have that we can complete the composition function of any category by adjoining a zero element.

Corollary. let $C$ be a category with composition $\circ$. Then $\circ + 0$ is a semigroup.

We can now use this to get something of the semigroup theoretic perspective on categories.

The issue of partiality

The most desirable properties in abstract algebra are associativity and distributivity. Semigroups and semirings are the most general structures containing these desirable properties. Although those are most desirable properties in abstract algebra, this doesn't entail anything about partiality.

A partial semigroup such as a category doesn't need to lose any of the most desirable properties, like associativity that make the structure convenient to work with. Indeed, a category may as well be a semigroup, as we have seen by adjoining a zero element. So the only real issue is partiality.

Question. what should the return value of composition of incompatible morphisms in a category be?

If the return value is nil, then the composition function of a category is just a semigroup: the semigroup with zero. If instead we decide to throw an error whenever incompatible morphisms are composed, that might cause a program to throw too many errors.

The adjoining of a zero/nil/null element is a possible solution, and that makes the composition function of the category a semigroup. This might just be an implementation detail, but it gets to what distinguishes categories from semigroups.

Polynomials in the noncommutative case

Let $R$ be a non-commutative ring. Then we can define the semigroup ring of $R$ over the free non-commutative semigroup $F^{\rightarrow}(A)$. Then this semigroup ring $RF^{\rightarrow}(A)$ consists of ordered words over the alphabet $A$ with coefficients in $R$. This mirrors the construction of the polynomial ring $R[x_1,x_2,...]$ in commutative algebra as a free commutative semigroup ring.

Elements of the free non-commutative semigroup ring $RF^{\rightarrow}(x,y,z)$ consist of ordered words with coefficients in $R$. For example, we might get a polynomial like $5xyx + 6xz + 7zx$. A term like $xyx$ is not the same as $x^2y$ and $xz$ and $zx$ are not the same as one another. This non-commutativity would naturally add a great deal of complexity to compuations over non-commutative rings.

The issue with this free semigroup ring, is that it is not truly the ring of polynomial functions over $R$. Consider $c_1,c_2,...$ to be constants and $x,y,z,...$ to be indeterminates. Then a coefficient may not commute with its indeterminate, and $c_1 x \not= xc_1$. So for polynomial functions over a non-commutative ring you ultimately get potentially nasty terms like $c_1 x c_2 c_3 y c_4 x c_5 z c_6$.

A term of a polynomial function in a non-commutative ring is an alternating sequence of coefficients and indeterminates, where the coefficients can be identities. So for example $c_1xyc_2yxc_3$ is a term except the coefficients between $x$ and $y$ and then between $y$ and $x$ are simply identities, but there is always the possibility of having coefficients between indeterminates.

The terms of the free semigroup ring are already complicated enough, but terms in the ring of polynomial functions with scattered coefficients are even more messy. This is a serious impediment to doing noncommutative algebraic geometry, so what is the big idea? It seems that noncommutative geometry has more to do with functional analysis and operator theory then polynomials.

Noncommutative spaces can instead be studied using concepts of functional analysis and operator theory like C*-algebras. In particular, the Gelfand representation related C* algebras to locally compact Hausdorff spaces. The study of noncommutative geometry based upon techniques from functional analysis is an interesting direction, albiet one that is very different from you might expect.

Rings of multivariable Laurent polynomials

The commutative group ring of the free commutative group $F^{\circ}(X)$ over a field $k$ is a ring extension of the commutative semigroup ring of the free commutative monoid $F(X)$ over $k$. Although, $F^{\circ}(X)$ is a natural semigroup extension of $F(X)$, rings of multivariable Laurent polynomials don't have the same level of importance as polynomial rings in commutative algebra.

A distinguishing property of ordinary polynomials is that they can be cast into functions, so that over affine space $\mathbb{A}^n$ they are functions $f: \mathbb{A}^n \to k$ and this works for any commutative ring. On the other hand, for Laurent polynomials to be cast into functions $f : \mathbb{A}^n \to k$ we need to have some notion of division to deal with negative degree exponents, so we need to work over a field.

In those cases when we take the commutative group ring of a commutative ring $R$ which is not a field, with respect to $F^{\circ}(X)$ then what we get is certainly still a commutative ring, it is just not a commutative ring of functions. Consider the commutative group ring $\mathbb{Z}(\mathbb{Z}^n,+)$ consisting of polynomials with integer exponents and integer coefficients. Then this is a valid commutative ring, but its elements are not functions because $\mathbb{Z}$ is not a field.

So in some sense we ought to have our free commutative group ring be over a field $k$. Then we get terms like $5\frac{x}{yz} + \frac{6y}{xz}$ consisting of fractional monomials, but then given any term like this we can add to get $\frac{5x^2 + 6y^2}{xyz}$ which is always a polynomial with a monomial in the denominator. So we see that multivariable Laurent polynomials are simply rational functions with monomials in the denominator, so we have an embedding. \[ kF^{\circ}(x,y,z) \subseteq k(x,y,z) \] The ring of Laurent polynomials is simply the localisation of the polynomial ring by the multiplicative set of monomials, and so they are merely a special case of rational functions. Now it is clear why we don't see Laurent polynomials so much in commutative alebra. They are simply part of the far more important and general concept of fields of rational functions $k(x,y,z)$.

Just as we don't tend to restricted localisations of the integers like the dyadic rationals that much, we won't see rings of multivariable Laurent polynomials showing up as much. In general, we always want to deal with the largest localisation of a domain, which is its field of fractions.

So although the group completion of the free commutative semigroup $F(X)$ is an important and natural concept in commutative semigroup theory, it doesn't have the same role and level of importance in commutative algebra, as determined by commutative semigroup rings. This demonstrates that not everything in commutative algebra is a consequence of commutative semigroup rings, but the use of semigroup rings is still an infinitely powerful technique in the construction of commutative rings.

Centralizers of division rings

We have that centralizers of commuting graphs determine subsemigroups and subrings, and corresponding to this there is the fact that centralizers of groups are subgroups and centralizers of division algebras are not simply subrings but division subalgebras. This can be used for example to determine the maximal subfields of a division algebra.

Subalgebras of division rings:
Let $R$ be a division ring, then $R$ as a ring is associated to a lattice of subrings. A meet subsemilattice of this lattice of subrings is the lattice of division subrings $Sub(R)$ of $R$, which consists of subrings that are also inverse closed with respect to non-zero elements.

The special case of centralizers:
By the theory of commutativity necessary subrings, we know that the centralizers of $R$ are subrings. The centralizers of $R$ together form a lattice: the centralizer lattice of the commuting graph of $R$. It remains to show that they are not only subrings but also division subrings.

Lemma 1. let $G$ be a group and $x$ an element of $G$ then the centralizer $C(x)$ is a subgroup of $G$.

Proof. the centralizer $C(x)$ is a submonoid, so let $y \in C(x)$ then $yx = xy$. Let $y^{-1}\in G$ then we want to show that $y^{-1}x = xy^{-1}$. By the fact that $G$ is a group, we can multiply both sides by $yx^{-1}$ to get $y^{-1}xyx^{-1} = 1$. Then by the fact that $x$ and $y$ commute this is equivalent to $y^{-1}yxx^{-1} = 1$ which is true, so that $y^{-1} \in C(x)$. $\square$

Lemma 2. let $S$ be a group with zero (respectively a Clifford 0-simple semigroup). Then centralizers of elements in $S$ are inverse closed.

Proof. let $x \in S$ and suppose that $x = 0$. Then the centralizer of $0$ is the entire semigroup, which is inverse closed. Suppose $x \not= 0$ then $x \in S-\{0\}$ which is a group, so the centralizer of $x$ in $S-\{0\}$ is a subgroup by lemma 1. It is therefore inverse closed. $\square$

Theorem. let $R$ be a division ring, then centralizers $C(x)$ are division subalgebras.

Proof. by commutativity necessary subrings, $C(x)$ is a subring and by lemma 2 it is inverse closed, so it is a division subalgebra. $\square$

The maximal cliques of the commuting graph of a division ring are precisely the maximal fields of the division ring. All the commutativity necessary subfields of a division ring are determined by maximal cliques and their intersections, which form a semilattice.

Centers of division rings:
The center of a division ring is precisely the intersection of all the maximal fields of the division ring. As it is the intersection of fields, it is a field. The division ring can then be seen to be a vector space over its central field. The measure of the commutativity of a division ring is the dimension of its extension over a central field: finite dimensional division rings (like the quaternions) are the most commutative.

Maximal subfields of a division ring:
An immediate corollary of this is that the maximal subfields of a division ring can be determined by the same general mechanism by which we determine maximal commutative subalgebras of semigroups, groups, rings, and semirings: they are maximal cliques of the commuting graph.

Proposition. let $D$ be a division ring then $F$ is a maximal subfield of $D$ iff $D$ is equal to its own centralizer: $C(D) = D$

It is not hard too see by the same reasoning that applies to any other algebraic structure like a group or ring, that every element of a division ring belongs to some maximal field.

Proposition. every element of a division ring belongs to some maximal field.

Maximal subfields of a division ring are a vital tool in the study of division rings. Their further properties can be studied using tensor products of division rings described as algebras over fields [1].

References:
[1] A first course in non-commutative rings
T.Y Lam

Applications of commutative semigroup rings

Let $R$ be a commutative ring. Then every commutative semigroup $S$ is naturally associated to a commutative ring extension of $R$, the commutative semigroup ring of $R$ by $S$. It is not hard to see that this construction is full of applications in commutative algebra and algebraic geometry. We will utilize commutative semigroup rings as an organizing principle in the theory of polynomial rings, which is an important part of algebraic geometry.

Polynomial rings:

The free $\mathbb{N}$-semimodule $F(X)$ is a very familiar object of commutative semigroup theory. It is not hard to see that the polynomial ring $R[x_1,x_2,...]$ is merely the commutative semigroup ring of $R$ by $F(x_1,x_2,...)$ : $RF(x_1,x_2,..)$. As a consequence, the polynomial rings that are so fundamental in algebraic geometry, can be considered to be a special case of a commutative semigroup ring.

Subalgebras of polynomial rings

Let $S$ be a finitely generated torsion-free cancellative J-trivial commutative semigroup. Then $S$ embeds into the free commutative semigroup $F(X)$ on a finite set of generators $X$. As a consequence, we can embed the commutative semigroup ring $RS$ into the polynomial ring $R[x_1,x_2,...]$.

As an example, any numerical semigroup can be embedded in the polynomial ring on a single generator. The polynomial subring $R[x^2,x^3]$ for example is merely the commutative semigroup ring of the numerical semigroup $\{2,3\}$. If we had $R[x^2y,yz^3]$ for example it would be generated by the commutative semigroup $(x^2y,yz^3) \in F(x,y)$, and so on.

Extensions of polynomial rings:

It is a basic fact of commutative algebra that $F(X)$ is a cancellative semigroup. Therefore, the free $\mathbb{N}$ semimodule $F(X)$ can be embedded in the free $\mathbb{Z}$-module $F^{\circ}(X)$. As a consequence, the commutative semigroup ring of multivariable polynomials $RF(X)$ can be embedded in the ring of multivariable Laurent polynomials $RF^{\circ}(X)$.

This can be further extended by considering rings of Puiseux polynomials $R\mathbb{Q}^n$ consisting of polynomials that have rational exponents, or this could even be embedded in $R\mathbb{R}^n$ to have arbitrary real exponents, so that we can have a complete extension of the ordinary polynomial ring $R[x_1,x_2,...]$.

Coordinate rings of varieties

Let $Y$ be an algebraic variety defined by a system of polynomial equations in $R[x_1,x_2,...]$. Then by now means is it the case that the coordinate ring $A(Y)$ can always be defined by a commutative semigroup ring. However, there is an important case in which they can be: algebraic varieties defined by differences of monomials. These correspond to relations in the presentation of a commutative semigroup.

Therefore, we can use commutative semigroup rings in algebraic geometry in order to deal with the important special case of varieties determined by differences of monomials. For example, consider the hyperbola $\frac{R[x,y]}{xy=1}$. Then this clearly produces a presentation of the commutative group $\mathbb{Z}$ so this is a ring of Laurent polynomials. As you can see, this is a very useful concept of commutative algebra.

References:
[1] Commutative semigroup rings by Gilmer

Multiset addition semigroups

The class of all multisets on a set forms a semigroup $F(S)$ with multiset addition as its operation. The additive property of $F(S)$ is formalied by a semigroup homomorphism $f : F(S) \to \mathbb{N}$ which maps each multiset to its cardinality. Given a free commutative semigroup $F(S)$ then there are two ways to form semigroups from it by taking a quotient to get a commutative semigroup presentation or taking a subalgebra to get a multiset addition semigroup.

Properties of free $\mathbb{N}$-semimodules

The free $\mathbb{N}$ semimodule $F(S)$ on a set $S$ has a number of properties that are inherited by its subalgebras. Although every commutative semigroup is a quotient of some $F(S)$, only a small number of commutative semigroups can be embedded in the free commutative semigroup $F(S)$.

Theorem. the free $\mathbb{N}$ semimodule $F(S)$ is:

1. $\mathbb{N}^S$ distributive lattice ordered
2. Cancellative
3. Torsion-free
4. Commutative and a monoid

Proof. (1) the semiring $\mathbb{N}$ is totally ordered. Therefore, $F(S)$ is ordered by the product ordering $\mathbb{N}^S$ having terms in $S$ with multiplicities in $S$. Distributive lattices are a variety of lattices that include total orders, so the product ordering on $F(S)$ is distributive.

(2) the semiring $\mathbb{N}$ is additively cancellative so that $a + b = a + c$ implies that $b = c$. It follows from additive cancellativity that we have $a + b = a + c$ for addition in the free $\mathbb{N}$ semimodule.

(3) the semiring $\mathbb{N}$ is multiplicatively cancellative for $n \not= 0$. It follows that $na = nb$ implies that $a = b$ for $n \not= 0$. Therefore, $F(S)$ is torsion-free.

(4) every semimodule is an additive commutative monoid, therefore so too is $F(S)$. $\square$

Although $F(S)$ is a distributive lattice ordered torsion-free commutative cancellative semigroup, not all of these propreties are inherited by its subsemigroups. In particular, the distributive lattice ordering is not preserved.

Definition. a commutative semigroup is subfinite provided that each element is contained in a finite number of principal ideals.

Corollary. every subsemigroup of $F(S)$ is a subfinite J-trivial commutative cancellative torsion-free semigroup

Proof. let $A \subseteq B$ be semigroups, then the algebraic preorder on $A$ is a suborder of that of $B$. Therefore, given $C \subseteq F(S)$ then the algebraic preorder on $C$ is a subpreorder of a subfinite partial order, so it is a subfinite partial order making $C$ subfinite J-trivial. It is also commutative, cancellative, and torsion-free as these properties are hereditary. $\square$

This demonstrates that not all J-trivial commutative cancellative torsion-free semigroups can be embedded in a free commutative semigroup $F(S)$. The Puiseux monoid $(\mathbb{Q}_{\ge 0}, +)$ is a J-trivial commutative cancellative semigroup but it is not subfinite so there is no way of achieving an embedding.

A notable property of the Puiseux monoid $(\mathbb{Q}_{\ge 0},+)$ is that is infinitely generated. This suggests perhaps we can produce an embedding in the finitely generated case. This is an easy corollary of Grillet's theorem.

Grillet's theorem. a monoid is finitely generated commutative cancellative reduced monoid iff it is embeddable in $\mathbb{N}^n$.

Corollary. a finitely generated commutative cancellative J-trivial monoid is embeddable in $\mathbb{N}^n$ iff it is torsion-free

This demonstrates that the only properties necessary to demonstrate that a finitely generated commutative J-trivial semigroup is embeddable in $\mathbb{N}^n$ is that it is cancellative and torsion-free. These semigroups can therefore be expressed as multiset addition semigroups.

Factorisation in $F(S)$ subsemimodules

The free commutative semigroup $F(S)$ is a $\mathbb{N}$ semimodule, and so most important operations over it can be solved by linear algebra over the natural numbers. A finitely generated subsemirgoup of $F(S)$ can be described by the span of a multiset system $\{M_1,M_2,...\}$ which is the set of all linear combinations of the system of multisets. Each solution is a different factorisation.

Example 1. consider the subsemigroup $xy,x^2,y^2$. Then every factorisation of $x^n,y^m$ is a solution of the following system of linear equations: \[ \begin{bmatrix} 1 & 2 & 0 \\ 1 & 0 & 2 \end{bmatrix} * v = \begin{bmatrix} n \\ m \end{bmatrix} \] Each solution to the system of linear equations produces a different factorisation of the multiset. For example, $x^4y^4$ has three factorisations: $(x^2)^2(y^2)^2$,$(xy)^2x^2y^2$,$(xy)^4$.

Example 2. consider the subsemigroup $x^3,x^2y,xy^2,y^3$. Then a factorisation of $x^n,y^m$ is a solution to the following system of linear equations: \[ \begin{bmatrix} 3 & 2 & 1 & 0 \\ 0 & 1 & 2 & 3 \end{bmatrix} * v = \begin{bmatrix} n \\ m \end{bmatrix} \] Now $x^6 y^6$ has five factorisations: $(x^3)^2(y^3)^2$, $(xy^2)^2 (x^2y)^2$, $x^3 y^3 x^2y xy^2$, $x^3 (xy^2)^3$, $y^3 (yx^2)^3$.

This demonstrates by linear factorisation, that not all commutative J-trivial cancellative torsion-free finitely generated semigroups have unique factorisations. Although $F(S)$ does have unique factorisations, so that each element is uniquely expressed as a multiset.

Definition. a commutative J-trivial semigroup is called factorial provided that every element has a unique factorisation.

Example. the condensation $\frac{*}{H}$ of the multiplicative semigroup $*$ of a UFD is a factorial commutative cancellative J-trivial semigroup.

Notice that $x^2,y^2,xy$ determines a commutative subsemigroup but $x^2,x^2,xy,x^2y^2$ determines the same semigroup. We therefore need one more concept in order to enable computations on multiset systems related to the subsemigroups they generate:

Definition. a multiset system $S$ is sum minimal provided that $\forall x : x \not\in (S-x)$ so that no element $x$ is generated by the other elements in the multiset system.

For example, we can describe a numerical semigroup by a minimal set of generators, which is a simple combinatorial data structure we can work with. With this definition, it is a fairly simple procedure to create an algorithm to check if a given multiset system is sum minimal by solving a system of linear equations to check for factorisations of each element.

Proposition. the category of free commutative monoids is equivalent to the category of $\mathbb{N}$ semimodules with natural matrices between them.

The linear algebraic approach to free $\mathbb{N}$ semimodules allows us to describe any homomorphism of $\mathbb{N}$ semimodules by natural matrices. In particular, the endomorphism semiring $End(F(S))$ of a free commutative semimodule is equivalent to a matrix ring $Mat_S(\mathbb{N})$ over the semiring of natural numbers.

The factorisation of multisets can be determined by solving systems of linear equations over the natural numbers, or by determining the inverse image of a natural-valued matrix. This leads to the linear algebraic approach to $\mathbb{N}$ semimodules.