MAF : Background : 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,tS 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,uS.

  1. (Reflexivity). s ≤ s
  2. (Transitivity). if s ≤ t and t ≤ u then s ≤ u
  3. (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 s1, s2... such that, for all i, si > si+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,bX* 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.