23
$\begingroup$

The discovery (or invention) of negatives, which happened several centuries ago by the Chinese, Indians and Arabs, has of course be of fundamental importance to mathematics. From then on, it seems that mathematicians have always striven to "put the negatives" into whatever algebraic structure they came across, in analogy with the usual "numerical" structure, $\mathbb{Z}$.

But perhaps there are cases in which the notion of a semiring seems more natural than the notion of a ring (I will be very very sloppy!):

1) The Cardinals. They have a natural structure of semiring, and the usual construction that allows to pass from $\mathbb{N}$ to $\mathbb{Z}$ cannot be performed in this case without great loss of information.

2) Vector bundles over a space; and notice that in the infinite rank case the Grothendieck ring is trivial just because negatives are allowed.

3) Tropical geometry.

4) The notion of semiring, as opposed to that of a ring, seems to be the most natural for "categorification", in two separate senses: (i) For example, the set of isomorphism classes of objects in a category with direct sums and tensor products (e.g. finitely-generated projective modules over a commutative ring) is naturally a semiring. When one constructs the Grothendieck ring of a category, one usually adds formal negatives, but this can be a very lossy operation, as in the case of vector bundles. (ii) A category with finite biproducts (products and coproducts, and a natural isomorphism between these) is automatically enriched over commutative monoids, but not automatically enriched over abelian groups. As such, it's naturally a "many object semiring", but not a "many object ring".

Do you have any examples of contexts in which semirings (which are not rings) arise naturally in mathematics?

$\endgroup$
11
  • 7
    $\begingroup$ I like the question but not the title: it seems unnecessarily argumentative. You're not really trying to decide whether rings are "better" than semirings, are you? $\endgroup$ Apr 7, 2010 at 13:36
  • $\begingroup$ Two comments: (1) Since example 1 is a special case of 2, I guess it should follow that adjoining negatives to cardinal arithmetic would make it trivial? (2) I'm a bit puzzled by example 4. An abelian category looks to me-- and not just me -- like a ring with many objects since you have additive inverses. Was there some other example that you had in mind? $\endgroup$ Apr 7, 2010 at 14:54
  • $\begingroup$ It's been many years since I looked at the precise definitions. But I understood the sum to be the cardinality of the disjoint union, which would be commutative. Is there something I'm missing? $\endgroup$ Apr 7, 2010 at 15:25
  • $\begingroup$ @GE: I thought the cardinals had commutative addition, given by disjoint union of sets. In particular, for infinite cardinals, addition is just "max", at least if we have axiom of choice (so that any two cardinals are comparable). The noncommutative addition, I thought, was for ordinals, which are (isomorphism classes of) sets along with well-orderings. The ordered disjoint union is definitely noncommutative. $\endgroup$ Apr 7, 2010 at 15:56
  • $\begingroup$ With DA, I think you should amend statement 4. Heck, this is a CW question, so I feel no compunction about editing it myself. $\endgroup$ Apr 7, 2010 at 15:58

6 Answers 6

10
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ I like your observation about modelling optimization problems, can you provide some reference? $\endgroup$
    – didest
    Apr 26, 2010 at 7:04
  • 2
    $\begingroup$ Roland Backhouse has written some nice papers on this subject -- I particularly like "Regular Algebra Applied to Language Problems". (cs.nott.ac.uk/~rcb/MPC/RegAlgLangProblems.ps.gz) Warning: his notation gets black-hole dense, since he likes to do everything by algebraic manipulations, including logic and quantifier manipulations. His techniques are pretty enough that it is worth persevering, though. $\endgroup$ Apr 26, 2010 at 8:11
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

Although not a ring, the renormalisation group of quantum field theory is really a semigroup. Moreover, there is no compelling physical reason to add inverses, since in fact physically inverses need not exist. Indeed, the process of renormalisation often loses information, admits fixed points,...

$\endgroup$
1
$\begingroup$

Nikolai Durov showed that a commutative algebraic monad with 0 "is" a semiring if and only if b(x,0)=x for all x, where b is a binary operation with b(x,y) not identically equal to x.

So semirings are in some sense easy to get.

On the other hand, the commutative algebraic monads that seem to be his motivating examples, the unit ball in a commutative Banach algebra, are not semirings.

$\endgroup$
1
$\begingroup$

This is not really an answer to the question, but you can really look at both of them together. Let $R$ be any (unital) ring, and let K$_0 (R)$ be the usual Grothendieck group (group generated by stable classes of fg projectives); let $P$ be the set of images of the projective modules in K${}_0$. Then $P$ is a pre-ordering on K$_0$, i.e., $P + P = P$; $P-P = {\rm K}_0$; but not necessarily $P \cap -P = (0)$. The last condition holds if $R$ is stably finite (no fg free module on $n$ generators is a direct summand of a free module on $m$ generators if $n \geq m$). In this case, $P$ is a bona fide positive cone for a partial ordering on K$_0$. The ordering plays a nontrivial role in some areas.

Of course, $P$ is an abelian monoid inside a group; it can happen that even if $R$ is not even close to being commutative, K$_0(R)$ has the structure of a partially ordered ring (this is relatively rare, but occurs for some big group rings), in which case you have both a ring and inside it, a canonical semigroup, which is actually a semiring ($P\cdot P = P$). The semiring in this case is more significant than the ring, since it conveys more information about the original $R$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.