The n-Category Café

Let’s start where we left off last time: with well-orders. I mentioned that well-orders are inevitable in set theory because for any set $X$, the set

$$K(X) = \{ \text{isomorphism classes of sets } \lt X \}$$

is well-ordered by $\leq$ (cardinal inequality). So let’s think about $K(X)$ more carefully.

First of all, $K(X)$ really is a well-defined set. Any set $\lt X$ is isomorphic to a subset of $X$, so we can construct $K(X)$ as a quotient of $\{ A \in 2^X : A \lt X \}$.

Category theorists generally work with non-strict inequalities, $\leq$, but here I’ve used a strict inequality, $\lt$. Why? Because it’s more general. If we want the set of isomorphism classes of sets $\leq X$, we can get it from this definition of $K$: it’s $K(X^+)$. But there’s no set $X$ with the property that $K(\mathbb{N})$ is the set of isomorphism classes of sets $\leq X$, because there’s no largest set $\lt \mathbb{N}$.

Now, the assignment $X \mapsto K(X)$ takes a set as input and produces a well-ordered set as output. We’ve already seen a different way of turning a set into a well-ordered set: the assignment $X \mapsto I(X)$, giving $X$ an initial well-order. How are $K$ and $I$ related — if at all?

For a start, they’re not the same. Suppose that $X$ is $\mathbb{N}^+$, the smallest set $\gt \mathbb{N}$. Then $K(X)$ consists of the isomorphism classes of sets $\lt \mathbb{N}^+$, or equivalently, $\leq \mathbb{N}$. These are the isomorphism classes of finite sets together with the isomorphism class of $\mathbb{N}$ itself:

$$0, 1, 2, \ldots, \mathbb{N}.$$

So $K(\mathbb{N}^+)$ is a countable well-ordered set. On the other hand, $I(\mathbb{N}^+)$ is the uncountable set $\mathbb{N}^+$ equipped with a certain well-order. So $K \neq I$.

But $K$ and $I$ are related. Indeed, one can show that

$$K(X) \preceq I(X)$$

for all $X$. In words: there are at most as many cardinalities smaller than $X$ as there are elements of $X$. We’ll use this fact another day.

At this point I’m going to do a harmless but unmotivated little sidestep, in order to conform with a certain custom in set theory (which we’ll meet next time). I don’t know of any way to justify it except tradition, though maybe someone will fill me in. Anyway, it’s this: we’re going to shift focus from the set of iso classes of all sets $\lt X$ to the set of iso classes of infinite sets $\lt$X. I’ll call this the index of $X$:

$$Index(X) = \{ \text{isomorphism classes of infinite sets } \lt X \}.$$

For example, $Index(\mathbb{N}^{+++})$ is the 3-element well-ordered set, the elements being the isomorphism classes of $\mathbb{N}$, $\mathbb{N}^+$ and $\mathbb{N}^{++}$. The index of a finite set is empty, so when I’m talking about indices, I’ll always assume it’s an infinite set we’re dealing with.

I just made up the word “index”.

Question Do set theorists have a standard name for “index”?

For reasons I’ll explain next time, I wouldn’t be surprised if they don’t. But if they do, I’d like to know it.

There’s a picture in my head:

This is what could be called the tautological bundle associated with $X$. The elements of $Index(X)$ are the isomorphism classes of infinite sets $A \lt X$, and this “bundle” consists of a set $E$ and a function

$$p: E \to Index(X)$$

such that the fibre $p^{-1}([A])$ over $[A]$ is $A$ itself. (You can construct $E$ as a subset of $Index(X) \times X$.) So each infinite set $\lt X$ appears as a fibre exactly once. If maps into $Index(X)$ are viewed as families indexed by $Index(X)$, then in slightly loose notation, this family is

$$\bigl( A \bigr)_{[A] \in Index(X)}.$$

Indices have some good properties. For example,

$$Index(X^+) \cong Index(X)^+.$$

The $+$ on the left-hand side means successor set, a construction I explained before and have already been using in this post. But the $+$ on the right-hand side is the successor well-ordered set, which I haven’t mentioned before. It’s the construction that takes a well-ordered set $W$ and produces a new one, $W^+$, consisting of $W$ with a new greatest element adjoined (even if $W$ already has one). It’s the smallest well-ordered set $\succ W$.

In fact, for infinite sets $X$,

