Horizontal categorification of binary operations

A fundamental first step in our understanding of abstract algebra is the process by which we can translate from a single-object structure like a monoid to get its many-object variant such as a category. In particular, it is by this process that we can consider generalisations of categories like magmoids.

Operation	Oidification
Partial magma	Partial magmoid
Magma	Magmoid
Semigroup	Semigroupoid
Monoid	Category
Group	Groupoid

For example, it is by this process by which I have managed to consider additional generalisations of categories like partial magmoids. In this context, a partial magmoid is simply the horizontal categorification of a partial magma. Partial magmoids are useful in the study of quotients.

I emphasize this comparison to demonstrate that semigroups and categories are not profoundly different subjects. Categories and monoids are alike in almost every way as they lie together on a common axis of odification. Either one can be used to study the other for all intents and purposes. Categories are just the nicer way of looking at things is all.

A far greater difference actually lies between order theory on the one hand and either category theory / semigroup theory on the other. The later subjects have far more algebraic flavour and can be seen as ways of studying higher forms of preorders, enriched with extra algebraic structure. Categories are like higher preorders. So these are far more genuinely different subjects.

Horizontal categorification is a nice tool that we can use to group mathematical subjects together. Subjects that are on the same line of horizontal categorification are the most similar to one another, and those subjects that are not are the most genuinely different from one another.

References:
Horizontal categorification

On the arrow category of partial semigroups

In the theory of semigroups of atomic charts, I described how categories are like partial semigroup homomorphisms from the partial semigroup of a category to the complete brandt semigroup of atomic charts. This is part of the partial algebraic theory of categories, which we can now extend here to deal with functors.

Definition. the category $PS$ of partial semigroups has two components:

• Objects: all maps $*: R \to X$ with $R \subseteq X^2$ that form partial semigroups so that if $(ab)c$ exists then so does $a(bc)$ and whenever they both exist they coincide $a(bc) = (ab)c$
• Morphisms: homomorphisms $f: (*_X: R \to X) \to (*_Y: S \to Y)$ defined by mappings of the form $f: X \to Y$ with the property that whenever $ab$ exists then $f(a)f(b)$ exists and $f(ab) = f(a)f(b)$

Then the arrow category of $PS$ is the standard arrow category defined in category theory: $PS^{\to}$. We will show that every category is associated to a partial semigroup homomorphism and every functor is associated to a morphism of partial semigroup homomorphisms in the arrow category. This leads to a functor: \[ A : Cat \to PS^{\to} \] This functor is the main way that we will form the partial algebraic theory of categories. In doing so, we will see that categories are just special types of actions in partial algebra.

Definition. the functor $A: Cat \to PS^{\to}$ has two components:

• the object part takes any category $C$ to a partial semigroup homomorphism $A(C): (Arrows(C),\circ) \to S_{Ob(C)}$ where $(Arrows(C),\circ)$ is the composition partial semigroup of the category and $S_{Ob(C)}$ is the complete brandt semigroup of partial transformations on the object set $Ob(C)$. Let $m: X \to Y$ be a morphism in $C$ then $A(C)(m)$ maps to the atomic action $(x,y) \in S_{Ob(C)}$.
• the morphism part takes any functor $F: C \to D$ to a morphism of partial semigroup homomorphisms $A(F) : A(C) \to A(D)$ which as a member of an arrow category has two components: (1) the arrow part of the functor $F$ which is a partial semigroup homomorphism from $(C,\circ)$ to $(D,\circ)$ and (2) a partial semigroup homomorphism of atomic partial transformation semigroups from $S_{Ob(C)}$ to $S_{Ob(D)}$ that maps $(x,y)$ to $(f(x),f(y))$.

This defines the object and morphism parts of the functor $A: Cat \to PS^{\to}$ and it describes how categories can be mapped to semigroup homomorphisms, while functors can be mapped to morphisms of partial semigroup morphisms but it doesn't definitively prove that this is a valid functor.

Theorem. the mapping $A: Cat \to PS^{\to}$ is a functor.

Proof. $A$ is a mapping from $Cat$ to $PS^{\to}$ which a functor to a morphism of partial semigroup homomorphisms. This forms a commutative diagram of the following form: Let $m : A \to B$ be an arrow in $C$ then by this commutative diagram we want to show that $A(F_M(m)) = F^*_O(A(m))$. In the first place $F(m) : F(A) \to F(B)$ so that $A(F(m)) = (F(A),F(B))$. On the other hand, $A(m) = (a,b)$ and $F(A(m)) = (f(a),f(b))$. It follows that this is a valid morphism of partial semigroups, so that $A : Cat \to PS^{\to}$ is a functor. $\square$

This demostrates the usefulness of the partial algebra construction, as every category can now be associated to partial semigroup homomorphism. We see that in general, all algebra should be done with a partial algebraic perspective in mind because that is how categories work. Categories are partially defined on composable morphisms, and so they are related to a number of interesting constructions in partial algebra.

References:
Semigroups of trivial charts

Preservation and reflection of subsemigroups

The functoriality of the Alexandrov topology of a thin category is a good first example of the broad theme of functorially produced set systems of algebraic structures. In order to continue along these lines we need to generalize from the category $Top$ of topological spaces and continuous maps to the categories of hypergraphs and either reflecting or preserving maps respectively. These produce functors that can be defined, for example over the category of semigroups.

Theorem. let $f : S \to T$ be a morphism of semigroups. Then $f$ preserves subsemigroups.

Proof. let $A \subseteq S$ then $\forall a_1,a_2 \in A: a1_a2 \in A$. So consider the image $f(A)$ and let $t_1,t_2 \in f(A)$ then there exists $a, b$ such that $f(a) = t_1$ and $f(b) = t_2$. Now consider the product $f(a)f(b)$ then by the definition of semigroup homomorphisms this is equal to $f(ab)$ but we have that $ab \in A$ so $t_1t_2 = f(ab) \in f(A)$ so that $f(A)$ is composition closed. $\square$

Theorem. let $f: S \to T$ be a morphism of semigroups. Then $f$ reflects subsemigroups.

