terminating reduction (original) (raw)

Examples.

• •
  If → is reflexive, or non-trivial symmetric, then it is never terminating.
• •
  Let X be the set of all positive integers greater than 1. Define → on X so that a→b means that a=b⁢c for some c∈X. Then → is a terminating reduction. By the way, → is also a normalizing reduction.
• •
  In fact, it is easy to see that a terminating reduction is normalizing: if a has no normal form, then we may form an infinite chain starting from a.
• •
  On the other hand, not all normalizing reduction is terminating. A canonical example is the set of all non-negative integers with the reduction → defined by a→b if and only if
  • –
    either a,b≠0, a≠b, and a<b,
  • –
    or a≠0 and b=0.
    The infinite chain is given by 1→2→3→⋯, so that → is not terminating. However, n→0 for every positive integer n. Thus every integer has 0 as its normal form, so that → is normalizing.

Remarks.

• •
  A reduction is said to be convergent if it is both terminating and confluent.
• •
  To see this, first let R be terminating on the set X. And let S be the transitive closure of R-1. Suppose A is a non-empty subset of X that contains no S-minimal elements. Pick x0∈A. Then we can find x1∈A with x1≠x0, such that x1⁢S⁢x0. By the assumption on A, this process can be iterated indefinitely. So we have a sequence x0,x1,x2,… such that xi+1⁢S⁢xi with xi≠xi+1. Since each pair (xi,xi+1) can be expanded into a finite chain with respect to R, we have produced an infinite chain containing elements x0,x1,x2,…, contradicting the assumption that R is terminating.
  On the other hand, suppose the transitive closure S of R-1 is well-founded. If the chain x0⁢R⁢x1⁢R⁢x2⁢R⁢⋯ is infinite, then the set {x0,x1,x2,…} has no S-minimal elements, as xi⁢S⁢xj whenever i>j, and j arbitrary.
• •
  The reflexive transitive closure of a terminating relation is a partial order.

A closely related concept is the descending chain condition (DCC). A reduction → on X is said to satisfy the descending chain condition (DCC) if the only infinite chains on X are those that are eventually constant. A chain x1→x2→x3→⋯ is eventually constant if there is a positive integer N such that for all n≥N, xn=xN. Every terminating relation satisfies DCC. The converse is obviously not true, as a reflexive reduction illustrates.

Another related concept is acyclicity. Let → be a reduction on X. A chain x0→x1→⋯⁢xn is said to be cyclic if xi=xj for some 0≤i<j≤n. This means that there is a “closed loop” in the chain. The reduction → is said to be acyclic if there are no cyclic chains with respect to →. Every terminating relation is acyclic, but not conversely. The usual strict inequality relation on the set of positive integers is an example of an acyclic but non-terminating relation.