Ascending chain condition

In mathematics, a poset P is said to satisfy the ascending chain condition (ACC)

Related Topics:
Mathematics - Poset

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

if every ascending chain a1 ≤ a2 ≤ ... of elements of P is eventually stationary,

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

that is, there is some positive integer n such that am = an for all m > n.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Similarly, P is said to satisfy the descending chain condition (DCC)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

if every descending chain a1 ≥ a2 ≥ ... of elements of P is eventually stationary (that is, there is no infinite descending chain).

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The ascending chain condition on P is equivalent to the maximum condition: every nonempty subset of P has a maximal element.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Similarly, the descending chain condition is equivalent to the minimum condition: every nonempty subset of P has a minimal element.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Every finite poset satisfies both ACC and DCC.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

A totally ordered set that satisfies the descending chain condition is called a well-ordered set.

Related Topics:
Totally ordered set - Well-ordered set

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

See also Noetherian and Artinian.

Related Topics:
Noetherian - Artinian

~ ~ ~ ~ ~ ~ ~ ~ ~ ~