1. Limited time only! Sign up for a free 30min personal 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!

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


    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


    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