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.

This is my first attempt to prove something a bit more serious than the usual trivial stuff. But I am not sure I actually proved the result. Does the following work?

Theorem (Dilworth, 1950): Every poset whose width is $n$ is equal to the union of $n$ chains.

Proof: We let $R$ be a partial order relation over a set and we let $P$ be an arbitrary poset with width $w(P)$ equal to $n$. We proceed on induction over $w(P)$.

i) Base case: We assume that $w(P)$ is equal to $2$. This means that there are two elements member of $P$, say $x_1$ and $x_2$, that are $R−incomparable$. We let $p$ be an arbitrary element of $P$ and let $C_i$ be a chain, subset of $P$, whose elements are all the elements of $P$ that are $R−comparable$ to $x_i$ (with $i=1,2$). To prove the sufficient condition we proceed by contradiction by assuming that $p$ is an arbitrary member of $P$ and that it is not a member of both $C_1$ and $C_2$. This last assumption implies that we have $¬pRx_i$ and $¬x_iRp$ (with $i=1,2$), but this means that $p$ is $R−incomparable$ to both $x_1$ and $x_2$. Hence $w(P)$ has to be more than $2$, contradicting our assumption. The necessary condition is immediate. Thus, the base case is proven.

ii) Inductive step: We assume that $w(P)=n$ implies $P=⋃^{n}_{i=1}C_i$, and we assume that $w(P)$ is equal to $n+1$. We let $p$ be an arbitrary element of $P$ and $C_i$ be the $i$-th chain, subset of $P$, whose elements are all the elements of $P$ that are $R−comparable$ to $x_i$ (with $i=1,...,n+1$). To prove the sufficient condition we proceed by contradiction by assuming that $p$ is an arbitrary member of $P$ and that $p$ is not a member of any of the $n+1$ chains previously defined. We define $P′=P/\{x_i\}$ as $P$ minus an arbitrary element $x_i$ member of $w(P)$ (with $i=1,...,n+1$). By construction the width $w(P′)$ is equal to $n$. We assume that $P′=⋃^{n}_{i=1}C_i$. This means that for every element $p$ of $P′$ there exist $n$ chains such that $p$ is a member of $P′$ if and only if $p$ is a member of at least one of the $n$ chains. Thus, we assume that $p$ is a member of at least one of the $n$ chains. However, this contradicts our assumption that $p$ is not a member of any of the $n+1$ chains that are equal to the union of the $n$ chains and the arbitrary $x_i$ element taken from $P$ to construct $P′$. Hence, the sufficient condition is proven. The necessary condition is immediate.

Thus, by the inductive step the theorem is proven.

share|improve this question
    
What is $R$? Why are you using two partial orders? Are $R$ and $P$ supposed to be partial orders over the same set? –  Thomas Andrews Dec 17 '12 at 18:47
    
"We let $p$ be an arbitrary element of P and let $C_i$ be a chain, subset of $P$, whose elements are all the elements of P that are $R$−comparable to $x_i$ (with $i=1,2$)." Where do you use $p$? How do you know the $C_i$ defined this way are chains?) (Hint, they don't need to be - it is easy to construct a $4$-element counter-example. –  Thomas Andrews Dec 17 '12 at 18:51
    
Just wondering. Can I save the proof or it is the structure itself that is not sound? I mean, if I properly define $C_i$ in both the base case and the inductive step, should it work? –  Kolmin Dec 18 '12 at 9:07
    
It might be hard to do induction on $w(P)$. There is a proof on Wikipedia that uses induction on $|P|$. –  Thomas Andrews Dec 18 '12 at 14:32
    
In particular, if you prove by induction on $w(P)$, would your proof work for infinite $P$? (The theorem is actually true when $P$ is infinite and $w(P)$ is finite, so it could, but that is a much deeper theorem.) –  Thomas Andrews Dec 18 '12 at 16:02

1 Answer 1

up vote 0 down vote accepted

As I mentioned in comments, it's not clear what the function of having two partial orders is. What is $R$ in relation to the statement that $P$ is a poset? Is $R$ supposed to be the partial order on $P$, or is it supposed to be something unrelated. It is really unclear.

When you write:

We let $p$ be an arbitrary element of P and let $C_i$ be a chain, subset of $P$, whose elements are all the elements of P that are $R$−comparable to $x_i$ (with $i=1,2$).

First: Where do you use $p$?

Second: How do you know the $C_i$ defined this way are chains? It is easy to provide counter-examples.

share|improve this answer
    
Thanks a lot. I will go back to work. –  Kolmin Dec 17 '12 at 19:04

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.