Motivation of inventing concept of well-ordered set?

Question

I've started studying set theory for a while. I understand what is an ordered sets but i still fail to see what motivated mathematicians to invent these concept.

Could you please enlightment me ? Thank you very much!

Answer 1

One of the main properties of well-ordered sets is that we can perform induction arguments on them. Let $(X,\leq)$ be a well ordered set. We define the $\textbf{zero}$ of $X$ $$0_X:=\min(X).$$ Let $\mathcal{P}$ be a property that can be satisfied by elements of $X$. If $x\in X$ satisfies $\mathcal{P}$, we write $\mathcal{P}(x)$. If $x$ doesn't satisfy $\mathcal{P}$ we write $\neg \mathcal{P}(x)$ The following theorem holds

Induction Principle: If $\mathcal{P}(0_X)$ and the following implication holds $$(\mathcal{P}(y)\text{ for any $y<x$})\Rightarrow \mathcal{P}(x)$$ for any $x\in X$, then $\mathcal{P}(x)$ for any $x\in X$

Proof: By contradiction, let's suppose that $\neg \mathcal{P}(x')$ for some $x'\in X$. So the following set is non-empty $$I:=\{x\in X:\neg \mathcal{P}(x)\}=\{x\in X \text{ that don't satisfy $\mathcal{P}$}\}$$ Since $I\neq \varnothing$ and $\leq$ is a well-order, we can define $$x_{\text{min}}:=\min(I).$$ Since $x_{\text{min}}=\min(I)$, we have that $\mathcal{P}(y)$ for any $y<x_{\text{min}}$. Then by the implication in our hyphothesis, we have that $\mathcal{P}(x_{\text{min}})$. This is a contradiction because $\neg\mathcal{P}(x_{\text{min}})$, since $x_{\text{min}}\in I$.$\ \ \ \square$

The "induction principle" is the main motivation behind the notion of well-ordered set. In fact, the following (even stronger) result holds.

The "Induction Principle" holds for a partially ordered set $(X,\leq)$ if and only if the order $\leq$ is a well-order.

Proof: We already proved that if we have a well-order the induction principle holds.

Viceversa, let's suppose that $(X,\leq)$ is a partially ordered set and the induction principle holds for $(X,\leq)$.

By contradiction, let's assume that $\leq$ is not a well-order; so there is a non-empty subset $J\subseteq X$ that has no minimum.

First thing first, $X$ must have a minimum $0_X$, otherwise the induction principle is completely meaningless.

Let $\mathcal{P}_J$ be the property of "NOT belonging to $J$": $$\mathcal{P}_J(x)\overset{\text{def}}{\iff} x\notin J.$$ Clearly $\mathcal{P}_J(0_X)$, otherwise $0_X$ would be the minimum of $J$.

Moreover, if $x\in X$ and $\mathcal{P}_J(y)$ for any $y<x$, then $\mathcal{P}_J(x)$. In fact, if by contradiction $x\in J$ and $y\notin J$ for any $y<x$, then $x$ would be the minimum of $J$.

Since $\mathcal{P}_J$ satisfies the hyphothesis of the Induction Principle, we have that $\mathcal{P}_J(x)$ for any $x\in X$. So $x\notin J$ for any $x\in X$. Since $J\subseteq X$, this implies that $J=\varnothing$. This is a contradiction, because $J$ was non-empty. $\ \ \ \square$

Answer 2

Many mathematical proofs depend on the concept of least. However, this concept is only meaningful in some contexts. A well-ordered set is a totally ordered set in which the idea of least generally makes sense, in that any nonempty subset has a least element. The reason that least is chosen, rather than greatest, is that mathematical objects, such as the natural numbers $0,1,...$ , are built from the ground upward.

Answer 3

Here is an application of well-ordered sets: the dictionary ordering. Suppose we have a countably infinite set of "letters" which are indexed by the natural numbers. We wish to put a well-ordering on the set of all "words" which are finite sequences of letters. The typical way to do this is to use the dictionary ordering: \begin{align*} (a_1 \cdots a_M) < (b_1 \cdots b_N) &\iff M < N \quad\text{or}\quad \bigl(M=N \quad\text{and}\quad \\ &\exists m = 1,\ldots,M \quad\text{such that} \\ &(a_m < b_m \quad\text{and}\quad a_i=b_i \quad\text{for all} \quad 1 \le i < m) \, \bigr) \end{align*} It turns out that this is a well-ordering. It's actually a useful one, too. For example, you can use it to put a well-ordering on the set of polynomials with natural number coefficients. This well-ordering has its own notation: $\omega^\omega$ (where $\omega$ is the usual ordinal notation for the usual well-ordering on the natural numbers). You can also extend the idea to obtain a well-ordering on the set of $n$-variable polynomials with integer coefficients, and then you can apply that well-ordering to describe a division algorithm on that set of polynomials; see for example these notes.