Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 $/$. –  martin.koeberl Dec 19 '12 at 10:13
    
Continuing: You should remove not only $x_j$ but all elements comparable with it in order to decrease the width by $1$. –  martin.koeberl Dec 19 '12 at 10:15
    
Thanks a lot. I hate typos. I will edit immediately. –  Kolmin Dec 19 '12 at 10:16
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$. –  martin.koeberl Dec 19 '12 at 10:26
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. –  Thomas Andrews Dec 19 '12 at 14:07

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Ok, that's bad (at least for me). :) –  Kolmin Dec 19 '12 at 10:26
    
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. –  Kolmin Dec 19 '12 at 10:27
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.) –  Brian M. Scott Dec 19 '12 at 10:31
    
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. :) –  Kolmin Dec 19 '12 at 10:40
    
@Kolmin: You’re welcome. And if you’re just starting and working on your own, I’d say that you’re doing tolerably well. –  Brian M. Scott Dec 19 '12 at 10:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.