Semiring

From Wikipedia, the free encyclopedia

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^[1] — this originated as a joke, suggesting that rigs are rings without negative elements.

Algebraic structures
Group-like Semigroup / Monoid Quasigroup and Loop Abelian group Magma Group Theory
Ring-like Ring Semiring Near-ring Commutative ring Domain Integral domain Field Ring Theory
Lattice-like Lattice Semilattice Map of lattices Lattice theory
Module-like Module Group with operators Vector space
Algebra-like Algebra Associative Non-associative Graded Bialgebra
v t e

Definition

A semiring is a set R equipped with two binary operations + and ·, called addition and multiplication, such that:^[2]^[3]^[4]

(R, +) is a commutative monoid with identity element 0:
1. (a + b) + c = a + (b + c)
2. 0 + a = a + 0 = a
3. a + b = b + a
(R, ·) is a monoid with identity element 1:
1. (a·b)·c = a·(b·c)
2. 1·a = a·1 = a
Multiplication left and right distributes over addition:
1. a·(b + c) = (a·b) + (a·c)
2. (a + b)·c = (a·c) + (b·c)
Multiplication by 0 annihilates R:
1. 0·a = a·0 = 0

This last axiom is omitted from the definition of a ring: it follows automatically from the other ring axioms. Here it does not, and it is necessary to state it in the definition.

The difference between rings and semirings, then, is that addition yields only a commutative monoid, not necessarily a commutative group. Specifically, elements in semirings do not necessarily have an inverse for the addition.

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

A commutative semiring is one whose multiplication is commutative.^[5] An idempotent semiring (also known as a dioid) is one whose addition is idempotent: a + a = a, that is, (R, +, 0) is a join-semilattice with zero.

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.^{[note 1]}

Examples

In general

Any ring is also a semiring.
The ideals of a ring form a semiring under addition and multiplication of ideals.
Any unital quantale is an idempotent semiring, or dioid, under join and multiplication.
Any bounded, distributive lattice is a commutative, idempotent semiring under join and meet.
In particular, a Boolean algebra is such a semiring. A Boolean ring is also a semiring—indeed, a ring—but it is not idempotent under addition. A Boolean semiring is a semiring isomorphic to a subsemiring of a Boolean algebra.^[6]
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 is also a semiring, where addition is idempotent and defined over arbitrary sets.

Specific examples

The motivating example of a semiring is the set of natural numbers N (including zero) under ordinary addition and multiplication. Likewise, the non-negative rational numbers and the non-negative real numbers form semirings. All these semirings are commutative.^[6]
The square n-by-n matrices with non-negative entries form a (non-commutative) semiring under ordinary addition and multiplication of matrices. More generally, this likewise applies to the square matrices whose entries are elements of any other given semiring S, and the semiring is generally non-commutative even though S may be commutative.^[6]
If A is a commutative monoid, the set End(A) of endomorphisms f:A→A form a semiring, where addition is pointwise addition and multiplication is function composition. The zero morphism and the identity are the respective neutral elements. If A is the additive monoid of natural numbers we obtain the semiring of natural numbers as End(A), and if A=S^n with S a semiring, we obtain (after associating each morphism to a matrix) the semiring of square n-by-n matrices with coefficients in S.
The commutative semiring B formed by the two-element Boolean algebra:^[3] this is the simplest example of a semiring which is not a ring.
N[x], polynomials with natural number coefficients form a commutative semiring. In fact, this is the free commutative semiring on a single generator {x}.
Of course, rings such as the integers or the real numbers are also examples of semirings.
The tropical semiring, R ∪ {−∞}, is a commutative, idempotent semiring with max(a,b) serving as semiring addition (identity −∞) and ordinary addition (identity 0) serving as semiring multiplication. In an alternative formulation, the tropical semiring is R ∪ {∞}, and min replaces max as the addition operation.^[3]
The set of cardinal numbers smaller than any given infinite cardinal form a semiring under cardinal addition and multiplication. The set of all cardinals of an inner model form a semiring under (inner model) cardinal addition and multiplication.
The probability semiring of non-negative real numbers under the usual addition and multiplication.^[3]
The log semiring on R ∪ ±∞ with addition given by

$x\oplus y=-\log(e^{{-x}}+e^{{-y}})\ ,$

with multiplication +, zero element +∞ and unit element 0.^[3]

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.^[7]

Semiring theory

Much of the theory of rings continues to make sense when applied to arbitrary semirings. In particular, one can generalise the theory of 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. Some mathematicians go so far as to say that semirings are really the more fundamental concept, and specialising to rings should be seen in the same light as specialising to, say, algebras over the complex numbers.

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

