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. Abstract algebra is the subject area of Mathematics that studies Algebraic structures such as groups, rings, fields, modules In Algebra, a branch of Pure mathematics, an algebraic structure consists of one or more sets closed under one or more operations, In Mathematics, a ring is an Algebraic structure which generalizes the algebraic properties of the Integers though the rational, real In mathematics the additive inverse, or opposite, of a Number n is the number that when added to n, yields zero. The term rig is also used occasionally—this originated as a joke, suggesting that rigs are rings without negative elements.
Contents |
Definition
A semiring is a set R equipped with two binary operations + and ·, called addition and multiplication, such that:
- (R, +) is a commutative monoid with identity element 0:
- (a + b) + c = a + (b + c)
- 0 + a = a + 0 = a
- a + b = b + a
- (R, ·) is a monoid with identity element 1:
- (a·b)·c = a·(b·c)
- 1·a = a·1 = a
- Multiplication distributes over addition:
- a·(b + c) = (a·b) + (a·c)
- (a + b)·c = (a·c) + (b·c)
- 0 annihilates R:
- 0·a = a·0 = 0
This last axiom is omitted from the definition of a ring: it follows automatically from the other ring axioms. In Mathematics, a binary operation is a calculation involving two Operands, in other words an operation whose Arity is two In Abstract algebra, a branch of Mathematics, a monoid is an Algebraic structure with a single Associative Binary operation In Mathematics, an identity element (or neutral element) is a special type of element of a set with respect to a Binary operation on that In Abstract algebra, a branch of Mathematics, a monoid is an Algebraic structure with a single Associative Binary operation In Mathematics, and in particular in Abstract algebra, distributivity is a property of Binary operations that generalises the distributive law In traditional Logic, an axiom or postulate is a proposition that is not proved or demonstrated but considered to be either self-evident, or subject In Mathematics, a ring is an Algebraic structure which generalizes the algebraic properties of the Integers though the rational, real 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 an abelian group. In Abstract algebra, a branch of Mathematics, a monoid is an Algebraic structure with a single Associative Binary operation An abelian group, also called a commutative group, is a group satisfying the additional requirement that the product of elements does not depend on their order (the
As usual, 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). In Algebra and Computer programming, when a number or expression is both preceded and followed by a Binary operation, a rule is required for which operation
A commutative semiring is one whose multiplication is commutative. In Mathematics, commutativity is the ability to change the order of something without changing the end result An idempotent semiring (also known as a dioid) is one whose addition is idempotent: a + a = a, that is, (R, +) is a band. Idempotence ˌaɪdɨmˈpoʊtəns describes the property of operations in Mathematics and Computer science which means that multiple applications of the operation In Mathematics, a band is a Semigroup in which every element is Idempotent (in other words equal to its own square
N. B. 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 : semiring and group : semigroup work more smoothly. In Mathematics, a group is a set of elements together with an operation that combines any two of its elements to form a third element In Mathematics, a semigroup is an Algebraic structure consisting of a nonempty set S together with an Associative Binary operation These authors often use rig for the concept defined here.
Examples
In general
- Any ring is also a semiring.
- The ideals of a ring form a semiring under addition and multiplication of ideals. In Ring theory, a branch of Abstract algebra, an ideal is a special Subset of a ring.
- Any unital, quantale is an idempotent semiring, or dioid, under join and multiplication. In Mathematics, quantales are certain partially ordered Algebraic structures that generalize locales ( point free topologies) as well as various
- Any bounded, distributive lattice is a commutative, idempotent semiring under join and meet. In Mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other
- In particular, a Boolean algebra is such a semiring. In Abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice. A Boolean ring is also a semiring—indeed, a ring—but it is not idempotent under addition. In Mathematics, a Boolean ring R is a ring (with identity for which x 2 = x for all x in R; that
- 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
. In Abstract algebra, a skew lattice is an Algebraic structure that is a non-commutative generalization of a Lattice. - A Kleene algebra is an idempotent semiring R with an additional unary operator * : R → R called the Kleene star. In Mathematics, a Kleene algebra (named after Stephen Cole Kleene, ˈkleɪni as in "clay-knee" is either of two different things A In Mathematical logic and Computer science, the Kleene star (or Kleene closure) is a Unary operation, either on sets of Kleene algebras are important in the theory of formal languages and regular expressions. A formal language is a set of words, ie finite strings of letters, or symbols. In Computing, regular expressions provide a concise and flexible means for identifying strings of text of interest such as particular characters words or patterns of characters
Specific examples
- The motivating example of a semiring is the set of natural numbers N (including zero) under ordinary addition and multiplication. In Mathematics, a natural number (also called counting number) can mean either an element of the set (the positive Integers or an Likewise, the non-negative rational numbers and the non-negative real numbers form semirings. In Mathematics, a rational number is a number which can be expressed as a Ratio of two Integers Non-integer rational numbers (commonly called fractions In Mathematics, the real numbers may be described informally in several different ways All these semirings are commutative.
- Of course, rings such as the integers or the real numbers are also examples of semirings. The integers (from the Latin integer, literally "untouched" hence "whole" the word entire comes from the same origin but via French In Mathematics, the real numbers may be described informally in several different ways
- The simplest example of a semiring which is not a ring is the commutative semiring B formed by the two-element Boolean algebra. In Mathematics and Abstract algebra, the two-element Boolean algebra is the Boolean algebra whose underlying set (or Universe or
- N[x], polynomials with natural number coefficients form a commutative semiring. In Mathematics, a polynomial is an expression constructed from Variables (also known as indeterminates and Constants using the operations In fact, this is the free commutative semiring on a single generator {x}. In Mathematics, the idea of a free object is one of the basic concepts of Abstract algebra.
- Square n-by-n matrices with non-negative entries form a (non-commutative) semiring under ordinary addition and multiplication of matrices. In Mathematics, a matrix (plural matrices) is a rectangular table of elements (or entries) which may be Numbers or more generally More generally, this likewise applies to the square matrices whose entries are elements of any other given semiring.
- 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. Tropical geometry is a relatively new area in Mathematics, which might loosely be described as a piece-wise linear or skeletonized version of Algebraic geometry In an alternative formulation, the tropical semiring is R ∪ {∞}, and min replaces max as the addition operation.
- The set of cardinal numbers smaller than any given infinite cardinal form a semiring under cardinal addition and multiplication. This article describes cardinal numbers in mathematics For cardinals in linguistics see Names of numbers in English. Infinity (symbolically represented with ∞) comes from the Latin infinitas or "unboundedness (We can't form a semiring of all cardinal numbers because they do not form a set. )
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. In Mathematics, specifically in Ring theory, an algebra over a commutative ring is a generalization of the concept of an algebra over a field, where the In Ring theory, a branch of Abstract algebra, a commutative ring is a ring in which the multiplication operation has the commutative property Then a ring is simply an algebra over the commutative semiring Z of integers. The integers (from the Latin integer, literally "untouched" hence "whole" the word entire comes from the same origin but via French 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. Complex plane In Mathematics, the complex numbers are an extension of the Real numbers obtained by adjoining an Imaginary unit, denoted
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). In Mathematics, especially Order theory, a partially ordered set (or poset) formalizes the intuitive concept of an ordering sequencing or arrangement It is easy to see that 0 is the least element with respect to this order: 0 ≤ a for all a. In Mathematics, especially in Order theory, the greatest element of a subset S of a Partially ordered set (poset is an element of S Addition and multiplication respect the ordering in the sense that a ≤ b implies ac ≤ bc and ca ≤ cb and (a+c) ≤ (b+c).
Further generalizations
A near-rig does not require addition to be commutative, nor does it require right-distributivity. In Mathematics, a near-semiring (also seminearring) is an algebraic structure more general to near-ring and semiring. Just as cardinal numbers form a rig, so do ordinal numbers form a near-rig. In Set theory, an ordinal number, or just ordinal, is the Order type of a Well-ordered set.
In category theory, a 2-rig is a category with functorial operations analogous to those of a rig. In Mathematics, category theory deals in an abstract way with mathematical Structures and relationships between them it abstracts from sets In Category theory, a branch of Mathematics, a functor is a special type of mapping between categories 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. In Mathematics, the category of sets, denoted as Set, is the category whose objects are all sets and whose Morphisms are In Mathematics, a topos (plural "topoi" or "toposes" is a type of category that behaves like the category of sheaves of sets
Applications
Dioids, especially the (max, +) and (min, +) dioids on the reals, are often used in performance evaluation on discrete event systems. For article assessment process on Wikipedia see WikipediaVersion 1 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. In Graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes such that the sum of the weights
See also
Bibliography
- 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. In Abstract algebra, a rng (also called a pseudo-ring or non-unital ring) is an Algebraic structure satisfying the same properties as a , 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, MR1163371. Mathematical Reviews is a journal and online database published by the American Mathematical Society that contains brief synopses (and occasionally evaluations of many Kluwer Academic Publishers, Dordrecht, 1999. xii+381 pp. ISBN 0-7923-5786-8 MR1746739
Dictionary
semiring
-noun
- (algebra) An algebraic structure similar to a ring, but without the requirement that each element must have an additive inverse.
Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic