Hasse Diagram, Greatest and Least Elements: Upper and Lower Bounds with Worked Examples

Build one divisibility Hasse diagram, then use it to distinguish greatest from maximal and calculate bounds, LUB, and GLB step by step.

KnowledgeGate Team

Exam prep & CS education

Updated 14 Nov 20266 min read
Hasse Diagram, Greatest and Least Elements: Upper and Lower Bounds with Worked Examples

A partially ordered set can produce a diagram that looks simple, yet two confusions cause wrong answers: a greatest element gets mistaken for any maximal element, and a bound for a subset gets treated as if it must be inside that subset. A lattice test asks whether every pair has a LUB and GLB; Lattices and Hasse Diagrams for GATE develops that pairwise test with the divisors of 30. Greatest and least elements are global endpoints, while upper and lower bounds depend on a chosen subset. Trace upward and downward through the six elements below.

Read a Hasse diagram from the order relation

A partially ordered set, or poset, is a set equipped with a reflexive, antisymmetric, and transitive relation. For our running example, the relation is divisibility: write x ≤ₚ y when x divides y. Height in the Hasse diagram represents this order. It does not represent numerical size by itself.

The key idea is a cover. An element y covers x when x <ₚ y and there is no element z in the poset for which x <ₚ z <ₚ y.

A Hasse diagram therefore removes three kinds of clutter:

  • self-loops are omitted;

  • arrowheads are omitted because upward already means larger in the order;

  • edges implied by a transitive path are omitted.

For example, 2 divides 12, but they are not joined directly when 4 or 6 lies between them.

Build the running Hasse diagram step by step

Take P = {1, 2, 3, 4, 6, 12}, ordered by divisibility. First list every proper comparable pair:

(1,2), (1,3), (1,4), (1,6), (1,12), (2,4), (2,6), (2,12), (3,6), (3,12), (4,12), (6,12).

Each pair says its first element divides its second, not that an edge must be drawn. A direct edge survives only if no third element creates a longer chain between the endpoints. This is the transitive-reduction test applied pair by pair.

Now perform the transitive reduction. Remove (1,4) because the path 1 <ₚ 2 <ₚ 4 already shows it. Remove (1,6) because either 1 <ₚ 2 <ₚ 6 or 1 <ₚ 3 <ₚ 6 shows it. Remove (1,12), (2,12), and (3,12) for the same reason: each has an intermediate element in P.

The exact cover edges left are 1-2, 1-3, 2-4, 2-6, 3-6, 4-12, and 6-12. Arrange the levels as bottom {1}, then {2,3}, then {4,6}, and top {12}.

Hasse diagram of the divisors 1, 2, 3, 4, 6 and 12, with 1 at the bottom, 2 and 3 above it, then 4 and 6, and 12 at the top.

Lines should not cross merely for decoration, although a crossing is acceptable when the layout makes it unavoidable. Adjacency must follow those seven cover edges, not visual proximity.

Greatest and least are not the same as maximal and minimal

In P, 1 divides every element, so 1 is the least element. Every element divides 12, so 12 is the greatest element. Consequently, 1 is also the only minimal element, and 12 is the only maximal element.

Minimal means nothing is strictly below; least means below everything. Maximal and greatest use the matching conditions above.

Now remove 12 and consider R = {1,2,3,4,6}. The element 1 is still least. However, 4 and 6 are both maximal because neither has a strictly greater element in R. Neither is greatest: 4 does not divide 6, and 6 does not divide 4. Thus R has two maximal elements but no greatest element.

For the opposite contrast, take Q = {2,3,4,6,12}. Here 12 is greatest, while 2 and 3 are both minimal. There is no least element because 2 does not divide 3 and 3 does not divide 2. Greatest and least elements, when they exist, are unique. Maximal and minimal elements can be several.

Compute upper bounds, lower bounds, LUB, and GLB

An upper bound of a subset is an element of P above every member. A lower bound is below every member. The LUB is the least of all upper bounds; the GLB is the greatest of all lower bounds.