Applications

Dioids, especially the (max, +) and (min, +) dioids 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 can thus be reformulated as a computation over a (min, +) algebra. Similarly, the Viterbi algorithm for finding the most probable state sequence corresponding to an observation sequence in a Hidden Markov model can also be formulated as a computation over a (max, ×) 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.

Starsemirings

A starsemiring is a semiring with an additional unary operator * (Kleene star).^[8] A Kleene algebra is a starsemiring with idempotent addition: they are important in the theory of formal languages and regular expressions. A Conway semiring is a starsemiring satisfying the sum-star and the product-star equations:^[9]

$(a+b)^{*}=(a^{*}b)^{*}a^{*},\,$

$(ab)^{*}=1+a(ba)^{*}b.\,$

Further generalizations

A near-ring does not require addition to be commutative, nor does it require right-distributivity. Just as cardinal numbers form a semiring, so do ordinal numbers form a near-ring.

In category theory, a 2-rig 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.

Semiring of sets

A semiring (of sets)^[10] is a non-empty collection S of sets such that

$\emptyset \in S$
If $E\in S$ and $F\in S$ then $E\cap F\in S$ .
If $E\in S$ and $F\in S$ then there exists a finite number of mutually disjoint sets $C_{i}\in S$ for $i=1,\ldots ,n$ such that $E\setminus F=\bigcup _{{i=1}}^{n}C_{i}$ .

Such semirings are used in measure theory. An example of a semiring of sets is the collection of half-open, half-closed real intervals $[a,b)\subset {\mathbb {R}}$ .

Notes

↑ For an example see the definition of rig on Proofwiki.org

Bibliography

↑ Głazek (2002) p.7
↑ Berstel & Perrin (1985), p. 26
↑ 3.0 3.1 3.2 3.3 3.4 Lothaire (2005) p.211
↑ Sakarovitch (2009) pp.27–28
↑ Lothaire (2005) p.212
↑ 6.0 6.1 6.2 Guterman, Alexander E. (2008). "Rank and determinant functions for matrices over semirings". In Young, Nicholas; Choi, Yemon. Surveys in Contemporary Mathematics. London Mathematical Society Lecture Note Series 347. Cambridge University Press. pp. 1–33. ISBN 0-521-70564-9. ISSN 0076-0552. Zbl 1181.16042.
↑ Bard, Gregory V. (2009), Algebraic Cryptanalysis, Springer, Section 4.2.1, "Combinatorial Classes", ff., pp. 30–34, ISBN 9780387887579 .
↑ Berstel & Reutenauer (2011) p.27
↑ Ésik, Zoltán; Kuich, Werner (2004). "Equational axioms for a theory of automata". In Martín-Vide, Carlos. Formal languages and applications. Studies in Fuzziness and Soft Computing 148. Berlin: Springer-Verlag. pp. 183–196. ISBN 3-540-20907-7. Zbl 1088.68117.
↑ Noel Vaillant, Caratheodory's Extension, on probability.net.

François Baccelli, Guy Cohen, Geert Jan Olsder, Jean-Pierre Quadrat, Synchronization and Linearity (online version), Wiley, 1992, ISBN 0-471-93609-X
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, MR 1163371. Kluwer Academic Publishers, Dordrecht, 1999. xii+381 pp. ISBN 0-7923-5786-8 MR 1746739
Berstel, Jean; Perrin, Dominique (1985). Theory of codes. Pure and applied mathematics 117. Academic Press. ISBN 978-0-12-093420-1. Zbl 0587.68066.
Lothaire, M. (2005). Applied combinatorics on words. Encyclopedia of Mathematics and Its Applications 105. A collective work by Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert, Sophie Schbath, Michael Waterman, Philippe Jacquet, Wojciech Szpankowski, Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche and Valérie Berthé. Cambridge: Cambridge University Press. ISBN 0-521-84802-4. Zbl 1133.68067.
Głazek, Kazimierz (2002). A guide to the literature on semirings and their applications in mathematics and information sciences. With complete bibliography. Dordrecht: Kluwer Academic. ISBN 1-4020-0717-5. Zbl 1072.16040.
Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge: Cambridge University Press. ISBN 978-0-521-84425-3. Zbl 1188.68177.
Berstel, Jean; Reutenauer, Christophe (2011). Noncommutative rational series with applications. Encyclopedia of Mathematics and Its Applications 137. Cambridge: Cambridge University Press. ISBN 978-0-521-19022-0. Zbl 1250.68007.

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.