In abstract algebra, a semiring is an algebraic structure. Semirings are a generalization of rings, dropping the requirement that each element must have an additive inverse. At the same time, semirings are a generalization of bounded distributive lattices.

The smallest semiring that is not a ring is the two-element Boolean algebra, for instance with logical disjunction as addition. A motivating example that is neither a ring nor a lattice is the set of natural numbers (including zero) under ordinary addition and multiplication. Semirings are abundant because a suitable multiplication operation arises as the function composition of endomorphisms over any commutative monoid.

Terminology

. This makes the analogy between ring and on the one hand and and on the other hand work more smoothly. These authors often use rig for the concept defined here. This originated as a joke, suggesting that rigs are rings without negative elements. (Akin to using rng to mean a ring without a multiplicative identity.)

The term dioid (for "double monoid") has been used to mean semirings or other structures. It was used by Kuntzmann in 1972 to denote a semiring. (It is alternatively sometimes used for naturally ordered semirings but the term was also used for idempotent subgroups by Baccelli et al. in 1992.)

Definition

A semiring is a set equipped with two binary operations called addition and multiplication, such that:

is a commutative monoid with an identity element:

:

Further, the following axioms tie to both operations:

Through multiplication, any element is left- and right-annihilated by the additive identity:

Multiplication left- and right-distributes over addition:

Notation

Similarly, an order of operations.

to emphasize which structure the units at hand belong to.

-times repeated addition.

Construction of new semirings

The zero ring is often silently assumed as if it were an additional axiom. Now given any semiring, there are several ways to define new ones.

.

. The zero morphism matrices, the matrix semiring using ordinary addition and multiplication was commutative.

Dorroh extensions is not actually required to have a multiplicative unit.

Zerosumfree to the underlying set and thus obtain such a zerosumfree semiring that also lacks zero divisors are used when performing these constructions.

Adjoining a new zero to the trivial semiring, in this way, results in another semiring which may be expressed in terms of the logical connectives has no additive inverse. In the self-dual, whose addition functions as xor.) In the von Neumann model of the naturals is replaced by any inhabited set whatsoever.

The ideals does not function as a two-sided multiplicative identity.

is an inhabited set denotes the free monoid.

.

Given a derivation, resulting in another semiring.

The above is by no means an exhaustive list of systematic constructions.

Derivations

.

.

Properties

is not a left or right zero divisor.

Some notable properties are inherited from the monoid structures: The monoid axioms demand unit existence, and so the set underlying a semiring cannot be empty. Also, the 2-ary, here defined for the addition operation, always constitutes the right canonical preorder relation. Reflexivity is always valid, and so zero is the least element, for example, this relation is anti-symmetric and strongly connected, and thus in fact a (non-strict) total order.

Below, more conditional properties are discussed.

Semifields

Any field is also a semifield, which in turn is a semiring in which also multiplicative inverses exist.

Rings

Any field is also a ring, which in turn is a semiring in which also additive inverses exist. Note that a semiring omits such a requirement, i.e., it requires only a commutative monoid, not a commutative group. The extra requirement for a ring itself already implies the existence of a multiplicative zero. This contrast is also why for the theory of semirings, the multiplicative zero must be specified explicitly.

is a trivial binary relation in a ring.

Commutative semirings

A semiring is called a commutative semiring if also the multiplication is commutative..

The center of a semiring is a sub-semiring and being commutative is equivalent to being its own center.

The commutative semiring of natural numbers is the initial object into any commutative semiring.

and an order constraint discussed below.

Ordered semirings

Notions or order can be defined using strict, non-strict or second-order formulations. Additional properties such as commutativity simplify the axioms.

Given a strict total order (also sometimes called linear order, or pseudo-order in a constructive formulation), then by definition, the positive and negative is false. The non-negative.

Generally, the strict total order can be negated to define an associated partial order. The asymmetry. In fact in classical mathematics. Likewise, given any (non-strict) total order, its negation is irreflexive and transitive, and those two properties found together are sometimes called strict quasi-order. Classically this defines a strict total order – indeed strict total order and total order can there be defined in terms of one another.

".

Additively idempotent semirings

A semiring in which every element is an additive idempotent, is called an (additively) idempotent semiring. suffices. Be aware that sometimes this is just called idempotent semiring, regardless of rules for multiplication.

.

.

A semiring such that there is a lattice structure on its underlying set is lattice-ordered. The lattice-ordered semiring of ideals of a semiring is not necessarily distributive with respect to the lattice structure.

