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},\ldots$ in $X$ such that $x_{1}\to x_{2}$, $x_{2}\to x_{3}$, etc… A chain with respect to $\to$ is usually written

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.

• If $\to$ is reflexive, or non-trivial symmetric, then it is never terminating.

• 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 non-negative integers with the reduction $\to$ defined by $a\to b$ if and only if

  • either $a,b\neq 0$, $a\neq b$, and $a<b$,

  • or $a\neq 0$ and $b=0$.

  The infinite chain is given by $1\to 2\to 3\to\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 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 $x_{0}\in A$. Then we can find $x_{1}\in A$ with $x_{1}\neq x_{0}$, such that $x_{1}Sx_{0}$. By the assumption on $A$, this process can be iterated indefinitely. So we have a sequence $x_{0},x_{1},x_{2},\ldots$ such that $x_{{i+1}}Sx_{i}$ with $x_{i}\neq 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},\ldots$, 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 $x_{0}Rx_{1}Rx_{2}R\cdots$ is infinite, then the set $\{x_{0},x_{1},x_{2},\ldots\}$ has no $S$-minimal elements, as $x_{i}Sx_{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\cdots$ is eventually constant if there is a positive integer $N$ such that for all $n\geq 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\cdots x_{n}$ is said to be cyclic if $x_{i}=x_{j}$ for some $0\leq i<j\leq n$. 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 non-terminating relation.