Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
2  
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? –  Pete L. Clark Apr 7 '10 at 13:36
    
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? –  Donu Arapura Apr 7 '10 at 14:54
    
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? –  Donu Arapura Apr 7 '10 at 15:25
    
@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. –  Theo Johnson-Freyd Apr 7 '10 at 15:56
    
With DA, I think you should amend statement 4. Heck, this is a CW question, so I feel no compunction about editing it myself. –  Theo Johnson-Freyd Apr 7 '10 at 15:58
show 5 more comments

5 Answers

up vote 8 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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!

share|improve this answer
    
I like your observation about modelling optimization problems, can you provide some reference? –  Diego de Estrada Apr 26 '10 at 7:04
1  
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. –  Neel Krishnaswami Apr 26 '10 at 8:11
add comment

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,...

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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