|
|
|
|
Dilworth's theorem
|
(Theorem)
|
|
Theorem 1 If $P$ is a poset with width $w<\infty$ then $w$ is also the smallest integer such that $P$ can be written as the union of $w$ chains.
Remark. The smallest cardinal $c$ such that $P$ can be written as the union of $c$ chains is called the chain covering number of $P$ So Dilworth's theorem says that if the width of $P$ is finite, then it is equal to the chain covering number of $P$ If $w$ is infinite, then statement is not true. The proof of Dilworth's theorem and its counterexample in the infinite case can be found in the reference below.
- 1
- J.B. Nation, ``Lattice Theory", http://www.math.hawaii.edu/~jb/lat1-6.pdf
|
"Dilworth's theorem" is owned by CWoo. [ full author list (2) ]
|
|
(view preamble | get metadata)
Cross-references: reference, counterexample, proof, infinite, finite, cardinal, chains, union, integer, width, poset
There is 1 reference to this entry.
This is version 11 of Dilworth's theorem, born on 2006-03-31, modified 2007-06-24.
Object id is 7794, canonical name is DilworthsTheorem.
Accessed 4256 times total.
Classification:
| AMS MSC: | 06A06 (Order, lattices, ordered algebraic structures :: Ordered sets :: Partial order, general) | | | 06A07 (Order, lattices, ordered algebraic structures :: Ordered sets :: Combinatorics of partially ordered sets) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
