idempotent semiring

Idempotent semirings


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 or may not be either be a zero nor a negative nor an inverse, for which reason do check.


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.


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

From now on we will assume that the semiring, SS, has a neutral element ε\varepsilon for + and one ee for \cdot. Moreover we assume that for all sSs\in S, sε=εs=εs\cdot \varepsilon =\varepsilon s = \varepsilon.


On an idempotent semiring, SS, 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.