1
$\begingroup$

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)?

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ What does bitwise mean here? $\endgroup$ – gete Dec 25 '18 at 14:30
  • $\begingroup$ You write the integers in base $2$, then take OR position by position. So for $10\vee 01$ it's $(1\vee 0)(0\vee 1)$. $\endgroup$ – Matt Samuel Dec 25 '18 at 14:32
  • $\begingroup$ Thanks i got it now..likewise we can find $10\wedge 01=00$. Right? $\endgroup$ – gete Dec 25 '18 at 14:42
  • $\begingroup$ @gete Yes, that is correct. $\endgroup$ – Matt Samuel Dec 25 '18 at 14:42
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.