terminating reduction


Let X be a set and a reductionPlanetmathPlanetmathPlanetmath (binary relationMathworldPlanetmath) on X. A chain with respect to is a sequencePlanetmathPlanetmath of elements x1,x2,x3, in X such that x1x2, x2x3, etc… A chain with respect to is usually written

x1x2x3xn.

The length of a chain is the cardinality of its underlying sequence. A chain is finite if its length is finite. Otherwise, it is infiniteMathworldPlanetmath.

Definition. A reduction on a set X is said to be terminating if it has no infinite chains. In other words, every chain terminates.

Examples.

  • If is reflexiveMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath, or non-trivial symmetricPlanetmathPlanetmathPlanetmath, then it is never terminating.

  • Let X be the set of all positive integers greater than 1. Define on X so that ab means that a=bc for some cX. 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 ab if and only if

    • either a,b0, ab, and a<b,

    • or a0 and b=0.

    The infinite chain is given by 123, so that is not terminating. However, n0 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 confluentMathworldPlanetmath.

  • A relationMathworldPlanetmathPlanetmath is terminating iff the transitive closureMathworldPlanetmath of its inverseMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath is well-founded.

    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 x0A. Then we can find x1A with x1x0, such that x1Sx0. By the assumptionPlanetmathPlanetmath on A, this process can be iterated indefinitely. So we have a sequence x0,x1,x2, such that xi+1Sxi with xixi+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 x0Rx1Rx2R is infinite, then the set {x0,x1,x2,} has no S-minimal elements, as xiSxj whenever i>j, and j arbitrary.

  • The reflexive transitive closure of a terminating relation is a partial orderMathworldPlanetmath.

A closely related conceptMathworldPlanetmath is the descending chain conditionMathworldPlanetmathPlanetmathPlanetmath (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 x1x2x3 is eventually constant if there is a positive integer N such that for all nN, xn=xN. Every terminating relation satisfies DCC. The converseMathworldPlanetmath is obviously not true, as a reflexive reduction illustrates.

Another related concept is acyclicity. Let be a reduction on X. A chain x0x1xn is said to be cyclic if xi=xj for some 0i<jn. 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.

Title terminating reduction
Canonical name TerminatingReduction
Date of creation 2013-03-22 17:57:41
Last modified on 2013-03-22 17:57:41
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 11
Author CWoo (3771)
Entry type Definition
Classification msc 68Q42
Related topic NormalizingReduction
Related topic Confluence
Related topic DiamondLemma
Defines terminating
Defines descending chain condition
Defines DCC
Defines convergent reduction
Defines acyclic