# Motivation of inventing concept of well-ordered set?

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!

• While studying Set theory , when you come across some interesting theorem & you see the Proof using Well-Ordering Concept , then you should try to see how that theorem can work without using that Concept. When you get the Proof without using that Concept , then Well-Ordering Concept is unnecessary ( at least here ) & you can rightly reject it. When you struggle for months ( years ) without Alternate Proof , then that itself is the motivation for Well-Ordering Concept !
– Prem
Commented Jul 13 at 7:51
• The goal is to seek the most general order structure so that inductive proofs remain well-founded and recursive functions always terminate. This leads to ordinals and - more generally - well-founded relations (e.g. well-founded strict partial orders such as strict divisibility of natural numbers). $\ \$ Commented Jul 13 at 19:54
• So we could make puns about the leader of a school requisitioning water-extraction infrastructure? Commented Jul 13 at 20:36
• Surely there's a critical difference between the ordering of the counting numbers and the ordering of the integers. I wonder what we should call it? Commented Jul 13 at 23:33
• @EricTowers I disagree with this viewpoint. The most noticeable difference between counting numbers and integers is that the latter has a minimum and the second doesn't: basically none would say that the difference is that every non-empty subset of the natural numbers has a minimum and this doesn't hold for the integers. A better (not perfect) example is the difference between $\mathbb{N}$ and $[0,\infty)$. Commented Jul 14 at 7:45

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 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. 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, then $$\mathcal{P}_J(x)$$. In fact, if by contradiction $$x\in J$$ and $$y\notin J$$ for any $$y, 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$$

• This is a good answer, but I think you should remove all occurrences of $0_X$, they are unnecessary. Commented Jul 13 at 16:01
• The phrasing of the equivalence is a bit misleading since induction also holds more generally for well-founded relations, e.g. well-founded strict partial orders, e.g. naturals ordered by strict divisibility. $\ \$ Commented Jul 13 at 19:32
• @BillDubuque I've made the statement less misleading. Does it seem right to you now? Commented Jul 14 at 7:31
• @CarstenS I've never realized it, but the implication in the induction principle already implies that $\mathcal{P}(0_X)$, if we take $x=0_X$. Nonentheless, I think the answer is clearer written like this. Commented Jul 14 at 7:33
• The statement of induction for well-ordered sets normally doesn't require that $X$ have a least element (It's implicit as it's a well-ordered set). E.g. here: proofwiki.org/wiki/Principle_of_Mathematical_Induction/…. So, from the (normal) statement of induction, I don't think you can argue that $X$ has a least element Commented Jul 15 at 0:06

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.

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.