Kolmin said:
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.
