# Every finite partially ordered set has a maximum length chain.

Every finite partially ordered set, $(A, \leq)$, has a maximum length chain.

A chain is a sequence of distinct elements $a_1 \leq a_2 \leq .......\leq a_n$ with relation $"\leq"$ where $a_i \in A$ for all $i$

How to prove this formally using wellordering principle ? I see that if we need to prove there exist a minimal length chain it will be useful, but what is WOP's relation with proving maximal length chain ? Is it related to a bounded set has a max element ? if so how to use well ordering to show this ?

• Start by showing that there are maximal chains in $A$, that is, chains $a_1<a_2<\dots<a_n$ that cannot be extended by adding an $a_0<a_1$ or an $a_{n+1}>a_n$, or an $a'$ with $a_i<a'<a_{i+1}$ for some $i$. The well-ordering principle comes handy here. In fact, check that every chain can be extended to a maximal one. Once you have maximal chains, to find one of maximum length is easy. – Andrés E. Caicedo Jan 13 '13 at 21:35

Let $(A,\leq)$ be a finite partially ordered set, then every chain in $A$ is finite. There are only finitely many subsets of $A$ so only finitely many chains exist, therefore the following set is finite: $$\{n\mid\exists C\subseteq A:|C|=n\land C\text{ is a chain in }(A,\leq)\}.$$
Finite sets of natural numbers have maximal elements, and therefore there exists $C\subseteq A$ which is a chain and has the maximal length possible. It is easy to see that such $C$ is a maximal chain as well, otherwise we could have extended it and there would be a chain whose length is longer.