\( \newcommand{\matr}[1] {\mathbf{#1}} \newcommand{\vertbar} {\rule[-1ex]{0.5pt}{2.5ex}} \newcommand{\horzbar} {\rule[.5ex]{2.5ex}{0.5pt}} \)
deepdream of
          a sidewalk
Show Question
\( \newcommand{\cat}[1] {\mathrm{#1}} \newcommand{\catobj}[1] {\operatorname{Obj}(\mathrm{#1})} \newcommand{\cathom}[1] {\operatorname{Hom}_{\cat{#1}}} \newcommand{\multiBetaReduction}[0] {\twoheadrightarrow_{\beta}} \newcommand{\betaReduction}[0] {\rightarrow_{\beta}} \newcommand{\betaEq}[0] {=_{\beta}} \newcommand{\string}[1] {\texttt{"}\mathtt{#1}\texttt{"}} \newcommand{\symbolq}[1] {\texttt{`}\mathtt{#1}\texttt{'}} \)
Math and science::Analysis::Tao::08. Infinite sets

Well-ordered sets

Let \( X \) be a partially ordered set, and let \( Y \) be a totally ordered subset of \( X \). We say that \( Y \) is well-ordered iff every non-empty subset of \( Y \) has a minimal element, \( \min(Y) \).

Every finite totally ordered set is well-ordered (proved in Ex. 8.5.8). Every subset of a well-ordered set is also well-ordered (why?)

One advantage of well-ordered sets is that they automatically obey the principle of strong induction.

Possible interpretation

Take a table representing an order on \( X \). There will be missing entries in the table representing an ordered pair of elements of \( X \) which is not in the domain of the ordering function. Let \( Y \) be a subset of \( X \) such that there are no such holes for the elements of \( Y \). Imagine this by moving all the columns/rows of the table for \( X \) and it's comparison function such that all of \( Y \)'s elements are bunched together. Then there will be a square in the table that is fully filled with values. All these elements are in \( Y \). Now, there still can be characteristics of these values. For example: the presence of cycles. This is where well-ordering comes in. Take any set of elements of \( Y \) and impose that there is a minimal element. Then, there cannot be cycles.


The natural numbers \( \mathbb{N} \) are well-ordered (see Prop. 8.1.4). The integers \( \mathbb{Z} \), the rationals \( \mathbb{Q} \),and the reals \( \mathbb{R} \) are not.