## You are here

HomeDilworth's theorem

## Primary tabs

# Dilworth’s theorem

###### Theorem.

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.

# References

- 1 J.B. Nation, “Lattice Theory”, http://www.math.hawaii.edu/ jb/lat1-6.pdf

Defines:

chain covering number

Related:

DualOfDilworthsTheorem

Synonym:

Dilworth chain decomposition theorem

Type of Math Object:

Theorem

Major Section:

Reference

Groups audience:

## Mathematics Subject Classification

06A06*no label found*06A07

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections