Well-ordered set

A well-or­dered set is a to­tally or­dered set \((S, \leq)\), such that for any nonempty sub­set \(U \subset S\) there is some \(x \in U\) such that for ev­ery \(y \in U\), \(x \leq y\); that is, ev­ery nonempty sub­set of \(S\) has a least el­e­ment.

Any finite to­tally or­dered set is well-or­dered. The sim­plest in­finite well-or­dered set is \(\mathbb N\), also called \(\omega\) in this con­text.

Every well-or­dered set is iso­mor­phic to a unique or­di­nal num­ber, and thus any two well-or­dered sets are com­pa­rable.

The or­der \(\leq\) is called a “well-or­der­ing,” de­spite the fact that “well” is usu­ally an ad­verb.

In­duc­tion on a well-or­dered set

math­e­mat­i­cal in­duc­tion works on any well-or­dered set. On well-or­dered sets longer than \(\mathbb N\), this is called trans­finite in­duc­tion.

In­duc­tion is a method of prov­ing a state­ment \(P(x)\) for all el­e­ments \(x\) of a well-or­dered set \(S\). In­stead of di­rectly prov­ing \(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\).

Let \(U = \{x \in S \mid \neg P(x) \}\) be the set of el­e­ments of \(S\) for which \(P\) doesn’t hold, and sup­pose \(U\) is nonempty. Since \(S\) is well-or­dered, \(U\) has a least el­e­ment \(x\). That means \(P(y)\) is true for all \(y < x\), which im­plies \(P(x)\). So \(x \not\in U\), which is a con­tra­dic­tion. Hence \(U\) is empty, and \(P\) holds on all of \(S\).

Parents:

  • Totally ordered set

    A set where all the el­e­ments can be com­pared as greater than or less than.