## June 17, 2021

### Large Sets 4

#### Posted by Tom Leinster

Previously: Part 3. Next: Part 5

The alephs are the succession of ever-larger infinite sets, beginning at $\aleph_0 = \mathbb{N}$, followed by the smallest set larger than $\aleph_0$, which is called $\aleph_1$, and then similarly $\aleph_2, \aleph_3, \ldots$, up to $\aleph_\omega$ and beyond. At least, that’s the usual way the alephs are introduced. But in this post and the next, I’m going to come at the alephs from another angle — the opposite direction, in some sense — which is better suited to ETCS.

Last time, I promised that I’d get to the alephs this time. But in the interests of keeping each post shortish, I’m actually going to split the explanation in two. So right now, I’m going to explain something I call the “index” of a set, and next time we’ll meet the alephs themselves.

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.

Posted at June 17, 2021 5:18 PM UTC

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

### Re: Large Sets 4

I’m enjoying this series. Could you write something about references? Presumably some of this category-theoretic approach to large sets is covered in papers or books somewhere and some of it is not and you are discovering this presentation for yourself.

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

### Re: Large Sets 4

Thanks, Jonathan. That means a lot coming from you. I know you’ve thought a lot about related things, and remember your talk at STUK in February last year about large cardinal axioms versus replacement.

(Later, that trip to London — nearly 18 months ago now — took on an extra personal significance for me: it was the last time I gave a talk in person, and the last time I left the country.)

I’m not very good at references. Mostly I’m working this stuff out for myself, with the help of standard non-categorical set theory texts. I’ve read and enjoyed several of Colin McLarty’s papers on categorical set theory, especially Exploring categorical structuralism, which are mostly written for philosophers.

Much of what’s known about ZFC vs ETCS seems to go back to the 1970s, with work of Cole, Mitchell, Osius and others. Mike Shulman’s Comparing material and structural set theories has a good reference list. I confess that I’ve only looked at those old papers in a very shallow way.

The adjunction $I \dashv U$ from last time and the stuff on “index” this time isn’t taken from any published source. Of course, that’s not to claim any kind of originality or nontriviality. I just mean that I don’t have a reference for it.

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

### Cofinality

I don’t remember enough of this stuff to compare it to what you’re presenting, but I expected when you brought up Aleph_ omega that you’d mention the result 2^{Aleph_0} != Aleph _omega, for some reason based on “cofinality”. Is that anywhere close to the concepts you’re getting into here?

Posted by: Allen Knutson on June 18, 2021 3:07 AM | Permalink | Reply to this

### Re: Cofinality

That’s a result of König’s theorem, and quite a nice theorem it is. The cofinality of $2^\kappa$ must be greater than $\kappa$.

Posted by: Todd Trimble on June 18, 2021 10:39 AM | Permalink | Reply to this

### Re: Cofinality

Yes, that is a nice theorem! And I plan to get to it in a few posts’ time.

But I can’t resist expanding on Todd’s answer right now, as a kind of rehearsal for the post to come.

The cofinality $cf(X)$ of an infinite set $X$ is the smallest set $I$ such that $X$ can be expressed as a union of $I$ sets $\lt X$. (Or you can equivalently replace “union” by “coproduct”.) For example, $\cf(\aleph_\omega) = \aleph_0$, as $\aleph_\omega$ can be expressed as a countable union of subsets isomorphic to $\aleph_0, \aleph_1, \ldots$ respectively. And $cf(X)$ is always $\leq X$, since $X$ can be expressed as a union of $X$ singletons.

The theorem of König that Todd mentions implies that

$X \lt cf(2^X)$

for every infinite set $X$. (In other words, $2^X$ can’t be written as the union of $X$ smaller sets.) This can be seen as a sharpening of Cantor’s theorem that $X \lt 2^X$, since $cf(2^X) \leq 2^X$.

Putting together everything I’ve just said implies that $\aleph_\omega$ can’t be the power set of anything at all (and in particular, not of $\aleph_0$). For if $\aleph_\omega = 2^X$ then

$X \lt cf(2^X) = cf(\aleph_\omega) = \aleph_0,$

so $X$ is finite, so $2^X = \aleph_\omega$ is finite, a contradiction.

Posted by: Tom Leinster on June 18, 2021 12:24 PM | Permalink | Reply to this

### Re: Cofinality

Doesn’t Konig’s theorem imply the axiom of choice sets?

### Re: Cofinality

Yes.

Posted by: Tom Leinster on June 18, 2021 2:01 PM | Permalink | Reply to this

### Re: Large Sets 4

It’s a very interesting series.

I don’t think I fully understand the special role $\mathbb{N}$ and the property “infinite” play in set theory. Wouldn’t it make sense to define “Index” for each weak limit set? I.e. let $A$ be a weak limit (or just some set) and $X$ be a set. Then the set of all isomorphism classes of sets with “cardinality in $[A, X)$” could be called the “$A$-Index of $X$”.

I havent’t yet looked into why $\mathbb{N}$ should produce a special kind of index, in comparison to other sets.

Posted by: Stéphane Desarzens on June 19, 2021 8:49 PM | Permalink | Reply to this

### Re: Large Sets 4

Thanks.

I agree, the “infinite” condition is peculiar. Here’s how I half-explained myself in the post:

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 […] 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$

In the next post, I’ll define the alephs, which are a succession of sets $\aleph_0, \aleph_1, \ldots, \aleph_\omega, \ldots$. In a sense I’ll describe, the alephs are closely related to the notion of index. But the point is that the alephs begin at $\aleph_0 = \mathbb{N}$. (That’s not my choice; it’s a standard convention.) One could define a different succession of sets beginning at $\emptyset$ instead of $\mathbb{N}$. They would be the same as the alephs, but with the indexing shifted. Although that’s a harmless, cosmetic change, as far as I know there’s no standard notation for these “shifted alephs”.

Inserting the condition “infinite” into the definition of index simply makes it match up with the indexing in the definition of the alephs. I’m only doing it so as to align with this convention in set theory, not for any deep and meaningful reason.

Posted by: Tom Leinster on June 19, 2021 10:58 PM | Permalink | Reply to this

### Re: Large Sets 4

My guess for why alephs begin at $\mathbb{N}$ is that in set theory, we are mainly interested in infinite sets and their behaviors, and not really in finite sets. Therefore, a lot of definitions become interesting only at the smallest infinite set, and some results are more easily stated if all alephs are infinite. The obvious example is the generalised continuum hypothesis, which can be simply written as “For any ordinal $\alpha$, $2^{\aleph_\alpha} = \aleph_{\alpha + 1}$.” But I agree that in some cases, it can be a bit clumsy.

Posted by: Gabin Kolly on July 2, 2021 1:37 PM | Permalink | Reply to this

Post a New Comment