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.

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.