terminating reduction
Let $X$ be a set and $\to $ a reduction^{} (binary relation^{}) on $X$. A chain with respect to $\to $ is a sequence^{} of elements ${x}_{1},{x}_{2},{x}_{3},\mathrm{\dots}$ in $X$ such that ${x}_{1}\to {x}_{2}$, ${x}_{2}\to {x}_{3}$, etc… A chain with respect to $\to $ is usually written
$${x}_{1}\to {x}_{2}\to {x}_{3}\to \mathrm{\cdots}\to {x}_{n}\to \mathrm{\cdots}.$$ 
The length of a chain is the cardinality of its underlying sequence. A chain is finite if its length is finite. Otherwise, it is infinite^{}.
Definition. A reduction $\to $ on a set $X$ is said to be terminating if it has no infinite chains. In other words, every chain terminates.
Examples.
 •

•
Let $X$ be the set of all positive integers greater than $1$. Define $\to $ on $X$ so that $a\to b$ means that $a=bc$ for some $c\in X$. Then $\to $ is a terminating reduction. By the way, $\to $ 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 nonnegative integers with the reduction $\to $ defined by $a\to b$ if and only if

–
either $a,b\ne 0$, $a\ne b$, and $$,

–
or $a\ne 0$ and $b=0$.
The infinite chain is given by $1\to 2\to 3\to \mathrm{\cdots}$, so that $\to $ is not terminating. However, $n\to 0$ for every positive integer $n$. Thus every integer has $0$ as its normal form, so that $\to $ is normalizing.

–
Remarks.

•
A reduction is said to be convergent if it is both terminating and confluent^{}.

•
A relation^{} is terminating iff the transitive closure^{} of its inverse^{} is wellfounded.
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 nonempty subset of $X$ that contains no $S$minimal elements. Pick ${x}_{0}\in A$. Then we can find ${x}_{1}\in A$ with ${x}_{1}\ne {x}_{0}$, such that ${x}_{1}S{x}_{0}$. By the assumption^{} on $A$, this process can be iterated indefinitely. So we have a sequence ${x}_{0},{x}_{1},{x}_{2},\mathrm{\dots}$ such that ${x}_{i+1}S{x}_{i}$ with ${x}_{i}\ne {x}_{i+1}$. Since each pair $({x}_{i},{x}_{i+1})$ can be expanded into a finite chain with respect to $R$, we have produced an infinite chain containing elements ${x}_{0},{x}_{1},{x}_{2},\mathrm{\dots}$, contradicting the assumption that $R$ is terminating.
On the other hand, suppose the transitive closure $S$ of ${R}^{1}$ is wellfounded. If the chain ${x}_{0}R{x}_{1}R{x}_{2}R\mathrm{\cdots}$ is infinite, then the set $\{{x}_{0},{x}_{1},{x}_{2},\mathrm{\dots}\}$ has no $S$minimal elements, as ${x}_{i}S{x}_{j}$ 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 $\to $ 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 ${x}_{1}\to {x}_{2}\to {x}_{3}\to \mathrm{\cdots}$ is eventually constant if there is a positive integer $N$ such that for all $n\ge N$, ${x}_{n}={x}_{N}$. Every terminating relation satisfies DCC. The converse^{} is obviously not true, as a reflexive reduction illustrates.
Another related concept is acyclicity. Let $\to $ be a reduction on $X$. A chain ${x}_{0}\to {x}_{1}\to \mathrm{\cdots}{x}_{n}$ is said to be cyclic if ${x}_{i}={x}_{j}$ for some $$. This means that there is a “closed loop” in the chain. The reduction $\to $ is said to be acyclic if there are no cyclic chains with respect to $\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 nonterminating relation.
Title  terminating reduction 
Canonical name  TerminatingReduction 
Date of creation  20130322 17:57:41 
Last modified on  20130322 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 