## November 12, 2018

### 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.

Posted at November 12, 2018 1:59 AM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3073

### 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!

Posted by: Paolo Perrone on November 12, 2018 9:54 AM | Permalink | Reply to this

### Re: A Well Ordering Is A Consistent Choice Function

Is there some way to think of the singleton embedding of X into P’(X) as the unit of an adjunction? (The set of non-empty finite subsets of X, equipped with the binary operation of union, is the free semilattice on the generating set X, and this looks temptingly similar to what you’ve got here)

Posted by: Yemon Choi on November 12, 2018 2:58 PM | Permalink | Reply to this

### Re: A Well Ordering Is A Consistent Choice Function

There is a well-known powerset monad P, which sends a set to its powerset and a function to the direct image, with unit the singleton embedding and multiplication given by the union operation on th complete Boolean algebra of subsets. Since the image of a nonempty set is nonempty, a singleton is nonempty, and a union of a nonempty set of nonempty sets is nonempty, this monad structure restricts to the subfunctor P’. So the singleton embedding is the unit for at least one adjunction, the free-forgetful adjunction associated to the Eilenberg-Moore category of this monad.

What is this Eilenberg-Moore category? For P, it is the complete semilattices (complete lattices with morphisms preserving only suprema.) For P’, I guess it should be the “nonempty-complete-semilattices”, for lack of a better term: things that are complete semilattices except insofar as they might lack a bottom element. I haven’t checked this carefully, but it seems right. These seem like pretty charming beasts, actually. For instance, what meets do they have? Roughly, only those which don’t want to be the bottom element: one has a meet of a family $(x_i)$ of elements only if there exists some $x$ satisfying $x\leq x_i$ for each $i$. It reminds me of some early 20th-century mathematician I heard about somewhere, maybe on here, who had the now-heretical opinion that intersections of subsets only exist when nonempty!

Posted by: Kevin Carlson on November 13, 2018 4:38 AM | Permalink | Reply to this

### Re: A Well Ordering Is A Consistent Choice Function

Moore of the Moore Method was the heretic. I forget where I read this, maybe Halmos’ automathography.

Posted by: Allen Knutson on November 13, 2018 2:37 PM | Permalink | Reply to this

### Re: A Well Ordering Is A Consistent Choice Function

Yes, your remembrance is correct: that this is mentioned in the book by Halmos. Actually, for all I know this may have been the more orthodox view in turn-of-the-century mathematics when Moore was a student. (Emptiness has probably long been considered a disconcerting concept.)

Posted by: Todd Trimble on November 13, 2018 3:26 PM | Permalink | Reply to this

### Re: A Well Ordering Is A Consistent Choice Function

Having a choice function rather than just being able to make a choice in each individual case is already a form of consistency (many local choices versus one global choice), let’s call it “very weak consistency”, since you already used “weak”. The axiom of choice is already bridging a gap between no consistency at all and some consistency.

Posted by: Vej Kse on November 12, 2018 9:36 PM | Permalink | Reply to this

### Re: A Well Ordering Is A Consistent Choice Function

Thanks for the comment. Perhaps I should have used a different word; actually, I hesitated between “consistent” and “coherent”.

Then again, perhaps it’s good to use the same word for both purposes. To have a choice function is to make choice into an operation, as in algebra. To have consistency in the sense of my post is for that operation to satisfy equations — again, as in algebra.

So consistency, in either of these senses, is a move towards an algebraic structure.

Posted by: Tom Leinster on November 13, 2018 3:59 PM | Permalink | Reply to this

### Re: A Well Ordering Is A Consistent Choice Function

Any constructivist light to be shone on the topic of this post?

…in constructive mathematics, the well-ordering principle is (seemingly) actually weaker than the full axiom of choice, as it does not imply excluded middle by itself. It does, however, imply the full axiom of choice (and hence excluded middle) if by ‘well-order’ we mean a classical well-order, in the sense that every inhabited subset has a least element, rather than the constructively sensible notion of well-order that merely permits inductive proofs.

