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.