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

Homework Help: Algebra: lattices

  1. Jan 15, 2007 #1
    1. The problem statement, all variables and given/known data

    "Prove that in a lattice (L, <=) every finite nonempty subset S has a least upper bound and a greatest lower bound"

    2. Relevant equations



    3. The attempt at a solution

    I'm going to try and prove this by induction.
    For the initial case, show its true for n=2.
    So take a lattice with 2 elts: call the elements a and b.

    So then the subsets would be {a,b}, {a}, and {b} (since we don't have to deal with the nonempty). All three of these have a glb and a lub.

    now assume for n. now we want to show it's true for n + 1:

    this is the part im unsure about. i know its simple, but-

    if it's true for n, then we just want to go once step further for n+1.
    for n there are 2^n total subsets, but we are concerned about the nonempty set, so we have 2^n - 1 subsets. and all of these subsets have a glb and a lub (by assumption.)

    now when we try to show this for n+1:
    we have a total of 2^(n + 1) total subsets, then subtract of one for the nonempty: 2^(n + 1) - 1. the majority of these subsets overlap with the ones above in the assumption case of n, so for all of these we get for free that they have a lub and a glb. :bugeye: now, im not putting my finger on how many more subsets i have here in this case, and how to show that these indeed have a lub and a glb.

    any suggestions?
     
  2. jcsd
  3. Jan 16, 2007 #2

    HallsofIvy

    User Avatar
    Science Advisor

    If [itex]\alpha[/itex] is the lowerbound of set A and B= A union {x}, what are the two possibilities for the lowerbound of B?
     
  4. Jan 16, 2007 #3
    this is what I've got going right now:

    [the previous initial step found above]

    Assume it holds for all subsets of n elements, and let A = {X1, X2, ..., Xn+1}. By the induction hypothesis, {X1, X2, ..., Xn} has a lub. Call this lub L1. Since {X1, X2, ..., Xn} has a lub, then L1 union Xn+1 has a lub.

    Now, I want to claim that L1 union Xn+1 is the lub of A..but how can I justify that??

    And for glb, it would be the dual of the above.

    ?
     
  5. Jan 16, 2007 #4

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    You need to prove it for any lattice, finite or infinite. Do induction on |S|, the size of the subset of L. Clearly, if |S| = 1, then S has a lub and a glb. Suppose that for every subset of L with size n, it has a glb and an lub. Now let S be a subset of L with |S| = n+1. Finish the proof.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook