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.
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 s1, s2... such that, for all i, si > si+1.
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.