1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Discrete Math Poset's

  1. Nov 3, 2005 #1
    I have a question from hw, the question is stated "Show that if the poset (S,R) is a lattice then the dual poset (S,R^-1) is also a lattice"

    I know by Rosen theory that the dual of a Poset is also a poset but how can i prove that it is also a lattice, what def. am i missing. Any help would be greatly apprieciated.
     
  2. jcsd
  3. Nov 3, 2005 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    By using the fact (S, R) is a lattice, presumably.
     
  4. Nov 3, 2005 #3

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    I'm seeing all this stuff for the first time, so don't mind the detail. (S,R) is a lattice iff for each pair of elements {a,b} in S, there is an element of S denoted supR{a,b} satisfying:

    1) aRsupR{a,b}, bRsupR{a,b}
    2) if s in S satisfies aRs and bRs, then supR{a,b}Rs

    and an element of S denoted infR{a,b} satisfying:

    1) infR{a,b}Ra, infR{a,b}Rb
    2) if s in S satisfies sRa and sRb, then sRinfR{a,b}

    I assume that R-1 is defined by aR-1b iff bRa. If so, then we want to show that for every pair {a,b} contained in S, there is a supremum and infimum with respect to R-1. Let's go back to the supremum in (S,R), and rewrite the conditions. So:

    1) aRsupR{a,b}, bRsupR{a,b}
    2) if s in S satisfies aRs and bRs, then supR{a,b}Rs

    becomes

    1) supR{a,b}R-1a, supR{a,b}R-1b
    2) If s in S satisfies sR-1a and sR-1b, then sR-1supR{a,b}

    So supR{a,b} satisfies precisely the conditions required for it to be an infimum of {a,b} with respect to R-1. So if (S,R) is a lattice, then for every pair {a,b}, there is a supremum s and infimum i with respect to R. (S,R-1) is a lattice because for each {a,b} there is a supremum with respect to R-1, that being the infimum with respect to R, namely i, and there is an infimum with respect to R-1, that being the supremum with respect to R, namely s.

    A good way to think of this is to think of S being the power set of some set X, and R being inclusion [itex]\subseteq[/itex]. Then sup{a,b} = [itex]a \cup b[/itex] and inf{a,b} = [itex]a \cap b[/itex]. R-1 would be containment, [itex]\supseteq[/itex] and clearly you can see why when we switch the relation around, the intersection plays the role of the union, and the union plays the role of the intersection.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Discrete Math Poset's
  1. Discrete math (Replies: 3)

  2. Discrete Maths (Replies: 3)

  3. Discrete Math (Replies: 2)

  4. Discrete Math Question (Replies: 9)

  5. Discrete Math Question (Replies: 9)

Loading...