Proof. let $B \subseteq T$ then $f^{-1}(B)$ is a subset of $S$. Suppose that $x,y \in f^{-1}(B)$ then $f(x) \in B$ and $f(y) \in B$. The product $f(xy)$ is equal to $f(x)f(y)$ by the definition of semigroup homomorphisms. Then since $f(x)$ is in $B$, $f(y)$ is in $B$ and $B$ is composition closed $f(xy) = f(x)f(y)$ is in $B$ which implies that $f^{-1}(B)$ is composition closed. $\square$

Theorem. let $f: M \to N$ be a morphism of monoids. Then $f$ preserves and reflect submonoids.

Proof. (1) let $S \subseteq M$ be a submonoid of $M$ then $1 \in S$ and by the definition of monoid homomorphisms $f(1)$ is the identity of $M$ so $1 \in f(S)$. (2) In the other direction, suppose that $S \subseteq M$ is a submonoid so that $1_N \in S$ then by the definition of monoid homomorphisms $f(1_M) = 1_M$ so that $1_M \in f^{-1}(S)$ so that monoid maps reflect identities. (3) then since $f$ preserves and reflects identities as well as subsemigroups it necessarily must also do so for submonoids as well. $\square$

Theorem. let $f: G \to H$ be a group homomorphism. Then $g$ preserves and reflects subgroups.

Proof. (1) let $S \subseteq G$ be a subgroup. Then for all $s \in S$ we have that $-s \in S$. Then consider $f(S)$ if $h$ is in $f(S)$ then we have that there exists $g$ such that $f(g) = h$. Then consider $-h$ by the definition of group homomorphisms $f(-g) = -h$ but then $-g$ is in $S$ because $S$ is a subgroup and therefore inverse closed. It follows that $f(-g) = -h$ is in $f(S)$ so that the image is a subgroup.

(2) in the other direction suppose that $S \subseteq H$ is a subgroup. Then $\forall s \in S : -s \in S$. Suppose that $g \in G$ and $f(g) \in S$. Then $f(-g) = -f(g)$ by the definition of group homomorphisms. By the fact that $S$ is a subgroup and $f(g)$ is in $S$ we have that $-f(g)$ is in $S$ which implies that $f^{-1}(S)$ is inverse closed for all $g \in f^{-1}(S)$. It follows that it is a subgroup. $\square$

We saw that monotone maps reflect ideals over thin categories. A generalization of this which is applicable to semigroups involves the reflection of semigroup ideals, which can be either left, right, or two sided. This produces a functor from the category of semigroups to the category of topological spaces.

Theorem. let $f : S \to T$ be a morphism of semigroups. Then $f$ reflects left, right, or two sided ideals.

Proof. let $I$ be a left ideal of $T$ then we have that for all $i \in I$ and $t \in T$ it holds that $it \in T$. So consider $f^{-1}(I)$ then if we have $x \in f^{-1}(I)$ it follows that $f(x) \in I$. Let $s \ in S$ then $f(sx) = f(s)f(x)$ and since $f(x)$ is in $I$ and $I$ is a left ideal $f(s)f(x)$ is in $I$. So $f$ reflects left ideals and by dualizing it reflects right ideals. By combining this $f$ reflects two sided ideals. $\square$

It is not enough for us to show that semigroup homomorphisms reflect subsemigroups. We would also like to know that they reflect prime ideals. This will then allow us to reproduce the familiar theorems of ring theory dealing with prime ideals.

Theorem. let $f : A \to B$ be a morphism of semigroups then $f$ reflects prime subsemigroups.

Proof. let $P \subseteq B$ be a prime subsemigroup then we have that $Q = B-P$ is a subsemigroup and in total we have $P,Q$ are subsemigroups with $P \cup Q = B$ and $P \cap Q = \emptyset$. Every element of $A$ produces some image, so by the fact that inverse images are lattice homomorphisms we have $f^{-1}(P) \cup f^{-1}(Q) = A$ and $f^{-1}(P) \cap f^{-1}(Q) = \emptyset$. So by the fact that $f$ reflects subsemigroups it follows that $f^{-1}(P)$ is a subsemigroup with complement subsemigroup $f^{-1}(Q)$. $\square$

Corollary. let $f : S \to T$ be a morphism of semigroups. Then $f$ reflects prime ideals.

The one other class of ideals we are really interested in are the radical ideals, especially in commutative algebra because of theri relationship to algebraic varieties under Hilbert'z nullstellensatz. There is a corresponding notion for semigroups, and so by considering that we will get closer to solving some problems related to radical subsemigroups and ideals.

Theorem. let $f : S \to T$ be a morphism of semigroups. Then $f$ reflects radical subsemigroups.

Proof. let $B \subseteq T$ be a radical subsemigroup. Then $f^{-1}(B)$ is a subsemigroup of $S$ because $f$ reflects subsemigroups, so it remains to show that $f^{-1}(B)$ is a radical subsemigroup. Let $x \in f^{-1}(B)$ and suppose that $y^n = x$ Then we can apply $f$ to both sides to get $f(y^n) = f(x)$ and expanding this $f(y)^n = f(x)$. Now since, $f(x)$ is in $B$ and $B$ is radical this implies that $f(y) \in B$. So to sum up this means that $f^{-1}(B)$ is a radical subsemigroup. $\square$

Corollary. let $f : S \to T$ be a morphism of semigroups. Then $f$ reflects semigroup radical ideals.

We can apply these semigroup theorems to our favourite algebraic structures, all of which are constructed out of semigroups. Like lattices (thin categories with all products and coproducts), semirings, and rings. In particular, this is enough to recover that the pre image of a prime ideal of a ring is a prime ideal.

Corollaries.

• Lattice homomorphisms preserve and reflect sublattices
• Semigroup homomorphisms preserve and reflect subsemirings
• Ring homomorphisms preserve and reflect subrings
• Ring homomorphisms reflect left, right, and two sided ideals, prime ideals, and radical ideals

It is always nice to apply our theorems to semigroups so that they have the widest degree of applicability to other common algebraic structures like lattices and semirings, but in the process we also recovered theorems applicable to rings. Each of these different notions of preservation and reflection naturally produce functors over appropriate categories.

Functorality of Green's relations

Green's relations are part of the relationship between order theory and monoid theory. Green's relations can be expressed in category theory as functors from the categories of monoids to the category of preorders, both of which are full subcategories of the category of categories $Cat$.

