Well-orderings & the least-element principle
A total order is a well-order if every non-empty subset has a least element. ℕ is the canonical example; ℤ and the non-negative rationals are not, since ℤ has no least element at all and {x ∈ ℚ : x > 0} has bounded but unattained infima. Well-ordering is equivalent to induction, and it is the engine behind minimal-counterexample proofs.
✓ Unlimited questions · marked criterion by criterion · no card needed
Method: how to approach it
The order below is what examiners expect to see, and each step carries its own marks.
- Check for a least element in every subsetTo refute, exhibit one non-empty subset with none — usually an infinite strictly decreasing sequence.
- Use minimal counterexamplesTo prove ∀n P(n), assume the set of counterexamples is non-empty, take its least element, and derive a contradiction.
- Derive a smaller counterexampleThe contradiction almost always comes from producing a counterexample below the least one, which is impossible.
- Note the equivalence with inductionWell-ordering of ℕ, weak induction and strong induction are interderivable, so use whichever makes the argument shortest.
Worked example
Use the well-ordering principle to prove every integer n ≥ 2 has a prime divisor.
- Suppose not, and let S be the set of integers ≥ 2 with no prime divisor. Assume S ≠ ∅.
- By well-ordering, S has a least element m.
- m is not prime (a prime divides itself), so m = ab with 1 < a < m.
- a ≥ 2 and a < m, so a ∉ S, meaning a has a prime divisor p. But p ∣ a and a ∣ m give p ∣ m — contradiction.
Answer. S must be empty, so every integer n ≥ 2 has a prime divisor.
Where marks get dropped
These are the specific errors that cost credit on well-orderings & the least-element principle questions — QED's rubric penalises each of them separately.
- Applying well-ordering to ℤ or ℝ. Neither is well-ordered under ≤, and the principle genuinely fails there.
- Forgetting to say the counterexample set is non-empty before taking its least element. The empty set has none, and that is the whole point.
- Not actually producing something smaller. The contradiction must contradict minimality.
Practise this until it is automatic
Unlimited fresh questions
QED generates new well-orderings & the least-element principle problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.
Marked like an examiner
Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.
Answer in real notation
A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.
Saved to your library
Every question you generate is kept and re-takeable as a timed exam, and your Orderings & Lattices mastery is tracked so you know when this is exam-ready.
Well-orderings & the least-element principle — frequently asked questions
Is the well-ordering principle the same as the well-ordering theorem?
No. The principle is the statement that ℕ is well-ordered. The theorem — that EVERY set can be well-ordered — is equivalent to the axiom of choice and far stronger.
How does it relate to induction?
They are equivalent over the usual axioms for ℕ. A minimal-counterexample proof can always be rewritten as strong induction and vice versa.
Can an infinite set be well-ordered?
Yes — ℕ is. What well-ordering forbids is an infinite strictly decreasing sequence, which is exactly why it justifies termination arguments.
The rest of Orderings & Lattices
Partial orders, Hasse diagrams, bounds, lattices. Each subtopic below has its own method, worked example and mark-losing traps.
- 1Partial vs total orders
- 2Hasse diagrams
- 3Minimal, maximal, least & greatest elements
- 4Upper & lower bounds, supremum & infimum
- 5Lattices: divisibility & subset orders
- 6Chains, antichains & comparability
- 7Topological sorting
- 8Well-orderings & the least-element principle
- 9Distributive & complemented lattices
- 10Product & lexicographic orders
- 11Dilworth’s theorem & chain covers
- 12Order isomorphism & comparing posets
- 13Scheduling with precedence constraints
Ready to make well-orderings & the least-element principle exam-proof?
Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.
Start practising free →