请输入您要查询的字词:

 

单词 TerminatingReduction
释义

terminating reduction


Let X be a set and a reductionPlanetmathPlanetmathPlanetmath (binary relationMathworldPlanetmath) on X. A chain with respect to is a sequencePlanetmathPlanetmath of elements x1,x2,x3, in X such that x1x2, x2x3, etc… A chain with respect to is usually written

x1x2x3xn.

The length of a chain is the cardinality of its underlying sequence. A chain is finite if its length is finite. Otherwise, it is infiniteMathworldPlanetmath.

Definition. A reduction on a set X is said to be terminating if it has no infinite chains. In other words, every chain terminates.

Examples.

  • If is reflexiveMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath, or non-trivial symmetricPlanetmathPlanetmathPlanetmath, then it is never terminating.

  • Let X be the set of all positive integers greater than 1. Define on X so that ab means that a=bc for some cX. 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 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 defined by ab if and only if

    • either a,b0, ab, and a<b,

    • or a0 and b=0.

    The infinite chain is given by 123, so that is not terminating. However, n0 for every positive integer n. Thus every integer has 0 as its normal form, so that is normalizing.

Remarks.

  • A reduction is said to be convergent if it is both terminating and confluentMathworldPlanetmath.

  • A relationMathworldPlanetmathPlanetmath is terminating iff the transitive closureMathworldPlanetmath of its inverseMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath 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 x0A. Then we can find x1A with x1x0, such that x1Sx0. By the assumptionPlanetmathPlanetmath on A, this process can be iterated indefinitely. So we have a sequence x0,x1,x2, such that xi+1Sxi with xixi+1. Since each pair (xi,xi+1) can be expanded into a finite chain with respect to R, we have produced an infinite chain containing elements x0,x1,x2,, 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 x0Rx1Rx2R is infinite, then the set {x0,x1,x2,} has no S-minimal elements, as xiSxj whenever i>j, and j arbitrary.

  • The reflexive transitive closure of a terminating relation is a partial orderMathworldPlanetmath.

A closely related conceptMathworldPlanetmath is the descending chain conditionMathworldPlanetmathPlanetmathPlanetmath (DCC). A reduction 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 x1x2x3 is eventually constant if there is a positive integer N such that for all nN, xn=xN. Every terminating relation satisfies DCC. The converseMathworldPlanetmath is obviously not true, as a reflexive reduction illustrates.

Another related concept is acyclicity. Let be a reduction on X. A chain x0x1xn is said to be cyclic if xi=xj for some 0i<jn. 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.

Titleterminating reduction
Canonical nameTerminatingReduction
Date of creation2013-03-22 17:57:41
Last modified on2013-03-22 17:57:41
OwnerCWoo (3771)
Last modified byCWoo (3771)
Numerical id11
AuthorCWoo (3771)
Entry typeDefinition
Classificationmsc 68Q42
Related topicNormalizingReduction
Related topicConfluence
Related topicDiamondLemma
Definesterminating
Definesdescending chain condition
DefinesDCC
Definesconvergent reduction
Definesacyclic

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 6:47:13