nLab
idempotent semiring

Idempotent semirings

Idempotent semirings

Idea

Recall that a semiring is a set RR equipped with two binary operations, denoted ++, and \cdot and called addition and multiplication, satisfying the ring (or rng) axioms except that there may neither be a zero nor a negative nor an inverse.

Definition

An idempotent semiring (also known as a dioid) is one in which addition is idempotent: x+x=xx + x = x, for all xRx\in R.

Terminology

The term dioid is sometimes used as an alternative name for idempotent semirings.

Properties

On a semiring there is a partial order given by

xy:x+y=y. x \leq y : \iff x + y = y.

To check transitivity observe that xy x \leq y and yz y \leq z imply z=yzy+z=xy(x+y)+z=x+(y+z)=yzx+z z \stackrel{y \leq z}{=} y + z \stackrel{x \leq y}{=} (x + y) + z = x + (y + z) \stackrel{y \leq z}{=} x + z . Due to idempotence the addition is a join with respect to this partial order: take a zz such that xzx\leq z and yzy\leq z, then z=z+z=x+z+y+z=x+y+zz = z + z = x + z + y + z = x + y + z. The partial order is preserved by multiplication.

Examples

  • Any quantale is an idempotent semiring, or dioid, under join and multiplication.

  • The set of languages over a given alphabet AA forms an idempotent semiring in which L+L=LLL + L' = L \cup L' and multiplication is given by concatentation. In fact this is a quantale P(A *)P(A^\ast) where the multiplication is the 2\mathbf{2}-enriched Day convolution product induced from the monoid multiplication of the free monoid A *A^\ast.

  • The tropical algebra and the max-plus algebra are idempotent semirings.

  • Given an idempotent semiring RR one can form the weak interval extension I(R)I(R). This is the idempotent semiring defined on all close intervals [x,y]={zRxzy}[x, y] = \{ z \in R \mid x \leq z \leq y \} by the operations [x,y]+[x,y]=[x+x,y+y][x, y] + [x', y'] = [x + x', y + y'] and [x,y][x,y]=[xx,yy][x, y] \cdot [x', y'] = [x \cdot x', y \cdot y']. The multiplicative unit is given by [1,1][1,1] and, if RR has an additive unit 00, an additive unit is given by [0,0][0,0].

Last revised on November 22, 2018 at 08:50:24. See the history of this page for a list of all contributions to it.