Infinite descending chain
Encyclopedia
Given a set S with a partial order ≤, an infinite descending chain is a chain V that is a subset of S upon which ≤ defines a total order
such that V has no least element, that is, an element m such that for all elements n in V it holds that m ≤ n.
As an example, in the set of integer
s, the chain −1, −2, −3, ... is an infinite descending chain, but there exists no infinite descending chain on the natural number
s, as every chain of natural numbers has a minimal element.
If a partially ordered set does not contain any infinite descending chains, it is called well-founded
or, in some case, Artinian
; it is then said to satisfy the descending chain condition. A stronger condition, that there be no infinite descending chains and no infinite antichains, defines the well-quasi-ordering
s. A totally ordered set without infinite descending chains is called well-order
ed.
Total order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
such that V has no least element, that is, an element m such that for all elements n in V it holds that m ≤ n.
As an example, in the set of integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s, the chain −1, −2, −3, ... is an infinite descending chain, but there exists no infinite descending chain on the natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s, as every chain of natural numbers has a minimal element.
If a partially ordered set does not contain any infinite descending chains, it is called well-founded
Well-founded relation
In mathematics, a binary relation, R, is well-founded on a class X if and only if every non-empty subset of X has a minimal element with respect to R; that is, for every non-empty subset S of X, there is an element m of S such that for every element s of S, the pair is not in R:\forall S...
or, in some case, Artinian
Artinian
In mathematics, Artinian, named for Emil Artin, is an adjective that describes objects that satisfy particular cases of the descending chain condition.*A ring is an Artinian ring if it satisfies the descending chain condition on ideals...
; it is then said to satisfy the descending chain condition. A stronger condition, that there be no infinite descending chains and no infinite antichains, defines the well-quasi-ordering
Well-quasi-ordering
In mathematics, specifically order theory, a well-quasi-ordering or wqo is a well-founded quasi-ordering with an additional restriction on sequences - that there is no infinite sequence x_i with x_i \not \le x_j for all i...
s. A totally ordered set without infinite descending chains is called well-order
Well-order
In mathematics, a well-order relation on a set S is a strict total order on S with the property that every non-empty subset of S has a least element in this ordering. Equivalently, a well-ordering is a well-founded strict total order...
ed.