Well-ordered set

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\).

Let \(U = \{x \in S \mid \neg P(x) \}\) be the set of elements of \(S\) for which \(P\) doesn’t hold, and suppose \(U\) is nonempty. Since \(S\) is well-ordered, \(U\) has a least element \(x\). That means \(P(y)\) is true for all \(y < x\), which implies \(P(x)\). So \(x \not\in U\), which is a contradiction. Hence \(U\) is empty, and \(P\) holds on all of \(S\).