# Is this a sound proof of Dilworth Theorem?

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.

-
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

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.
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.