Infinite Descending Chain

Given a set S with a partial order ≤, an infinite descending chain is an infinite, strictly decreasing sequence of elements x1 > x2 > ... > xn > ...

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 possess any infinite descending chains, it is said then, that it satisfies the descending chain condition. Assuming the axiom of choice, the descending chain condition on a partially ordered set is equivalent to requiring that the corresponding strict order is well-founded. 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.

Other articles related to "infinite descending chain, infinite":

Robertson–Seymour Theorem - Statement
... A preorder is said to form a well-quasi-ordering if it contains neither an infinite descending chain nor an infinite antichain ... same ordering on the set of all integers is not, because it contains the infinite descending chain 0, −1, −2, −3.. ... graph minor relationship does not contain any infinite descending chain, because each contraction or deletion reduces the number of edges and vertices of the ...

Famous quotes containing the words chain, infinite and/or descending:

    Man ... cannot learn to forget, but hangs on the past: however far or fast he runs, that chain runs with him.
    Friedrich Nietzsche (1844–1900)

    Age cannot wither her, nor custom stale
    Her infinite variety. Other women cloy
    The appetites they feed, but she makes hungry
    Where most she satisfies.
    William Shakespeare (1564–1616)

    The sun of her [Great Britain] glory is fast descending to the horizon. Her philosophy has crossed the Channel, her freedom the Atlantic, and herself seems passing to that awful dissolution, whose issue is not given human foresight to scan.
    Thomas Jefferson (1743–1826)