Moving from that question to this new one due to space reasons, here there is a new attempt to prove the theorem that (I hope) take into account the feedbacks of Thomas Andrews.
Theorem (Dilworth, 1950)
Every poset whose width is $n$ is equal to the union of $n$ chains.
Proof:
We let $(X,\succsim)$ be an arbitrary poset with width $w(X,\succsim)$ equal to $n$.
To prove the result we proceed on induction over $w(X,\succsim)$.
i) Base case
We assume that $w(X,\succsim)$ is equal to $2$. This means that there are two elements of $(X,\succsim)$, say $x_1$ and $x_2$, that are $\succsim$-incomparable.
We let $C_i$ be the subset of $(X,\succsim)$ that is the union of the singleton $\{x_i\}$ and the subset of $(X,\succsim)$ whose elements are all those that are $\succsim$-comparable to $x_i$ (with $i=1,2$). By construction we have that $C_i$ is a chain.
To prove the sufficient condtion we proceed by contradiction by assuming that every element of $(X,\succsim)$ is not a member of both $C_1$ and $C_2$. This implies that there exists an arbitrary element of $(X,\succsim)$ that it is not $\succsim$-comparable to both $x_1$ and $x_2$. However this means that there are at least three elements that are $\succsim$-incomparable, thus $w(X,\succsim)$ is higher than $2$, which contradicts our assumption.
The necessary condition is immediate.
Hence, the base case is proven.
Inductive step:
We assume that if $w(X,\succsim)$ is equal to $n$, then $(X,\succsim)=\bigcup^{n}_{i=1} C_i$, where $C_i$ is the subset of $(X,\succsim)$ that is the union of the singleton $x_i$ and the subset of $(X,\succsim)$ whose elements are all those that are $\succsim$-comparable to $\{x_i\}$ (with $i=1,\dots,n+1$). By construction we have that $C_i$ is a chain.
We assume that $w(X,\succsim)$ is equal to $n+1$. Then, we construct a new set, subset of $(X,\succsim)$, taking an arbitrary member of $w(X,\succsim)$ out of it, say $x_j$, and we call this new set $(X’,\succsim)$. Hence we have that $(X’,\succsim)$ is equal to $(X,\succsim)\setminus\{x_j\}$. Clearly, by construction $w(X’,\succsim)$ is equal to $n$. Thus we assume that $(X’,\succsim)=\bigcup^{n}_{i=1} C_i$. This implies that every element of $(X’,\succsim)=\bigcup^{n}_{i=1} C_i$ has to be an element of at least one of the $n$ chains.
To prove the sufficient condition we proceed by contradiction by assuming that every element of $(X,\succsim)$ is not a member of any of the $n+1$ chains $C_i$. Now, we have to consider two cases: (1) we take an arbitrary element of $(X,\succsim)$ different from $x_j$ ; (2) we take $x_j$.
1) By assumption this arbitrary element of $(X,\succsim)$ is not a member of any of the $n+1$ chains and it has to be an element of at least one of the $n$ chains whose union is equal to $(X’,\succsim)$. However the we have that $\bigcup^{n}_{i=1} C_i$ is a subset of $\bigcup^{n+1}_{i=1} C_i$. Thus we have reached a contradiction.
2) The contradiction is immediate because by definition $x_j$ cannot be an element of any chain, because it should imply that $x_j$ is $\succsim$-comparable to at least another element of $w(X,\succsim)$.
The necessary condition is immediate.
Thus, by the inductive step the result is proven.
I hope to have improved the notation. I guess that in this way the subsets $C_i$ are indeed chains. I am not sure this proof works, so I am really looking forward to any feedback (style or content are both relevant).
Thanks a lot.
