Prove Lattice Has Finite Nonempty Subsets w/ GLB & LUB

[sarahr]

Homework Statement

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

Homework Equations

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 I am 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. now, I am 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?

 

[HallsofIvy]

If \alpha is the lowerbound of set A and B= A union {x}, what are the two possibilities for the lowerbound of B?

 

[sarahr]

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.

?

 

[AKG]

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.