Is the natural order relation on an idempotent semiring total/linear?

112 Views Asked by At

We know that on an idempotent semiring $R$, the natural order relation is defined as: for all $x, y\in R$, $x\leq y$ when $x+y=y$, which is clearly a partial order relation. I am unable to point out whether this relation is a total order relation too? i.e., does it satisfy Comparability (trichotomy law)?

2

There are 2 best solutions below

4
On

Take the nonnegative integers with bitwise OR ($\vee$) as the sum and bitwise AND ($\wedge$) as the product.

$$10\vee 01 = 11\neq 10,01$$ Thus $10$ and $01$ are incomparable.

The partial order relation in this case is easy to describe. $x\leq y$ if and only if whenever $x$ has a bit in the $i$th position set, so does $y$. So this is the product partial order on $\{0,1\}^\infty$.

0
On

A distributive lattice is an idempotent semiring (with addition $\vee$ and multiplication $\wedge$), but most lattices are not totally ordered.