Editing Lexicographic order (section)

==Group orders of Z<sup>''n''</sup>==

Let <math>\Z^n</math> be the [[free Abelian group]] of rank <math>n,</math> whose elements are sequences of <math>n</math> integers, and operation is the [[Additive group|addition]]. A [[Totally ordered group|group order]] on <math>\Z^n</math> is a [[total order]], which is compatible with addition, that is 
<math display=block>a < b \quad \text{ if and only if } \quad a+c < b+c.</math>

The lexicographical ordering is a group order on <math>\Z^n.</math>

The lexicographical ordering may also be used to characterize all group orders on <math>\Z^n.</math><ref>Robbiano, L. (1985). Term orderings on the polynomial ring. In ''European Conference on Computer Algebra'' (pp. 513-517). Springer Berlin Heidelberg.</ref><ref>{{citation
 | last = Weispfenning | first = Volker
 | date = May 1987
 | doi = 10.1145/24554.24557
 | issue = 2
 | journal = SIGSAM Bulletin
 | location = New York, NY, USA
 | pages = 16–18
 | publisher = ACM
 | title = Admissible Orders and Linear Forms
 | volume = 21| s2cid = 10226875
 | doi-access = free
 }}.</ref> In fact, <math>n</math> [[linear form]]s with [[real number|real]] coefficients, define a map from <math>\Z^n</math> into <math>\R^n,</math> which is injective if the forms are [[linearly independent]] (it may be also injective if the forms are dependent, see below). The lexicographic order on the image of this map induces a group order on <math>\Z^n.</math> Robbiano's theorem is that every group order may be obtained in this way.

More precisely, given a group order on <math>\Z^n,</math> there exist an integer <math>s \leq n</math> and <math>s</math> linear forms with real coefficients, such that the induced map <math>\varphi</math> from <math>\Z^n</math> into <math>\R^s</math> has the following properties;

* <math>\varphi</math> is injective;
* the resulting isomorphism from <math>\Z^n</math> to the image of <math>\varphi</math> is an order isomorphism when the image is equipped with the lexicographical order on <math>\R^s.</math>