Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

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)P'(X) for the set of nonempty subsets of a set XX. One formulation of the axiom of choice is that for any set XX, there is a function h:P(X)Xh: P'(X) \to X such that h(A)Ah(A) \in A for all AP(X)A \in P'(X).

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

  • We could, quite simply, take h(AB)ABh(A \cup B) \in A \cup B.

  • Alternatively, we could take first take h(A)Ah(A) \in A and h(B)Bh(B) \in B, then use hh to choose an element of {h(A),h(B)}\{h(A), h(B)\}. The result of this two-step process is h({h(A),h(B)})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(AB)=h({h(A),h(B)}) h(A \cup B) = h(\{h(A), h(B)\})

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

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

for all ΩPP(X)\Omega \in P'P'(X).

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

The central point is this:

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

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 XX, define h:P(X)Xh: P'(X) \to X by taking h(A)h(A) to be the least element of AA. It’s easy to see that this is a consistent choice function. In the other direction, given a consistent choice function hh on XX, define \leq by

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

You can convince yourself that \leq is a well ordering and that h(A)h(A) is the least element of AA, for any nonempty AXA \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 hh 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 hh 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

23 Comments & 0 Trackbacks

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)(x_i) of elements only if there exists some xx satisfying xx ix\leq x_i for each ii. 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?

From nLab: well-ordering theorem:

…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 XX is a well-order if and only if “transfinite induction works over ()(\prec)”, that is iff the only \prec-inductive subset is all of XX, that is iff AX.(xX.(yX.yxyA)xA)A=X. \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, PP' carries a monad structure. If uu is the unit of the monad, then for a map h:P(X)Xh:P'(X) \to X the condition

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

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

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

PPX Ph PX m h PX h X\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 fu:XPXf \leq u: X \to P'X, then also ufu \leq f. Now, by pre-composing uh1u h \leq 1 with uu, we get uhuuu h u \leq u, which by atomicity of uu gives uuhuu \leq u h u so that u=uhuu = u h u, and now 1=hu1 = h u by monicity of uu. So the unit law is also satisfied, i.e., the type of structure Tom is describing is indeed a PP'-algebra (with an extra condition: uh1u h \leq 1).

As Kevin was saying, PP'-algebras are posets which admit all sups except possibly the empty sup (which would be the bottom element). Ordinarily, the structure map h:PXXh: P'X \to X would be interpreted as sending a nonempty subset of XX to its sup h(X)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 uh1u 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)Ah(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 PP-coalgebra map!!

Think of any relation <\lt as giving a coalgebra XPXX \to P X of the endofunctor PP. 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 PP-coalgebra, but the punch line was that the category of well-orders and initial segment inclusions is a full subcategory of the category of PP-coalgebras.

You probably know from Taylor’s book about well-founded coalgebras. For the endofunctor PP, a well-founded PP-coalgebra θ:XPX\theta: X \to P X (interpreted as taking an element xx to the set {y:yRx}\{y: y R x\} for some relation RR) 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 RR which is well-founded, transitive, and extensional (meaning the coalgebra structure θ:XPX\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 TT-coalgebra maps are called simulations, which I think Taylor mentions somewhere. There’s a nice little theory of (well-founded) TT-coalgebras when TT 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 XX be an ordered set, and think about the associated coalgebra XP(X)X \to P(X) for the powerset functor PP, given by x{x:x<x}x \mapsto \{ x' : x' \lt x\}. The result is that given ordered sets XX and YY, a PP-coalgebra map XYX \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 XX 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-2\mathbf{2}-categories, we can see things as follows. The “maps” into a poset YY (I mean, the order-preserving injections with downwards-closed image) correspond one-to-one with the downsets of YY, which are just presheaves on YY, which in turn correspond one-to-one with the discrete fibrations into YY.

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 TT on a (2,1)-category, the condition uh1u h \le 1 for all TT-algebras is an equivalent way to say that TT 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)Bh(A) \in B and h(B)Ah(B) \in A then h(A)=h(B)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

Re: A Well Ordering Is A Consistent Choice Function

Thank you! That’s very helpful.

Posted by: Tom Leinster on November 15, 2018 12:57 AM | Permalink | Reply to this

Post a New Comment