Lattice in Discrete Mathematics: Definition, Formation, Join and Meet Worked Examples

Learn a reliable pair-by-pair method for testing a lattice. Build two divisor posets, calculate joins and meets, apply lattice laws, and spot a failed join.

KnowledgeGate Team

Exam prep & CS education

Updated 15 Nov 20266 min read
Lattice in Discrete Mathematics: Definition, Formation, Join and Meet Worked Examples

A Hasse diagram can look orderly and still fail to be a lattice. The usual confusion is that an upper bound is not necessarily the least upper bound. A repeatable pair-by-pair test determines whether a poset is a lattice and finds its join and meet. For the divisor set D12 = {1, 2, 3, 4, 6, 12}, the pair (4, 6) has join 12 and meet 2.

Lattice, join and meet: start from the order relation

A poset (P, <=) has a reflexive, antisymmetric and transitive relation. A lattice is a poset in which every pair x, y has both a unique least upper bound and a unique greatest lower bound. Use Lattices and Hasse Diagrams for GATE for the broader D30, bounded, complemented and distributive treatment. D12 is the operation-focused model: formation, exact bound sets and lattice identities stay tied to one six-element poset before the numeric failure case changes the set.

  • An upper bound u satisfies x <= u and y <= u. The least one is below every other common upper bound. It is the join, x ∨ y.

  • A lower bound l satisfies l <= x and l <= y. The greatest one is above every other common lower bound. It is the meet, x ∧ y.

Both results must belong to P, and least or greatest refers to the given order, not numerical size. Every pair must pass, including incomparable pairs. One failure disproves a lattice.

Form the Hasse diagram for the divisor poset D12

Take D12 = {1, 2, 3, 4, 6, 12}, with a <= b meaning a divides b. Divisibility is reflexive, antisymmetric on positive integers, and transitive because a | b and b | c imply a | c.

Hasse Diagram, Greatest and Least Elements derives the same D12 transitive reduction and distinguishes greatest from maximal elements. Starting from that construction, remove self-loops and transitive edges. Put 1 at the bottom, 2 and 3 on the next level, 4 and 6 above them, and 12 at the top. These seven covers then become the input for pairwise joins, meets and lattice laws.

1-2, 1-3, 2-4, 2-6, 3-6, 4-12, 6-12.

Omit 1-4, 1-6 and 1-12 because intermediate elements show them. Similarly, 2-12 runs through 4 or 6, and 3-12 through 6.

For each pair, list all common elements above and below it inside the set. Identify one least upper bound and one greatest lower bound. Repeat for every pair rather than judging by appearance.

Hasse diagram of the divisor lattice D12, with 4 and 6 marked, their meet 2 below them and their join 12 at the top.

Worked example: compute join and meet for exact pairs in D12

For (4, 6), the elements above 4 are {4, 12} and those above 6 are {6, 12}. The common-upper-bound set is {12}, so 4 ∨ 6 = 12.

Below 4 are {1, 2, 4}; below 6 are {1, 2, 3, 6}. The common-lower-bound set is {1, 2}, whose greatest element is 2. Thus 4 ∧ 6 = 2.

The pairs (2, 3) and (2, 6) illustrate the method:

  • For (2, 3), the common upper bounds are 6 and 12, and the least of them is 6; the only common lower bound is 1. Hence 2 ∨ 3 = 6 and 2 ∧ 3 = 1, which shows that a join need not be the top element.

  • For comparable (2, 6), 2 ∨ 6 = 6 and 2 ∧ 6 = 2.

Because D12 contains every positive divisor of 12, join is lcm(a,b) and meet is gcd(a,b), with both inside D12. Check: lcm(4,6)=12, gcd(4,6)=2, lcm(2,3)=6, gcd(2,3)=1.

A second lattice model and one numeric non-lattice counterexample

Consider the subset order on P({a,b,c}). For A={a,c} and B={b,c}:

  • A ∧ B = A intersection B = {c}.

  • A ∨ B = A union B = {a,b,c}.

Intersection is the greatest set below both; union is the least set above both. They are therefore the meet and join.

Now take divisibility on S = {1, 2, 3, 12, 18, 36}. For (2, 3), common upper bounds are {12, 18, 36}. The minimal ones, 12 and 18, are incomparable because neither divides the other. Thus 2 ∨ 3 does not exist in S. Its meet is 1, but one missing join makes S a non-lattice.

Here lcm(2,3)=6 is absent from S, and neither 12 nor 18 can replace it. The allowed set and its order decide the answer.

Two divisibility Hasse diagrams side by side: D12, where 4 and 6 have join 12 and meet 2, and S, where 2 and 3 have no least upper bound.

Lattice laws and traps that change the answer

Law

Identity

Check in D12

Idempotent

x ∨ x=x, x ∧ x=x

4 ∨ 4=4, 4 ∧ 4=4

Commutative

x ∨ y=y ∨ x, similarly for meet

4 ∨ 6=12=6 ∨ 4, 4 ∧ 6=2=6 ∧ 4

Associative

(x ∨ y) ∨ z=x ∨ (y ∨ z), similarly for meet

(2 ∨ 3) ∨ 4=12=2 ∨ (3 ∨ 4); meet gives 1 on both sides

Absorption

x ∨ (x ∧ y)=x, x ∧ (x ∨ y)=x

4 ∨ (4 ∧ 6)=4 ∨ 2=4, 4 ∧ (4 ∨ 6)=4 ∧ 12=4

Recover the order by x <= y exactly when x ∨ y=y, equivalently x ∧ y=x. For 2 <= 6, these checks give 2 ∨ 6=6 and 2 ∧ 6=2.

Error

Consequence

Correction

Minimal mistaken for least

Chooses 12 or 18 in S

They are incomparable, so no join exists.

Numerical maximum used

Calls 6 the join of 4,6

Under divisibility, the join is 12.

Only cover pairs checked

Misses incomparable pairs

Test every pair.

Result outside the set

Uses missing 6 in S

Results must belong to the poset.

Transitive lines drawn

Hides the covers

Remove edges represented by longer paths.

How exam-style questions test join, meet and lattice formation

Questions may ask you to read join and meet from a Hasse diagram, find a pair disproving a lattice, complete an operation table, or apply idempotence, commutativity, associativity or absorption. All use the same bound reasoning.

For a timed self-check, rebuild the seven D12 cover edges, recover 4 ∨ 6 and 4 ∧ 6, then explain why (2,3) has no join in S.

Solution

Edges: 1-2, 1-3, 2-4, 2-6, 3-6, 4-12, 6-12. Also, 4 ∨ 6=12 and 4 ∧ 6=2. In S, common upper bounds 12 and 18 are minimal but incomparable, so neither is least.

The short version and the next practice step

Use this five-action checklist:

  1. Confirm that the relation is a partial order.

  2. Draw only the cover edges.

  3. Choose a pair, including incomparable pairs.

  4. Find all common upper and lower bounds inside the poset.

  5. Require one least upper bound and one greatest lower bound for every pair.

For a structured GATE CS sequence, continue with GATE Guidance by Sanchit Sir. For a wider route, browse CS Fundamentals for Exams and Placements. Both are optional next steps after you can perform the test unaided.

Finally, delete 12 from D12 and examine (4,6). No remaining element is above both, so there is no common upper bound and no join. Justify this from the bound sets before redrawing the diagram.