In
abstract algebra
In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures, which are set (mathematics), sets with specific operation (mathematics), operations acting on their elements. Algebraic structur ...
, a semiring is an
algebraic structure
In mathematics, an algebraic structure or algebraic system 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 multiplicatio ...
. Semirings are a generalization of
rings, dropping the requirement that each element must have an
additive inverse
In mathematics, the additive inverse of an element , denoted , is the element that when added to , yields the additive identity, 0 (zero). In the most familiar cases, this is the number 0, but it can also refer to a more generalized zero el ...
. At the same time, semirings are a generalization of
bounded distributive lattice
In mathematics, a distributive lattice is a lattice (order), lattice in which the operations of join and meet distributivity, distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice o ...
s.
The smallest semiring that is not a ring is 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 ''carrier'') ''B'' is the Boolean domain. The elements of the Boolean domain are 1 and 0 by convention, so that ''B ...
, for instance with
logical disjunction
In logic, disjunction (also known as logical disjunction, logical or, logical addition, or inclusive disjunction) is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is ...
as addition. A motivating example that is neither a ring nor a lattice is the set of
natural number
In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
s
(including zero) under ordinary addition and multiplication. Semirings are abundant because a suitable multiplication operation arises as the
function composition
In mathematics, the composition operator \circ takes two function (mathematics), functions, f and g, and returns a new function h(x) := (g \circ f) (x) = g(f(x)). Thus, the function is function application, applied after applying to . (g \c ...
of
endomorphism
In mathematics, an endomorphism is a morphism from a mathematical object to itself. An endomorphism that is also an isomorphism is an automorphism. For example, an endomorphism of a vector space is a linear map , and an endomorphism of a g ...
s over any
commutative monoid
In abstract algebra, 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 .
Monoids are semigroups with identity ...
.
Terminology
Some authors define semirings without the requirement for there to be a
or
. 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 ri''n''gs without ''n''egative elements. (Akin to using ''
rng'' to mean a r''i''ng without a multiplicative ''i''dentity.)
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 semiring
In mathematics, monus is an operator on certain commutative monoids that are not groups. A commutative monoid on which a monus operator is defined is called a commutative monoid with monus, or CMM. The monus operator may be denoted with the &minus ...
s but the term was also used for idempotent subgroups by
Baccelli et al. in 1992.)
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 ...
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, a binary operation ...
s
and
called addition and multiplication, such that:
*
is a
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. Perhaps most familiar as a pr ...
monoid
In abstract algebra, 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 .
Monoids are semigroups with identity ...
with an
identity element
In mathematics, an identity element or neutral element of a binary operation is an element that leaves unchanged every element when the operation is applied. For example, 0 is an identity element of the addition of real numbers. This concept is use ...
called
:
**
**
**
**
*
is a monoid with an identity element called
:
**
**
**
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
The symbol
is usually omitted from the notation; that is,
is just written
Similarly, an
order of operations
In mathematics and computer programming, the order of operations is a collection of rules that reflect conventions about which operations to perform first in order to evaluate a given mathematical expression.
These rules are formalized with a ...
is conventional, in which
is applied before
. That is,
denotes
.
For the purpose of disambiguation, one may write
or
to emphasize which structure the units at hand belong to.
If
is an element of a semiring and
, then
-times repeated multiplication of
with itself is denoted
, and one similarly writes
for the
-times repeated addition.
Construction of new semirings
The
zero ring
In ring theory, a branch of mathematics, the zero ring or trivial ring is the unique ring (up to isomorphism) consisting of one element. (Less commonly, the term "zero ring" is used to refer to any rng of square zero, i.e., a rng in which fo ...
with underlying set
is a semiring called the trivial semiring. This triviality can be characterized via
and so when speaking of nontrivial semirings,
is often silently assumed as if it were an additional axiom.
Now given any semiring, there are several ways to define new ones.
As noted, the natural numbers
with its arithmetic structure form a semiring. Taking the zero and the image of the successor operation in a semiring
, i.e., the set
together with the inherited operations, is always a sub-semiring of
.
If
is a commutative monoid, function composition provides the multiplication to form a semiring: The set
of endomorphisms
forms a semiring where addition is defined from pointwise addition in
. The
zero morphism In category theory, a branch of mathematics, a zero morphism is a special kind of morphism exhibiting properties like the morphisms to and from a zero object.
Definitions
Suppose C is a category, and ''f'' : ''X'' → ''Y'' is a morphism in C. The ...
and the identity are the respective neutral elements. If
with
a semiring, we obtain a semiring that can be associated with the square
matrices
Matrix (: matrices or matrixes) or MATRIX may refer to:
Science and mathematics
* Matrix (mathematics), a rectangular array of numbers, symbols or expressions
* Matrix (logic), part of a formula in prenex normal form
* Matrix (biology), the ...
with coefficients in
, the
matrix semiring
In abstract algebra, a matrix ring is a set of matrices with entries in a ring ''R'' that form a ring under matrix addition and matrix multiplication. The set of all matrices with entries in ''R'' is a matrix ring denoted M''n''(''R'') (altern ...
using ordinary
addition
Addition (usually signified by the Plus and minus signs#Plus sign, plus symbol, +) is one of the four basic Operation (mathematics), operations of arithmetic, the other three being subtraction, multiplication, and Division (mathematics), divis ...
and
multiplication
Multiplication is one of the four elementary mathematical operations of arithmetic, with the other ones being addition, subtraction, and division (mathematics), division. The result of a multiplication operation is called a ''Product (mathem ...
rules of matrices. Given
and
a semiring,
is always a semiring also. It is generally non-commutative even if
was commutative.
Dorroh extensions: If
is a semiring, then
with pointwise addition and multiplication given by
defines another semiring with multiplicative unit
. Very similarly, if
is any sub-semiring of
, one may also define a semiring on
, just by replacing the repeated addition in the formula by multiplication. Indeed, these constructions even work under looser conditions, as the structure
is not actually required to have a multiplicative unit.
Zerosumfree semirings are in a sense furthest away from being rings. Given a semiring, one may adjoin a new zero
to the underlying set and thus obtain such a zerosumfree semiring that also lacks
zero divisor
In abstract algebra, an element of a ring is called a left zero divisor if there exists a nonzero in such that , or equivalently if the map from to that sends to is not injective. Similarly, an element of a ring is called a right ze ...
s. In particular, now
and the old semiring is actually not a sub-semiring. One may then go on and adjoin new elements "on top" one at a time, while always respecting the zero. These two strategies also work under looser conditions. Sometimes the notations
resp.
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
In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. Connectives can be used to connect logical formulas. For instance in the syntax of propositional logic, the ...
of disjunction and conjunction:
. Consequently, this is the smallest semiring that is not a ring. Explicitly, it violates the ring axioms as
for all
, i.e.
has no additive inverse. In the
self-dual definition, the fault is with
. (This is not to be conflated with the ring
, whose addition functions as
xor
Exclusive or, exclusive disjunction, exclusive alternation, logical non-equivalence, or logical inequality is a logical operator whose negation is the logical biconditional. With two inputs, XOR is true if and only if the inputs differ (one ...
.)
In the
von Neumann model of the naturals,
,
and
. The two-element semiring may be presented in terms of the set theoretic union and intersection as
. Now this structure in fact still constitutes a semiring when
is replaced by any inhabited set whatsoever.
The
ideals on a semiring
, with their standard operations on subset, form a lattice-ordered, simple and zerosumfree semiring. The ideals of
are in bijection with the ideals of
. The collection of left ideals of
(and likewise the right ideals) also have much of that algebraic structure, except that then
does not function as a two-sided multiplicative identity.
If
is a semiring and
is an
inhabited set
In mathematics, a set A is inhabited if there exists an element a \in A.
In classical mathematics, the property of being inhabited is equivalent to being non- empty. However, this equivalence is not valid in constructive or intuitionistic logic, a ...
,
denotes the
free monoid
In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero ...
and the formal polynomials