Why is well order defined like that?

Question

a well ordered set is a partially ordered set where every subset has a first element, but why not just say "every pair of elements in the set has a first element?" is there a more general reason to do it like this?

Answer 1

There's two questions here:

• Why doesn't your definition work?

• Why should you care about the given definition? That is, why is the notion "well-order" useful?

I'll answer the first one first, since it's a bit easier: in any linear order (also called total order), every pair has a least element. Similarly for finite subsets - this is because in a linear order, any two elements are comparable.

An example of a linear order which is not a well-order might help at this point: let $L$ be the integers (positive and negative), ordered in the usual way. Then the set $\{$negatives$\}$ does not have a least element! So $L$ is not a well-order.

---

In terms of motivating well-orders in the first place: basically, they're the things that let us do induction.

Exercise. If $L$ is a linear order, then the following are equivalent: $(a)$ $L$ is a well-order. $(b)$ If $A\subseteq L$ satisfies $$\forall x\in L[(\forall y\in L(y<x\implies y\in A))\implies x\in A],$$ then $A=L$.

You should check that $(b)$ is equivalent to the usual statement of induction in case $L=\mathbb{N}$.

To motivate this exercise, take $L=\mathbb{Z}$ as above, and look at $A=\emptyset$. Does $A$ satisfy the hypothesis of part $(b)$? Why or why not?

So we can recast the question

"Why do we care about well-orderings?"

as

"Why do we need induction arguments on things more complicated than the natural numbers?"

This gets a bit technical, but there are lots of times in mathematics when we need transfinite induction. Some examples:

• Classifying countable abelian $p$-groups requires Ulm invariants, which are defined in terms of well-orderings, and the relevant proofs require transfinite induction. (See https://en.wikipedia.org/wiki/Height_(abelian_group)#Ulm.27s_theorem.)

• Practically anything about Borel sets. (See https://en.wikipedia.org/wiki/Borel_set.)

• Every closed set $A\subseteq\mathbb{R}$ can be partitioned as $A=C\sqcup P$, where $C$ is countable and $P$ is perfect (= closed with no isolated points), in a unique way. (Also works for many spaces besides $\mathbb{R}$.) (See https://en.wikipedia.org/wiki/Perfect_set_property.)

• Many of the more advanced theorems in graph theory or combinatorics - e.g., the Graph Minor Theorem or Fraisse's Conjecture/Laver's Theorem - require induction along truly astoundingly large (but still countable) well-orderings.

• Peano Arithmetic is consistent. (See https://en.wikipedia.org/wiki/Gentzen%27s_consistency_proof.)

---

$^*$Do I really mean "require?" And if so, what does that even mean? This is a question for another context, but it can be made very precise - look up reverse mathematics or proof-theoretic ordinals if you are interested.