2
$\begingroup$

Let $(S,+,.)$ be an idempotent $( a+a=a ~ \forall ~a~ \in S)$ semiring. A partial order on $S$ defined as $a\leq b$ iff $a+b=b$ $\forall ~ a,b \in S$. Note that by an involution function on $S$, we just mean a function $*:S \rightarrow S$ satisfying $(a*)^{*}=a ~ \forall ~a \in S$. Then is the following statement true?

$ab \leq c \Leftrightarrow c^{*}a \leq b^{*} \Leftrightarrow bc^{*} \leq a^{*}$ $\forall ~ a,b,c \in S$.

$\endgroup$
2
$\begingroup$

The statement is not true. For a counterexample, let $X$ be a set with at least two elements, let $S={\mathcal P}(X)$ be the power set of $X$, let addition in $S$ equal the union operation, and let multiplication equal intersection. The order relation on $S$ is just the inclusion order.

Let the involution be the function that swaps subsets $\emptyset$ and $X$, but fixes all other elements. Now choose some nonempty proper subset $U$ of $X$ and define $a, b, c\in S$ as follows: $a=U, b=X-U, c=\emptyset$. Then it is easily computed that $ab = \emptyset\leq \emptyset =c$, but $c^*a = a = U\not\leq X-U = b^*$.

The problem here is that the involution is not related to any of the other operations, so one cannot hope to prove $ab\leq c \Leftrightarrow c^*a\leq b^*$. But one can check that this bi-implication is true for the powerset semiring $\langle {\mathcal P}(X); \cup, \cap\rangle$ if you take the involution to be complementation: $U^* = X-U$. If you assume some complementation-like properties for the involution, you will be able to arrange that $ab\leq c \Leftrightarrow c^*a\leq b^*$ holds.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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