PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Very high Entry average rating: No information on entry rating
[parent] idempotent semiring (Definition)

A semiring $S$ is called an idempotent semiring, or i-semiring for short, if, addition $+$ is an idempotent binary operation: $$a+a=a,\qquad\mbox{ for all }a\in S.$$

Some properties of an i-semiring $S$ .

  1. If we define a binary relation $\le$ on $S$ by $$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$ .
  2. $0\le a$ for any $a\in S$ , because $0+a=a$ .
  3. Define $a\vee b$ as the supremum of $a$ and $b$ (with respect to $\le$ ). 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\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$ .
  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. 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$ .

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.




"idempotent semiring" is owned by CWoo.
(view preamble | get metadata)

View style:

Other names:  i-semiring, dioid

This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: theory, Kleene algebra, lattice, multiplication, operation, join, upper semilattice, information, supremum, implies, partial order, binary relation, properties, binary operation, idempotent, addition, semiring
There are 4 references to this entry.

This is version 5 of idempotent semiring, born on 2006-04-24, modified 2007-04-28.
Object id is 7866, canonical name is IdempotentSemiring.
Accessed 2773 times total.

Classification:
AMS MSC16Y60 (Associative rings and algebras :: Generalizations :: Semirings)

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)