Are rings really more fundamental objects than semi-rings?

Semirings are pervasive throughout computer science: every notion of resource lacking a corresponding notion of debt gives rise to semiring structure in a standard way.

  1. First, you formalize resource as a (partial) commutative monoid. That is, you have a set representing resources (for example, time bounds or memory usage of a computer program), and the monoidal structure has the unit representing "no resource", and the concatenation representing "combine these two resources".

  2. Then, you can generate a quantale from this monoid by taking the powerset of the monoid. This forms a quantale, where the ordering is set inclusion, meet and join are set intersection and union, with monoidal structure $A \otimes B = \{ a \cdot b \;|\; a \in A \land b \in B \}$, and $I = \{e\}$ (For partial monoids, we can just consider the defined pairs.) This quantale can be interpreted as "propositions about resources".

  3. Note that $(I, \otimes, \bot, \vee)$ forms a semiring. As an aside, this fact is very useful for reasoning about programs.

Some further observations:

  1. If you have a notion of "debt" corresponding to your notion of resource, then you can start with a group structure in step 1, and repeat the construction to get a ring.

  2. Mariano's example fits into this framework, too, if you relax the commutativity restriction. Then you can view words as elements of a free monoid over an alphabet, and then you get languages as forming a noncommutative quantale.

  3. Tropical algebra is an excellent framework for modelling optimization problems (ie, minimizing a cost function). You can often derive algorithms for by just twiddling Galois connections between the tropical semiring and a semiring of data. When this works, the process is so transparent it feels like magic!


Of course the real question is whether abelian groups are really more fundamental objects than commutative monoids. In a sense, the answer is obviously no: the definition of commutative monoid is simpler and admits alternative descriptions such as the one I give here. The latter description can be adapted to other settings, such as to the 2-category of locally presentable categories, which shares many formal properties with the category of commutative monoids (such as being closed symmetric monoidal, having a zero object, having biproducts). As such I would claim that any locally presentable closed symmetric monoidal category is itself a categorified version of a semiring, not in the sense you describe, but in that it is an algebra object in a closed symmetric monoidal category, so we may talk of modules over it, etc.

However, it is undeniable that there is a large qualitative difference between the theories of abelian groups and commutative monoids. Observe that an abelian group is just a commutative monoid which is a module over $\mathbb{Z}$ (more precisely a commutative monoid has either a unique structure of $\mathbb{Z}$-module, if it has additive inverses, and no structure of $\mathbb{Z}$-module otherwise). The situation is analogous to the (smaller) difference between abelian groups and $\mathbb{Q}$-vector spaces. I do not know of a characterization of $\mathbb{Z}$ as a commutative monoid that can be transported to other settings. It seems that there is something deep about the fact that $\mathbb{Z}$-modules are so much nicer than commutative monoids, which often is taken for granted.


The algebraic treatment of formal language theory uses systematically semi-rings of power series.