Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Ascending chain condition"

m (Ascending Chain Condition moved to Ascending chain condition: I shouldn't have capitalized it)
(Undo revision 99456 by Erich2007 (talk))
(Tag: Undo)
 
(3 intermediate revisions by 3 users not shown)
Line 6: Line 6:
 
Similarly, if every descending chain
 
Similarly, if every descending chain
 
<cmath> x_0 \geqslant x_1 \geqslant x_2 \geqslant \dotsc </cmath>
 
<cmath> x_0 \geqslant x_1 \geqslant x_2 \geqslant \dotsc </cmath>
−
stabilizes, we say that <math>S</math> satisfies the '''descending chain condition''' ('''DCC''').  A set <math>S</math> with an ordering <math>\leqslant</math> satisifes ACC if and only if
+
stabilizes, we say that <math>S</math> satisfies the '''descending chain condition''' ('''DCC''').  A set <math>S</math> with an ordering <math>\leqslant</math> satisfies ACC if and only if
 
its opposite ordering satisfies DCC.
 
its opposite ordering satisfies DCC.
  
Line 16: Line 16:
 
say that <math>M</math> is [[Noetherian]].  If this set satisfies DCC, we say
 
say that <math>M</math> is [[Noetherian]].  If this set satisfies DCC, we say
 
that <math>M</math> is [[Artinian]].
 
that <math>M</math> is [[Artinian]].
 +
 +
'''Theorem.''' A partially ordered set <math>S</math> satisfies the ascending
 +
chain condition if and only if every subset of <math>S</math> has a
 +
[[maximal element]].
 +
 +
''Proof.''  First, suppose that every subset of <math>S</math> has a maximal
 +
element.  Then every ascending chain in <math>S</math> has a maximal element,
 +
so <math>S</math> satisfies ACC.
 +
 +
Now, suppose that some subset of <math>S</math> has no maximal element.  Then
 +
we can recursively define elements <math>x_0, x_1, \dotsc</math> such that
 +
<math>x_{n+1} > x_n</math>, for all <math>n\ge 0</math>.  This sequence constitutes
 +
an ascending chain that does not stabilize, so <math>S</math> does not
 +
satisfy ACC.  <math>\blacksquare</math>
 +
  
 
{{stub}}
 
{{stub}}

Latest revision as of 17:00, 15 December 2018

Let $S$ be a partially ordered set. We say that $S$ satisfies the ascending chain condition (ACC) if every ascending chain \[x_0 \leqslant x_1 \leqslant x_2 \leqslant \dotsc\] eventually stabilizes; that is, there is some $N\ge 0$ such that $x_n = x_N$ for all $n\ge N$.

Similarly, if every descending chain \[x_0 \geqslant x_1 \geqslant x_2 \geqslant \dotsc\] stabilizes, we say that $S$ satisfies the descending chain condition (DCC). A set $S$ with an ordering $\leqslant$ satisfies ACC if and only if its opposite ordering satisfies DCC.

Every finite ordered set necessarily satisfies both ACC and DCC.

Let $A$ be a ring, and let $M$ be an $A$-module. If the set of sub-modules of $M$ with the ordering of $M$ satifies ACC, we say that $M$ is Noetherian. If this set satisfies DCC, we say that $M$ is Artinian.

Theorem. A partially ordered set $S$ satisfies the ascending chain condition if and only if every subset of $S$ has a maximal element.

Proof. First, suppose that every subset of $S$ has a maximal element. Then every ascending chain in $S$ has a maximal element, so $S$ satisfies ACC.

Now, suppose that some subset of $S$ has no maximal element. Then we can recursively define elements $x_0, x_1, \dotsc$ such that $x_{n+1} > x_n$, for all $n\ge 0$. This sequence constitutes an ascending chain that does not stabilize, so $S$ does not satisfy ACC. $\blacksquare$


This article is a stub. Help us out by expanding it.

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Ascending_chain_condition&oldid=99457"