Partial orders and lattices

Objectives, prerequisites and conventions

Recognize a partial order, read its Hasse diagram, distinguish minimal from least elements, find bounds of a subset, and decide whether a finite poset is a lattice. Prerequisite: sets, functions and relation properties. This is an introductory lesson, not complete lattice theory; distributive, complemented and Boolean lattices need further study.

A relation's underlying set is part of the problem. We use finite nonempty sets in all worked examples. The notation a≼b describes an abstract ordering; it need not mean numerical a≤b. When divisibility is the order, a≼b means a divides b, written a|b.

1. A partial order is three properties together

A relation ≼ on A is a partial order when it is reflexive (a≼a), antisymmetric (a≼b and b≼a imply a=b), and transitive (a≼b and b≼c imply a≼c). The pair (A,≼) is a partially ordered set, or poset. Antisymmetry forbids a two-way ordering between distinct elements; it does not forbid diagonal pairs.

Two elements a and b are comparable if a≼b or b≼a. A total order is a partial order in which every pair is comparable. A partial order need not compare every pair. “Partial” does not mean incomplete data; the relation may be fully known while some elements remain incomparable.

Ordinary ≤ on integers is a total order. Inclusion ⊆ on a power set is a partial order: {a} and {b} are incomparable when a≠b. Divisibility on positive integers is a partial order; 2 and 3 are incomparable. We say positive integers because extending divisibility to all nonzero signed integers would make 2 and −2 divide each other without being equal, violating antisymmetry.

2. What a Hasse diagram omits

For a finite poset, b covers a when a≺b and there is no c strictly between them. Here a≺b means a≼b and a≠b. A Hasse diagram draws cover relations, conventionally with greater elements higher. It omits self-loops and edges already implied by transitivity. Restore those when interpreting the full order.

Consider the positive divisors of 12: D={1,2,3,4,6,12}, ordered by divisibility. A textual specification of its Hasse diagram is:

• Bottom: 1. Top: 12.
• Cover pairs from lower to higher: (1,2), (1,3), (2,4), (2,6), (3,6), (4,12), (6,12).

Although (1,12) is not a cover pair, 1≼12 is true: upward paths encode transitivity. A missing direct edge does not necessarily mean two elements are incomparable. In contrast, there is no upward path from 4 to 6 or from 6 to 4, so they are incomparable. Vertical position alone is not a relation; use the paths or the stated divisibility rule.

3. Minimal is not the same as least

An element m is minimal if no distinct element lies below it. It is least if it lies below every element. Similarly, M is maximal if no distinct element lies above it; it is greatest if every element lies below it.

There can be several minimal or maximal elements, but at most one least and at most one greatest element. To see uniqueness of a least element, if l and l′ were both least, then l≼l′ and l′≼l, so antisymmetry forces l=l′. A least element is minimal; the converse need not hold.

Worked example: A={2,3,6} with divisibility. Elements 2 and 3 are both minimal because neither has a distinct divisor in A. There is no least element: neither 2 divides 3 nor 3 divides 2. Element 6 is both maximal and greatest because every element of A divides 6. Do not invent a least element 1; it is outside A.

On all divisors D of 12, the least element is 1 and the greatest is 12. These conclusions depend on the underlying set, not on the relation's name alone.

4. Bounds belong to the ambient poset

Let S be a subset of a poset A. A lower bound l of S lies in A and satisfies l≼s for every s∈S. An upper bound u lies in A and satisfies s≼u for every s∈S. Bounds do not have to belong to S itself.

The greatest lower bound, or glb, is a lower bound above every other lower bound. The least upper bound, or lub, is an upper bound below every other upper bound. “Greatest lower” and “least upper” use the poset's order, not the numerical sizes of arbitrary labels. Whenever they exist, each is unique by antisymmetry.

For S={4,6} inside D, lower bounds are {1,2}; the glb is 2. Upper bounds are {12}; the lub is 12. Neither 2 nor 12 belongs to S, and that is allowed. A lower bound need not itself be the greatest one: 1 is a lower bound but not the glb.

Worked contrast: S={2,3} inside A={1,2,3} under divisibility. The glb is 1, but no upper bound exists in A. Although the integer 6 is a common multiple, it cannot be a bound in this poset because it is not an element of A.

5. A lattice must support every pair

A lattice is a poset in which every pair of elements has both a glb and a lub. The glb of a,b is called their meet, a∧b; the lub is their join, a∨b. These symbols resemble logical AND and OR, but here they denote operations in the specified poset.

One successful pair is not enough to prove a poset is a lattice. One pair lacking a meet or join is enough to disprove it. A poset need not be totally ordered to be a lattice. Conversely, a totally ordered set is a lattice: the smaller member of any pair is its meet and the larger is its join.

The divisors D of 12 form a lattice. For any two divisors, their gcd is their meet and their lcm is their join. Both are still divisors of 12. For 4 and 6, meet=2 and join=12. For 2 and 6, meet=2 and join=6 because the pair is comparable.

The poset {1,2,3} under divisibility is not a lattice: 2 and 3 have no join within the set. Do not apply the gcd/lcm shortcut to an arbitrary subset without checking membership and the bound definitions. The shortcut works directly for the complete set of positive divisors of one fixed positive integer.

6. Worked example: a power-set lattice

Let A={a,b}. Its power set is {∅,{a},{b},{a,b}}, ordered by inclusion. The cover pairs are ∅<{a}, ∅<{b}, {a}<{a,b}, {b}<{a,b}. The middle elements are incomparable, yet every pair has a meet and a join.

