Dilworth’s theorem

Theorem.

If $P$ is a poset with width , 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.

Title	Dilworth’s theorem
Canonical name	DilworthsTheorem
Date of creation	2013-03-22 15:49:37
Last modified on	2013-03-22 15:49:37
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	14
Author	CWoo (3771)
Entry type	Theorem
Classification	msc 06A06
Classification	msc 06A07
Synonym	Dilworth chain decomposition theorem
Related topic	DualOfDilworthsTheorem
Defines	chain covering number