Well-Ordered Set — Definition, Formula & Examples

A well-ordered set is an ordered set in which every non-empty subset contains a smallest (least) element. The natural numbers under the usual ordering are the most familiar example.

A set $S$ equipped with a total order $\leq$ is well-ordered if for every non-empty subset $A \subseteq S$ , there exists an element $a_0 \in A$ such that $a_0 \leq a$ for all $a \in A$ .

How It Works

To check whether an ordered set is well-ordered, you must verify that no matter which non-empty subset you pick, that subset has a least element. This rules out infinite descending chains: you can never have

a_1 > a_2 > a_3 > \cdots

without end. Every well-ordered set is automatically totally ordered, meaning any two elements are comparable. The Well-Ordering Theorem (equivalent to the Axiom of Choice) states that every set can be well-ordered, though the ordering may not be the "natural" one you expect.

Example

Problem: Determine whether the set of integers

\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, \ldots\}

under the usual ordering

\leq

is well-ordered.

Step 1: Identify a non-empty subset and check for a least element. Consider the subset of all negative integers:

A = \{-1, -2, -3, \ldots\}

Step 2: Ask: does

A

have a least element? For any

n \in A

, the integer

n - 1

is also in

A

and satisfies

n - 1 < n

. So no element of

A

is less than or equal to every other element.

Step 3: Since we found a non-empty subset with no least element, the condition fails.

Answer:

\mathbb{Z}

under the usual ordering is not well-ordered. In contrast, the natural numbers

\mathbb{N} = \{0, 1, 2, \ldots\}

under

\leq

are well-ordered because every non-empty subset of

\mathbb{N}

has a minimum.

Why It Matters

Well-ordering is the foundation for transfinite induction and ordinal arithmetic, which appear throughout set theory, logic, and abstract algebra. It also underlies the principle of strong induction on the natural numbers, which you use constantly in proof-based courses. The Well-Ordering Theorem's equivalence to the Axiom of Choice makes it central to modern foundations of mathematics.

Common Mistakes

Mistake: Confusing a totally ordered set with a well-ordered set.

Correction: Every well-ordered set is totally ordered, but not every totally ordered set is well-ordered. The rationals

\mathbb{Q}

and integers

\mathbb{Z}

are totally ordered under

\leq

but not well-ordered, because they contain non-empty subsets with no least element.