Minimal does not mean least
Definition 2.3.1
(Partial order, minimal and least elements)
A partial order on a set is reflexive, antisymmetric and transitive. Two elements need not be comparable. For a subset of a partially ordered set, an element is
- minimal in if no distinct satisfies ;
- least in if for every .
Maximal and greatest elements are defined by reversing the inequalities.
Theorem 2.3.2
(A least element is minimal and unique)
If has a least element , then is minimal in , and is the only least element of .
Proof
(Antisymmetry forces equality)
Let satisfy . Since is least, also , so antisymmetry gives . Hence no distinct element lies below , and is minimal. If is another least element, then and , so .
A minimal element can fail to be least because it may be incomparable with another element.
Theorem 2.3.3
(Finite nonempty posets have a minimal element)
Every nonempty finite partially ordered set has a minimal element.
Proof
(A strictly descending walk must stop)
Start at any element . If is not minimal, choose with , and continue in the same way. By transitivity, whenever , and antisymmetry together with prevents any element from repeating: if with , then would force . In a finite set the walk must therefore stop, and it stops at a minimal element.
This is not a guarantee of a least element, and it fails for infinite sets: with its usual order has no minimal element.
Common mistake
(Reading a unique-looking bottom as a least element)
In a finite poset with several minimal elements, none of them is least. The statement "every finite nonempty poset has a minimal element" must not be strengthened to "has a least element". The divisibility order on has minimal elements and , and neither divides the other.
Building a total order without contradicting the original order
Definition 2.3.4
(Linear extension)
A linear extension of a partial order on is a total order on the same set such that implies for all .
Theorem 2.3.5
(Removing minimal elements gives a linear extension)
Let be a finite poset. Repeatedly remove a minimal element of what remains, and list the removed elements in order of removal. The resulting list is a linear extension of . Conversely, the first element of any linear extension is minimal.
Proof
(A larger element is never removed before a smaller one)
Suppose and . While remains in the set, is not minimal, because is a distinct element below it; so cannot be removed yet. Hence is removed before and appears earlier in the list. Each step is possible because every nonempty finite poset has a minimal element. For the converse, let be first in a linear extension. If some satisfied , then would have to precede , which is impossible. So is minimal.
Proof X-ray
Why minimality is the right test for the next element
The proof turns on one comparison: for a pair , the test "is minimal in what remains" blocks precisely because is still present. Nothing else is needed, so the procedure never has to look ahead or backtrack. Finiteness is used twice, to guarantee that a minimal element exists at every stage and that the process ends after steps. Antisymmetry is used in the existence of a minimal element, since without it a cycle could leave no minimal element at all. The converse shows the choice is not an artifact of the method: every linear extension starts with a minimal element, and removing it leaves a linear extension of the rest. Different admissible choices of minimal element produce different extensions, so the result is existence, not uniqueness.
The next examples apply both results to divisibility orders, where means .
Worked examples
Worked example 2.3.6
(Minimal and least in a divisibility order)
On , find all minimal and maximal elements and decide whether least and greatest elements exist.
Only and have no different divisor inside : each other member is divisible by at least one of them. Hence the minimal elements are . Neither is least, since and . Every member divides , so is greatest, and therefore maximal. No other element is maximal because it is a distinct divisor of . Thus is the unique maximal element and there is no least element.
Worked example 2.3.7
(Listing every linear extension)
Order by divisibility. List every linear extension and justify completeness.
Since divides every member, it must come first; since every member divides , it must come last. The remaining elements and are incomparable, so either may come first. Both lists and preserve all divisibility comparisons. These are the only possibilities, because the first and last positions are forced and there are only two orders for the middle pair.
Worked example 2.3.8
(An antichain has no comparisons to respect)
Let with only when . Every element is both minimal and maximal, and no element is least or greatest. The removal procedure may begin with any of the three elements, then any of the remaining two, then the last, so every one of the orderings of is a linear extension. This is the edge case in which the partial order imposes no constraint at all.
Counterexample mode
Minimal elements need not be unique, so no least element
Claim: a finite nonempty poset has a least element. Test it on ordered by divisibility. The element is minimal, since neither nor divides . The element is minimal for the same reason. If were least it would divide , which is false; if were least it would divide , which is false; and is not least because . So has no least element, although it is finite and nonempty. The repair is the weaker, true statement proved above: a minimal element exists, and a least element exists only when all elements lie above one common element.
Exercises
Quick check
(Is every least element minimal? Is every minimal element least?)
Use antisymmetry for one direction and the set under divisibility for the other.
Solution · Answer
Every least element is minimal, by antisymmetry. The converse is false: is minimal in under divisibility but does not divide , so it is not least.
Quick check
(Order by divisibility. How many linear extensions are there?)
Choose a minimal element first, then repeat on what remains. The relations are , , .
Solution · Answer
There are . The minimal elements are and . Starting with , the rest must keep before , giving , , . Starting with , the element must come next, since and both need first, and then either order of works: , . In total .
Quick check
(Why does with its usual order have a minimal element in every nonempty subset, while does not?)
Compare the subset with a nonempty subset of .
Solution · Answer
Every nonempty subset of has a least element by well-ordering, which is also minimal. The set itself has no minimal element, because for every integer the integer is strictly smaller. The finiteness argument of this unit does not apply to either set.