### A Well Ordering Is A Consistent Choice Function

#### Posted by Tom Leinster

Well orderings have slightly perplexed me for a long time, so every now and then I have a go at seeing if I can understand them better. The insight I’m about to explain doesn’t resolve my perplexity, it’s pretty trivial, and I’m sure it’s well known to lots of people. But it does provide a fresh perspective on well orderings, and no one ever taught me it, so I thought I’d jot it down here.

In short: the axiom of choice allows you to choose one element from each
nonempty subset of any given set. A well ordering on a set is a way of making such
a choice *in a consistent way*.

Write $P'(X)$ for the set of nonempty subsets of a set $X$. One formulation of the axiom of choice is that for any set $X$, there is a function $h: P'(X) \to X$ such that $h(A) \in A$ for all $A \in P'(X)$.

But if we think of $h$ as a piece of algebraic structure on the set $X$, it’s natural to ask that $h$ behaves in a consistent way. For example, given two nonempty subsets $A, B \subseteq X$, how can we choose an element of $A \cup B$?

We could, quite simply, take $h(A \cup B) \in A \cup B$.

Alternatively, we could take first take $h(A) \in A$ and $h(B) \in B$, then use $h$ to choose an element of $\{h(A), h(B)\}$. The result of this two-step process is $h(\{ h(A), h(B) \})$.

A weak form of the “consistency” I’m talking about is that these two methods give the same outcome:

$h(A \cup B) = h(\{h(A), h(B)\})$

for all $A, B \in P'(X)$. The strong form is similar, but with arbitrary unions instead of just binary ones:

$h\Bigl( \bigcup \Omega \Bigr) = h\Bigl( \bigl\{ h(A) : A \in \Omega \bigr\} \Bigr)$

for all $\Omega \in P'P'(X)$.

Let’s say that a function $h: P'(X) \to X$ satisfying the weak or strong
consistency law is a weakly or strongly **consistent choice function**
on $X$.

The central point is this:

A consistent choice function on a set $X$ is the same thing as a well ordering on $X$.

That’s true for consistent choice functions in both the weak and the strong sense — they turn out to be equivalent.

The proof is a pleasant little exercise. Given a well ordering $\leq$ on $X$, define $h: P'(X) \to X$ by taking $h(A)$ to be the least element of $A$. It’s easy to see that this is a consistent choice function. In the other direction, given a consistent choice function $h$ on $X$, define $\leq$ by

$x \leq y \Leftrightarrow h(\{x, y\}) = x.$

You can convince yourself that $\leq$ is a well ordering and that $h(A)$ is the least element of $A$, for any nonempty $A \subseteq X$. The final task, also easy, is to show that the two constructions (of a consistent choice function from a well ordering and vice versa) are mutually inverse. And that’s that.

(For anyone following in enough detail to wonder about the difference between weak and strong: you only need to assume that $h$ is a *weakly* consistent choice function in order to prove that the resulting relation $\leq$ is a well ordering, but if you start with a well ordering $\leq$, it’s clear that the resulting function $h$ is *strongly* consistent. So weak is equivalent to strong.)

For me, the moral of the story is as follows. As everyone who’s done some set theory knows, if we assume the axiom of choice then every set can be well ordered. Understanding well orderings as consistent choice functions, this says the following:

If we’re willing to assume that it’s possible to choose an element of each nonempty subset of a set, then in fact it’s possible to make the choice

in a consistent way.

People like to joke that the axiom of choice is obviously true, and that the well orderability of every set is obviously false. (Or they used to, at least.) The theorem on well ordering is derived from the axiom of choice by an entirely uncontroversial chain of reasoning, so I’ve always taken that joke to be the equivalent of throwing one’s hands up in despair: isn’t math weird! Look how this highly plausible statement implies an implausible one!

So the joke expresses a breakdown in many people’s intuitions. And with
well orderings understood in the way I’ve described, we can specify the
point at which the breakdown occurs: it’s in the gap between making a choice
and making a *consistent* choice.

## Re: A Well Ordering Is A Consistent Choice

Very nice. I was always having the “feeling” that a well-ordered set could be interpreted as a set where one always has a “preferred” option, but I never could make it precise. This is

exactlythe way to make it precise! Thank you for sharing!