- #1
sarahr
- 13
- 0
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?