Day 03Part 11-Discrete Mathematics-Example on lattice How to find a hasse diagram is lattice or not

Day 03Part 11-Discrete Mathematics-Example on lattice How to find a hasse diagram is lattice or not

 Day 03 | Part 11 – Discrete Mathematics

 Example on Lattice: How to Check if a Hasse Diagram is a Lattice?

 What is a Hasse Diagram?

A Hasse diagram is a graphical representation of a partially ordered set (poset). It helps in visualizing relationships between elements.

Rules for drawing a Hasse diagram:

• Arrange elements in increasing order.
• Draw edges to connect directly related elements.
• Do not draw edges for indirect relations.

 How to Check if a Hasse Diagram is a Lattice?

A poset is a Lattice if every pair of elements has:

• A Least Upper Bound (LUB) → Join (∨)
• A Greatest Lower Bound (GLB) → Meet (∧)

Steps to Check:
Draw the Hasse Diagram of the given poset.
Pick any two elements and find their:

• LUB (Join ∨) → The smallest element greater than both.
• GLB (Meet ∧) → The largest element smaller than both.
  Check for all pairs – If every pair has both Join & Meet, it is a Lattice.

 Example: Check if the Following Poset Forms a Lattice

Consider the set S = {1, 2, 3, 6} under divisibility.
The Hasse diagram is:

Check Join (∨) and Meet (∧):

• Join (∨):

  • 2 ∨ 3 = 6 (smallest multiple)
  • 1 ∨ 2 = 2
  • 1 ∨ 3 = 3

• Meet (∧):

  • 2 ∧ 3 = 1 (largest divisor)
  • 2 ∧ 6 = 2
  • 3 ∧ 6 = 3

Conclusion: Every pair has a Join & Meet → It is a Lattice!

 Example: A Poset That is NOT a Lattice

Consider the set {a, b, c, d} with the following Hasse diagram:

Check Join (∨) and Meet (∧):

• Join (∨) of b and c?  (No single smallest element above both)
• Meet (∧) of a and d?  (Exists, d)

 Since b and c do not have a unique LUB (Join), this is NOT a Lattice!

 Key Takeaways

A poset is a Lattice if every two elements have a Join (∨) and a Meet (∧).
Use Hasse diagrams to check Join & Meet for all pairs.
If any pair lacks Join or Meet, the poset is NOT a Lattice.

Would you like more examples or step-by-step solved problems?

Day 03Part 11-Discrete Mathematics-Example on lattice How to find a hasse diagram is lattice or not