Semiring

In abstract algebra, a semiring is an algebraic structure similar to a ring, but without the requirement that each element must have an additive inverse. In abstract algebra, a semiring is an algebraic structure similar to a ring, but without the requirement that each element must have an additive inverse. The term rig is also used occasionally—this originated as a joke, suggesting that rigs are rings without negative elements, similar to using rng to mean a ring without a multiplicative identity. A semiring is a set R equipped with two binary operations + and ⋅, called addition and multiplication, such that: The symbol ⋅ is usually omitted from the notation; that is, a⋅b is just written ab. Similarly, an order of operations is accepted, according to which ⋅ is applied before +; that is, a + bc is a + (bc). Compared to a ring, a semiring omits the requirement for inverses under addition; that is, it requires only a commutative monoid, not a commutative group. In a ring, this implies the existence of a multiplicative zero, so here it must be specified explicitly. If a semiring's multiplication is commutative, then it is called a commutative semiring. There are some authors who prefer to leave out the requirement that a semiring have a 0 or 1. This makes the analogy between ring and semiring on the one hand and group and semigroup on the other hand work more smoothly. These authors often use rig for the concept defined here. Much of the theory of rings continues to make sense when applied to arbitrary semirings.In particular, one can generalise the theory of (associative) algebras over commutative rings directly to a theory of algebras over commutative semirings.Then a ring is simply an algebra over the commutative semiring Z of integers. A semiring in which every element is an additive idempotent (that is, a + a = a for all elements a) is called an idempotent semiring. Idempotent semirings are special to semiring theory as any ring which is idempotent under addition is trivial. One can define a partial order ≤ on an idempotent semiring by setting a ≤ b whenever a + b = b (or, equivalently, if there exists an x such that a + x = b). It is easy to see that 0 is the least element with respect to this order: 0 ≤ a for all a. Addition and multiplication respect the ordering in the sense that a ≤ b implies ac ≤ bc and ca ≤ cb and (a + c) ≤ (b + c). The (max, +) and (min, +) tropical semirings on the reals, are often used in performance evaluation on discrete event systems. The real numbers then are the 'costs' or 'arrival time'; the 'max' operation corresponds to having to wait for all prerequisites of an events (thus taking the maximal time) while the 'min' operation corresponds to being able to choose the best, less costly choice; and + corresponds to accumulation along the same path.