Day 03Part 12- Discrete mathematics – Examples based on lattice for finding lattice in faster speed

Day 03Part 12- Discrete mathematics – Examples based on lattice for finding lattice in faster speed

To efficiently determine whether a partially ordered set (poset) is a lattice, especially in the context of GATE or other competitive exams, you can follow a systematic approach. Here’s a step-by-step guide with examples to help you quickly assess lattice structures.

Quick Method to Identify a Lattice

A lattice is a poset in which every pair of elements has both:

• a least upper bound (LUB), also known as join

• a greatest lower bound (GLB), also known as meet

To verify if a poset is a lattice:XYQuadrat

1. List all pairs of elements in the poset.

2. For each pair, determine:

   • The LUB: the smallest element greater than or equal to both.

   • The GLB: the largest element less than or equal to both.

3. If both LUB and GLB exist for every pair, the poset is a lattice.

Example 1:

Set: $\{1,3,6,9,12\}$ with the relation “divides” (denoted as $|$).

Analysis:

• Pair (3, 6):

  • GLB: $\gcd (3,6)=3$

  • LUB: $\text{lcm}(3,6)=6$

• Pair (6, 9):

  • GLB: $\gcd (6,9)=3$

  • LUB: $\text{lcm}(6,9)=18$

  • However, 18 is not in the set.

Conclusion: Since the LUB for (6, 9) is not in the set, this poset is not a lattice.

Example 2:

Set: $\{1,2,4,8,16\}$ with the relation “divides” ($|$).

Analysis:

• For any pair, both $\gcd$ and $\text{lcm}$ are within the set.

Conclusion: This poset is a lattice.

Example 3:

Set: $\{1,2,3,4,6,12\}$ with the relation “divides” ($|$).

Analysis:

• Pair (3, 4):

  • GLB: $\gcd (3,4)=1$

  • LUB: $\text{lcm}(3,4)=12$

• All other pairs also have their $\gcd$ and $\text{lcm}$ within the set.

Conclusion: This poset is a lattice.

Tips for Faster Identification:

• Use Hasse Diagrams: Visual representations can help quickly identify LUBs and GLBs.

• Check for Completeness: Ensure that for every pair, both LUB and GLB exist within the set.

• Utilize Mathematical Properties: For numerical sets, leveraging $\gcd$ and $\text{lcm}$ can expedite the process.

Recommended Video Tutorials:

• Problems on Lattice – Poset and Lattice – Discrete Mathematics: This video covers various problems related to lattices and posets, providing clear explanations and examples.

• Check if a poset is a lattice: This tutorial demonstrates how to determine whether a given poset is a lattice, including checks for distributive lattices.

If you need further assistance with specific examples or concepts related to lattices, feel free to ask!