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

https://www.gyanodhan.com/video/7B5.%20GATE%20CSEIT/Discrete%20Mathematics%202/493.%20Day%2003Part%2011-Discrete%20Mathematics-Example%20on%20lattice%20How%20to%20find%20a%20hasse%20diagram%20is%20lattice%20or%20not.mp4

 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

डिस्क्रीट मैथमेटिक्स में लैटिस (Lattice) एक विशेष प्रकार का आंशिक क्रमित समुच्चय (Poset) होता है, जिसमें प्रत्येक युग्म (pair) के लिए एक अद्वितीय Least Upper Bound (LUB) और Greatest Lower Bound (GLB) होता है। Hasse Diagram का उपयोग करके यह निर्धारित किया जा सकता है कि कोई Poset लैटिस है या नहीं।

---

Hasse Diagram से लैटिस की पहचान कैसे करें?

Hasse Diagram एक ग्राफिकल प्रतिनिधित्व है जो Poset के तत्वों और उनके आंशिक क्रम को दर्शाता है। इसमें तत्वों को बिंदुओं के रूप में और उनके आदेश संबंधों को रेखाओं के माध्यम से दर्शाया जाता है। Hasse Diagram की सहायता से हम निम्नलिखित चरणों का पालन करके यह निर्धारित कर सकते हैं कि कोई Poset लैटिस है या नहीं:

1. हर युग्म के लिए LUB और GLB की जांच करें:
   • Poset के प्रत्येक युग्म (a, b) के लिए यह जांचें कि क्या उनके पास एक अद्वितीय Least Upper Bound (LUB) और Greatest Lower Bound (GLB) है।
   • यदि किसी युग्म के लिए LUB या GLB मौजूद नहीं है, या अद्वितीय नहीं है, तो वह Poset लैटिस नहीं है।
2. Hasse Diagram में तत्वों की तुलना करें:
   • Hasse Diagram में देखें कि क्या प्रत्येक युग्म के लिए एक सामान्य ऊपरी और निचला तत्व मौजूद है।
   • यदि किसी युग्म के लिए ऐसा तत्व नहीं है, तो वह Poset लैटिस नहीं है।
3. उदाहरण के माध्यम से समझें:
   • उदाहरण के लिए, यदि हमारे पास संख्याओं का समुच्चय {1, 2, 3, 6} है और हम “a divides b” (a, b को विभाजित करता है) संबंध पर विचार करते हैं, तो यह एक लैटिस बनाता है क्योंकि हर युग्म के लिए LUB और GLB मौजूद होते हैं।

---

Hasse Diagram के उदाहरण

नीचे दिए गए वीडियो में Hasse Diagram के विभिन्न उदाहरणों के माध्यम से यह समझाया गया है कि कैसे यह निर्धारित किया जाए कि कोई Poset लैटिस है या नहीं:

CHECK WHETHER 15 HASSE DIAGRAMS ARE LATTICES OR …

---

यदि आप किसी विशेष Hasse Diagram या Poset के उदाहरण पर चर्चा करना चाहते हैं, तो कृपया विवरण प्रदान करें, ताकि हम उस पर विस्तार से चर्चा कर सकें।

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

Hasse Diagram 

Notes on Lattice Theory