Theorem. Green's preorders $\subseteq_L, \subseteq_R, \subseteq_J$ are forgetful functors from the category of monoids to the categories of preorders. \[ \subseteq_L : Mon \to Ord \] \[ \subseteq_R : Mon \to Ord \] \[ \subseteq_J : Mon \to Ord \] Proof. (1) suppose that that $a \subseteq_L b$ then $\exists x : xa = b$ which implies that $f(x)f(a) = f(b)$. This implies that $f(a) \subseteq_L f(b)$ by $f(x)$.

(2) similarly, if $a \subseteq_R b$ then $\exists y: ay = b$ which implies that $f(a)f(y) = f(b)$. This implies that $f(a) \subseteq_R f(b)$ by $f(y)$.

(3) finally, by combining the two we have that $a \subseteq_J b$ then $\exists x,y : xay = b$. This implies that $f(x)f(a)f(y) = f(b)$ which implies that $f(a) \subseteq f(b)$ by $f(x)$ and $f(y)$. $\square$

Green's preorders are functors from the category of monoids to the category of preorders, and Green's relations are as well. The only difference is that Green's relations are always symmetric.

Theorem. Green's relations $L,R,J,D,H$ are functors from the category of monoids to the category of preorders.

Proof. (1) suppose that $a \text{ L } b$ then $a \subseteq_L b$ and $b \subseteq_L a$ so by functoriality $f(a) \subseteq_L f(b)$ and $f(b) \subseteq_L f(a)$ which implies that $f(a) \text{ L } f(b)$. The same applies for $R$ and $J$.

(2) suppose that $a \text { H } b$ then $a \text{ L } b$ and $a \text{ R } b$. By part (1) we have that this implies $f(a) \text{ L } f(b)$ and $f(a) \text{ R } f(b)$. By combination this implies $f(a) \text{ H } f(b)$.

(3) finalyl suppose that $a \text{ D } b$ then because $D$ is defined by transitive closure this implies that there is a chain $a \text{ L } x_1 \text{ R } ... \text{ L } x_n \text{ R } b$. Then we can apply $f$ to this chain of relations to get $f(a) \text{ L } f(x_1) \text{ R} ... \text{ L } f(x_n) \text{ R} f(b)$. This implies that $f(a) \text{ D } f(b)$. $\square$

Green's preorders can be defined as the action preorders of monoid actions, but this is not functorial because each monoid has a different topos of monoid actions, so there is no single output category to define a functor for. So we are going to have make do with the functorality of Green's relations for now.

These theorems can be used as a foundation of a number of more advanced constructions in semigroup theory. For example, we can use this to show that monotone maps reflect ideals from which it follows that semigroup morphism reflect ideals as well. That ring maps reflect ideals immediately follows.

Algebraic laws of motion

The three subjects of order theory, semigroup theory, and category theory clearly form a common whole, described by the algebraic laws of motion. As algebraic descriptions of change, the closest relatives of categories are monoid actions. A common framework for describing the algebraic preorders associated to categories, monoids, etc will be presented based upon the laws of motion.

This is distinguished from the geometric theory of motion in a Lorentzian manifold. In that context, the laws of motion dictate that objects can only move along time-like future-pointing curves. This creates a geometric preorder on a Lorentzian manifold. As a consequence, there are both algebraic and geometric theories of motion.

Transformations:

Functions are among the most basic units of mathematics alongside sets. We will start by describing the changes in a set by functions from the set back to itself. This is generalized to include partial transformations, which allow us to describe changes on only parts of a set back to themselves.

• Transformations
• Permutations
• Partial transformations
• Charts

A first realization is that each of these units of change produce different types of semigroups. Permutations produce groups which are structures whose motions are reversible. Inverse semigroups of charts are their partial transformation counterpart. Total and partial transformations both lead to monoids.

Monotone Galois connections:

The different types of actions by transformations, permutations, charts, etc all necessarily produce preorders that describe how they move the elements of the sets they act upon.

Definitions. let $X$ be a set then for any set of partial transformations $S$ we define $Rel(S)$ to be the preorder closure of the set of all ordered pairs of $S$. For a preorder $R$ we define $Full(R)$ to be the full set of all partial transformations whose ordered pairs are in $R$. \[ Rel : Sub(PT_X) \to Po(X) \] \[ Full : Po(X) \to Sub(PT_X) \] Then these two form adjoints of one another between the lattice of preorders $Po(X)$ and the lattice of partial transformation semigroups $Sub(PT_X)$. $Rel$ is a lower adjoint and $Full$ is an upper adjoint.

Theorem. $Rel$ and $Full$ are adjoints of one another. \[ S \subseteq Full(R) \Leftrightarrow Rel(S) \subseteq R \] Proof. (1) suppose that $Rel(S) \subseteq R$ then every partial transformation of $S$ is included in $R$, so that $S \subseteq Full(R)$. (2) suppose that $S \subseteq Full(R)$ then every partial transformation of $S$ is included in $R$, which implies that $Rel(S) \subseteq S$. $\square$

The monotonicity of $Rel$ means that the larger a set of motions, the larger the corresponding preorder it moves in. The same general principle is true for any kind of motion. This is very useful in keeping track of the directions of special types of actions.

The monotone Galois connection between preorders and partial transformations can be restricted to other sets of transformations. Each of the different types of transformations has a corresponding complete system of transformations associated to a preorder: \[ Full : Po(X) \to Sub(PT_X) \] \[ FT : Po(X) \to Sub(T_X) \] \[ FPS : Po(X) \to Sub(PS_X) \] \[ FS : Po(X) \to Sub(S_X) \] These four have the obvious inclusions: $FT(X) \subseteq Full(X)$, $FPS(X) \subseteq Full(X)$, $FS(X) \subseteq FPS(X)$, and $FS(X) \subseteq FPS(X)$. In the case of actions by charts and permutations, we know they often form inverse semigroups or groups.

Theorem. let $E$ be a symmetric preorder on $X$, then $FPS(E)$ is an inverse subsemigroup of $PS_X$ and $FS(X)$ is a subgroup of $S_X$.

Proof. suppose that $p \subseteq E$ then $p^{-1} \subseteq E^{-1}$ because the transpose relation is monotone. $E^{-1} = E$ because $E$ is symmetric, so that $p^{-1} \subseteq E$, which means that $FPS(X)$ is inverse closed and $FS(X)$ is as well. $\square$

