I'm looking for a classification (or just non-trivial examples) of partial orders on monoid $\mathbb{N}^{m}$ that are compatible with addition. That is, partial orders $\leq$ satisfying two additional axioms: $$\forall A \in \mathbb{N}^{m} \;\; (0, ..., 0) \leq A,$$ $$\forall A, B, C, D (A \leq B \text{ and } C \leq D) \rightarrow (A + C \leq B + D).$$

Apart from lexicographical order there exist many examples defined in terms of scalar products i.e. fix collection of vectors $v_1, ..., v_k \in \mathbb{R}_{\geq 0}^{m}$ and declare $A \leq B$ iff $(B - A, v_j) \geq 0 \; \forall j$.

  • $\begingroup$ en.wikipedia.org/wiki/Monomial_order is very close to what you want at least; that might be a good place to start looking. $\endgroup$ May 11, 2021 at 19:34
  • $\begingroup$ @SamHopkins Thanks. Indeed, that seems very close, but i'm not sure about the relation between the two. $\endgroup$ May 11, 2021 at 19:44
  • $\begingroup$ You can also just use the pointwise ordering and many many more $\endgroup$ May 12, 2021 at 0:21
  • 2
    $\begingroup$ @Sam, it seems equivalent to monomial order (with the $+$ operation). If the order is compatible with addition, and $A \le B$, then taking $D=C$ gives $A+C \le B+C$, so it is monomial. If the order is monomial, and $A\le B$ and $C \le D$, then $A+C \le B+C \le B+D$, where the first inequality is by adding $C$ to $A \le B$, and the second is by adding $B$ to $C \le D$. $\endgroup$ Jan 26 at 16:54


Your Answer

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

Browse other questions tagged or ask your own question.