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 for the set of nonempty subsets of a set . One formulation of the axiom of choice is that for any set , there is a function such that for all .
But if we think of as a piece of algebraic structure on the set , it’s natural to ask that behaves in a consistent way. For example, given two nonempty subsets , how can we choose an element of ?
We could, quite simply, take .
Alternatively, we could take first take and , then use to choose an element of . The result of this two-step process is .
A weak form of the “consistency” I’m talking about is that these two methods give the same outcome:
for all . The strong form is similar, but with arbitrary unions instead of just binary ones:
for all .
Let’s say that a function satisfying the weak or strong consistency law is a weakly or strongly consistent choice function on .
The central point is this:
A consistent choice function on a set is the same thing as a well ordering on .
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 on , define by taking to be the least element of . It’s easy to see that this is a consistent choice function. In the other direction, given a consistent choice function on , define by
You can convince yourself that is a well ordering and that is the least element of , for any nonempty . 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 is a weakly consistent choice function in order to prove that the resulting relation is a well ordering, but if you start with a well ordering , it’s clear that the resulting function 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 exactly the way to make it precise! Thank you for sharing!