There is therefore a natural adjointness relationship between symmetric preorders and orbit symmetric permutation groups, which are the maximal permutation groups with a given orbit. This demonstrates the various ways in which we can get different types of actions from preorders, but there is yet one more.

A preorder $R$ on a set $X$ is a set of ordered pairs $(a,b)$ but an ordered pair is also an atomic partial transformation $\{(a,b)\}$ with a single element. This produces a partial semigroup action associated with any preorder $R$ on its ground set: \[ f: R \to PS_X \] By considering a preorder as an action on a set by atomic partial transformations, we can see that the underlying action preorder of an action is simply a way of reducing a transformation system to its simplest components: which are the ordered pairs that define movements from one point to another.

Monoid actions and categories:

The concept of a transformation semigroup can naturally be generalized to a monoid action. Instead of a fixed set of transformatinos, a monoid action can have a set of elements that transform another set.

* A monoid action is the action of a total semigroup on a set by a set of total transformations. \[ f : M \to T_X \] * A category is the action of a partial semigroup on a set by a set of atomic partial transformations. \[ f : Arrows(C) \to PT_{Ob(C)} \] This demonstrates that the morphisms of a category act on objects. A morphism $f : A \to B$ can move an object from point $A$ to point $B$, which is an atomic partial transformation.

	Elements	Actions
Monoid action	Elements	Transformations
Category	Objects	Morphisms

The action representatives of a monoid action for an ordered pair $(a,b)$ are $\{ m : ma = b \}$. The action representatives in a category are hom classes. The action preorder of a monoid action and the object preordering of a category, are both the underlying action preorders of their underlying partial transformations systems. Finally, the corresponding notion of a faithful monoid action in category is simply a preorder.

Definition. a faithful category is a preorder.

A preorder is a faithful category, because each morphism $f : A \to B$ produces a different atomic partial transformation $\{(A,B)\}$. Faithful categories can therefore be identified uniquely by their action preorders. The opposite notion, a completely faithless category is a trivial monoid action on a single object. In that case, every action of a morphism moves an object back to itself.

The idea of defining actions by atomic partial transformations is so fundamental that categories play an important role in the algebraic theory of motion and change. There closest relatives, as we have seen here are the monoid actions which also play an important role in models of change.

We have described both monoid actions and categories by their actions on an underlying set of objects. But another aspect of the algebraic laws of motion in monoid actions and categories, is that transformations and morphisms can act on themselves.

Definition. let $f : M \to T_X$ be a monoid action of $M$ on $X$. Then $M$ also acts on itself by the left, or right, or two sided actions. Dually for a category $f : Arrows(C) \to PS_{OB(C)}$. Green's preorders are the action preorders of these self-induced actions and Green's relations are defined from them.

The Green's relations merely described the algebraic laws of motion of a monoid, in therefore makes sense that in general they are the most important property of a given monoid. As they are very general concept dealing with the dynamics of motion, they can naturally be generalized to categories.

This produces the left, right, and two sided action preorders of a category. Furthermore, we can get subpreorders by subcategories like the mono preorder and the epi preorder. These produce the mono input action and epi input action preorders whose condensations are the posets of subobjects and quotients of a category.

An immediate difference between monoid actions and categroies is that the former form topoi, and the later do not. But the topoi of monoid actions comes by fixing a given ground monoid $M$ and then considering only $M$ sets, where categories can be constructed from many different kinds of partial semigroups.

A framework for higher category theory:

A general model of algebraic motions arises by keeping track of types of objects and how they can act on each other. In the simplest models of algebraic motion, we only have two types of objects: elements and transformations which can only act on each other in a single way but there is no reason that this cannot be generalized.

A 2-category is an algebraic system of motion, in which 2-morphisms can act on 1-morphisms to move them from point to another, 1-morphisms can act on objects. This is further generalized to tricategories, which are categories that are enriched over 2-categories and so on. In each case, we have a number of types that act on each other.

See also:
[1] Categories for order theorists

[2] Semigroup methods in category theory

References:
[1] Categories

Semigroup methods in category theory

Semigroups and categories have a common origin in associative operations. As a consequence, there are a number of relations between the two constructs. A semigroup can be made into a category by adjoining an identity. In the other direction, a category can be made into a semigroup by adjoining a zero element. In both cases, the respective structures are only one element away.

Proposition. let $S$ be a semigroup then $S+1$ is a category with a single object

The first case, that a semigroup can be made into a single object category is obvious and requires no further proof. Instead, we will investigate the second case. This describes a category as a partial semigroup of non-zero elements of a semigroup with zero.

Proposition. let $C$ be a category then $C+0$ is a semigroup with zero.

A consequence of this construction is that a number of aspects of the bridge between these two subjects are best expressed in terms of semigroupoids instead of categories. Categories are defined in terms of partial identities which don't have a well established counterpart in semigroup theory.

Subsemigroups and zero preserving subsemigroups:

Let $C$ be a category, then the lattice of subsemigroupoids $Sub(C)$ is isomorphic to the sublattice of zero-preserving subsemigroups of the lattice of subsemigroups of $C+0$. So subalgebras cleanly translate between semigroups and semigroupoids and vice versa.

Theorem. let $C$ be a category and $M$ a subset of $Arrows(C)$ then $M$ is a subsemigroupoid iff $M+0$ is a subsemigroup of $C+0$.

Proof. (1) let $S \subseteq C$ be a subsemigroupoid and let $m_1,m_2$ in $S$ then if $m_1,m_2$ exists then $m_1 m_2 \in S$ which implies $m_1m_2 \in S+0$. Suppose instead that $m_1m_2 = 0$ then since $0 \in S+0$ we have that $m_1m_2 \in S+0$. If one of $m_1,m_2$ are not in $S$ then they are equal to zero and $m_1m_2 = 0$ which is in $S+0$. So subsemigroupoids correspond to zero-preserving subsemigroups.

