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 ?

  • 2
    $\begingroup$ 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. $\endgroup$ – Andrés E. Caicedo Jan 13 '13 at 21:35

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.