Infinite descending chain: Difference between revisions
Tagging with {{settheory-stub}} using user scripts |
add well-quasi-ordering; remove see-also link already included in main text |
||
| Line 3: | Line 3: | ||
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. |
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 relation|well-founded]]. A totally ordered set without infinite descending chains is called [[well-order]]ed. |
If a partially ordered set does not contain any infinite descending chains, it is called [[Well-founded relation|well-founded]] and 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. |
||
==See also== |
|||
* [[Descending chain condition]] |
|||
* [[Well-founded relation]] |
|||
[[Category:Order theory]] |
[[Category:Order theory]] |
||
Revision as of 06:16, 4 August 2010
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 integers, the chain −1, −2, −3, ... is an infinite descending chain, but there exists no infinite descending chain on the natural numbers, 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 and 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-orderings. A totally ordered set without infinite descending chains is called well-ordered.
 | This set theory-related article is a stub. You can help Wikipedia by expanding it. |