Register to reply 
A proof of Dilworth Theorem?  Looking for feedbacks 
Share this thread: 
#1
Dec1712, 05:24 AM

P: 67

It is the very first time I try such a long shot, attempting to prove a wellknown 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! 


#2
Dec1712, 05:28 AM

P: 67

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 ##Rincomparable##. 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 ##Rcomparable## 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 ##Rincomparable## 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 ##Rcomparable## 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. 


#3
Jan113, 08:24 PM

P: 523

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? 


Register to reply 
Related Discussions  
Transitive Relation over Set  Feedbacks on proofwriting skills  Precalculus Mathematics Homework  3  
Mean Value Theorem Proof  Topology and Analysis  3  
Role of mean value theorem in fundamental theorem of calculus proof  Calculus & Beyond Homework  5  
Proof using meanvalue theorem  Calculus & Beyond Homework  1  
Proof of the mean value theorem  Calculus & Beyond Homework  9 