Ascending chain condition
Let be a partially ordered set. We say that satisfies the ascending chain condition (ACC) if every ascending chain eventually stabilizes; that is, there is some such that for all .
Similarly, if every descending chain stabilizes, we say that satisfies the descending chain condition (DCC). A set with an ordering satisfies ACC if and only if its opposite ordering satisfies DCC.
Every finite ordered set necessarily satisfies both ACC and DCC.
Theorem. A partially ordered set satisfies the ascending chain condition if and only if every subset of has a maximal element.
Proof. First, suppose that every subset of has a maximal element. Then every ascending chain in has a maximal element, so satisfies ACC.
Now, suppose that some subset of has no maximal element. Then we can recursively define elements such that , for all . This sequence constitutes an ascending chain that does not stabilize, so does not satisfy ACC.
This article is a stub. Help us out by .