More strictly than just additive idempotence, a semiring is called simple with the inherited operations is its simple sub-semiring. An example of an additively idempotent semiring that is not simple is the tropical semiring with the 2-ary maximum function, with respect to the standard order, as addition. Its simple sub-semiring is trivial.

A c-semiring is an idempotent semiring and with addition defined over arbitrary sets.

, is called additively and multiplicatively idempotent semiring, but sometimes also just idempotent semiring. The commutative, simple semirings with that property are exactly the bounded distributive lattices with unique minimal and maximal element (which then are the units). Heyting algebras are such semirings and the Boolean algebrass are a special case.

Further, given two bounded distributive lattices, there are constructions resulting in commutative additively-idempotent semirings, which are more complicated than just the direct sum of structures.

Number lines

, or classically the law of trichotomy. With its standard addition and multiplication, this structure forms the strictly ordered field that is Dedekind-complete. By definition, all first-order properties proven in the theory of the reals are also provable in the decidable theory of the real closed field.

, including the rationals, the integers, as well as the non-negative parts of each of these structures. In particular, the non-negative reals, the non-negative rationals and the non-negative integers are such a semirings. The first two properties are analogous to the property valid in the idempotent semirings: Translation and scaling respect these ordered rings, in the sense that addition and multiplication in this ring validate

and so squaring of elements preserves positivity.

. In particular, the positive additive difference existence can be expressed as

, all squares are proven non-negative. Consequently, non-trivial rings have a positive multiplicative unit,

, etc.

Discretely ordered semirings

being positive and covering. Now in the present context, an order shall be called discrete if this is fulfilled and, furthermore, all elements of the semiring are non-negative, so that the semiring starts out with the units.

as its initial segment and Gödel incompleteness and Tarski undefinability. The non-negative elements of a commutative, discretely ordered ring. So a slightly more exotic model of the theory is given by the positive elements in the polynomial ring proves all \Sigma_1-sentences, beyond this complexity one can find simple such statements that are independent ("odd or even demonstrates independence of some statements about factorization.

. To this end one defines an equivalence class of pairs from the original semiring. Roughly, the ring corresponds to the differences of elements in the old structure, generalizing the way in which the initial can be defined from.

, which is dense can be ordered, but not discretely so.

Natural numbers

plus mathematical induction gives a theory equivalent to first-order Peano arithmetic. The theory is also famously not categorical proves that there are no zero divisors and it is zerosumfree and so no model of it is a ring.

". However, just removing the potent induction principle from that axiomatization does not leave a workable algebraic theory. Indeed, even Robinson arithmetic.

Complete semirings

A complete semiring is a semiring for which the additive monoid is a complete monoid, meaning that it has an infinitary for any index set and that the following (infinitary) distributive laws must hold:

Examples of a complete semiring are the power set of a monoid under union and the matrix semiring over a complete semiring. For commutative, additively idempotent and simple semirings, this property is related to residuated lattices.

Continuous semirings

A continuous semiring is similarly defined as one for which the addition monoid is a continuous monoid. That is, partially ordered with the least upper bound property with usual addition, multiplication and order extended is a continuous semiring.

Any continuous semiring is complete: this may be taken as part of the definition.

Star semirings

A star semiring (sometimes spelled starsemiring) or closed semiring, satisfying

A Kleene algebra is a star semiring with idempotent addition and some additional axioms. They are important in the theory of formal languages and regular expressions.

Complete star semirings

In a complete star semiring, the star operator behaves more like the usual Kleene star: for a complete semiring we use the infinitary sum operator to give the usual definition of the Kleene star:

where

Note that star semirings are not related to *-algebra, where the star operation should instead be thought of as complex conjugation.

Conway semiring

A Conway semiring is a star semiring satisfying the sum-star and product-star equations:

Every complete star semiring is also a Conway semiring, but the converse does not hold. An example of Conway semiring that is not complete is the set of extended non-negative rational numbers with the usual addition and multiplication (this is a modification of the example with extended non-negative reals given in this section by eliminating irrational numbers). An iteration semiring is a Conway semiring satisfying the Conway group axioms, associated by John Conway to groups in star-semirings.

Examples

• By definition, any ring and any semifield is also a semiring.

• .

• Also the non-negative rational numbers as well as the non-negative real numbers form commutative, ordered semirings. The latter is called . Neither are rings or distributive lattices. These examples also have multiplicative inverses.

• New semirings can conditionally be constructed from existing ones, as described. The extended natural numbers.

• The set of polynomials forms a commutative semiring. In fact, this is the free Also polynomials with coefficients in other semirings may be defined, as discussed.

• The non-negative terminating fractions, in a positional number system and is dense.

• The log semiring

• Similarly, the tropical semiring) and ordinary addition (identity 0) serving as semiring multiplication. Likewise, the and min replaces max as the addition operation. as the underlying set. They are an active area of research, linking algebraic varieties with piecewise linear structures.

