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