The n-Category Café

Pick up any book on set theory, and you’ll find significant amounts of order theory (and I include in that the theory of ordinals). Order is everywhere. I used to find that mysterious, but I think I have it clearer now.

There are two ways in which order arises inevitably in set theory. Both are to do with injections.

First, for any set $X$, the collection of subsets of $X$ is naturally ordered by inclusion. This ordered set is a Boolean algebra, accounting for the prominence of Boolean algebras in set theory.

Second, and with just a little poetic licence, the relation $\leq$ on sets is a well-ordering. (Here $X \leq Y$ means that there exists an injection $X \to Y$.) Precise statements are that any nonempty family of sets has a $\leq$-least element, or that for any set $X$, the set of isomorphism classes of sets smaller than $X$ is well-ordered by $\leq$. This accounts for the prominence of well-orderings in set theory.

Experience shows that when dealing with well-ordered sets, the most important notion of “map” is a quite restrictive one: an order-embedding whose image is downwards closed (or an “initial segment”, in the jargon). When I say a map of well-ordered sets, that’s always what I’ll mean.

This notion of map is actually so restrictive that for any well-ordered sets $V$ and $W$, there is at most one map $V \to W$. I’ll write $V \preceq W$ if there exists a map $V \to W$.

So, the category $\mathbf{WOSet}$ of well-ordered sets is a preorder. Indeed, it’s a “well-preorder”: any nonempty family of well-ordered sets has a $\preceq$-least element.

At the start of this post, I promised to explain an important adjunction between well-ordered sets and sets. I was being a bit of a tease, because there are no interesting adjunctions between $\mathbf{WOSet}$ and the usual category of sets. The forgetful functor $\mathbf{WOSet} \to \mathbf{Set}$ certainly doesn’t have an adjoint.

However, there is a highly significant adjunction between $\mathbf{WOSet}$ and the preorder $(\mathbf{Set}, \leq)$. By $(\mathbf{Set}, \leq)$, I mean the category whose objects are sets, and with one map $X \to Y$ when $X \leq Y$ and no maps $X \to Y$ if not. To emphasize that the category $\mathbf{WOSet}$ is also a preorder, I’ll write it now as $(\mathbf{WOSet}, \preceq)$. There is a forgetful functor

$$U: (\mathbf{WOSet}, \preceq) \to (\mathbf{Set}, \leq)$$

that takes the underlying set of a well-ordered set. It’s well-defined on maps (that is, $V \preceq W \implies U(V) \leq U(W)$) because order-embeddings are injective. And it’s this forgetful functor $U$ that has an adjoint.

The adjoint of $U$ is a left adjoint,

$$I: (\mathbf{Set}, \leq) \to (\mathbf{WOSet}, \preceq).$$

It’s defined on a set $X$ by taking $I(X)$ to be the set $X$ equipped with an initial well-order, that is, a well-order $\trianglelefteq$ such that for any other well-order $\trianglelefteq'$ on $X$,

$$(X, \trianglelefteq) \preceq (X, \trianglelefteq').$$

To see that this definition of $I$ is valid, we have to run through a little argument. First of all, the axiom of choice (which is part of ETCS, and which I assume throughout) implies that there is at least one well-order on $X$. And I noted above that any nonempty family of well-ordered sets has a $\preceq$-least element. So $X$ has an initial well-order. In general, $X$ will have many initial well-orders, since given any one of them, you can permute the elements of $X$ to get another. But the usual universal property argument shows that it’s unique up to isomorphism: if $\trianglelefteq$ and $\trianglelefteq'$ are initial well-orders on $X$ then

$$(X, \trianglelefteq) \cong (X, \trianglelefteq').$$

The adjointness $I \dashv U$ says that for a set $X$ and a well-ordered set $W$,

$$I(X) \preceq W \iff X \leq U(W).$$

The left-to-right implication is somewhat trivial: apply $U$ to the inequality $I(X) \preceq W$ and note that $U I(X) \cong X$. The right-to-left implication uses the definition of initial well-order.

For example, suppose that $X$ is countably infinite. There are many isomorphism classes of countably infinite well-ordered sets, but the initial one is $\omega = \{0, 1, \ldots\}$. (It’s traditional to write $\omega$ for $\mathbb{N}$ when it’s being regarded as a well-ordered set.) So $I(X) = \omega$. The adjointness relation for $X$ says that a well-ordered set $W$ is infinite if and only if $\omega \preceq W$.

Incidentally, since $\preceq$ and $\leq$ are total orders, the adjointness can equivalently be stated as

$$W \prec I(X) \iff U(W) \lt X.$$

To a category theorist, it’s maybe a bit funny to see the left adjoint $I$ on the right of the inequality and the right adjoint $U$ on the left. But this statement is just the contrapositive of the earlier formulation of adjointness.

So, we have adjoint functors

$$I: (\mathbf{Set}, \leq) \rightleftarrows (\mathbf{WOSet}, \preceq): U.$$

Since $U \circ I \cong id$, this adjunction restricts to an equivalence of categories

$$I: (\mathbf{Set}, \leq) \rightleftarrows (\text{initial well-ordered sets}, \preceq): U.$$

By an “initial well-ordered set” I mean one isomorphic to $I(X)$ for some set $X$, or more directly, one that’s $\preceq$-least of its cardinality.

I phrased the last few paragraphs in a categorical way, guessing that most readers of The $n$-Category Café would find that enlightening rather than… endarkening? But whether you look at things categorically or not, the important point is that there’s a correspondence

$$sets \leftrightarrow \text{initial well-ordered sets}.$$

So you can, if you want, identify sets with initial well-ordered sets. In ZFC-based developments of set theory, it’s standard to define a cardinal as an initial ordinal. That definition relies on particularities of membership-based set theory that I want to avoid here because I’m doing things “neutrally”. But behind the traditional cardinals-as-ordinals definition, there’s an idea expressible in neutral terms, and it’s exactly this correspondence.

Next time

In parts 4 and 5, we’ll contemplate the ladder of alephs, which involves a different — but also important — pair of back-and-forth processes between sets and well-ordered sets.