What is meant at the end there by the “constructively sensible notion”?

Posted by: David Corfield on November 13, 2018 1:16 PM | Permalink | Reply to this

### Re: A Well Ordering Is A Consistent Choice Function

What is meant at the end there by the “constructively sensible notion”?

I believe the following notion is meant. A transitive relation $(\prec)$ on a set $X$ is a well-order if and only if “transfinite induction works over $(\prec)$”, that is iff the only $\prec$-inductive subset is all of $X$, that is iff $\forall A \subseteq X. (\forall x \in X. (\forall y \in X. y \prec x \Rightarrow y \in A) \Rightarrow x \in A) \Rightarrow A = X.$ Some more details are at this entry (which I’ll link from the quoted passage in a second).

Posted by: Ingo Blechschmidt on November 13, 2018 2:36 PM | Permalink | Reply to this

### Re: A Well Ordering Is A Consistent Choice Function

This sure is interesting! Never seen it before – it probably deserves to be published.

Picking up on the train of ideas started by Yemon and Kevin, it looks like there are chunks that are translatable into relational algebra of a kind reminiscent of Barr’s definition of topological space as relational $\beta$-module.

I’ll just make a few observations. As Kevin said, $P'$ carries a monad structure. If $u$ is the unit of the monad, then for a map $h:P'(X) \to X$ the condition

