June 13, 2021

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.

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

Posted at June 13, 2021 8:29 PM UTC

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

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?

Posted by: Allen Knutson on June 13, 2021 9:36 PM | Permalink | Reply to this

Re: Set category

Yes, exactly that. I’ll rephrase to clarify. Thanks!

Posted by: Tom Leinster on June 13, 2021 9:38 PM | Permalink | Reply to this

Re: Large Sets 3

I really like this idea which I hadn’t seen before, except that you explained it in your comment to the previous post.

Posted by: Jonathan Kirby on June 13, 2021 9:52 PM | Permalink | Reply to this

Re: Large Sets 3

So you can, if you want, identify sets with initial well-ordered sets.

This isn’t neutral, is it? It requires that everything is bijection-invariant, right? And in ZFC, that’s not so. So looking at isomorphism classes is required—in material set theory—to get anything like this working…

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

…I don’t think it matters though how you work with isomorphism classes. In particular, it doesn’t need to use von Neumann ordinals, or any other concrete encoding with membership.

Posted by: Matt Oliveri on June 15, 2021 8:22 AM | Permalink | Reply to this

Post a New Comment