next up previous contents
Next: Products of posets Up: Posets Previous: Maximal and minimal elements.   Contents

Chains and antichains.

If $ (E, \prec )$ is a poset and $ x,y \in E$, we can denote $ x \prec y$ by $ y \succ x$.

Definition 4.4.9   Let $ (E, \prec )$ be a poset. A descending chain in $ E$ is a sequence $ a_1 \succ a_2 \succ a_3 \succ \dots$, where all the $ a_i$'s are elements of $ E$. An antichain in $ E$ is a subset of $ E$ with no two elements directly comparable.

For example, $ \{ 12,4,2 \}$ is a descending chain and $ \{4,6,9\}$ is an antichain in $ \mathcal{D}_{36}$.

Proposition 4.4.10   If $ E$ is a poset with no chains of length gretaer than $ n$, then $ E$ can be covered by at most $ n$ antichains.

Proof. By induction on $ n$. Take $ n > 1$ and let $ M$ be the set of all maximal elements in $ E$. Now $ S \setminus M$ has no chains of length $ > n - 1$ and $ M$ is an antichain. $ \qedsymbol$



root 2002-06-10