• The Łukasiewicz appears in multi-valued logic.

• The Viterbi and has the maximum as its addition, but its multiplication is the usual multiplication of real numbers. It appears in probabilistic parsing.

• The set of all ideals of a given semiring form a semiring under addition and multiplication of ideals.

• Any bounded, distributive lattice is a commutative, semiring under join and meet. A Boolean algebra is a special case of these. A Boolean ring is also a semiring (indeed, a ring) but it is not idempotent under . A is a semiring isomorphic to a sub-semiring of a Boolean algebra.

• . It is also called the . binary relations with entries in the Boolean semiring, matrix addition corresponds to union of relations, and matrix multiplication corresponds to composition of relations.

• Any unital quantale is a semiring under join and multiplication.

• A normal skew lattice

More using monoids,

• form a matrix semiring.

• Given an alphabet (finite set) Σ, the set of formal languages (subsets of \Sigma^*) is a semiring with product induced by string concatenation and addition as the union of languages (that is, ordinary union as sets). The zero of this semiring is the empty set (empty language) and the semiring's unit is the language containing only the empty string.

• as the free monoid

• is a monoid, then the set of finite multisets

Regarding sets and similar abstractions,

• the set of binary relations is a semiring with addition the union (of relations as sets) and multiplication the composition of relations. The semiring's zero is the empty relation and its unit is the identity relation. These relations correspond to the matrix semiring (indeed, matrix semialgebra) of square matrices with entries in the Boolean semiring, and then addition and multiplication are the usual matrix operations, while zero and the unit are the usual zero matrix and identity matrix.

• The set of cardinal numbers smaller than any given infinite cardinal form a semiring under cardinal addition and multiplication. The class of of an inner model form a (class) semiring under (inner model) cardinal addition and multiplication.

• The family of (isomorphism equivalence classes of) combinatorial classes (sets of countably many objects with non-negative integer sizes such that there are finitely many objects of each size) with the empty class as the zero object, the class consisting only of the empty set as the unit, disjoint union of classes as addition, and Cartesian product of classes as multiplication.

• Isomorphism classes of objects in any distributive category, under coproduct and product operations, form a semiring known as a Burnside rig. A Burnside rig is a ring if and only if the category is trivial.

Star semirings

Several structures mentioned above can be equipped with a star operation.

• The aforementioned semiring of binary relations This star operation is actually the reflexive and transitive closure).

• The semiring of formal languages is also a complete star semiring, with the star operation coinciding with the Kleene star (for sets/languages).

• The set of non-negative extended reals (that is, the geometric series

Applications

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.

The Floyd–Warshall algorithm for shortest paths algebra. Similarly, the Viterbi algorithm for finding the most probable state sequence corresponding to an observation sequence in a hidden Markov model algebra on probabilities. These dynamic programming algorithms rely on the distributive property of their associated semirings to compute quantities over a large (possibly exponential) number of terms more efficiently than enumerating each of them.

Generalizations

A generalization of semirings does not require the existence of a multiplicative identity, so that multiplication is a semigroup rather than a monoid. Such structures are called or . A further generalization are , which additionally do not require right-distributivity (or , which do not require left-distributivity).

Yet a further generalization are : in addition to not requiring a neutral element for product, or right-distributivity (or left-distributivity), they do not require addition to be commutative. Just as cardinal numbers form a (class) semiring, so do ordinal numbers form a near-semiring, when the standard ordinal addition and multiplication are taken into account. However, the class of ordinals can be turned into a semiring by considering the so-called natural (or Hessenberg) operations instead.

In category theory, a is a category with functorial operations analogous to those of a rig. That the cardinal numbers form a rig can be categorified to say that the category of sets (or more generally, any topos) is a 2-rig.

See also

Notes

Citations

Bibliography

• Golan, Jonathan S. (1999) Semirings and their applications. Updated and expanded version of The theory of semirings, with applications to mathematics and theoretical computer science (Longman Sci. Tech., Harlow, 1992, ). Kluwer Academic Publishers, Dordrecht. xii+381 pp.

Further reading