A proof of Dilworth Theorem? - Looking for feedbacks

[Kolmin]

It is the very first time I try such a long shot, attempting to prove a well-known theorem (small one, but still not completely obvious).

I would be really grateful to anyone ready to give a feedback (contents or style doesn't matter - they are both important).

PS: Obviously I am not sure I actually proved!

 

[Kolmin]

It is the very first time I try such a long shot, attempting to prove a well-known theorem (small one, but still not completely obvious).

I would be really grateful to anyone ready to give a feedback (contents or style doesn't matter - they are both important).

PS: Obviously I am not sure I actually proved!

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 $\neg pRx_i$ and $\neg 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= \bigcup_{i=1}^{n} 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,\dots, 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,\dots,n+1$). By construction the width $w(P’)$ is equal to $n$. We assume that $P'= \bigcup_{i=1}^{n} 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.

 

[bpet]

It's not obvious that the Ci are chains - e.g. {A>C, A>D, B>C} may present some difficulties for n=2.

Did you find another approach?