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$~$. %%