Course contentsShow
← Computer Science
Lesson 96 of 2,8722. Discrete Mathematics for CSFree lesson

Well-Ordering Principle

Understanding that every non-empty set of natural numbers has a least element, equivalent to induction.

Well-Ordering Principle

What You'll Learn

You'll discover a powerful axiom about natural numbers that guarantees every non-empty set has a smallest element—and see why it's logically equivalent to induction.

The Core Idea

The Well-Ordering Principle (WOP) states that every non-empty set of natural numbers contains a least element.

In plain English: if you gather any collection of natural numbers (0, 1, 2, 3, ...) that isn't empty, you can always find the smallest one. No exceptions.

Why This Matters

This seems obvious—"of course there's a smallest number!"—but it's a foundational truth we use to prove things. Here's the surprising part: WOP and mathematical induction are two sides of the same coin. You can prove induction using WOP, and you can prove WOP using induction.

How WOP Relates to Induction

Remember induction? You prove a base case, then show "if it's true for n, it's true for n+1."

WOP gives us another proof technique: suppose something is false for some natural numbers. Then by WOP, there's a smallest number where it fails. Often this leads to a contradiction because we can construct an even smaller counterexample, which is impossible.

An Analogy

Imagine sorting an unsorted pile of numbered cards (all positive integers). WOP guarantees you can always pick out the lowest-numbered card—even if the pile is infinite! You don't need to check every card; the smallest one must exist.

Why Both Principles Exist

Though equivalent, sometimes WOP makes a proof clearer than induction. If you're thinking "assume it fails somewhere—find the first failure," you're thinking with WOP.

Key Takeaway: The Well-Ordering Principle guarantees every non-empty set of natural numbers has a smallest element and provides an alternative proof method equivalent to induction.