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
New model helps explain how provisions promote or reduce wildlife disease
Stress can make hard-working mongooses less likely to help in the future
Grammatical habits in written English reveal linguistic features of non-native speakers' languages
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