Register to reply

A proof of Dilworth Theorem? - Looking for feedbacks

by Kolmin
Tags: dilworth, feedbacks, proof, theorem
Share this thread:
Kolmin
#1
Dec17-12, 05:24 AM
P: 67
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!
Phys.Org News Partner Science news on Phys.org
FIXD tells car drivers via smartphone what is wrong
Team pioneers strategy for creating new materials
Team defines new biodiversity metric
Kolmin
#2
Dec17-12, 05:28 AM
P: 67
Quote Quote by Kolmin View Post
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.
bpet
#3
Jan1-13, 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 mean-value theorem Calculus & Beyond Homework 1
Proof of the mean value theorem Calculus & Beyond Homework 9