(2) suppose that $X \subseteq S+0$ and $0 \in X$. Then consider $X-0$ then $(X-0) \subseteq C$ so it is a morphism system in the category $C$. Then for each $m_1,m_2 in X$ we have two cases either $m_1m_2 \not= 0$ or $m_1m_2 = 0$. If the former then $m_1m_2 \not= 0$ and $m_1m_2 \in X$ implies that $m_1m_2 \in X-0$ so that $X-0$ is a subsemigroupoid. $\square$

This characterizes the zero-preserving subsemigroups of a category. The other subsemigroups, those that do not contain zero are subsemigroups of endomorphism monoids. A special property of the semigroups with zero of categories is that their maximal zero-free subsemigroups are all disjoint.

Definition. let $S$ be a semigroup with zero, then $S$ satisfies the disjointness condition provided that all the maximal zero free subsemigroups of $S$ are disjoint.

This property is inherent to semigroupoids. As the zero preserving subsemigroups of a semigroupoid, are again semigroup completions of semigroupoids this implies that the disjointness condition is hereditary for semigroupoids. We will show that this is true in general for any semigroup with zero.

Theorem. the disjointness condition is preserved under zero-closed subsemigroups

Proof. let $S$ be a semigroup with zero that satisfies the disjointness condition. Let $P$ be the pairwise disjoint family of maximal zero-free subsemigroups. Then the union of $P$ consists of all non-nilpotent elements of $S$. The nilpotent elements are not in any zero-free subsemigroup because their own monogenic semigroups contain zero. Then $P$ is a partition of the non-nilpotents of $S$ into separate classes.

Let $T$ be a zero preserving subsemigroup of $S$. Then nilpotents are still not in the maximal subsemigroups of $T$. Let $U$ be a subset of $T$ consisting of non-nilpotents. Then in order for $U$ to not include zero it must be $P$-equal so that all elements are contained in a single class of $P$ because if $x$ and $y$ are different classes then the digenic subsemigroup $(x,y)$ must contain zero since it is not contained in any zero-free subsemigroup.

Thusly, all the maximal zero-free subsemigroups of $T$ are subsets of semigroups in $P$. Let $C$ be a $P$ class, then each $C$ has a maximal representative equal to the intersection $C \cap T$ which is again a subsemigroup, by the fact that subsemigroups are intersection closed. So the class of all maximal zero-free subsemigroups of $T$ is equal to $\{ v : v = C \cap T, C \in P \}$. It follows that the disjointness condition is preserved. $\square$

This describes the special class of semigroups with zero satisfying the disjointness condition on maximal zero-free subsemigroups. The following theorem relates this back to categories.

Theorem. let $C$ be a category vith semigroup $C+0$ then maximal zero-free subsemigroups are endomorphism monoids.

Proof. (1) any non-endofunction is nilpotent and so must be excluded (2) non compatible endofunctions with different underlying objects compose to zero and so they must also be excluded. Therefore, every single zero-free subsemigroup is a family of endofunctions of a single object. The maximal families of endofunctions of an object of a category are precisely endomorphism monoids, all of which are disjoint for different objects. $\square$

A key use of this theorem and the disjointness condition on categories, is that we can use it to get the identities of a semigroup with zero of a category. Then with these identities established, we can find subcategories of a semigroup with zero, which are always a restricted case compared to semigroupoids which simply correspond to zero preserving subsemigroups.

Definition. let $C+0$ be a semigroup with zero satisfying the disjointness condition, then the identities of $C+0$ are precisely the identities of all maximal zero-free semigroups (which are all monoids in the case of a category).

So in order to characterize the zero preserving subsemigroups of $C+0$ of a category $C$ that form subcategories, we need to add a special condition on the set of identities $I$ of $C+0$.

Theorem. let $C+0$ be a the semigroup with zero of a category with set of identities $I$. Then $S \subseteq C+0$ is a subcategory if it preserves zero $0 \in S$ and $\forall e \in I, x \in S$ then if $ex \not= 0$ or $xe \not=0$ then $e \in S$.

Proof. let $C$ be a category and let $m : A \to B$ be a morphism then in order for $m$ to preserve its identities in a set $S$ it must be that $1_A \in S$ and $1_B \in S$, but $1_A$ and $1_B$ are precisely the identities for which $m1_A$ and $1_Bm$ are defined so they are $e \in I$ that are compatible with a morphism under composition in the sense of producing non-zero values. $\square$

We can see from this that the characterization of subcategories in semigroup theoretic terms is considerably more involved then the characterization of semigroupoids. In the later case, there is a clean and easy translation between semigroups and semigroupoids. This translation is one of the cleanest components of the bridge between semigroup theory and category theory.

Inverse semigroups and groupoids:

An inverse semigroup is an idempotent commutative regular semigroup. Therefore, in order to characterize categories that form inverse semigroups with zero, it is useful to first consider the properties of the idempotents of a category.

Definition. a category is called an E-category provided that all of its transformation monoids are E-categories. It is idempotent commutative, provided that all of its transformation monoids are.

Lemma. let $C$ be a category then if $C$ is an E-category $C+0$ is an E-semigroup. If $C$ is idempotent commutative then $C+0$ is.

Proof. every idempotent is a category is contained within some endomorphism monoid. Therefore, in an E-category it is contained in a semigroup of idempotents of a transformation monoid. If we take any two transformation monoids, their transformations compose to zero. So by adjoining zero to the set of idempotents, we get that all idempotents together fom a subsemigroup so that $C+0$ is an E-semigroup. If all idempotents are locally idempotent commutative, they are between each other as well as they compose to zero in either order. $\square$

If $C$ is a category all of whose endomorphism monoids are groups, then clearly it is idempotent commutative. We want to show that the semigroup completion of a groupoid is an inverse semigroup, by this lemma this only requires showing that $G+0$ is regular.

Theorem. let $G$ be a groupoid then $G+0$ is an inverse semigroup.

Proof. by the preceding lemma the fact that $G$ is idempotent commutative implies that $G+0$ is as well. Let $a$ be an element of $G+0$ then there are two cases (1) $a = 0$ or (2) $a \not= 0$. In the former case, zero is an idempotent so it is a regular element. In case (2) $a \not= 0$ by the fact that $G$ is a groupoid there exists an inverse $a^{-1}$ such that $aa^{-1}a = a$ which implies that $a$ is a regular element. By the fact that $G+0$ is idempotent commutative and every element is regular, it is an inverse semigroup. $\square$

