A well-ordered set is a totally ordered set , 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 $N$ , also called $ω$ 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 $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$ .

Show proof

Let $U = {x \in S ∣ \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 \notin U$ , which is a contradiction. Hence $U$ is empty, and $P$ holds on all of $S$ .

LESSWRONG
LW

LESSWRONG
LW

Well-ordered set

Induction on a well-ordered set