Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A proof of Dilworth Theorem? - Looking for feedbacks

  1. Dec 17, 2012 #1
    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! :smile:
     
  2. jcsd
  3. Dec 17, 2012 #2
    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.
     
  4. Jan 1, 2013 #3
    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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: A proof of Dilworth Theorem? - Looking for feedbacks
Loading...