$$\text{the set }\ X \ \text{ is a successor} \iff \text{the well-ordered set }\ Index(X) \ \text{ is a successor}.$$

A well-ordered set that is not a successor is called a limit, and a set that is not a successor is a weak limit. So another way to say this is:

$$\text{the set }\ X \ \text{ is a weak limit} \iff \text{the well-ordered set }\ Index(X)\ \text{ is a limit}.$$

But the most important property of the index is this: for infinite sets $X$ and $Y$,

$$X \lt Y \implies Index(X) \prec Index(Y).$$

In particular, the process of taking the index is injective (up to isomorphism):

$$Index(X) \cong Index(Y) \implies X \cong Y.$$

So, writing $\mathbf{Set}_\infty$ for the collection of infinite sets, Index is an order embedding

$$Index: (\mathbf{Set}_\infty, \leq) \hookrightarrow (\mathbf{WOSet}, \preceq).$$

There’s now an obvious question: what is the image of this embedding? That is:

Which well-ordered sets are the index of some set?

Certainly $\emptyset$ is: it’s the index of $\mathbb{N}$. And since $Index(X^+) \cong Index(X)^+$, if $W$ is the index of something then so is $W^+$. It’s also not too hard to see that if $W$ is the index of something then so is every well-ordered set $\prec W$. So the collection of well-ordered sets arising as indices is nonempty, closed under taking successors, and downwards closed.

But in ETCS, not every well-ordered set has to be the index of something. Indeed:

It is consistent with ETCS that there is no set with index $\omega$.

For we saw above that since the well-ordered set $\omega$ is a limit, any set with index $\omega$ must be a weak limit. It must also be uncountable. And in part 2, we saw that it’s consistent with ETCS that there are no uncountable weak limits.

So the picture is this. In a model of ETCS, either all well-ordered sets arise as indices, or those below some threshold do and those above the threshold don’t.

We might therefore consider adding the following axiom to ETCS:

Every well-ordered set is the index of some set.

This axiom can be rephrased in several equivalent ways, as follows.

Take a model of ETCS, and suppose it satisfies this axiom. Let $W$ be a well-ordered set. Then $W$ is the index of some set $X$, and the “tautological bundle” of $X$ consists of a set $E$ and a function $p: E \to W$ with the following property:

for each $w \in W$, the fibre $p^{-1}(w)$ is the smallest infinite set $\gt p^{-1}(v)$ for each $v \lt w$.

Let’s say that a model of ETCS is Cantorian if every well-ordered set $W$ admits a map into it with this property. So, we’ve just shown that “every well-ordered set is an index” implies Cantorian.

The converse is also true… but isn’t quite obvious.

Let me explain briefly how the proof goes. We’ve got a well-ordered set $W$ and we’re trying to show that it’s the index of some set $X$. How can we lay our hands on such an $X$?

Well, we’re given that there’s a map into $W$ whose fibres are the infinite sets up to a certain threshold. But none of them is quite as big as $X$: they stop one short. For example, if $W = \mathbf{3}$ then the $E$ above has fibres $\mathbb{N}$, $\mathbb{N}^+$ and $\mathbb{N}^{++}$. But $W$ is the index of $\mathbb{N}^{+++}$, so this isn’t quite enough.

What we actually have to do is apply the Cantorian axiom to $W^+$. This gives a map $E \to W^+$ with the property above, and it’s the top fibre — the fibre over the isomorphism class of $W$ itself — that gives us the desired set $X$, of which $W$ is the index.

So for models of ETCS,

(every well-ordered set is the index of some set) $\iff$ Cantorian.

There’s yet another equivalent way of stating this condition, which has the virtue of being entirely about sets, not ordered sets:

For every set $I$, there exists a function into $I$ whose fibres are pairwise non-isomorphic.

In other words, for every set $I$, there exist a set $E$ and a function $p: E \to I$ such that $p^{(-1)}(i)$ is not isomorphic to $p^{(-1)}(j)$ for $i \neq j$ in $I$. This is clearly implied by the Cantorian axiom: just well-order $I$ arbitrarily. But a little argument shows that in fact, it’s equivalent.

Next time

We’ve seen that the process of taking the index defines a bijection from

isomorphism classes of infinite sets

to

isomorphims classes of well-ordered sets that are the index of something.

Next time, we’ll look at the inverse process, mapping a well-ordered set to the set of which it is the index (if there is one). This inverse is written as $W \mapsto \aleph_W$ — and these are the promised alephs.