Semiring
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 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
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 rings without negative elements.The term dioid has been used to mean semirings or other structures. It was used by Kuntzmann in 1972 to denote a semiring.
Definition
A semiring is a set equipped with two binary operations and called addition and multiplication, such that:- is a commutative monoid with an identity element called :
- *
- *
- *
- *
- is a monoid with an identity element called :
- *
- *
- *
- 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 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 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 and the identity are the respective neutral elements. If with a semiring, we obtain a semiring that can be associated with the square matrices with coefficients in, the matrix semiring using ordinary addition and multiplication 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 divisors. 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 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.
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 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, denotes the free monoid and the formal polynomials over its words form another semiring. For small sets, the generating elements are conventionally used to denote the polynomial semiring. For example, in case of a singleton such that, one writes. Zerosumfree sub-semirings of can be used to determine sub-semirings of.
Given a set, not necessarily just a singleton, adjoining a default element to the set underlying a semiring one may define the semiring of partial functions from to.
Given a derivation on a semiring, another the operation "" fulfilling can be defined as part of a new multiplication on, resulting in another semiring.
The above is by no means an exhaustive list of systematic constructions.
Derivations
Derivations on a semiring are the maps with and.For example, if is the unit matrix and, then the subset of given by the matrices with is a semiring with derivation.
Properties
A basic property of semirings is that is not a left or right zero divisor, and that but also squares to itself, i.e. these have.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 predicate defined as, here defined for the addition operation, always constitutes the right canonical preorder relation. Reflexivity is witnessed by the identity. Further, is always valid, and so zero is the least element with respect to this preorder. Considering it for the commutative addition in particular, the distinction of "right" may be disregarded. In the non-negative integers, for example, this relation is anti-symmetric and strongly connected, and thus in fact a 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.Here, the additive inverse of, squares to. As additive differences always exist in a ring, is a trivial binary relation in a ring.
Commutative semirings
A semiring is called a commutative semiring if also the multiplication is commutative. Its axioms can be stated concisely: It consists of two commutative monoids and on one set such that and.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 among its kind, meaning there is a unique structure preserving map of into any commutative semiring.
The bounded distributive lattices are partially ordered commutative semirings fulfilling certain algebraic equations relating to distributivity and idempotence. Thus so are their duals.
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, then by definition, the positive and negative elements fulfill resp.. By irreflexivity of a strict order, if is a left zero divisor, then is false. The non-negative elements are characterized by, which is then written.
Generally, the strict total order can be negated to define an associated partial order. The asymmetry of the former manifests as. In fact in classical mathematics the latter is a total order and such that implies. Likewise, given any 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.
Recall that "" defined above is trivial in any ring. The existence of rings that admit a non-trivial non-strict order shows that these need not necessarily coincide with "".
Additively idempotent semirings
A semiring in which every element is an additive idempotent, that is, for all elements, is called an idempotent semiring. Establishing suffices. Be aware that sometimes this is just called idempotent semiring, regardless of rules for multiplication.In such a semiring, is equivalent to and always constitutes a partial order, here now denoted. In particular, here. So additively idempotent semirings are zerosumfree and, indeed, the only additively idempotent semiring that has all additive inverses is the trivial ring and so this property is specific to semiring theory. Addition and multiplication respect the ordering in the sense that implies, and furthermore implies as well as, for all and.
If is additively idempotent, then so are the polynomials in.
A semiring such that there is a lattice structure on its underlying set is lattice-ordered if the sum coincides with the join,, and the product lies beneath the meet. 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 iff for all. Then also and for all. Here then functions akin to an additively infinite element. If is an additively idempotent semiring, then with the inherited operations is its simple sub-semiring.
An example of an additively idempotent semiring that is not simple is the tropical semiring on 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.
An additively idempotent semiring with idempotent multiplication,, 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. Heyting algebras are such semirings and the Boolean algebras 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.