nLab
residuated idempotent semiring

Idea

In general, in the idempotent semiring (max,+)(max,+), an equation of form Ax=bAx=b has no solution, but the inequality AxbAx\leq b does by taking x=𝟘x=\mathbb{0}. (Here recall that in any idmepotent semiring, there is a natural partial order on the elements.) It is natural to relax equality in the search for somultions, and study instead the set of its ‘subsolutions’. One way forward in this approach is to use the notion of residuated mapping from the theory of posets.

Definition

An idempotent semiring, SS is residuated if the right and left multiplication maps

λ a:xax\lambda_a:x\mapsto ax

and

ρ a:xxa\rho_a:x\mapsto xa

from SS to itself are residuated.

Example

Any complete idempotent semiring is automatically residuated. We set

a\b:=λ a #(b)=max{xaxb}a \backslash b:= \lambda^\#_a (b) = max \{x \mid ax \leq b\}

and

b/a:=ρ a #(b)=max{xxab}.b / a:= \rho_a^\# (b) = max \{ x \mid xa \leq b\}.

In the completed (max,+)(max,+) semiring, ¯ max\overline{\mathbb{R}}_{max}, a\ba\backslash b and b/ab/a are equal and both equal bab-a, provided that a𝟘a\neq \mathbb{0}, in which case they equal ++\infty.

References

Last revised on September 9, 2021 at 04:53:05. See the history of this page for a list of all contributions to it.