A semiring is an algebraic structure equipped with a commutative and associative addition operator $+$ with a neutral element $0$, and an associative multiplication operator $\times$ with a neutral element $1$, such that $0$ is absorptive for $\times$ and that $\times$ distributes over $+$. We can define a preorder on a semiring $K$ by $x \leq y$ iff $\exists z$ such that $x + z = y$. We call the semiring $K$ naturally ordered if the relation $\leq$ is a partial order, i.e., if it is antisymmetric.

We further say that the semiring $K$ is an m-semiring if the following holds: for any $x, y \in K$, the set $\{z \in K \mid x \leq y + z\}$ has a smallest element for $\leq$.

What is an example of a naturally ordered semiring which is not an m-semiring?

Such an example is claimed by Example 4 of this paper, page 6, but (as confirmed with one author of this paper) there is a problem with the example. (In "Clearly, this is not bounded below", the authors mean the usual order on $\mathbb{R}$, but the natural order $\leq$ is the reverse of the usual order.)

(Edit: note that this question can be posed just for monoids already, as it is independent from the $\times$ operator; but requiring that a suitable $\times$ operator can be defined makes it slightly harder to build a counterexample.)

up vote 1 down vote accepted

Here is an example:

Let $K$ be $\mathbb{N} \cup \{42'\}$ where $42'$ is an element distinct from each element of $\mathbb{N}$. For any $x$ in $K$ we will define $h(x)$ by $x$ if $x \in \mathbb{N}$ and $42$ if $x = 42'$; we denote $+$ (resp $\times$) the usual addition (resp., multiplication) in $\mathbb{N}$. Now, we define the commutative binary relation $\oplus$ on $K$ as follows:

  • $0 \oplus a = a = a \oplus 0$ for every $a \in K$
  • $a \oplus b = h(a) + h(b)$ for every $a,b \neq 0$

We can easily see that $(K, \oplus, 0)$ is a commutative monoid.

In what follows, we will ensure that $h$ is a homomorphism of semirings from $K$ to $\mathbb{N}$.

The preorder on this monoid defined by $x\leq y$ iff $\exists z ~ x \oplus z=y$ is then:

  • for $a,b \in \mathbb{N}$ then $a\leq b$ iff $a$ is less than or equal to $b$ in the usual sense
  • $0 \leq 42'$
  • $42'$ is incomparable with $1$, with $2$, ..., with $42$
  • $42'\leq 42'$
  • $42' \leq 43$, $42'\leq 44$, ...

This preorder is antisymmetric, so that $(K, \oplus, 0)$ is naturally ordered.

We define the commutative binary relation $\otimes$ on $K$ as follows:

  • $1 \otimes a = a \otimes 1 = a$ for every $a \in K$
  • $a \otimes b = h(a) \times h(b)$ for every $a,b \neq 1$

Then $(K, \oplus, \otimes, 0, 1)$ is naturally ordered (as we just proved), and we must now prove that it is actually a semiring.

Indeed associativity of $\otimes$, $1$ being neutral for $\otimes$, $0$ an annihilator for $\otimes$ are all easy to check, so let us look at distributivity: is $a \otimes ( b \oplus c )$ equal to $a \otimes b \oplus a \otimes c$?

First, note that since $(\mathbb{N}, +, \times, 0, 1)$ is a semiring, $h(a) \times ( h(b) + h(c) ) = h(a) \times h(b) + h(a) \times h(c)$. And $h$ has been defined so that $h(x\oplus y)=h(x)+h(y)$ and $h(x\otimes y)=h(x)\times h(y)$, so we have: $h(a \otimes ( b \oplus c )) = h(a \otimes b \oplus a \otimes c)$. This means that if distributivity were not to hold, it would be because we obtained $42$ on one side of the equation and $42'$ on the other. But, with a single operation, $42'$ can only be obtained as a product on the left-hand side with $42' \otimes 1$ or $1 \otimes 42'$. We thus distinguish the cases:

  • if $a = 1$, then distributivity holds trivially
  • if $b \oplus c=1$, then $\{b,c\}=\{0,1\}$ and distributivity holds

Similarly, $42'$ can only be obtained as a sum on the right-hand side with $42' \oplus 0$ or $0 \oplus 42'$. You can do a case-by-case analysis and check that distributivity holds.

However, $(K, \oplus, \otimes, 0, 1)$ does not satisfy the additional m-semiring property that for every $x$ and $y$, the set $S(x,y) = \{z \in K \text{~s.t~} x \leq y \oplus z\}$ has a smallest element. Indeed we have $42 \in S(142,100)$ and $42' \in S(142,100)$ but $42$ and $42'$ are incomparable. And no element smaller than both (it would have to be $0$ by the definition of $\leq$) is in the set.

Remark: it should even possible to make the example finite by cutting at 142 and defining, e.g., $a {\oplus'} b = \max(a \oplus b, 142)$.

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.