There are other cases where in the semigroup completion of a category is an inverse semigroup, such as when $C$ is an inverse monoid but in the case of a groupoid we know that it is always an inverse semigroup. As we will see, groupoids produce special types of inverse semigroups.

Theorem. let $G$ be a groupoid then zero preserving inverse subsemigroups of $G+0$ are subgroupoids.

Proof. let $f: A \to A$ be a morphism then $f \circ f^{-1} = 1_A$ so that if $f \in S$ then $1_A \in S$. Then if $f : A \to B$ then $f^{-1} : B \to A$ and $f^{-1} f = 1_A$ and $f f^{-1} = 1_B$ so that $f \in S$ implies that $1_A \in S$ and $1_B \in S$. So $S$ is a subcategory. Then the fact that it is an inverse subsemigroup implies that for any $f$ we have $f^{-1}$ which means that $S$ is inverse closed, which implies that it is a subgroupoid. $\square$

In order to create a structure theorem for groupoids in terms of their semigroup completions, we need to introduce one more basic construction.

Definition. let $A$,$B$ be semigroups with zero then their disjoint union $A+B$ is the semigroup with zero constructed by getting the partial semigroups of $A$ and $B$ by removing their zeros, getting the disjoint union of the two of them, and then adjoining a single zero for the both of them.

Proposition. $A+B$ is a semigroup with zero.

Proof. let $A$ and $B$ are subsemigroups of $A+B$, and whenever zero is an element of a triple $(a,b,c)$ it always produces zero so that triple will be associative. The only remaining case is when we mix $a$ and $b$ terms so suppose that one element is from one of the two semigroups and the other two elements are from the other. Then the other two elements can compose either to zero or an element in themselves, but in either case when the two elements from the two different semigroups compose we get zero so that triple is associative. Therefore, $A+B$ is associative and it is a semigroup. $\square$

Theorem. let $C$ be a category with connected components $P_1,P_2$ then $C+0$ is the semigroup with zero disjoint union of $P_1+0,P_2+0,...$.

Proof. $P_1+0$,$P_2+0$,... are all subsemigroups of $C+0$. Whenever any two components compose they produce zero, so the partial semigroup of $C$ is equal to the disjoint union of its of its connected components. Therefore, $C+0$ is the disjoint union of the semigroups of its connected components. $\square$

The class of groupoids for which $C$ is a disjoint union of groups, is precisely the class of groupoids whose completions $C+0$ are Clifford. This means that each groupoid is a semigroup disjoint union of a collection of semigroups with zero of connected groupoids.

Theorem. let $G$ be a connected groupoid. Then $G+0$ is a Brandt semigroup.

Proof. let $f : A \to B$ be a morphism and $g : A \to C$ be another. Then $(gf^{-1})f = g$. In the other direction, $f : A \to C$ and $g : B \to C$ are morphisms. Then $f(f^{-1})g = g$. So that the only invariants of $L$ and $R$ are the input and output objects, which implies that $G$ is $D$ total and $J$ total, and since $S+0$ is group bound this implies that it is a 0-simple semigroup and hence Brandt. $\square$

The $H$ classes of the Brandt semigroup of a groupoid are precisely the automorphism groups. With this, we can characterize the structure of the semigroups with zero of groupoids.

Corollary. let $G$ be a groupoid then $G+0$ is the disjoint union of semigroups with zero of Brandt semigroups.

The $H$ classes contained in the same $D$ class are isomorphic groups. Therefore, the fact that the groups in the same connected component of a groupoid are isomorphic is merely a special case of this fact.

Green's relations:

The Green's preorder can be determined by the action preorders of certain monoid actions. In order to do something similar for categories, we need a theory of partial semigroups, partial transformations, and partial semigroup actions.

Proposition. 0-semigroups are in one to one correspondence with partial semigroups satisfying the conditions of associativity and existence associativity ($a(bc)$ exists is logically equivalent to $(ab)c$ existing).

We can define an analogue of the self-induced monoid actions of a semigroup, by defining self-induced partial transformations of a category. These are mappings from the arrows of a category to the semigroup of partial transformations $PT_S$. \[ L : S \to PT_S \] \[ R : S \to PT_S \] We can therefore safely say even though the action of morphisms on category is not a monoid action, there is a type of action which moves one morphism to another. Here are some of the properties of the partial transformation representation:

Theorem. $L : S \to PT_S$ is a partial semigroup homomorphism and $R : S \to PT_S$ is a partial semigroup anti homomorphism.

Proof. if we have $L(ab)(x)$ then this is equal to $(ab)x$ which by associativity is equal to $a(bx)$ which can be expressed as $[L(a)\circ L(b)](x)$. The right action anti homomorphism is defined dually. $\square$

The partial transformation representation of morphisms is similar to the functor of points used to define Yoneda's lemma. A basic difference is that the functors of points are centered around individual objects, and the partial transformation representation is concerned solely with the properties of morphisms.

Definition. let $X \subseteq PT_S$ be a subsemigroup of the complete semigroup of partial transformations. Let the partial action preorder on $S$ defined by $X$ is the preorder closure of all the single valued binary relations defined by the partial transformations in $X$.

With this, we can simply define the $L$ and $R$ action preorders of a category as the partial action preorders of the $L$ and $R$ partial transformation representations.

Definition. let $C$ be a category then $L$ and $R$ are the partial action preorders of the partial action representations in the complete semigroup of partial transformations $PT_S$. Then $J$ is the partial action preorder of the union of the partial transformation semigroups produced by $L$ and $R$.

The Green's relations $L,R,J,D,H$ are defined by the Green's preorders and their interesctions in the obvious manner. Then if $C$ is a category, $C+0$ is a semigroup and the zero element is J-trivial. Therefore, each Green's relations is equal to the Green's relations of the category with a zero element adjoined.

Definition. let $C$ be a category then the Green's relations of $C+0$ are the Green's relations of the category $C$ with a distinguished zero element adjoined to each of them.

Furthermore, the semigroup ideals of the semigroup $C+0$ are simply the categorical ideals of $C$ except with a zero element adjoined. With this, we can define the Green's relations of the semigroup completion of a category.

Hom class congruence

