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 \(\mathbb N\), also called in this context.well-ordered set is
Every well-ordered set is isomorphic to a unique , 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
\(\mathbb N\), this is called .works on any well-ordered set. On well-ordered sets longer than
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\).
- Totally ordered set
A set where all the elements can be compared as greater than or less than.