terminating reduction
Let be a set and a reduction (binary relation) on . A chain with respect to is a sequence of elements in such that , , etc… A chain with respect 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 on a set is said to be terminating if it has no infinite chains. In other words, every chain terminates.
Examples.
- •
-
•
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.
-
–
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 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.
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 |