Let be the set of all positive integers greater than . Define on so that means that for some . 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 has no normal form, then we may form an infinite chain starting from .
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 if and only if
either , , and ,
or and .
The infinite chain is given by , so that is not terminating. However, for every positive integer . Thus every integer has as its normal form, so that is normalizing.
A reduction is said to be convergent if it is both terminating and confluent.
To see this, first let be terminating on the set . And let be the transitive closure of . Suppose is a non-empty subset of that contains no -minimal elements. Pick . Then we can find with , such that . By the assumption on , this process can be iterated indefinitely. So we have a sequence such that with . Since each pair can be expanded into a finite chain with respect to , we have produced an infinite chain containing elements , contradicting the assumption that is terminating.
On the other hand, suppose the transitive closure of is well-founded. If the chain is infinite, then the set has no -minimal elements, as whenever , and 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 is said to satisfy the descending chain condition (DCC) if the only infinite chains on are those that are eventually constant. A chain is eventually constant if there is a positive integer such that for all , . 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 . A chain is said to be cyclic if for some . 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.
|Date of creation||2013-03-22 17:57:41|
|Last modified on||2013-03-22 17:57:41|
|Last modified by||CWoo (3771)|
|Defines||descending chain condition|