0
$\begingroup$

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.

  • 0
    Just to make a link to a [new question](http://math.stackexchange.com/questions/261991/new-attempt-to-prove-dilworth-theorem) where I tried to incorporate the feedback I got here in a new attempt to prove the result. Thanks a lot.2012-12-19

1 Answers 1

0

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.

  • 0
    Thanks a lot. I will go back to work.2012-12-17