Prove Lattice Has Finite Nonempty Subsets w/ GLB & LUB

  • Thread starter sarahr
  • Start date
  • Tags
    Algebra
In summary, the conversation discusses proving that in a lattice, every finite nonempty subset has a least upper bound and a greatest lower bound. The individual proposes using induction to prove this, starting with the base case of n=2. They also mention that for the case of n+1, there are 2^(n+1)-1 subsets and that the majority of these will already have a glb and a lub, but they are unsure of how many more subsets need to be considered. Another person suggests proving it for any lattice, finite or infinite, by using induction on the size of the subset.
  • #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. :bugeye: 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?
 
Physics news on Phys.org
  • #2
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?
 
  • #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.

?
 
  • #4
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.
 

1. What is a lattice?

A lattice is a mathematical structure consisting of a partially ordered set in which every two elements have a greatest lower bound (GLB) and a least upper bound (LUB).

2. What does it mean for a lattice to have finite nonempty subsets?

This means that there are subsets of the lattice that contain a finite number of elements and are not empty. In other words, there are finite collections of elements in the lattice that have a GLB and LUB.

3. How do you prove that a lattice has finite nonempty subsets with a GLB and LUB?

To prove this, you would need to show that for any finite subset of the lattice, there exists a GLB and a LUB for that subset. This can be done by using mathematical induction or by directly showing the existence of a GLB and LUB for any finite subset.

4. Can you give an example of a lattice with finite nonempty subsets and a GLB and LUB?

One example of a lattice with finite nonempty subsets and a GLB and LUB is the set of positive integers (1, 2, 3, ...), with the ordering defined as "less than or equal to". Any finite subset of this lattice will have a GLB (the smallest number in the subset) and a LUB (the largest number in the subset).

5. Why is it important for a lattice to have finite nonempty subsets with a GLB and LUB?

This property is important because it allows us to make certain mathematical statements and proofs about the lattice, such as the existence of supremums and infimums, which are useful in many areas of mathematics and science.

Similar threads

  • Calculus and Beyond Homework Help
Replies
20
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
457
  • Calculus and Beyond Homework Help
Replies
4
Views
461
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
675
  • Calculus and Beyond Homework Help
Replies
2
Views
824
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
7
Views
339
  • Calculus and Beyond Homework Help
Replies
1
Views
624
Back
Top