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 [infinity infinite] well-ordered set is [45h $\mathbb N$], also called [ordinal_omega $\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$.

%%hidden(Show proof): 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$. %%