A well-ordered set is a totally ordered set \((S, \leq)\), such that for any nonempty subset \(U \subset S\) there is some \(x \in U\) such that for every \(y \in U\), \(x \leq y\); that is, every nonempty subset of \(S\) has a least element.

Any finite totally ordered set is well-ordered. The simplest infinite well-ordered set is \(\mathbb N\), also called \(\omega\) in this context.

Every well-ordered set is isomorphic to a unique ordinal number, and thus any two well-ordered sets are comparable.

The order \(\leq\) is called a “well-ordering,” despite the fact that “well” is usually an adverb.

Induction on a well-ordered set

mathematical induction works on any well-ordered set. On well-ordered sets longer than \(\mathbb N\), this is called transfinite induction.

Induction is a method of proving a statement \(P(x)\) for all elements \(x\) of a well-ordered set \(S\). Instead of directly proving \(P(x)\), you prove that if \(P(y)\) holds for all \(y < x\), then \(P(x)\) is true. This suffices to prove \(P(x)\) for all \(x \in S\).