# dual of Dilworth’s theorem

###### Theorem 1.

Let $P$ be a poset of height $h$. Then $P$ can be partitioned into $h$ antichains^{} and furthermore at least $h$ antichains are required.

###### Proof.

Induction^{} on $h$. If $h=1$, then no elements of $P$ are comparable^{}, so $P$ is an antichain. Now suppose that $P$ has height $h\ge 2$ and that the theorem is true for $h-1$. Let ${A}_{1}$ be the set of maximal elements^{} of $P$. Then ${A}_{1}$ is an antichain in $P$ and $P-{A}_{1}$ has height $h-1$ since we have removed precisely one element from every chain. Hence, $P-{A}_{1}$ can be paritioned into $h-1$ antichains ${A}_{2},{A}_{3},\mathrm{\dots}{A}_{h}$. Now we have the partition^{} ${A}_{1}\cup {A}_{2}\cup \mathrm{\dots}\cup {A}_{h}$ of $P$ into $h$ antichains as desired.

The necessity of $h$ antichains is trivial by the pigeonhole principle^{}; since $P$ has height $h$, it has a chain of length $h$, and each element of this chain must be placed in a different antichain of our partition.
∎

Title | dual of Dilworth’s theorem |
---|---|

Canonical name | DualOfDilworthsTheorem |

Date of creation | 2013-03-22 15:01:49 |

Last modified on | 2013-03-22 15:01:49 |

Owner | justice (4961) |

Last modified by | justice (4961) |

Numerical id | 7 |

Author | justice (4961) |

Entry type | Theorem |

Classification | msc 06A06 |

Related topic | DilworthsTheorem |