Stay inside P and choose A = {4,6}. The elements at or above 4 are {4,12}. Those at or above 6 are {6,12}. Their intersection is {12}, so:

UB(A) = {4,12} ∩ {6,12} = {12}, and therefore lub(A) = 12.

Now trace downward. The elements at or below 4 are {1,2,4}, while those at or below 6 are {1,2,3,6}. Their intersection gives:

LB(A) = {1,2,4} ∩ {1,2,3,6} = {1,2}.

Because 1 divides 2, the greatest member of this lower-bound set is 2. Hence glb(A) = 2.

Repeat the process for B = {2,3}. Common upper elements are {6,12}, so UB(B) = {6,12} and lub(B) = 6. The only common lower element is 1, so LB(B) = {1} and glb(B) = 1.

The same divisibility diagram with 4 and 6 shaded, 12 labelled UB(A) = {12}, LUB = 12, and 2 circled as LB(A) = {1,2}, GLB = 2.

A bound must belong to the ambient poset P, but it need not belong to the chosen subset.

Use one mechanical method on any diagram

Apply this four-step scan whenever a subset is marked:

  1. Mark every element of the subset.

  2. Trace upward from each marked element and intersect the reached sets. These common elements are the upper bounds.

  3. Trace downward and intersect again. These common elements are the lower bounds.

  4. Among the common upper elements, choose the least one for the LUB. Among the common lower elements, choose the greatest one for the GLB.

Here, "least" and "greatest" refer to the relation, not the smallest numeral or the vertical position in a careless sketch. Compare candidates using the order.

In R = {1,2,3,4,6}, the subset {4,6} has no upper bound. The common multiple 12 is absent, and no remaining element is divisible by both. Its lower-bound set is still {1,2}, with glb({4,6}) = 2.

Check your understanding with three exam-style mini problems

Each answer follows the same reachability intersections used above.

Check 1: In P, find the bounds of C = {2,4}. Elements above 2 are {2,4,6,12}, and elements above 4 are {4,12}. Their intersection is UB(C) = {4,12}, so lub(C) = 4. The downward sets are {1,2} and {1,2,4}. Thus LB(C) = {1,2} and glb(C) = 2.

Check 2: List all extremal elements of R. The least and only minimal element is 1. The maximal elements are {4,6}. Since neither divides the other, there is no greatest element.

Check 3: Can a greatest element coexist with no least element? Yes. In Q, 12 is greatest, 2 and 3 are minimal, and neither minimal element lies below the other. Therefore no least element exists.

Avoid the traps that make a correct diagram produce a wrong answer

  • Trap: Select one maximal element and call it greatest. Correction: Check whether it is above every element.

  • Trap: Require a lower bound to be inside the subset. Correction: Search the whole ambient poset.

  • Trap: Draw every comparable pair. Correction: Draw only cover edges.

  • Trap: Reverse divisibility because the larger numeral is above. Correction: Follow the relation: upward means "is divisible by" here.

Two quick checks expose common errors. The edge 2-12 must not appear because 2 <ₚ 4 <ₚ 12 and also 2 <ₚ 6 <ₚ 12. Also, 1 is a lower bound of {4,6}, but it is not the greatest lower bound because 1 <ₚ 2.

Practice may ask you to choose a valid diagram, list minimal or maximal elements, find bounds of a marked subset, or test whether LUB and GLB exist. Use Discrete Mathematics Set Theory and Relations MCQs to practise these distinctions.

Remember the short version and choose the next step

Reduce the relation to cover edges. Check a candidate against the whole poset before calling it greatest or least. Intersect upward reachability for upper bounds and downward reachability for lower bounds. Then select a least upper bound or greatest lower bound only when that element exists.

For a broader Computer Science foundation, explore ZERO TO HERO. For structured GATE planning and practice guidance, use GATE Guidance by Sanchit Sir. You can also browse the GATE courses and choose the route that fits your next stage.