HOME

TheInfoList



OR:

In
abstract algebra In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include groups, rings, fields, modules, vector spaces, lattices, and algebras over a field. The term ''a ...
, a semiring is an
algebraic structure In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set of ...
similar to a
ring Ring may refer to: * Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry * To make a sound with a bell, and the sound made by a bell :(hence) to initiate a telephone connection Arts, entertainment and media Film and ...
, but without the requirement that each element must have an
additive inverse In mathematics, the additive inverse of a number is the number that, when added to , yields zero. This number is also known as the opposite (number), sign change, and negation. For a real number, it reverses its sign: the additive inverse (opp ...
. The term rig is also used occasionally—this originated as a joke, suggesting that rigs are ri''n''gs without ''n''egative elements, similar to using '' rng'' to mean a r''i''ng without a multiplicative ''i''dentity.
Tropical semiring In idempotent analysis, the tropical semiring is a semiring of extended real numbers with the operations of minimum (or maximum) and addition replacing the usual ("classical") operations of addition and multiplication, respectively. The tropical s ...
s are an active area of research, linking
algebraic varieties Algebraic varieties are the central objects of study in algebraic geometry, a sub-field of mathematics. Classically, an algebraic variety is defined as the set of solutions of a system of polynomial equations over the real or complex numbers. Mo ...
with piecewise linear structures.


Definition

A semiring is a
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
R equipped with two
binary operation In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two. More specifically, an internal binary op ...
s \,+\, and \,\cdot,\, called addition and multiplication, such that:Lothaire (2005) p.211Sakarovitch (2009) pp.27–28 * (R, +) is a
commutative monoid In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0. Monoids ar ...
with
identity element In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures su ...
0: ** (a + b) + c = a + (b + c) ** 0 + a = a = a + 0 ** a + b = b + a * (R, \,\cdot\,) is a
monoid In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0. Monoids ...
with identity element 1: ** (a \cdot b) \cdot c = a \cdot (b \cdot c) ** 1 \cdot a = a = a \cdot 1 * Multiplication left and right distributes over addition: ** a \cdot (b + c) = (a \cdot b) + (a \cdot c) ** (a + b) \cdot c = (a \cdot c) + (b \cdot c) * Multiplication by 0 annihilates R: ** 0 \cdot a = 0 = a \cdot 0 The symbol \cdot is usually omitted from the notation; that is, a \cdot b is just written ab. Similarly, an
order of operations In mathematics and computer programming, the order of operations (or operator precedence) is a collection of rules that reflect conventions about which procedures to perform first in order to evaluate a given mathematical expression. For exampl ...
is conventional, in which \,\cdot\, is applied before \,+\,; that is, a + b c is a + (b c). Compared to a
ring Ring may refer to: * Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry * To make a sound with a bell, and the sound made by a bell :(hence) to initiate a telephone connection Arts, entertainment and media Film and ...
, a semiring omits the requirement for inverses under addition; that is, it requires only a
commutative monoid In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0. Monoids ar ...
, not a
commutative group In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is commut ...
. In a ring, the additive inverse requirement implies the existence of a multiplicative zero, so here it must be specified explicitly. If a semiring's multiplication is
commutative In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name o ...
, then it is called a commutative semiring.Lothaire (2005) p.212 There are some authors who prefer to leave out the requirement that a semiring have a 0 or 1. This makes the analogy between and on the one hand and and on the other hand work more smoothly. These authors often use for the concept defined here.For an example see the definition of rig on Proofwiki.org
/ref>


Theory

One can generalize the theory of (associative)
algebras In mathematics, an algebra over a field (often simply called an algebra) is a vector space equipped with a bilinear product. Thus, an algebra is an algebraic structure consisting of a set together with operations of multiplication and addition a ...
over
commutative ring In mathematics, a commutative ring is a ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra. Complementarily, noncommutative algebra is the study of ring properties that are not sp ...
s directly to a theory of algebras over commutative semirings. A semiring in which every element is an additive
idempotent Idempotence (, ) is the property of certain operation (mathematics), operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence ...
(that is, a + a = a for all elements a) is called an . Idempotent semirings are specific to semiring theory since any idempotent semiring that is also a ring is in fact
trivial Trivia is information and data that are considered to be of little value. It can be contrasted with general knowledge and common sense. Latin Etymology The ancient Romans used the word ''triviae'' to describe where one road split or forked ...
.i.e. is a ring consisting of just one element, because rings have additive inverses, unlike semirings. One can define a
partial order In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
\,\leq\, on an idempotent semiring by setting a \leq b whenever a + b = b (or, equivalently, if there exists an x such that a + x = b). The
least element In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set (poset) is an element of S that is greater than every other element of S. The term least element is defined dually, that is, it is an eleme ...
with respect to this order is 0, meaning that 0 \leq a for all a. Addition and multiplication respect the ordering in the sense that a \leq b implies a c \leq b c and c a \leq c b and (a + c) \leq (b + c).


Applications

The (\max, +) and (\min, +)
tropical semiring In idempotent analysis, the tropical semiring is a semiring of extended real numbers with the operations of minimum (or maximum) and addition replacing the usual ("classical") operations of addition and multiplication, respectively. The tropical s ...
s on the reals are often used in
performance evaluation A performance appraisal, also referred to as a performance review, performance evaluation,Muchinsky, P. M. (2012). ''Psychology Applied to Work'' (10th ed.). Summerfield, NC: Hypergraphic Press. (career) development discussion, or employee appr ...
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 In computer science, the Floyd–Warshall algorithm (also known as Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, or the WFI algorithm) is an algorithm for finding shortest paths in a directed weighted graph with p ...
for
shortest path In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between tw ...
s can thus be reformulated as a computation over a (\min, +) algebra. Similarly, the
Viterbi algorithm The Viterbi algorithm is a dynamic programming algorithm for obtaining the maximum a posteriori probability estimate of the most likely sequence of hidden states—called the Viterbi path—that results in a sequence of observed events, especiall ...
for finding the most probable state sequence corresponding to an observation sequence in a
hidden Markov model A hidden Markov model (HMM) is a statistical Markov model in which the system being modeled is assumed to be a Markov process — call it X — with unobservable ("''hidden''") states. As part of the definition, HMM requires that there be an ob ...
can also be formulated as a computation over a (\max, \times) algebra on probabilities. These
dynamic programming Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. I ...
algorithms rely on the
distributive property In mathematics, the distributive property of binary operations generalizes the distributive law, which asserts that the equality x \cdot (y + z) = x \cdot y + x \cdot z is always true in elementary algebra. For example, in elementary arithmetic, ...
of their associated semirings to compute quantities over a large (possibly exponential) number of terms more efficiently than enumerating each of them.


Examples

By definition, any ring is also a semiring. A motivating example of a semiring is the set of
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''Cardinal n ...
s \N (including the number zero) under ordinary addition and multiplication. Likewise, the non-negative
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ration ...
s and the non-negative
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s form semirings. All these semirings are commutative.Sakarovitch (2009) p.28


In general

* The set of all ideals of a given ring form an idempotent semiring under addition and multiplication of ideals. * Any unital quantale is an idempotent semiring under join and multiplication. * Any bounded,
distributive lattice In mathematics, a distributive lattice is a lattice in which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set uni ...
is a commutative, idempotent semiring under join and meet. * In particular, a
Boolean algebra In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas in e ...
is such a semiring. A
Boolean ring In mathematics, a Boolean ring ''R'' is a ring for which ''x''2 = ''x'' for all ''x'' in ''R'', that is, a ring that consists only of idempotent elements. An example is the ring of integers modulo 2. Every Boolean ring gives rise to a Boolean al ...
is also a semiring (indeed, a ring) but it is not idempotent under . A is a semiring isomorphic to a subsemiring of a Boolean algebra. * A normal skew lattice in a ring R is an idempotent semiring for the operations multiplication and nabla, where the latter operation is defined by a \nabla b = a + b + ba - aba - bab. * Any
c-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. The term rig is also used occasionally—this originated as a joke, suggesting that rigs are ...
is also a semiring, where addition is idempotent and defined over arbitrary sets. * Isomorphism classes of objects in any
distributive category In mathematics, a category is distributive if it has finite products and finite coproducts and such that for every choice of objects A,B,C, the canonical map : mathit_A \times\iota_1, \mathit_A \times\iota_2: A\!\times\!B \,+ A\!\times\!C \to A\! ...
, under
coproduct In category theory, the coproduct, or categorical sum, is a construction which includes as examples the disjoint union of sets and of topological spaces, the free product of groups, and the direct sum of modules and vector spaces. The coprodu ...
and
product Product may refer to: Business * Product (business), an item that serves as a solution to a specific consumer problem. * Product (project management), a deliverable or set of deliverables that contribute to a business solution Mathematics * Produ ...
operations, form a semiring known as a Burnside rig. A Burnside rig is a ring if and only if the category is
trivial Trivia is information and data that are considered to be of little value. It can be contrasted with general knowledge and common sense. Latin Etymology The ancient Romans used the word ''triviae'' to describe where one road split or forked ...
.


Semiring of sets

A (of sets) is a (non-empty) collection \mathcal of subsets of X such that
  1. \varnothing \in \mathcal. * If (3) holds, then \varnothing \in \mathcal if and only if \mathcal \neq \varnothing.
  2. If E, F \in \mathcal then E \cap F \in \mathcal.
  3. If E, F \in \mathcal then there exists a finite number of mutually
    disjoint sets In mathematics, two sets are said to be disjoint sets if they have no element in common. Equivalently, two disjoint sets are sets whose intersection is the empty set.. For example, and are ''disjoint sets,'' while and are not disjoint. A ...
    C_1, \ldots, C_n \in \mathcal such that E \setminus F = \bigcup_^n C_i.
Conditions (2) and (3) together with S \neq \varnothing imply that \varnothing \in S. Such semirings are used in
measure theory In mathematics, the concept of a measure is a generalization and formalization of geometrical measures ( length, area, volume) and other common notions, such as mass and probability of events. These seemingly distinct concepts have many simil ...
. An example of a semiring of sets is the collection of half-open, half-closed real
intervals Interval may refer to: Mathematics and physics * Interval (mathematics), a range of numbers ** Partially ordered set#Intervals, its generalization from numbers to arbitrary partially ordered sets * A statistical level of measurement * Interval est ...
[a, b) \subset \R. A or is a collection \mathcal of subsets of X satisfying the semiring properties except with (3) replaced with: * If E \in \mathcal then there exists a finite number of mutually
disjoint sets In mathematics, two sets are said to be disjoint sets if they have no element in common. Equivalently, two disjoint sets are sets whose intersection is the empty set.. For example, and are ''disjoint sets,'' while and are not disjoint. A ...
C_1, \ldots, C_n \in \mathcal such that X \setminus E = \bigcup_^n C_i. This condition is stronger than (3), which can be seen as follows. If \mathcal is a semialgebra and E, F \in \mathcal, then we can write F^c = F_1 \cup ... \cup F_n for disjoint F_i \in S. Then: E \setminus F = E \cap F^c = E \cap (F_1 \cup ... \cup F_n) = (E \cap F_1) \cup ... \cup (E \cap F_n) and every E \cap F_i \in S since it is closed under intersection, and disjoint since they are contained in the disjoint F_i's. Moreover the condition is ''strictly'' stronger: any S that is both a ring and a semialgebra is an algebra, hence any ring that is not an algebra is also not a semialgebra (e.g. the collection of finite sets on an infinite set X).


Specific examples


Variations


Complete and continuous semirings

A complete semiring is a semiring for which the additive monoid is a complete monoid, meaning that it has an Finitary, infinitary sum operation \Sigma_I for any index set I and that the following (infinitary) distributive laws must hold: \sum_ = a \cdot \left(\sum_\right), \qquad \sum_ = \left(\sum_\right) \cdot a. Examples of a complete semiring are the power set of a monoid under union and the matrix semiring over a complete semiring. 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 In mathematics, the least-upper-bound property (sometimes called completeness or supremum property or l.u.b. property) is a fundamental property of the real numbers. More generally, a partially ordered set has the least-upper-bound property if eve ...
, and for which addition and multiplication respect order and suprema. The semiring \N \cup \ 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.Sakaraovich (2009) p.471


Star semirings

A star semiring (sometimes spelled starsemiring) is a semiring with an additional unary operator ,Droste, M., & Kuich, W. (2009). Semirings and Formal Power Series. ''Handbook of Weighted Automata'', 3–28. , pp. 7-10Lehmann, Daniel J. "Algebraic structures for transitive closure." ''Theoretical Computer Science'' 4, no. 1 (1977): 59-76.Berstel & Reutenauer (2011) p.27 satisfying a^* = 1 + a a^* = 1 + a^* a. A
Kleene algebra In mathematics, a Kleene algebra ( ; named after Stephen Cole Kleene) is an idempotent (and thus partially ordered) semiring endowed with a closure operator. It generalizes the operations known from regular expressions. Definition Various ineq ...
is a star semiring with idempotent addition and some additional axioms. They are important in the theory of
formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of symb ...
s and
regular expression A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a search pattern in text. Usually such patterns are used by string-searching algorithms for "find" or ...
s.


Complete star semirings

In a complete star semiring, the star operator behaves more like the usual
Kleene star In mathematical logic and computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. In mathematics, it is more commonly known as the free monoid c ...
: for a complete semiring we use the infinitary sum operator to give the usual definition of the Kleene star: a^* = \sum_, where a^j = \begin 1, & j = 0,\\ a \cdot a^ = a^ \cdot a, & j > 0. \end Note that star semirings are not related to *-algebra, where the star operation should instead be thought of as
complex conjugation In mathematics, the complex conjugate of a complex number is the number with an equal real part and an imaginary part equal in magnitude but opposite in sign. That is, (if a and b are real, then) the complex conjugate of a + bi is equal to a - ...
.


Conway semiring

A Conway semiring is a star semiring satisfying the sum-star and product-star equations: \begin (a + b)^* &= \left(a^* b\right)^* a^*, \\ (ab)^* &= 1 + a(ba)^* b. \end Every complete star semiring is also a Conway semiring,Droste, M., & Kuich, W. (2009). Semirings and Formal Power Series. ''Handbook of Weighted Automata'', 3–28. , Theorem 3.4 p. 15 but the converse does not hold. An example of Conway semiring that is not complete is the set of extended non-negative
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ration ...
s \Q_ \cup \ 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 John Horton Conway (26 December 1937 – 11 April 2020) was an English mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory. He also made contributions to many branches ...
to groups in star-semirings.


Examples

Examples of star semirings include: * the ( aforementioned) semiring of
binary relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
s over some base set U in which R^* = \bigcup_ R^n for all R\subseteq U \times U. This star operation is actually the reflexive and
transitive closure In mathematics, the transitive closure of a binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite s ...
of R (that is, the smallest reflexive and transitive binary relation over U containing R.). * 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 real In mathematics, the affinely extended real number system is obtained from the real number system \R by adding two infinity elements: +\infty and -\infty, where the infinities are treated as actual numbers. It is useful in describing the algebra ...
s , \infty/math> together with the usual addition and multiplication of reals is a complete star semiring with the star operation given by a^* = \frac for 0 \leq a < 1 (that is, the
geometric series In mathematics, a geometric series is the sum of an infinite number of terms that have a constant ratio between successive terms. For example, the series :\frac \,+\, \frac \,+\, \frac \,+\, \frac \,+\, \cdots is geometric, because each succ ...
) and a^* = \infty for a \geq 1. * The Boolean semiring with 0^* = 1^* = 1. * The semiring on \N \cup \, with extended addition and multiplication, and 0^* = 1, a^* = \infty for a \geq 1.


Dioid

The term dioid (for "double monoid") has been used to mean various types of semirings: * It was used by Kuntzman in 1972 to denote what is now termed semiring. * The use to mean idempotent subgroup was introduced by Baccelli et al. in 1992. * The name "dioid" is also sometimes used to denote
naturally ordered semiring In mathematics, monus is an operator on certain commutative property, commutative monoid#Commutative monoid, monoids that are not group (mathematics), groups. A commutative monoid on which a monus operator is defined is called a commutative monoid ...
s.


Generalizations

A generalization of semirings does not require the existence of a multiplicative identity, so that multiplication is a
semigroup In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it. The binary operation of a semigroup is most often denoted multiplicatively: ''x''·''y'', or simply ''xy'', ...
rather than a monoid. Such structures are called or . A further generalization are ,Michel Gondran, Michel Minoux, ''Graphs, Dioids, and Semirings: New Models and Algorithms'', Chapter 1, Section 4.1, p20 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 number In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, th, etc.) aimed to extend enumeration to infinite sets. A finite set can be enumerated by successively labeling each element with the least n ...
s form a
near-semiring In mathematics, a near-semiring (also ''seminearring'') is an algebraic structure more general than a near-ring or a semiring. Near-semirings arise naturally from functions on monoids. Definition A near-semiring is a set ''S'' with two binar ...
, 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 Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, cate ...
, a is a category with
functor In mathematics, specifically category theory, a functor is a Map (mathematics), mapping between Category (mathematics), categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) ar ...
ial operations analogous to those of a rig. That the cardinal numbers form a rig can be categorified to say that the
category of sets In the mathematical field of category theory, the category of sets, denoted as Set, is the category whose objects are sets. The arrows or morphisms between sets ''A'' and ''B'' are the total functions from ''A'' to ''B'', and the composition of m ...
(or more generally, any
topos In mathematics, a topos (, ; plural topoi or , or toposes) is a category that behaves like the category of sheaves of sets on a topological space (or more generally: on a site). Topoi behave much like the category of sets and possess a notion ...
) is a 2-rig.


See also

* *


Notes


Citations


Bibliography

* * François Baccelli, Guy Cohen, Geert Jan Olsder, Jean-Pierre Quadrat,
Synchronization and Linearity (online version)
', Wiley, 1992, * Golan, Jonathan S., ''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, 1999. xii+381 pp. * * * * * *


Further reading

* * * * * * Steven Dolan (2013
Fun with Semirings
{{Authority control Algebraic structures Ring theory