0

In a computer science class about automata the professor claims that a semiring can not have both additive inverse and canonical partial order at the same time. I do not understand how additive inverse contradicts with canonical partial order?

The canonical partial order is defined as $\forall a,b \in F. [ a \leq b \equiv \exists c \in F. a+c=b ] $.

If the additive inverse exists than a possible $c$ is $c=(-a)+b$ which would result into $a \leq b \equiv a+(-a)+b \leq b = b \leq b$. But this does not look like a valid proof by contradiction.

viefs
  • 101
  • If for all $a, b$ we have $a \le b$, then also $b \le a$, so $a = b$. So, the only possibility would be the trivial semiring (which is degenerate since $0 = 1$), and depending on the definition, if you also want to require $0 \lneq 1$, that would give a contradiction. – Daniel Schepler Aug 08 '17 at 21:50
  • But I don't see where the additive inverse comes into play. – viefs Aug 08 '17 at 22:25
  • You already showed if the semiring has additive inverses then for all $a, b \in F$, the canonical partial order would have to give $a \le b$. – Daniel Schepler Aug 08 '17 at 22:27

0 Answers0