Namespaces
Variants
Actions

Difference between revisions of "Chain condition"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(Comments: Topological terminology)
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
A finiteness condition for ascending or descending chains in a partially ordered set. The descending chain condition for a partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c0213901.png" /> states: For any chain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c0213902.png" /> of elements there is a number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c0213903.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c0213904.png" />. This condition is equivalent to each of the following properties of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c0213905.png" />:
+
{{TEX|done}}
 +
A finiteness condition for ascending or descending [[chain]]s in a [[partially ordered set]]. The descending chain condition for a partially ordered set $P$ states: For any chain $a_1\geq\dots\geq a_k\geq\dots$ of elements there is a number $n$ such that $a_n=a_{n+1}=\dots$. This condition is equivalent to each of the following properties of $P$:
  
1) every non-empty subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c0213906.png" /> has at least one minimal element in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c0213907.png" /> (the minimum condition);
+
1) every non-empty subset $M\subseteq P$ has at least one minimal element in $M$ (the minimum condition);
  
2) all elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c0213908.png" /> have a given property <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c0213909.png" /> if all minimal elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c02139010.png" /> have this property and if the validity of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c02139011.png" /> for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c02139012.png" /> can be deduced from the fact that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c02139013.png" /> is valid for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c02139014.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c02139015.png" /> (the inductiveness condition).
+
2) all elements of $P$ have a given property $\epsilon$ if all minimal elements of $P$ have this property and if the validity of $\epsilon$ for any $a\in P$ can be deduced from the fact that $\epsilon$ is valid for all $x<a$, $x\in P$ (the inductiveness condition).
  
The inductiveness condition enables one to carry out proofs and constructions by induction for sets with the descending chain condition. Here if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c02139016.png" /> is totally ordered (and hence well-ordered) one obtains [[Transfinite induction|transfinite induction]], and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c02139017.png" /> is isomorphic to the set of natural numbers, one obtains ordinary mathematical induction (see [[Induction axiom|Induction axiom]]).
+
The inductiveness condition enables one to carry out proofs and constructions by induction for sets with the descending chain condition. Here if $P$ is [[Totally ordered set|totally ordered]] (and hence [[Well-ordered set|well-ordered]]) one obtains [[Transfinite induction|transfinite induction]], and if $P$ is isomorphic to the set of natural numbers, one obtains ordinary mathematical induction (see [[Induction axiom|Induction axiom]]).
  
The ascending chain condition (and assertions equivalent to it) is formulated in a dual way (see [[Duality principle|Duality principle]] in partially ordered sets); it therefore states that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c02139018.png" /> is an ascending chain in a partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c02139019.png" />, then for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c02139020.png" /> large enough <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c02139021.png" />. In a lattice with the ascending chain condition every ideal is principal. Every finite set obviously satisfies both chain conditions, but the converse assertion (that a set satisfying both these conditions is finite) is false. A lattice satisfying the descending and ascending chain conditions is complete.
+
The ascending chain condition (and assertions equivalent to it) is formulated in a dual way (see [[Duality principle|Duality principle]] in partially ordered sets); it therefore states that if $a_1\leq\ldots\leq a_k\leq\dots$ is an ascending chain in a partially ordered set $P$, then for $n$ large enough $a_n=a_{n+1}=\dots$. In a lattice with the ascending chain condition every ideal is principal. Every finite set obviously satisfies both chain conditions, but the converse assertion (that a set satisfying both these conditions is finite) is false. A lattice satisfying the descending and ascending chain conditions is complete.
  
 
In algebra, chain conditions are mainly applied to sets of subsystems of various algebraic systems ordered by inclusion (see for example, [[Artinian module|Artinian module]]; [[Artinian group|Artinian group]]; [[Artinian ring|Artinian ring]]; [[Composition sequence|Composition sequence]]; [[Noetherian module|Noetherian module]]; [[Noetherian group|Noetherian group]]; [[Noetherian ring|Noetherian ring]]).
 