For any subsets X and Y of A, meet is X∩Y and join is X∪Y. Why? Every common lower bound must be contained in both sets, hence in their intersection. The intersection itself is a common lower bound, so it is the greatest. Dually, any common upper bound must contain both sets, hence their union; the union is the least such bound.

Thus {a}∧{b}=∅ and {a}∨{b}={a,b}. Here the least element is ∅ and the greatest is A. This example demonstrates that incomparable elements can still have a meet and a join; incomparability alone does not refute the lattice property.

7. A reliable finite-poset workflow

First fix the underlying set and order. If the relation is given as ordered pairs, check all required diagonal pairs, antisymmetry and transitivity before calling it a poset. If a valid Hasse diagram is supplied, restore reachability rather than treating only its drawn edges as the relation.

For minimal/maximal elements, ask whether any distinct element is below/above the candidate. For least/greatest, compare the candidate against every element. For bounds of S, filter all ambient elements with the required comparisons. Finally test which bound dominates the other lower bounds or is dominated by the other upper bounds.

To prove a finite poset is a lattice, test every unordered pair or give a general construction, as with intersection/union. Distinct pairs suffice for nontrivial checks because an element paired with itself has itself as both meet and join. Test the candidate against every upper bound, rather than relying on a picture alone. In a finite nonempty set of upper bounds, a genuinely unique minimal member is also the least member: every upper bound has some minimal upper bound below it, which must be that unique member.

Quick reference

• Poset: reflexive + antisymmetric + transitive.
• Total order: every pair also comparable.
• Hasse edges: covers, not every true ordered pair.
• Least ⇒ minimal; greatest ⇒ maximal; converses can fail.
• Bounds are elements of the ambient set, not necessarily the subset being bounded.
• Lattice: every pair has a meet and a join.
• In P(A) with inclusion: meet=intersection, join=union.

Original practice: six single-correct MCQs

Original questions, not previous-year questions. Choose exactly one option. All stated domains and operations matter.

C01. Which three properties define a partial order on a set?

A. Reflexive, antisymmetric and transitive B. Reflexive, symmetric and transitive C. Irreflexive, symmetric and transitive D. Reflexive, symmetric and nontransitive

Answer: A

A: These are exactly the partial-order requirements; total comparability is not required.

B: These define an equivalence relation, not the general partial-order condition.

C: A partial order is reflexive, not irreflexive, and requires antisymmetry.

D: A partial order requires transitivity and antisymmetry.

C02. In the divisibility poset D={1,2,3,4,6,12}, which statement about 1 and 12 is correct?

A. They are incomparable because no cover edge joins them. B. 1≼12 is true, but 12 does not cover 1. C. 12 covers 1 because 1 divides 12. D. 1≼12 is false because Hasse diagrams omit transitive pairs.

Answer: B

A: Comparability is determined by the full order or upward paths, not just direct cover edges.

B: 1 divides 12, but an intermediate element such as 2 satisfies 1≺2≺12, so this is not a cover.

C: Divisibility proves the ordering, but the intermediate elements rule out a cover.

D: Omitting a drawn edge does not delete the underlying transitive relation.

C03. For A={2,3,6} ordered by divisibility, what are the minimal elements and the least element?

A. Minimal {2}; least 2 B. Minimal {1}; least 1 C. Minimal {2,3}; no least element D. Minimal {6}; least 6

Answer: C

A: 3 is minimal too, and 2 does not divide 3, so 2 is not least.

B: 1 is not in the underlying set and cannot be one of its elements or bounds.

C: Neither 2 nor 3 has a distinct predecessor in A, and neither divides the other; no element is below them both.

D: 6 is greatest and maximal, not minimal, because 2 and 3 lie below it.

C04. In the lattice of all positive divisors of 12 under divisibility, what are the meet and join of 4 and 6, respectively?

A. 1, 12 B. 4, 6 C. 12, 2 D. 2, 12

Answer: D

A: 1 is a lower bound, but 2 is a larger common lower bound in this order.

B: 4 and 6 are incomparable; neither is a common bound of the required kind.

C: This exchanges meet and join: 12 is the upper bound and 2 the greatest lower bound.

D: The greatest common divisor is 2 and the least common multiple is 12; both belong to the divisor set.

C05. Why is {1,2,3}, ordered by divisibility, not a lattice?

A. Divisibility is not transitive on this set. B. 2 and 3 have no common upper bound inside the set. C. 2 and 3 have no lower bound inside the set. D. Every lattice must be a total order.

Answer: B

A: Divisibility remains transitive; the poset condition is not the problem.

B: Neither 1,2 nor 3 is divisible by both 2 and 3, so this pair has no join in the poset.

C: 1 is a common lower bound and is their meet.

D: Lattices can contain incomparable elements; the failure is the missing join, not incomparability itself.

C06. In P({a,b}) ordered by inclusion, what are the meet and join of {a} and {b}?

A. ∅ and {a,b} B. {a,b} and ∅ C. {a} and {b} D. Neither exists because {a} and {b} are incomparable

Answer: A

A: Meet is intersection and join is union: {a}∩{b}=∅ and {a}∪{b}={a,b}.

B: Intersection and union roles have been reversed.

C: Neither singleton is a common lower or upper bound for both singletons.

D: Incomparability does not prevent a meet and join; the ambient power set contains both.

Sources and scope

This original foundation lesson aligns with Discrete Mathematics in Section 1 of the official GATE 2027 CS syllabus. It is not full-topic or full-syllabus coverage. The syllabus confirms relevance; the NPTEL course is a primary institutional further-study reference. Examples and practice are original, not copied examination questions.

• Official GATE 2027 CS syllabus
• NPTEL: Discrete Mathematical Structures, IIT Madras

Sources checked 2026-10-14.