idempotent semiring

A semiring S is called an idempotent semiring, or i-semiring for short, if, additionPlanetmathPlanetmath + is an idempotentMathworldPlanetmathPlanetmath binary operationMathworldPlanetmath:

a+a=a, for all aS.

Some properties of an i-semiring S.

  1. 1.

    If we define a binary relationMathworldPlanetmath on S by

    ab   iff   a+b=b

    then becomes a partial orderMathworldPlanetmath on S. Indeed, for a+a=a implies aa; if ab and ba, then b=a+b=a; and finally, if ab and bc, then a+c=a+(b+c)=(a+b)+c=b+c=c so ac.

  2. 2.

    0a for any aS, because 0+a=a.

  3. 3.

    Define ab as the supremumMathworldPlanetmathPlanetmath of a and b (with respect to ). Then ab exists and


    To see this, we have a+(a+b)=(a+a)+b=a+b, so aa+b. Similarly ba+b. If ac and bc, then (a+b)+c=a+(b+c)=a+c=c. So a+bc.

  4. 4.

    Collecting all the information above, we see that (S,+) is an upper semilatticePlanetmathPlanetmath with + as the join operationMathworldPlanetmath on S and 0 the bottom element.

  5. 5.

    Additon and multiplication respect partial ordering: suppose ab, then for any cS, (c+a)+(c+b)=(c+c)+(a+b)=c+b, hence c+ac+b; also, cb=c(a+b)=ca+cb implies cacb.

Remark. S in general is not a latticeMathworldPlanetmathPlanetmath, and 1 is not the top element of S.

The main example of an i-semiring is a Kleene algebra used in the theory of computations.

Title idempotent semiring
Canonical name IdempotentSemiring
Date of creation 2013-03-22 15:52:12
Last modified on 2013-03-22 15:52:12
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 8
Author CWoo (3771)
Entry type Definition
Classification msc 16Y60
Synonym i-semiring
Synonym dioid