In algebra, chain conditions are mainly applied to sets of subsystems of various algebraic systems ordered by inclusion (see for example, [[Artinian module|Artinian module]]; [[Artinian group|Artinian group]]; [[Artinian ring|Artinian ring]]; [[Composition sequence|Composition sequence]]; [[Noetherian module|Noetherian module]]; [[Noetherian group|Noetherian group]]; [[Noetherian ring|Noetherian ring]]).
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  G. Birkhoff,  "Lattice theory" , ''Colloq. Publ.'' , '''25''' , Amer. Math. Soc.  (1973)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  A.G. Kurosh,  "Lectures on general algebra" , Chelsea  (1963)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  L.A. Skornyakov,  "Elements of lattice theory" , A. Hilger &amp; Hindushtan Publ. Comp.  (1977)  (Translated from Russian)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[1]</TD> <TD valign="top">  G. Birkhoff,  "Lattice theory" , ''Colloq. Publ.'' , '''25''' , Amer. Math. Soc.  (1973)</TD></TR>
 +
<TR><TD valign="top">[2]</TD> <TD valign="top">  A.G. Kurosh,  "Lectures on general algebra" , Chelsea  (1963)  (Translated from Russian)</TD></TR>
 +
<TR><TD valign="top">[3]</TD> <TD valign="top">  L.A. Skornyakov,  "Elements of lattice theory" , A. Hilger &amp; Hindustan Publ. Comp.  (1977)  (Translated from Russian)</TD></TR>
 +
</table>
  
 +
====Comments====
 +