Recall that the hom class equivalence of a category forms a congruence whose quotient is the underlying thin category of the category. We can generalize this to semigroups, by first defining underlying transitions.

Definition. let $S$ be a semigroup with zero, whose maximal zerofree subsemigroups are monoids, and let $I$ be its set of identities. Let $x \in S$ be a non-zero element. Then the underlying transition $(i,o)$ of $x$ is the ordered pair of identities in $I$ such that $xi \not= 0$ and $ox \not= 0$.

Theorem. let $C$ be a category, then the underlying transition forms a congruence on $C+0$.

Proof. form the idempotent semiring of the category $\wp(Arrows(C))$. Then the underlying relation $R$ forms a congruence of $\wp(Arrows(C)))$ so in particular it also forms a congruence of its multiplicative semigroup. This produces an endomorphism of semigroups $q : * \to \frac{*}{R}$. Then we have an inclusion map into the multiplicative semigroup by defining all max size one morphism systems $q \circ i : C+0 \to * \to \frac{*}{R}$ whose equivalence relation is the restriction of the congruence $R$, and by the fundamental theorem of semigroup homomorphisms $R|_i$ is a congruence. $\square$

It is not hard to see that the quotient semigroup $C+0$ is a semigroup of trivial charts (embedding in the complete brandt semigroup of trivial charts $K_n+0$ by correspondence with the case of thin categories). Thusly, this connects every category to semigroups of trivial charts, likewise for semigroupoids.

Proposition. $\frac{C+0}{R}$ is a semigroup of trivial charts.

In terms of the Green's relations, we have that if $a \subseteq b$ in $C+0$ then $\pi(a) \subseteq \pi(b)$ in $\frac{C+0}{R}$. This is the semigroup characterisation of the monotonicity of morphism properties.

The commuting graph of a category is not something we typically think about, but as a binary operation even categories can have commuting elements. The commuting graph of a category as partial semigroup is the union of the commuting graphs of each endomorphism monoid. The commuting graph of the semigroup completion is a bit bigger.

Proposition. let $C$ be a category then $Com(C+0)$ the commuting graph of the semigroup completion of $C$ is equal to the union of the symmetric component of the zero divisor graph of $C$ and the commuting graphs of all endomorphism monoids of $C$.

Proof. (1) the symmetric component of the zero divisor graph is a part of the commuting graph, because the commuting graph is the union of the symmetric components of all the fibers of the binary operation (2) in order for any two elements of $C+0$ to commute such that they are not composing to zero then they most be like endofunctions because the partial semigroup of a thin category is anticommutative. So as the elements must be like endofunctions, they are in the same transformation monoid. Commutativity of like endofunctions is then determined by the commuting graphs of each endomorphism monoid. $\square$

The non-existence commutativity conditions in the semigroup completion aren't that important to category theory itself, which is why commutativity is not typically dealt with in categories to the same extent as semigroups. The zero divisor graph determined this way is always an inflation of the zero divisor graph of the underlying quotient semigroup of trivial charts. The complement is the domain of the partial semigroup of the category.

Proposition. let $C$ be a category, then the domain of the partial semigroup $\circ$ of $C$ is equal to the non zero divisor graph of $C+0$.

With this, we can recover the partial semigroup of a category from its semigroup with zero. As seen here, there are a number of other properties of categories that can be recovered from their semigroup completions.

See also:
[1] Categories for order theorists

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.

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.

R-trivial semigroups

The monoid of increasing actions on a poset is R-trivial. This leads to the following question: can all R-trivial semigroups be embedded within a monoid of increasing actions on a poset. We will prove the affirmative, and demonstrate a couple of ways to go about producing an embedding.

Lemma 1. let $S$ be an R-faithful R-trivial semigroup, then its representation by left actions produces an embedding into the monoid of increasing actions on $\subseteq_R$.

Proof. $S$ induces a monoid action on itself by left actions, this monoid action in turn induces a preorder on $S$. If $R$ is trivial, then left actions on $S$ are antisymmetric ($R$ follows from defining right principal ideals as $aS^1$). Then this produces a semigroup homomorphism from $S$ into a monoid of increasing actions on $\subseteq_R$. This is injective provided that the representation of $S$ by left actions is faithful. $\square$

Lemma 2. let $S$ be a monoid then it is left and right faithful.

Proof. $S$ has an identity element $e$, so that for all $x,y$ we have $ex \not= ey$ and $xe \not= ye$ so that $x$ and $y$ cannot have equal left or right actions. $\square$

Theorem 1. every $R$ trivial monoid is a monoid of increasing actions on itself ordered by $\subseteq_R$.

Proof. by lemma 2 $R$ has a faithful representation by left actions and by lemma 1, it therefore has an embedding into the monoid of increasing actions on itself ordered by $\subseteq_R$. $\square$

As an example, a right zero band is a faithless extension of the unique increasing identity action on an antichain. In such a R-trivial band, each element is also a left identity. Although its actions are all increasing, its faithlessness means it cannot be represented by left actions. We can fix this by adjoining an identity, to get an R-trivial monoid.

Theorem 2. let $S$ be an R-trivial semigroup, then it can be embedded in a monoid of increasing actions.

Proof. $S$ is an R-trivial monoid, then let $S^1$ be the monoid constructed from $S$ by adjoining an identity $e$. Then $e$ is a J-trivial element, so that $S^1$ is R-trivial. $S$ is also an ideal in $S^1$. Therefore, by theorem 1 this produces an embedding of $S$ into $S^1$ which is a monoid of increasing actions on itself. $\square$

We saw that a rectangular band cannot faithfully be represented by its increasing actions on itself. By embedding it in a monoid we have resolved that issue. Consider the height two tree ordered set $[1,n]$, then its monoid of increasing actions is precisely a rectangular band plus the identity. So the rectangular band is a subsemigroup of increasing actions produced by removing the identity action.

Every category is associated to its dual category, so a R-trivial monoid of increasing actions has an order dual L-trivial monoid of increasing actions. By duality, this produces a classification of both L-trivial and R-trivial monoids in terms of increasing actions on partial orders.

Corollary. every $L$ trivial monoid is dual to a monoid of increasing actions.

The difference between $L$ triviality and $R$ triviality isn't so important, and it is only a matter of representation. In either case, L-trivial and R-trivial monoids can be studied by increasing actions on certain posets. A J-trivial monoid can also be considered to be a system of increasing actions on a poset, in either direction.

