Day 03Part 09-CseIt- Cross structure failure case of greatest lower bound and least upper bound.

Day 03Part 09-CseIt- Cross structure failure case of greatest lower bound and least upper bound.

https://www.gyanodhan.com/video/7B5.%20GATE%20CSEIT/Discrete%20Mathematics%202/495.%20Day%2003Part%2009-CseIt-%20Cross%20structure%20failure%20case%20of%20%20greatest%20lower%20bound%20and%20least%20upper%20bound.mp4

Day 03 Part 09 – CSE/IT: Cross Structure Failure Cases of Greatest Lower Bound (GLB) and Least Upper Bound (LUB)

---

Understanding GLB and LUB in Posets

In a partially ordered set (poset), for any two elements $a$ and $b$:

• Greatest Lower Bound (GLB): The largest element that is less than or equal to both $a$ and $b$.

• Least Upper Bound (LUB): The smallest element that is greater than or equal to both $a$ and $b$.

A lattice is a poset where every pair of elements has both a GLB and a LUB.

---

Cross Structure Failure Cases

Certain poset configurations, known as cross structures, fail to be lattices because some pairs of elements lack a GLB or LUB.Mathematics Stack Exchange

Example 1: Missing LUB

Consider the poset with elements $\{a,b,c\}$ and the following relations:

• $a$ and $b$ are incomparable.

• Both $a$ and $b$ are less than $c$.

Hasse Diagram:

Analysis:

• GLB of $a$ and $b$: Does not exist since $a$ and $b$ are incomparable and have no common lower bound.

• LUB of $a$ and $b$: Exists and is $c$.

Example 2: Missing GLB

Consider the poset with elements $\{a,b,d\}$ and the following relations:

• $a$ and $b$ are incomparable.

• Both $d$ is less than $a$ and $b$.

Hasse Diagram:

Analysis:

• GLB of $a$ and $b$: Exists and is $d$.

• LUB of $a$ and $b$: Does not exist since $a$ and $b$ are incomparable and have no common upper bound.focs.computer.org

---

Key Takeaways

• In cross structures, certain pairs of elements lack either a GLB or LUB, preventing the poset from being a lattice.

• Identifying these failure cases is crucial in discrete mathematics and computer science, especially in topics like compiler design and formal language theory.

---

If you need further clarification or additional examples on this topic, feel free to ask!

Day 03Part 09-CseIt- Cross structure failure case of greatest lower bound and least upper bound.