The phrase  "chain condition"  is used in a different sense in the theory of Boolean algebras and in set theory (a [[Boolean algebra|Boolean algebra]], considered as a [[Partially ordered set|partially ordered set]], satisfies the descending chain condition if and only if it is finite, so this condition is not of interest in the context of Boolean algebras). A Boolean algebra $B$ is said to satisfy the $\kappa$-chain condition, where $\kappa$ is an infinite cardinal number, if every chain (i.e. totally ordered subset) in $B$ has cardinality less then $\kappa$. In particular, the $\aleph_1$-chain condition is commonly called the ''countable chain condition'' (abbreviated ccc); this is an important condition in the set-theoretic [[forcing method]] (see [[#References|[a1]]], Section 3, for example). For a complete Boolean algebra, the $\kappa$-chain condition is equivalent to the $\kappa$-antichain condition, i.e. the condition that every discretely ordered subset has cardinality less than $\kappa$. In the theory of forcing, set-theorists frequently work not with complete Boolean algebras of forcing conditions, but with partially ordered sets which generate them (as algebras of regular open sets); such a set satisfies the $\kappa$-antichain condition if and only if the same condition holds for the Boolean algebra which it generates. Unfortunately, set-theorists tend to use the term  "$\kappa$-chain condition"  in this context, when they really mean  "$\kappa$-antichain condition" .
  
 +
====References====
 +
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  J.P. Burgess,  "Forcing"  J. Barwise (ed.) , ''Handbook of mathematical logic'' , North-Holland  (1977)  pp. 403–452</TD></TR>
 +
</table>
  
 
====Comments====
 
====Comments====
The phrase  "chain condition"  is used in a different sense in the theory of Boolean algebras and in set theory (a [[Boolean algebra|Boolean algebra]], considered as a [[Partially ordered set|partially ordered set]], satisfies the descending chain condition if and only if it is finite, so this condition is not of interest in the context of Boolean algebras). A Boolean algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c02139022.png" /> is said to satisfy the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c02139024.png" />-chain condition, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c02139025.png" /> is an infinite cardinal number, if every chain (i.e. totally ordered subset) in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c02139026.png" /> has cardinality less then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c02139027.png" />. In particular, the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c02139028.png" />-chain condition is commonly called the countable chain condition (abbreviated ccc); this is an important condition in the set-theoretic [[Forcing method|forcing method]] (see [[#References|[a1]]], Section 3, for example). For a complete Boolean algebra, the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c02139029.png" />-chain condition is equivalent to the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c02139031.png" />-antichain condition, i.e. the condition that every discretely ordered subset has cardinality less than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c02139032.png" />. In the theory of forcing, set-theorists frequently work not with complete Boolean algebras of forcing conditions, but with partially ordered sets which generate them (as algebras of regular open sets); such a set satisfies the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021390/c02139033.png" />-antichain condition if and only if the same condition holds for the Boolean algebra which it generates. Unfortunately, set-theorists tend to use the term  "k-chain condition"  in this context, when they really mean  "k-antichain condition" .
+
A [[topological space]] satisfies the ''countable chain condition'' if every disjoint family of [[open set]]s is countable.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J.P. Burgess,   "Forcing"  J. Barwise (ed.) , ''Handbook of mathematical logic'' , North-Holland  (1977) pp. 403–452</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[b1]</TD> <TD valign="top">  John L. Kelley, ''General Topology'', Graduate Texts in Mathematics '''27''', Springer (1975) ISBN 0-387-90125-6, p.60</TD></TR>
 +
</table>
 +
 
 +
[[Category:Order, lattices, ordered algebraic structures]]

Revision as of 21:08, 19 December 2015

A finiteness condition for ascending or descending chains in a partially ordered set. The descending chain condition for a partially ordered set $P$ states: For any chain $a_1\geq\dots\geq a_k\geq\dots$ of elements there is a number $n$ such that $a_n=a_{n+1}=\dots$. This condition is equivalent to each of the following properties of $P$:

1) every non-empty subset $M\subseteq P$ has at least one minimal element in $M$ (the minimum condition);

2) all elements of $P$ have a given property $\epsilon$ if all minimal elements of $P$ have this property and if the validity of $\epsilon$ for any $a\in P$ can be deduced from the fact that $\epsilon$ is valid for all $x<a$, $x\in P$ (the inductiveness condition).

The inductiveness condition enables one to carry out proofs and constructions by induction for sets with the descending chain condition. Here if $P$ is totally ordered (and hence well-ordered) one obtains transfinite induction, and if $P$ is isomorphic to the set of natural numbers, one obtains ordinary mathematical induction (see Induction axiom).

The ascending chain condition (and assertions equivalent to it) is formulated in a dual way (see Duality principle in partially ordered sets); it therefore states that if $a_1\leq\ldots\leq a_k\leq\dots$ is an ascending chain in a partially ordered set $P$, then for $n$ large enough $a_n=a_{n+1}=\dots$. In a lattice with the ascending chain condition every ideal is principal. Every finite set obviously satisfies both chain conditions, but the converse assertion (that a set satisfying both these conditions is finite) is false. A lattice satisfying the descending and ascending chain conditions is complete.

In algebra, chain conditions are mainly applied to sets of subsystems of various algebraic systems ordered by inclusion (see for example, Artinian module; Artinian group; Artinian ring; Composition sequence; Noetherian module; Noetherian group; Noetherian ring).

References

[1] G. Birkhoff, "Lattice theory" , Colloq. Publ. , 25 , Amer. Math. Soc. (1973)
[2] A.G. Kurosh, "Lectures on general algebra" , Chelsea (1963) (Translated from Russian)
[3] L.A. Skornyakov, "Elements of lattice theory" , A. Hilger & Hindustan Publ. Comp. (1977) (Translated from Russian)

Comments

The phrase "chain condition" is used in a different sense in the theory of Boolean algebras and in set theory (a Boolean algebra, considered as a partially ordered set, satisfies the descending chain condition if and only if it is finite, so this condition is not of interest in the context of Boolean algebras). A Boolean algebra $B$ is said to satisfy the $\kappa$-chain condition, where $\kappa$ is an infinite cardinal number, if every chain (i.e. totally ordered subset) in $B$ has cardinality less then $\kappa$. In particular, the $\aleph_1$-chain condition is commonly called the countable chain condition (abbreviated ccc); this is an important condition in the set-theoretic forcing method (see [a1], Section 3, for example). For a complete Boolean algebra, the $\kappa$-chain condition is equivalent to the $\kappa$-antichain condition, i.e. the condition that every discretely ordered subset has cardinality less than $\kappa$. In the theory of forcing, set-theorists frequently work not with complete Boolean algebras of forcing conditions, but with partially ordered sets which generate them (as algebras of regular open sets); such a set satisfies the $\kappa$-antichain condition if and only if the same condition holds for the Boolean algebra which it generates. Unfortunately, set-theorists tend to use the term "$\kappa$-chain condition" in this context, when they really mean "$\kappa$-antichain condition" .

References

[a1] J.P. Burgess, "Forcing" J. Barwise (ed.) , Handbook of mathematical logic , North-Holland (1977) pp. 403–452

Comments

A topological space satisfies the countable chain condition if every disjoint family of open sets is countable.

References

[b1] John L. Kelley, General Topology, Graduate Texts in Mathematics 27, Springer (1975) ISBN 0-387-90125-6, p.60
How to Cite This Entry:
Chain condition. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Chain_condition&oldid=15683
This article was adapted from an original article by T.S. Fofanova (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article