# 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},\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

 $x_{1}\to x_{2}\to x_{3}\to\cdots\to x_{n}\to\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 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,

• 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 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. 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.

 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