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 ?
Best Answer
We will use the fact that every subset of a finite set is finite.
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.