3
$\begingroup$

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.

  • 0
    Shouldn't your assumption in the induction step be that a poset having width $n$ is the union of $n$ antichains? (You wrote it as the union of $n+1$ antichains). Apart from that, set difference is written using $\setminus$ (\setminus), not $/$.2012-12-19
  • 0
    Continuing: You should remove not only $x_j$ but all elements comparable with it in order to decrease the width by $1$.2012-12-19
  • 0
    Thanks a lot. I hate typos. I will edit immediately.2012-12-19
  • 0
    I don't see why I should remove $x_j$ and all the elements comparable to it in order to decrease the width. Isn't the width the set of all the elements who are not comparable to each others? Anyway, I am not that quick, so I will carefully think about it. :)2012-12-19
  • 1
    Consider the poset consisting of the integers from $1$ to $6$ with the following relation on them: $1\preceq2\preceq3\preceq6$ and $1\preceq4\preceq5\preceq6$, take the transitive and reflexive closure of this but assume no other relations. This poset clearly has width $2$ (for example, $2,4$ are the elements of a maximal antichain) but after removing $5$ you still have the same antichain and hence still have width $2$.2012-12-19
  • 0
    Ok, now I start to see.2012-12-19
  • 1
    The error is exactly the same as the one you made in the original post. I wrote: "How do you know the $C_i$ defined this way are chains? It is easy to provide counter-examples." It should always concern you when you assert something without giving any argument.2012-12-19
  • 0
    Definitely true! The problem is how I read your feedback: basically I thought you meant that with my old proof I stated that something was a chain (stylistic problem) without properly definying it (technical problem). If you read this new "proof", you can see that I kinda tried to overcome what I thought were those problems, because I rephrased that part. In my mind I had overcomed those issues...the real problem is that now I start to realize I simply didn't have the right picture in my mind about width and chains to incorporate your feedbacks.2012-12-19
  • 0
    I am afraid that the first time I simply didn't properly get what you wrote. I had to take the wrong path another time thinking to have fixed it in order to realize the meaning of what you wrote. Too bad. My fault. :)2012-12-19

1 Answers 1

2

You’ve a problem already with the base case. Consider this partial order of width $2$:

                    o                      / \                     o   o                     |\ /|                     | X |                     |/ \|                     o   o 

Let $x_1$ and $x_2$ be the two elements at the bottom of the Hasse diagram. Then $C_1=X\setminus\{x_2\}$ and $C_2=X\setminus\{x_1\}$, so neither is a chain.

  • 0
    Ok, that's bad (at least for me). :)2012-12-19
  • 0
    Just wondering, do you think that the structure itself is doomed to fail? I would like to understand if I basically chose the wrong path from the beginning.2012-12-19
  • 1
    @Kolmin: To be honest, I came to a screeching halt with the base case and haven’t yet read much further. I just checked Dilworth’s original paper, and he does argue by induction on the width, so there’s hope. (I’ve not looked at all at the details.)2012-12-19
  • 0
    Thanks a lot. I got Galvin's paper, but I didn't want to read it before completing the attempt in order to not be influenced. I am really new to order theory and to proving stuff in general, so this was mainly an attempt to train myself at the same time in two things that are really important to me and where I am a newbie. I would say I wanted to understand where I stand in the learning phase. Still a lot to work, but it's ok. No pain, no gain, and I love it. So again, thanks a lot! PS: Anyway, now I am intrigued to where I could go on this path. :)2012-12-19
  • 0
    @Kolmin: You’re welcome. And if you’re just starting and working on your own, I’d say that you’re doing tolerably well.2012-12-19
  • 0
    The problem with the base case is easily resolved, you could start with $n=1$ where the order is total and your poset is a chain. (As long as you do not need in your induction step, that the width is at least $3$).2012-12-19
  • 0
    @martin: Which simply postpones the difficulty. Dealing successfully with the width $2$ case may well open the door to the general case.2012-12-19