POSETs, Hasse Diagrams, Lattices & Boolean Algebras
“Partial orders, topological sorting, LUB/GLB existence, distributive and complemented lattices, and Boolean algebras.”
1.Partially Ordered Sets & Hasse Diagrams
§ 2.1.A relation R on set S is a Partial Order if it is Reflexive, Anti-Symmetric, and Transitive. The pair (S, R) is called a POSET.
Hasse Diagrams:
A visual drawing of a finite POSET where:
1. All reflexive loops (x, x) are omitted.
2. All transitive edges (if x <= y and y <= z, omit (x, z)) are omitted.
3. Edge arrows are replaced by vertical orientation: if x < y, y is drawn above x and connected by an edge.
2.The Lattice Hierarchy to Boolean Algebra
§ 2.2.1. Lattice: A POSET (L, <=) where every pair of elements {a, b} has a unique Least Upper Bound (LUB / Join a lor b) and a unique Greatest Lower Bound (GLB / Meet a land b).
2. Bounded Lattice: Has a global universal lower bound 0 and global universal upper bound 1.
3. Distributive Lattice: Meet distributes over join, and join distributes over meet. (Non-distributive lattices always contain sublattices isomorphic to the pentagon N_5 or diamond M_3).
4. Complemented Lattice: In a bounded lattice, every element a has a complement a' such that a lor a' = 1 and a land a' = 0.
5. Boolean Algebra: A lattice that is simultaneously Bounded, Distributive, and Complemented. In a Boolean algebra, the complement of every element is strictly unique.
3. Worked Problem: Testing Divisibility Lattices for Complements
D_n is a Boolean algebra if and only if n has no repeated prime factors (square-free).
Problem: Consider the divisibility relation on D_36 = {1, 2, 3, 4, 6, 9, 12, 18, 36}. Determine whether (D_36, |) is a lattice, and whether it forms a Boolean algebra.
Step 1: Determine whether D_36 is a lattice:
For any a, b in D_36:
LUB(a, b) = lcm(a, b), and GLB(a, b) = gcd(a, b).
Since gcd and lcm are unique positive integers and both divide 36 for any divisors of 36, every pair has a unique LUB and GLB.
Therefore, (D_36, |) is a valid LATTICE. Lower bound 0 = 1, Upper bound 1 = 36.
Step 2: Test for complementation:
In a complemented lattice, for every element a, there exists b such that:
gcd(a, b) = 1 (meet is 1), and lcm(a, b) = 36 (join is 36).
Step 3: Test element a = 6:
We require gcd(6, b) = 1 and lcm(6, b) = 36.
If gcd(6, b) = 1, then b cannot be divisible by 2 or 3.
The only divisors of 36 not divisible by 2 or 3 is {1}.
However, lcm(6, 1) = 6 != 36.
No element in D_36 satisfies the condition for a = 6. Hence, 6 has NO COMPLEMENT!
Final Conclusion: (D_36, |) is a distributive lattice, but it is NOT a complemented lattice, and therefore NOT a Boolean algebra.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
GATE-focused discrete maths with formula-sheet style rapid coverage.
All relation/function counting formulas in exam-pattern format.
University-level rigour with engaging visual proofs.