From: whopkins@alpha2.csd.uwm.edu (Mark William Hopkins) Subject: Semirings (was: Algebra without additive inverses) Date: 13 Oct 2000 03:27:22 GMT Newsgroups: sci.math Summary: [missing] In article <39E308F3.8D5281A0@sm.luth.se> Erland Gadde writes: >Does anyone know what an algebraic system is called, which has two >binary operations + and * , which are both commutative and associative, >and the distributive law a*(b+c)=a*b+a*c holds, with an additive >identity 0 and a multiplicative identity 1, such that a*0=0 for all a, >and such that 0=/=1? (Essentially a commutative ring, but additive >inverses need not exist.) A semiring is given by the axioms: (a+b)+c = a+(b+c); a+0 = 0 = 0+a (ab)c = a(bc); a1 = a = 1a a(b+c)d = abd + acd; a0d = 0 The 0 is not present in all definitions of semirings; several different definitions are floating out there. The Semiring is commutative if ab = ba. The multiplicative structure, alone, defines a monoid. Any monoid M can be freely extended to a semiring by taking the set of all formal (non-negative) linear combinations (LC) over M. This can be formally defined as: A LC is a map P: M -> { 0, 1, 2, 3, ... } such that support(P) = { m in M: P(m) > 0) } is finite. Addition P+Q is defined point-wise (P+Q)(m) = P(m) + Q(m). Products are defined pointwise (PQ)(m) = sum (P(p)Q(q): pq = m). These are all well-defined. The function corresponding to m is (x) = 1 if x = m, 0 otherwise. Finally, you can define products by integers point-wise by (kP)(m) = k P(m), for k = 0, 1, 2, .... Then you have, based on these definitions, the standard form for any LC: P = P(m1) + ... + P(mn) where support(P) = { m1, ..., mn } The resulting structure is the free semiring extension of the monoid M.