(adsbygoogle = window.adsbygoogle || []).push({}); 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. 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?

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Algebra: lattices

**Physics Forums | Science Articles, Homework Help, Discussion**