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 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 0=\aleph_0 = \mathbb{N}, followed by the smallest set larger than 0\aleph_0, which is called 1\aleph_1, and then similarly 2, 3,\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 XX, the set

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

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

First of all, K(X)K(X) really is a well-defined set. Any set <X\lt X is isomorphic to a subset of XX, so we can construct K(X)K(X) as a quotient of {A2 X:A<X}\{ 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 X\leq X, we can get it from this definition of KK: it’s K(X +)K(X^+). But there’s no set XX with the property that K()K(\mathbb{N}) is the set of isomorphism classes of sets X\leq X, because there’s no largest set <\lt \mathbb{N}.

Now, the assignment XK(X)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 XI(X)X \mapsto I(X), giving XX an initial well-order. How are KK and II related — if at all?

For a start, they’re not the same. Suppose that XX is +\mathbb{N}^+, the smallest set >\gt \mathbb{N}. Then K(X)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,,. 0, 1, 2, \ldots, \mathbb{N}.

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

But KK and II are related. Indeed, one can show that

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

for all XX. In words: there are at most as many cardinalities smaller than XX as there are elements of XX. 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 <X\lt X to the set of iso classes of infinite sets <\lt X. I’ll call this the index of XX:

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

For example, Index( +++)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:

Tautological bundle over the index of X

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

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

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

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

Indices have some good properties. For example,

Index(X +)Index(X) +. 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 WW and produces a new one, W +W^+, consisting of WW with a new greatest element adjoined (even if WW already has one). It’s the smallest well-ordered set W\succ W.

In fact, for infinite sets XX,

the set X is a successorthe well-ordered set Index(X) is a successor. \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:

the set X is a weak limitthe well-ordered set Index(X) is a limit. \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 XX and YY,

X<YIndex(X)Index(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)Index(Y)XY. Index(X) \cong Index(Y) \implies X \cong Y.

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

Index:(Set ,)(WOSet,). 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 +)Index(X) +Index(X^+) \cong Index(X)^+, if WW is the index of something then so is W +W^+. It’s also not too hard to see that if WW is the index of something then so is every well-ordered set W\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 WW be a well-ordered set. Then WW is the index of some set XX, and the “tautological bundle” of XX consists of a set EE and a function p:EWp: E \to W with the following property:

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

Let’s say that a model of ETCS is Cantorian if every well-ordered set WW 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 WW and we’re trying to show that it’s the index of some set XX. How can we lay our hands on such an XX?

Well, we’re given that there’s a map into WW whose fibres are the infinite sets up to a certain threshold. But none of them is quite as big as XX: they stop one short. For example, if W=3W = \mathbf{3} then the EE above has fibres \mathbb{N}, +\mathbb{N}^+ and ++\mathbb{N}^{++}. But WW 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 +W^+. This gives a map EW +E \to W^+ with the property above, and it’s the top fibre — the fibre over the isomorphism class of WW itself — that gives us the desired set XX, of which WW 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 II, there exists a function into II whose fibres are pairwise non-isomorphic.

In other words, for every set II, there exist a set EE and a function p:EIp: E \to I such that p (1)(i)p^{(-1)}(i) is not isomorphic to p (1)(j)p^{(-1)}(j) for iji \neq j in II. This is clearly implied by the Cantorian axiom: just well-order II 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 WW \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

11 Comments & 0 Trackbacks

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 IUI \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 κ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)cf(X) of an infinite set XX is the smallest set II such that XX can be expressed as a union of II sets <X\lt X. (Or you can equivalently replace “union” by “coproduct”.) For example, cf( ω)= 0\cf(\aleph_\omega) = \aleph_0, as ω\aleph_\omega can be expressed as a countable union of subsets isomorphic to 0, 1,\aleph_0, \aleph_1, \ldots respectively. And cf(X)cf(X) is always X\leq X, since XX can be expressed as a union of XX singletons.

The theorem of König that Todd mentions implies that

X<cf(2 X) X \lt cf(2^X)

for every infinite set XX. (In other words, 2 X2^X can’t be written as the union of XX smaller sets.) This can be seen as a sharpening of Cantor’s theorem that X<2 XX \lt 2^X, since cf(2 X)2 Xcf(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 0\aleph_0). For if ω=2 X\aleph_\omega = 2^X then

X<cf(2 X)=cf( ω)= 0, X \lt cf(2^X) = cf(\aleph_\omega) = \aleph_0,

so XX is finite, so 2 X= ω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?

Posted by: Madeleine Birchfield on June 18, 2021 1:47 PM | Permalink | Reply to this

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 AA be a weak limit (or just some set) and XX be a set. Then the set of all isomorphism classes of sets with “cardinality in [A,X)[A, X)” could be called the “AA-Index of XX”.

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 <X\lt X to the set of iso classes of infinite sets <X\lt X. I’ll call this the index of XX

In the next post, I’ll define the alephs, which are a succession of sets 0, 1,, ω,\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 0=\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 α= α+12^{\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

Re: Large Sets 4

“Index” was a word I made up for this post, so I’m pleased to discover that it does actually appear in the literature with the same meaning. It’s defined in the first sentence of section 6 of Shelah’s Cardinal arithmetic for skeptics. The way he phrases the definition suggests it’s a term he’s coining rather than something established.

Posted by: Tom Leinster on January 25, 2024 8:58 AM | Permalink | Reply to this

Post a New Comment