Example 1. the commutative J-trivial monoid $(\mathbb{N},+)$ can be seen as a monoid of increasing actions: each addition operation by a non-negative integer produces a larger number. Dually with respect to $(\mathbb{N},*)$ over the divisibility ordering.

Example 2. the three element non-commutative totally ordered semigroup $T_3^*$ can be embedded in the monoid of increasing actions on a total order on three elements $T_3$ by $[1,2,3],[2,3,3],[3,3,3]$. In this case, $T_3^*$ is also embeddable in the submonoid of increasing monotone actions. Its dual semigroup is not faithful.

Example 3. in a rectangular band $S$ both $L$ and $R$ form congruences with $L$ trivial and $R$ trivial quotients, and $S$ is the direct product of $\frac{S}{L}$ and $\frac{S}{R}$. As a direct product, $L$ and $R$ also form direct products in the semilattice of set partitions.

Directed preorders and semigroups

It should be readily apparent that not all posets can appear as the orderings of J-trivial semigroups. By the same token, not all preorders can arise from semigroups in general. A first thought is that perhaps all orderings of J-trivial semigroups are semilattices, but of course this isn't the case for semigroups of order greater then four: because there is a unique [2,2,1] weak ordered commutative J-trivial semigroup. What we can get is a generalisation of semilattices: the class of directed posets.

Theorem. let $S$ be a semigroup then its algebraic $J$ preorder $\subseteq$ is a directed preorder, which means that every two elements $a$ and $b$ have an upper bound.

Proof. let $a,b \in S$ then we can construct an upper bound by $ab$ $\square$

Corollary. every J-trivial semigroup is a directed poset.

Directed posets can be seen to be the posets that have some kind of compositional process associated to them, even if that compositional process is not a semilattice. Upper bounds correspond to the composition of elements.

Example. the free non-commutative semigroup $S$ on a set of generators $X$ is a J-trivial semigroup, whose partial ordering is the consecutive subsequence ordering. This is not a semilattice, but it is directed because any two words have an upper bound provided by their composition.

The example of the free non-commutative semigroup should demonstrate that $L$ and $R$ preorders are not directed in general, even though $J$ is. The prefix and postfix orderings on the free non-commutative semigroups are trees, so elements don't have an upper bound unless they are comparable. There is also the example of a pure rectangular band, which has one of its $L$ or $R$ preorders an antichain.

The reason every pair of elements in a semigroup has an upper bound, is every element has a composition that exists. It follows that in a partial semigroup such as a category, its preorder need not be directed. Morphisms in different connected components don't need to have an upper bound.

• The $L$ and $R$ preorders of a semigroup need not be directed.
• The morphism preorder of a category need not be directed.

A directed preorder describes a set of elements for which a compositional process exists, but those don't need to exist in a partial semigroup such as a category. Nonetheless, we can use directed posets in the study of J-trivial semigroups. Directed posets still have suprema they just don't need to be unique, so we have to adjust the theory a little bit.

Rectangular band-free semigroups

The least commutative semigroups are rectangular bands, so the condition that a semigroup is rectangular band free is a natural generalization of commutativity. It means that there are no non-trivial anticommutative subsemigroups. Idempotent commutative semigroups such as inverse semigroups are rectangular band free.

It can be seen to be dual to E-semigroups, because all rectangular-band free E-semigroups are idempotent commutative. This follows from Clifford's theorem which characterizes all rectangular band free semigroups as semilattices. As a result, the intersection of the class of rectangular band free semigroups and E-semigroups is the class of idempotent commutative semigroups.

Definition. a semigroup is rectangular band free if it contains no subsemigroups of order two or greater that are rectangular bands

The relationship between rectangular band freeness and idempotent commutativity are dealt with in the following ontology of classes of semigroups. Idempotent commutative semigroups, as well as commutative semigroups themselves are rectangular-band free. While the relationship between idempotent commutativity and rectangular band freeness is interesting. It is also noticeable that rectangular band free semigroups tend to be divisibility commutative (L=R) for the smallest semigroups. Rectangular bands are responsible for different L and R relations in the smallest semigroups.

The weakest generalisation of commutativity is that semigroups be anticommutative semigroup free, because the anticommutative semigroups clearly have the least commutative behaviour (the most different Green's L and R relations, the least commutativity, etc). As a result, it is worth highlighting this as a possible generalisation of commutativity.

Proposition. a semigroup of order four or less is divisibility commutative iff it is rectangular band free

We see that semigroups that are of order four or less are rectangular band free iff they are divisibility commutative, but by no means is this the case in general. If it were, then every inverse semigroup would be Clifford.

Example 1. the inverse semigroup on five elements containing all non-permutation charts on two elements is the smallest non-Clifford inverse semigroup. It is idempotent commutative but not divisibility commutative. In general, non-trivial symmetric inverse semigroups are rectangular band free but not divisibility commutative.

Example 2. the monoid of increasing monotone increasings on a three element total order, is a four element tree ordered J-trivial semiband. As a non-commutative J-trivial semiband it is rectangular band free and not idempotent commutativity. In general, non-commutative J-trivial semibands are rectangular band free and not idempotent commutative.

The existence of non-commutative J-trivial semibands as well as non-Clifford inverse semigroups demonstrates that while rectangular band freeness is bascially the weakest generalisation of commutativity (by forbidding anticommutative components) it doesn't imply any of the other nice conditions like divisibility commutative and idempotent commutativity.

There are a couple of things that can be said about the commuting graphs of rectangular band free semigroups. A graph is idempotent commutative provided that all singleton centralizers form a clique. It is rectangular band free only if no non-trivial centralizers are independent sets. The cyclic graph $C_4$ is an ordered pair of rectangular bands in two different ways, so it cannot be rectangular band free.

In general, a complete bipartite graph $K_{n,m}$ with $n,m \ge 2$ is an ordered pair of rectangular bands, and so it cannot be rectangular band free, for example. The path graph $P_4$ on four elements is not idempotent commutative, but it doesn't have any commutativity necessary rectangular band subsemigroups, so it is an example of the weaker condition.

See also:
[1] Divisibility commutativity

[2] Idempotent commutativity