A well-ordered set is a totally ordered set $(S,\le )$, such that for any nonempty subset $U\subset S$ there is some $x\in U$ such that for every $y\in U$, $x\le 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 $\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 $\le$ 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\left(x\right)$ for all elements $x$ of a well-ordered set $S$. Instead of directly proving $P\left(x\right)$, you prove that if $P\left(y\right)$ holds for all $y<x$, then $P\left(x\right)$ is true. This suffices to prove $P\left(x\right)$ for all $x\in S$.