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.

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 XX, the collection of subsets of XX 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 XYX \leq Y means that there exists an injection XYX \to Y.) Precise statements are that any nonempty family of sets has a \leq-least element, or that for any set XX, the set of isomorphism classes of sets smaller than XX 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 VV and WW, there is at most one map VWV \to W. I’ll write VWV \preceq W if there exists a map VWV \to W.

So, the category WOSet\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 WOSet\mathbf{WOSet} and the usual category of sets. The forgetful functor WOSetSet\mathbf{WOSet} \to \mathbf{Set} certainly doesn’t have an adjoint.

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

U:(WOSet,)(Set,) 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, VWU(V)U(W)V \preceq W \implies U(V) \leq U(W)) because order-embeddings are injective. And it’s this forgetful functor UU that has an adjoint.

The adjoint of UU is a left adjoint,

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

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

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

To see that this definition of II 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 XX. And I noted above that any nonempty family of well-ordered sets has a \preceq-least element. So XX has an initial well-order. In general, XX will have many initial well-orders, since given any one of them, you can permute the elements of XX 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 XX then

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

The adjointness IUI \dashv U says that for a set XX and a well-ordered set WW,

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

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

For example, suppose that XX is countably infinite. There are many isomorphism classes of countably infinite well-ordered sets, but the initial one is ω={0,1,}\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)=ωI(X) = \omega. The adjointness relation for XX says that a well-ordered set WW is infinite if and only if ωW\omega \preceq W.

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

WI(X)U(W)<X. W \prec I(X) \iff U(W) \lt X.

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

So, we have adjoint functors

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

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

I:(Set,)(initial well-ordered sets,):U. 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)I(X) for some set XX, 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 nn-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

setsinitial well-ordered sets. 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:

4 Comments & 0 Trackbacks

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