I understand why the set of natural numbers $\mathbb N = \{ 0, 1, 2, \cdots \}$ is equipped with a total order. Indeed, every monoid has a pre-order, where $$n' \succeq n \quad \mathrm{if~and~only~if} \quad n' = n + m \quad \mathrm{~for~some~} m.$$ In the case of $\mathbb N$, this pre-order is a total order.

However, the same construction does not result in a total order on the set of integers $\mathbb Z$. Indeed, this set is a group, so its canonical monoid pre-order is trivial. i.e., $n' \succeq n$ for all $n, n' \in \mathbb Z$, since $n' = n + (n' - n)$.

Nonetheless, $\mathbb N$ is a subset of $\mathbb Z$, so it makes sense to assign an order relation to $\mathbb Z$ which extends the natural order on $\mathbb N$. I see (at least) two natural ways to do this:

  • The standard total order $\ge$ on $\mathbb Z$.
  • The pre-order on $\mathbb Z$ which corresponds to the absolute value norm. i.e., $n' \succeq n$ if and only if $|n'| \succeq |n|$.

There is obvious pragmatic justification for choosing the standard total order; it's utility is not in question. However, there are also pragmatic advantages for the alternate pre-order. For example, it admits $0$ as a minimal element ($n \succeq 0$ for all $n \in \mathbb Z$), and it extends the canonical pre-orders on the monoids $\mathbb N$ and $-\mathbb N$. It also generalizes nicely to higher-dimensional settings such as $\mathbb Z^d$, where no natural total order exists.

The integers exist in a universal mathematical sense: they form the Grothendieck group for the natural numbers. However, there seem to be (at least) two order-theoretic models for the integers: the totally ordered set $(\mathbb Z, \ge)$ and the pre-ordered set $(\mathbb Z, \succeq)$.

I taught an undergraduate discrete mathematics course last semester and the book never even acknowledged the second model, nor did it provide justification for the first. I suppose this is acceptable for undergraduates, but as a mathematician I am bothered by the implicit choice for an ubiquitous mathematical structure.

Ergo my question:

  • What is a mathematical justification for "always" choosing the "standard order" $(\mathbb Z, \ge)$?

That is, is there a universal characterization of this order structure which can be adapted to the setting of a Grothendieck group over general monoid? When does it it result in a total or partial order on the group instead of just a pre-order?

  • 13
    $\begingroup$ I feel like your question is bordering on being pedantic rather than being research oriented. The literal answer is you use whichever order is more relevant to the situation. In dynamical systems, the Sharkovski order is popular. But the order you're calling the standard order is popular since people call the operation $n \longmapsto n+1$ it an "increment". There's no increment for what you're calling the pre-ordered set, as you have to decide where to send zero. $\endgroup$ Feb 27 '13 at 20:16
  • 3
    $\begingroup$ The question is, bordering it on what side! :D $\endgroup$ Feb 28 '13 at 4:41
  • $\begingroup$ +1 Ryan. It depends what are your needs to have an order. There are several beautiful orderings also on $\mathbb{Q}$ -- except for the school version, which appear in various brilliant theorems. $\endgroup$
    – Victor
    Feb 28 '13 at 6:50
  • 2
    $\begingroup$ @Ryan Budney, one mathematician's pedantry is another's research program. Thank you for sharing your observation on the Sharkovski order; it looks interesting. $\endgroup$ Feb 28 '13 at 22:07

I assume (your) monoids are cancellative.

Then the pre-order you define is a (partial) order if and only of the monoid $M$ is reduced (i.e. has no invertible elements besides the neutral one).

For getting an order on the Grothendieck group $G$ say the element in $M$ are "positive elements" and define on $G$ the relation $g\ge h$ if $g-h \in M$. This extends the preorder of $M$; is transitive and reflexive; and it is anti-symetric if and only if $M$ contains no non-trivial invertible elements.

It is a total order if $g$ or $-g$ in $M$ for each $g \in G$; such a monoid $M$ is sometimes called a valuation monoid (in analogy with valuation rings, which have this property with respect to their quotient field, for multiplication of course; thus also these monoids are more frequently noted multiplicatively).

  • $\begingroup$ Thank you, @quid. This is a great answer to my question. $\endgroup$ Feb 28 '13 at 22:08
  • $\begingroup$ @Tom LaGatta: You are welcome! $\endgroup$
    – user9072
    Mar 1 '13 at 11:40

The standard order is (up to isomorphism) the only total order on $\mathbb Z$ that makes it an ordered group under addition. So I'd expect it to be useful in situations where addition plays a role; these are probably most (though certainly not all, as Ryan Budney pointed out in a comment to the question) of the situations that arise in practice

  • $\begingroup$ Thank you, @Andreas Blass. In a sense, I should have anticipated this answer: if we insist on a total order, then it is not at all surprising that the standard order is the only one. $\endgroup$ Feb 28 '13 at 22:08

Maybe the following can be an justification:

A linear order of a semigroup can be continued by one and only one way to a linear order of its semigroup of fractions (L. Fuchs, Partially Ordered Algebraic Systems, Theorem III.X.4).

Note. Here the semigroup can be neither commutative nor cancellative.

  • $\begingroup$ Thank you, @Boris Novikov. This is an excellent fact to know. $\endgroup$ Feb 28 '13 at 22:14

Every element in a well order can be represented by an ordinal number such as $0,1,2,3,\omega,\omega+1$ and $\omega^2+1$. Elements in the transpose of a well order can be represented with an inverted ordinal number such as $0,-1,-2,-3$, and $-\omega$. Since well orders and the transposed well orders have an exact representation they have no order automorphisms.

The smallest total ordering relation that does have order automorphisms is the set of integers $\mathbb{Z}$ and their set of automorphisms is the additive abelian group $(\mathbb{Z},+)$ because for all $x,y\in\mathbb{Z}$ $(x\le y)\Leftrightarrow (x+a\le y+a)$ for any $a\in\mathbb{Z}$.

Given an automorphism group of a total order like $\mathbb{Z}$ it is customary to totally ordered the group itself by growth rates so the automorphism (+2) would be less then (+5) because for any $x\in\mathbb{Z}$ in $(x+2 \le x+5)$. The linear order automorphisms of $\mathbb{Q}$ represented as $ax+b$ can likewise be totally ordered by $ax+b \le cx + d$ when $a\le c$ or $a=c$ and $b \le d$.

The linear ordered automorphism group of $\mathbb{Q}$ contains the order type of $\mathbb{Q}$ as a suborder and they only form a subset of all the automorphisms of $\mathbb{Q}$. The set of integers $\mathbb{Z}$ are the smallest totally ordered automorphism group arising from their own total order.


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.