Lattices and Hasse Diagrams for GATE: Posets, LUB, GLB and the Lattice Test, Solved

"Is this poset a lattice?" becomes a clean scoring question once you can read a Hasse diagram and find the LUB and GLB of a pair. Students lose it by trusting the shape of the picture or checking only the easiest pairs. The reliable method is to reconstruct the order, then test the required bounds inside the given set.

Posets, Hasse diagrams and what the drawing hides

A partial order is a relation that is reflexive, antisymmetric and transitive, the three properties worked through in set theory and relations. A set equipped with such an order is a partially ordered set, or poset.

A Hasse diagram is a reduced drawing of that order. It follows three rules:

1. It omits every self-loop because reflexivity is understood.

2. It omits every edge implied by transitivity.

3. It places a larger element above a smaller one, so arrowheads are normally unnecessary.

Suppose a < b < c. The diagram shows the covering edges from a to b and from b to c, but not a direct edge from a to c. The relation a < c still holds by transitivity. Reading only drawn edges as relations, or adding every transitive relation as a covering edge, are both mistakes.

An element y covers x when x < y and no element lies strictly between them. Those cover relations, not the full relation, are what the lines encode.

LUB and GLB: join and meet

For two elements a and b, an upper bound is an element greater than or equal to both. Their least upper bound is the smallest of those common upper bounds, if one unique least element exists. It is also called the join and written a ∨ b.

A lower bound is less than or equal to both elements. The greatest lower bound is the largest common lower bound, if it exists uniquely. It is called the meet and written a ∧ b.

A poset is a lattice exactly when every pair of elements has both a join and a meet within the poset. It is not enough that common bounds exist. The common upper bounds need a least member, and the common lower bounds need a greatest member.

Worked example: divisors of 30

Take

D30 = {1, 2, 3, 5, 6, 10, 15, 30}

and order it by divisibility. In other words, x ≤ y means x divides y.

The Hasse diagram has four levels:

• Bottom: 1

• Next level: 2, 3, 5

• Next level: 6, 10, 15

• Top: 30

Its covering edges are:

• 1-2, 1-3, 1-5

• 2-6, 2-10

• 3-6, 3-15

• 5-10, 5-15

• 6-30, 10-30, 15-30

Check one edge and one omitted relation. The edge 2-6 is present because 2 divides 6 and there is no divisor of 30 strictly between them in this order. The relation 1 ≤ 6 is true, but the edge 1-6 is omitted because 2 and 3 lie on paths between them.

For a divisibility order, the operations are number-theoretic:

• LUB(a,b) = lcm(a,b)

• GLB(a,b) = gcd(a,b)

Now compute four bounds from the set itself rather than from the picture:

1. LUB(2,3) = lcm(2,3) = 6. The common multiples in D30 are 6 and 30, and 6 divides 30, so 6 is least.

2. GLB(6,10) = gcd(6,10) = 2. Their common divisors in D30 are 1 and 2, so 2 is greatest.

3. LUB(6,10) = lcm(6,10) = 30. No smaller element in the set is divisible by both 6 and 10.

4. GLB(2,3) = gcd(2,3) = 1.

Every divisor of 30 corresponds to a subset of the prime factors {2,3,5}. The gcd keeps the shared factors and the lcm takes their union, so both stay inside D30 for every pair. Therefore D30 is a lattice.

Since 30 = 2 × 3 × 5 is square-free, it has 2^3 = 8 divisors. This lattice is isomorphic to the Boolean lattice on three elements. It is both distributive and complemented.

Worked non-example: one bad pair is enough

Take the poset {a, b, c, d}. Put a and b at the bottom as incomparable elements. Put c and d at the top, also incomparable. Define all four cross relations:

a ≤ c, a ≤ d, b ≤ c, b ≤ d

Now test the pair {a,b}. Its upper bounds are c and d. Neither is below the other, so the two candidates are incomparable. There is no least upper bound.

Test the dual pair {c,d}. Its lower bounds are a and b, again incomparable. There is no greatest lower bound.

The failure of either operation for one pair is sufficient. This poset is not a lattice.

Bounded, complemented and distributive lattices: the GATE names

A bounded lattice has a least element, commonly written 0, and a greatest element, commonly written 1. These labels describe positions in the order, not necessarily the numbers zero and one.

A complemented lattice is bounded and gives each element a at least one complement b such that a ∨ b = 1 and a ∧ b = 0.

A distributive lattice satisfies both distributive laws, with meet distributing over join and join distributing over meet. D30 has both properties. Do not generalise that result to every finite lattice. The five-element diamond M3 and pentagon N5 are the standard non-distributive counterexamples. A lattice that is both distributive and complemented is a Boolean algebra, which is why D30 behaves exactly like the algebra of subsets of {2,3,5}. For the neighbouring algebraic structures, see group theory and algebraic structures.

Traps that decide the answer

• Do not draw reflexive loops or transitive edges as Hasse covering edges.

• A maximal element has nothing strictly above it. A greatest element is above every element. A poset may have several maximal elements but at most one greatest element.

• Check all pairs, or use a structural argument that covers all pairs, as gcd and lcm did for D30.

• Never import a bound from outside the given set. lcm(a,b) helps only when it belongs to the poset.

• A lattice need not be distributive or complemented.

How GATE tests lattices

Typical questions ask whether a pictured poset is a lattice, bounded, complemented or distributive. Others ask for a join, meet or complement, or ask you to count elements after recognising a Boolean lattice.

Work one of them. Is D12 = {1, 2, 3, 4, 6, 12} under divisibility a lattice, and is it complemented? It is a lattice, because the gcd and the lcm of any two divisors of 12 are again divisors of 12. It is not complemented. A complement of 2 would need gcd(2,b) = 1 and lcm(2,b) = 12. Only 1 and 3 are coprime to 2 inside the set, and their lcms with 2 are 2 and 6, never 12. The difference from D30 is that 12 = 2^2 × 3 is not square-free, so its divisors do not correspond to subsets of a prime set.

How much of the paper Discrete Mathematics carries moves between cycles, so read the current brochure on the organising IIT's GATE portal rather than an old syllabus.

The short version and next step

A lattice needs a unique LUB and GLB for every pair. Under divisibility these are lcm and gcd, and a single pair with no join or meet kills the lattice claim.

The Discrete Mathematics sequence in GATE Guidance by Sanchit Sir takes lattices in order with the rest of the syllabus, and the GATE category keeps the wider preparation path together. KnowledgeGate's question bank carries about 1,300 Discrete Mathematics questions, enough to run this lattice test on posets you have not seen before.