Well-Ordering Principle
Every nonempty set of positive integers has a least element.
Key idea
Every nonempty set of positive integers has a least element.
In depth
Every non-empty set of positive integers has a least element. It is equivalent to induction and underpins proofs by minimal counterexample: if a statement fails, there is a smallest failing case, leading to a contradiction.
Worked example
To prove every integer > 1 has a prime factor, take the smallest divisor > 1 of n; it must be prime.
Real-world uses
- Justifying that a shortest route or smallest counterexample exists in algorithm proofs
Common mistake
Applying it to sets that are not bounded below, like integers or positive reals.
How to learn this
- Read the key idea and say it in your own words.
- Work through the worked example, then try a similar problem.
- Use the interactive lesson’s visual and mini-quiz to check the pattern.
Frequently asked questions
What is Well-Ordering Principle?
Every nonempty set of positive integers has a least element. It is a topic at the expert level in Discrete Math & Number Theory.
Where is Well-Ordering Principle used in real life?
Real-world examples: Justifying that a shortest route or smallest counterexample exists in algorithm proofs.
What should I learn before Well-Ordering Principle?
Make sure you are comfortable with Strong Induction, the previous topic in Discrete Math & Number Theory.
What is a common mistake with Well-Ordering Principle?
Applying it to sets that are not bounded below, like integers or positive reals.
How can I practise Well-Ordering Principle?
Open the interactive lesson, play with the visual, then answer the three-question mini-quiz. Getting two right marks the topic complete.
What comes after Well-Ordering Principle?
Move on to Sets and Elements next.
Related expert topics in Discrete Math & Number Theory
- Strong Induction – Assume all earlier cases to prove the next.
- Partial Orders – Reflexive, antisymmetric, transitive relations.
- Cardinality of Sets – Comparing sizes of infinite sets.
- Countable and Uncountable Sets – ℕ and ℚ are countable; ℝ is not.
- Cantor’s Diagonal Argument – Proof that real numbers are uncountable.
- Combinations with Repetition – Stars and bars.