Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
1  
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. –  Andres Caicedo Jan 13 '13 at 21:35

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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