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

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
usatisfiesx <= uandy <= u. The least one is below every other common upper bound. It is the join,x ∨ y.A lower bound
lsatisfiesl <= xandl <= 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.

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 are6and12, and the least of them is6; the only common lower bound is1. Hence2 ∨ 3 = 6and2 ∧ 3 = 1, which shows that a join need not be the top element.For comparable
(2, 6),2 ∨ 6 = 6and2 ∧ 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.

Lattice laws and traps that change the answer
Law | Identity | Check in |
|---|---|---|
Idempotent |
|
|
Commutative |
|
|
Associative |
|
|
Absorption |
|
|
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 | They are incomparable, so no join exists. |
Numerical maximum used | Calls | Under divisibility, the join is |
Only cover pairs checked | Misses incomparable pairs | Test every pair. |
Result outside the set | Uses missing | 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:
Confirm that the relation is a partial order.
Draw only the cover edges.
Choose a pair, including incomparable pairs.
Find all common upper and lower bounds inside the poset.
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.
Keep learning
Lattice MCQs: 12 Solved Questions on Join, Meet and Hasse Diagrams
Solve 12 lattice questions from basic definitions to divisor posets, complements, sublattices and the distributive law. Each answer names the decisive pair or identity.
Wheel Graph in Discrete Mathematics: W6 Representation, Logic Encoding and Exam Patterns
Build one labelled W6 from its rim and spokes, then verify the same graph through degrees, a matrix, logical formulas, colouring and quick decisions.
Discrete Mathematics for GATE: A 6-Week Topic-by-Topic Study Plan
Build Discrete Mathematics in prerequisite order over six weeks. Each week combines concepts, worked problems, timed sets, and scheduled error repair.
Set Theory in Discrete Mathematics: Operations, Laws and Worked Examples
Build set theory from elements and subsets to algebra, inclusion-exclusion and Cartesian products, with every important result worked out step by step.





