Day 03Part 08-Discrete mathematics for gate- Concept of Least upper bound and greatest lower bound.

Day 03Part 08-Discrete mathematics for gate- Concept of Least upper bound and greatest lower bound.

Least Upper Bound (LUB) and Greatest Lower Bound (GLB) – Discrete Mathematics (GATE)

The concepts of Least Upper Bound (LUB) and Greatest Lower Bound (GLB) are essential in partially ordered sets (posets) in Discrete Mathematics. These are also known as Supremum (sup) and Infimum (inf), respectively.

1. Partial Order & Lattice Basics

A poset (Partially Ordered Set) is a set $S$ with a relation $\le$ that satisfies:
Reflexivity: $a\le a$
Antisymmetry: If $a\le b$ and $b\le a$, then $a=b$.
Transitivity: If $a\le b$ and $b\le c$, then $a\le c$.

If every pair of elements in $S$ has a Least Upper Bound (LUB) and Greatest Lower Bound (GLB), then $S$ forms a lattice.

2. Least Upper Bound (LUB) / Supremum (sup)

The Least Upper Bound (LUB) of a subset $A$ of a poset $(S,\le )$ is the smallest element in $S$ that is greater than or equal to all elements of $A$.

Mathematically, an element $u$ is LUB (sup) of $A$ if:

1. $u$ is an upper bound of $A$ ($\forall a\in A,a\le u$).
2. $u$ is the smallest such element, meaning if $v$ is another upper bound, then $u\le v$.

Example:
Consider $A=\{2,4,5\}$ in the poset $(S,\le )$ where $S=\{1,2,3,4,5,6\}$.
✔ Upper bounds of $A$ in $S$: {5, 6}
✔ Least Upper Bound (LUB): 5 (because it is the smallest upper bound)

3. Greatest Lower Bound (GLB) / Infimum (inf)

The Greatest Lower Bound (GLB) of a subset $A$ of a poset $(S,\le )$ is the largest element in $S$ that is less than or equal to all elements of $A$.

Mathematically, an element $g$ is GLB (inf) of $A$ if:

1. $g$ is a lower bound of $A$ ($\forall a\in A,g\le a$).
2. $g$ is the largest such element, meaning if $h$ is another lower bound, then $h\le g$.

Example:
Consider $A=\{2,4,5\}$ in the poset $(S,\le )$ where $S=\{1,2,3,4,5,6\}$.
Lower bounds of $A$ in $S$: {1, 2}
Greatest Lower Bound (GLB): 2 (because it is the largest lower bound)

4. Graphical Representation in Hasse Diagram

In a Hasse Diagram,

• The LUB of a subset is the lowest common ancestor in the diagram.
• The GLB is the highest common descendant.

Example Hasse Diagram for Divisibility Ordering on {1, 2, 3, 6}

✔ LUB of {2, 3} is 6 (smallest number divisible by both).
✔ GLB of {2, 3} is 1 (largest number dividing both).

5. Special Cases

 If LUB exists and belongs to $A$, it is called the maximum of $A$.
 If GLB exists and belongs to $A$, it is called the minimum of $A$.
 If every subset has an LUB and a GLB, the poset is called a complete lattice.

6. Application in GATE Questions

Question 1 (GATE 2025)

Let $A=\{4,8,12\}$ in the poset $(S,\le )$ where $S=\{1,2,4,6,8,12\}$ and $\le$ is the divisibility relation.
Find LUB and GLB of $A$.

Solution:
✔ Upper bounds of {4, 8, 12} in $S$: {12}
✔ Least Upper Bound (LUB): 12
✔ Lower bounds of {4, 8, 12} in $S$: {1, 2, 4}
✔ Greatest Lower Bound (GLB): 4

7. Summary Table

8. Conclusion

LUB is the smallest element that is greater than or equal to all elements in the subset.
GLB is the largest element that is less than or equal to all elements in the subset.
 These concepts are widely used in Lattice Theory and Poset Analysis in GATE.

Would you like more GATE practice problems on this topic?

Day 03Part 08-Discrete mathematics for gate- Concept of Least upper bound and greatest lower bound.

8 Ordered Set, Least Upper Bound, Greatest Lower …

11 Ordered set, least upper bound, greatest lower …