A well-ordered set is a totally ordered set , such that for any nonempty subset there is some such that for every , ; that is, every nonempty subset of has a least element.
Any finite totally ordered set is well-ordered. The simplest infinite well-ordered set is , 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 is called a "well-ordering," despite the fact that "well" is usually an adverb.
Mathematical_induction works on any well-ordered set. On well-ordered sets longer than , this is called transfinite_induction.
Induction is a method of proving a statement for all elements of a well-ordered set . Instead of directly proving , you prove that if holds for all , then is true. This suffices to prove for all .
Let be the set of elements of for which doesn't hold, and suppose is nonempty. Since is well-ordered, has a least element . That means is true for all , which implies . So , which is a contradiction. Hence is empty, and holds on all of .