$u h \leq 1_{P'(X)}$

is synonymous with $h(A) \in A$ for all nonempty $A$.

Tom’s strong consistency condition says that for the covariant monad structure $(P', u: 1_{Set} \to P', m: P'P' \to P')$ as described by Kevin, the diagram

$\array{ P'P'X & \stackrel{P'h}{\to} & P'X \\ \downarrow \mathrlap{m} & & \downarrow \mathrlap{h} \\ P'X & \underset{h}{\to} & X }$

commutes.

Another fun fact about this monad is that the unit map is atomic in the sense that if $f \leq u: X \to P'X$, then also $u \leq f$. Now, by pre-composing $u h \leq 1$ with $u$, we get $u h u \leq u$, which by atomicity of $u$ gives $u \leq u h u$ so that $u = u h u$, and now $1 = h u$ by monicity of $u$. So the unit law is also satisfied, i.e., the type of structure Tom is describing is indeed a $P'$-algebra (with an extra condition: $u h \leq 1$).

As Kevin was saying, $P'$-algebras are posets which admit all sups except possibly the empty sup (which would be the bottom element). Ordinarily, the structure map $h: P'X \to X$ would be interpreted as sending a nonempty subset of $X$ to its sup $h(X)$. The only difference here is that Tom is following the usual convention that a well-order is defined to be a linear order in which every nonempty subset contains its inf; we could of course buck the trend and define a well-order to be a linear order in which every nonempty subset contains its sup, at the cost of reversing the conventional order and confusing the hell out of people, but the concept seems to be the same.

Anyway, this is a really cool idea. I’m wondering about this weird laxity $u h \leq 1$, i.e., where else it comes up in this sort of categorical relational algebra.

Posted by: Todd Trimble on November 13, 2018 2:30 PM | Permalink | Reply to this

### Re: A Well Ordering Is A Consistent Choice Function

Thanks! I’d been wondering how to think about the condition that $h(A) \in A$, which does an awful lot of work.

Maybe now is a good time to explain part of what perplexes me about well-ordered sets.

Undoubtedly well orderings are very important in set theory; and personally, I find the theory of well-ordered sets very aesthetically pleasing. (I mean what’s usually called the theory of ordinals, but understood in a category theorists’ way — i.e. without all the stuff about transitive sets.) So, let’s take it as a given that the standard, basic, theory of well-ordered sets deserves to be understood from a categorical point of view.

Here’s the crunch. When one looks at that theory, by far the most prominent notion of a map between well ordered sets is that of an order-preserving injection whose image is downwards closed. (Or in other terminology: an embedding as an initial segment.) Categorically, why?

In other words, can you phrase the definition of well-ordered set in such a way that the natural notion of map is the one just described?

I’ve been wondering this for years and never got to the bottom of it. I mention it now for two reasons. One is that perhaps your relational algebra perspective can help. The other is that I’ve always had a sneaking suspicion that the answer might be in Paul Taylor’s Practical Foundations book, but I’ve never succeeded in finding it. But Todd, I think you know that book pretty well.

Posted by: Tom Leinster on November 13, 2018 4:15 PM | Permalink | Reply to this

### Re: A Well Ordering Is A Consistent Choice Function

Why, yes! It’s just a $P$-coalgebra map!!

Think of any relation $\lt$ as giving a coalgebra $X \to P X$ of the endofunctor $P$. The rest I leave as an exercise. :-)

Posted by: Todd Trimble on November 13, 2018 4:18 PM | Permalink | Reply to this

### Re: A Well Ordering Is A Consistent Choice Function

So while my last comment was meant to have a certain punch to it, I should probably say a little more. A well-order is a particular kind of $P$-coalgebra, but the punch line was that the category of well-orders and initial segment inclusions is a full subcategory of the category of $P$-coalgebras.

You probably know from Taylor’s book about well-founded coalgebras. For the endofunctor $P$, a well-founded $P$-coalgebra $\theta: X \to P X$ (interpreted as taking an element $x$ to the set $\{y: y R x\}$ for some relation $R$) amounts to a well-founded relation, meaning a relation for which the induction idiom applies. For the sake of convenience, you can have a look at the nLab article on well-founded relation, particularly the section here.

But what about well-orders in the sense of linear orders? Well, the nLab has this:

Theorem: A relation $R$ which is well-founded, transitive, and extensional (meaning the coalgebra structure $\theta: X \to P X$ is monic) is the same as a linear well-order.

See here. I actually wrote up that proof (with some edits by Toby); I’m not sure who first proved it.

By the way: sometimes $T$-coalgebra maps are called simulations, which I think Taylor mentions somewhere. There’s a nice little theory of (well-founded) $T$-coalgebras when $T$ is any taut functor (preserves pullbacks where one of the arrows of the cospan is monic).

But I expect you may want to hook up some of this theory with the theory you’re developing now.

Posted by: Todd Trimble on November 13, 2018 5:02 PM | Permalink | Reply to this

### Re: A Well Ordering Is A Consistent Choice Function

Fantastic! Thank you! I should have asked you years ago.

So, you just told me the following. Let $X$ be an ordered set, and think about the associated coalgebra $X \to P(X)$ for the powerset functor $P$, given by $x \mapsto \{ x' : x' \lt x\}$. The result is that given ordered sets $X$ and $Y$, a $P$-coalgebra map $X \to Y$ is the same thing as an order-preserving injection whose image is downwards closed. I just worked through the proof, and if I’m not mistaken, we need to assume that $X$ is totally ordered. Of course, that covers the case I’m talking about: well-orderings in the traditional sense.

Posted by: Tom Leinster on November 14, 2018 8:53 PM | Permalink | Reply to this

### Re: A Well Ordering Is A Consistent Choice Function

I asked (because I’d been wondering for years):

Here’s the crunch. When one looks at that theory, by far the most prominent notion of a map between well ordered sets is that of an order-preserving injection whose image is downwards closed. (Or in other terminology: an embedding as an initial segment.) Categorically, why?

In other words, can you phrase the definition of well-ordered set in such a way that the natural notion of map is the one just described?

Todd gave one great answer. Here’s another answer: the order-preserving injections with downwards-closed image are exactly the discrete fibrations.

That is, if you view posets as categories in the usual way, then a discrete fibration is precisely an order-preserving injection with downwards-closed image, provided only that the domain is totally ordered.

(I haven’t taken the time to figure out what the discrete fibrations look like when the domain isn’t totally ordered. Maybe “order-preserving injection” is replaced by “order-preserving and order-reflecting map”?)

In a way, that should have been obvious. If you allow me to blur the distinction between posets-as-ordinary-categories and posets-as-$\mathbf{2}$-categories, we can see things as follows. The “maps” into a poset $Y$ (I mean, the order-preserving injections with downwards-closed image) correspond one-to-one with the downsets of $Y$, which are just presheaves on $Y$, which in turn correspond one-to-one with the discrete fibrations into $Y$.

But now here’s another conceptual puzzle. Given that we’re interested in certain posets and the discrete fibrations between them, why should it be the well-ordered sets? What is it about well orders that make them a natural companion for discrete fibrations?

Posted by: Tom Leinster on November 21, 2018 2:19 PM | Permalink | Reply to this

### Re: A Well Ordering Is A Consistent Choice Function

Thanks Tom. That’s a curious question. From this perspective do you think it is worth widening the perspective to preorders, hence possibly WQOs, BQOs etc.? I ask because antisymmetry is not (to me) such a canonical requirement from the perspective of posets as categories.

Posted by: Sam Staton on November 23, 2018 7:59 AM | Permalink | Reply to this

### Re: A Well Ordering Is A Consistent Choice Function

Well, my categorical heart is certainly open to preorders!

I take it WQO = well-quasi-order, and quasi-order is a synonym for preorder? What’s the B of BQO?

Posted by: Tom Leinster on November 23, 2018 1:27 PM | Permalink | Reply to this

### Re: A Well Ordering Is A Consistent Choice Function

That’s right. B=better, I’m afraid. I have fond memories of learning this stuff from Thomas Forster and possibly Harold Simmons, although that was quite some time ago. Thomas wrote some notes. Maybe these.

Posted by: Sam Staton on November 23, 2018 3:26 PM | Permalink | Reply to this

### Re: A Well Ordering Is A Consistent Choice Function

For a (2,1)-monad $T$ on a (2,1)-category, the condition $u h \le 1$ for all $T$-algebras is an equivalent way to say that $T$ is colax-idempotent. So maybe this is some kind of “local” colax-idempotence?

Posted by: Mike Shulman on November 13, 2018 9:35 PM | Permalink | Reply to this

### Re: A Well Ordering Is A Consistent Choice Function

FWIW, this equivalent way of thinking about well-orders is used a lot in the model theory for conditional logics. (Specifically in Stalnaker’s selection function semantics, which is formalized in terms of consistent choice functions but typically glossed in terms of well-orders.) The consistency condition is usually stated slightly differently though: if $h(A) \in B$ and $h(B) \in A$ then $h(A)=h(B)$.

Posted by: Andrew Bacon on November 14, 2018 5:38 PM | Permalink | Reply to this

### Re: A Well Ordering Is A Consistent Choice Function

Thanks! Can you point me to a reference for that?

Posted by: Tom Leinster on November 14, 2018 8:55 PM | Permalink | Reply to this

### Re: A Well Ordering Is A Consistent Choice Function

Here’s Stalnaker’s original paper: http://fitelson.org/269/Stalnaker_ATOC.pdf (see pages 103-105).

The equivalence of the selection function way of doing things with the well-order way appears to be implicit in Stalnaker’s discussion, and the subsequent literature. (I believe it’s articulated explicitly somewhere in David Lewis’s book “Counterfactuals” – at least, I recall the reconstruction of a well-order by applying the selection function to doubleton sets. I don’t have my copy to hand right now so I can’t check the exact details.) These writers are obviously not thinking about it in a particularly categorical way though, or about it’s relation to the axiom of choice and the well-ordering principle.

Posted by: Andrew Bacon on November 15, 2018 12:38 AM | Permalink | Reply to this