MAF : Background : Orderings
## Orderings

If *S* is any set and *R* is a subset of the Cartesian product *S*×*S* then *R* is a binary relation on *S*. If *s*,*t* ∈ *S* and (s,t) ∈ *R* then one can write *s R t* to denote the fact that *s* and *t* are *R*-related.

A partial ordering of a set *S* is a relation *≤* with the following additional properties for all *s,t,u* ∈ *S*.

- (Reflexivity).
*s ≤ s*
- (Transitivity). if
*s ≤ t* and *t ≤ u* then *s ≤ u*
- (Antisymmetry). if
*s ≤ t* and *t ≤ s* then *s = t*

The notation *s < t* means *s ≤ t* and *s ≠ t*. The notation *t ≥ s* is a synonymous with *s ≤ t*, and *t > s* is synonymous with *s < t*.

Elements *s* and *t* are said to be comparable if either *s ≤ t* or *t ≤ s*. A partial ordering of *S* in which any two elements are comparable is called a total ordering or linear ordering of *S*. A total ordering is a well-ordering if there is no infinite sequence of elements of *S* *s*_{1}, s_{2}... such that, for all *i*, *s*_{i} > *s*_{i+1}.

#### Reduction orderings

If *X* is an alphabet then a partial ordering of *X*^{*} (words on *X*) is said to be translation invariant if for all *u,v,a,b* ∈ *X*^{*} *u < v* implies *aub < avb*. A translation invariant well-ordering is called a reduction ordering. In such an ordering, words are necessarily
greater than any of their proper subwords (because otherwise we would find a word *w* with w > *awb* with *a* and *b* not both empty, and then we would have *awb* > *aawbb* by translation invariance, and clearly we can get an infinite descending chain of words by repetition). This shows that the empty word is first in the ordering.

A total ordering of *X*^{*} is said to be geodesic or consistent with length if *l(u)* < *l(v)* implies *u* < *v*. Such an ordering is necessarily a well ordering.

Pages 41-50 of [Sims94] contain a number of results about reduction orderings. In particular it is shown that shortlex (there called length + lexicographic ordering) and wreath product orderings are reduction orderings.