### Large Sets 3

#### Posted by Tom Leinster

*Previously: Part 2. Next: Part 4.*

Inherent in set theory is the notion of *well-ordered* set. If you think
about sets for long enough, well-orderings are bound to show up. In this post I’ll explain why, and I’ll summarize some of the
fundamental facts about well-orderings — the least standard of which
is an adjunction between sets and well-ordered sets.

There are no *large* sets this time, but what we do here will be needed in later instalments.

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.

## Set category

I’m trying to understand what “the collection of all sets preordered by cardinal inequality” means. Is it a category whose Obj = {sets}, but homsets are of size 1 or 0, with #Hom(X,Y)=1 exactly when there exists an injection X->Y?