# idempotent semiring

 $a+a=a,\qquad\mbox{ for all }a\in S.$

Some properties of an i-semiring $S$.

1. 1.

If we define a binary relation  $\leq$ on $S$ by

 $a\leq b\qquad\mbox{ iff }\qquad a+b=b$

then $\leq$ becomes a partial order  on $S$. Indeed, for $a+a=a$ implies $a\leq a$; if $a\leq b$ and $b\leq a$, then $b=a+b=a$; and finally, if $a\leq b$ and $b\leq c$, then $a+c=a+(b+c)=(a+b)+c=b+c=c$ so $a\leq c$.

2. 2.

$0\leq a$ for any $a\in S$, because $0+a=a$.

3. 3.

Define $a\vee b$ as the supremum   of $a$ and $b$ (with respect to $\leq$). Then $a\vee b$ exists and

 $a\vee b=a+b.$

To see this, we have $a+(a+b)=(a+a)+b=a+b$, so $a\leq a+b$. Similarly $b\leq a+b$. If $a\leq c$ and $b\leq c$, then $(a+b)+c=a+(b+c)=a+c=c$. So $a+b\leq c$.

4. 4.

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

5. 5.

Additon and multiplication respect partial ordering: suppose $a\leq b$, then for any $c\in S$, $(c+a)+(c+b)=(c+c)+(a+b)=c+b$, hence $c+a\leq c+b$; also, $cb=c(a+b)=ca+cb$ implies $ca\leq cb$.

Remark. $S$ in general is not a lattice   , 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 IdempotentSemiring 2013-03-22 15:52:12 2013-03-22 15:52:12 CWoo (3771) CWoo (3771) 8 CWoo (3771) Definition msc 16Y60 i-semiring dioid