| Version 2 |
Version 1 |
| A semiring $S$ is called an \emph{idempotent semiring}, or \emph{i-semiring} for short if addition $+$ is an idempotent binary operation: |
A semiring $S$ is called an \emph{idempotent semiring}, or \emph{i-semiring} for short if addition $+$ is an idempotent binary operation: |
| $$a+a=a,\qquad\mbox{ for all }a\in S.$$ |
$$a+a=a,\qquad\mbox{ for all }a\in S.$$ |
|
|
| \textbf{Some properties on an i-semiring $S$}. |
\textbf{Some properties on an i-semiring $S$}. |
| \begin{enumerate} |
\begin{enumerate} |
| \item If we define a binary relation $\le$ on $S$ by |
\item If we define a binary relation $\le$ on $S$ by |
| $$a\le b\qquad\mbox{ iff }\qquad a+b=b$$ |
$$a\le b\qquad\mbox{ iff }\qquad a+b=b$$ |
| then $\le$ becomes a partial order on $S$. Indeed, for $a+a=a$ implies $a\le a$; if $a\le b$ and $b\le a$, then $b=a+b=a$; and finally, if $a\le b$ and $b\le c$, then $a+c=a+(b+c)=(a+b)+c=b+c=c$ so $a\le c$. |
then $\le$ becomes a partial order on $S$. Indeed, for $a+a=a$ implies $a\le a$; if $a\le b$ and $b\le a$, then $b=a+b=a$; and finally, if $a\le b$ and $b\le c$, then $a+c=a+(b+c)=(a+b)+c=b+c=c$ so $a\le c$. |
| \item $0\le a$ for any $a\in S$, because $0+a=a$. |
\item $0\le a$ for any $a\in S$, because $0+a=a$. |
| \item $a+b$ is the supremum of $a$ and $b$: $a+(a+b)=(a+a)+b=a+b$, so $a\le a+b$. Similarly $b\le a+b$. If $a\le c$ and $b\le c$, then $(a+b)+c=a+(b+c)=a+c=c$. So $a+b\le c$. |
\item $a+b$ is the supremum of $a$ and $b$: $a+(a+b)=(a+a)+b=a+b$, so $a\le a+b$. Similarly $b\le a+b$. If $a\le c$ and $b\le c$, then $(a+b)+c=a+(b+c)=a+c=c$. So $a+b\le c$. |
| \item 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. |
\item 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. |
| \item Additon and multiplication respect partial ordering: suppose $a\le b$, then for any $c\in S$, $(c+a)+(c+b)=(c+c)+(a+b)=c+b$, hence $c+a\le c+b$; also, $cb=c(a+b)=ca+cb$ implies $ca\le cb$. |
\item Additon and multiplication respect partial ordering: suppose $a\le b$, then for any $c\in S$, $(c+a)+(c+b)=(c+c)+(a+b)=c+b$, hence $c+a\le c+b$; also, $cb=c(a+b)=ca+cb$ implies $ca\le cb$. |
| \end{enumerate} |
\end{enumerate} |
|
|
| \textbf{Remark}. $S$ in general is not a lattice, and in particular, $1$ is not the top element of $S$. |
\textbf{Remark}. $S$ in general is not a lattice, and in particular, $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. |
The main example of an i-semiring is a Kleene algebra used in the theory of computations. |
