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 20, 2021

Large Sets 5

Posted by Tom Leinster

Previously: Part 4. Next: Part 6

Last time, we met the “index” of an infinite set XX, which is the well-ordered set

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

It cannot be proved in ETCS that every well-ordered set WW is the index of some infinite set XX. However, if such an XX does exist, it’s unique for WW (up to isomorphism). It’s called W\aleph_W: aleph-WW.

To recap, we saw that the process of taking the index defines an order-embedding

Index:(infinite sets)(well-ordered sets). Index: \text{(infinite sets)} \hookrightarrow \text{(well-ordered sets)}.

So

X<YIndex(X)Index(Y), X \lt Y \implies Index(X) \prec Index(Y),

and therefore

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

So if a well-ordered set WW is isomorphic to Index(X)Index(X) for some infinite set XX, then XX is determined uniquely up to isomorphism, and we write X= WX = \aleph_W. In that case, I’ll say W\aleph_W exists.

For natural numbers nn, there’s exactly one well-ordered set with nn elements; call it n\mathbf{n}. We write n\aleph_{\mathbf{n}} as n\aleph_n. For example:

  • 0\aleph_0 is the unique infinite set whose index is the empty well-ordered set 0\mathbf{0}; that is, 0\aleph_0 \cong \mathbb{N}.

  • 1\aleph_1 is the unique infinite set whose index is the one-element well-ordered set 1\mathbf{1}. That is, up to isomorphism, there is exactly one infinite set smaller than 1\aleph_1. So 1\aleph_1 is +\mathbb{N}^+, the smallest set >\gt \mathbb{N}.

The assignments IndexIndex and \aleph_\bullet are mutually inverse:

Index(X)X \aleph_{Index(X)} \cong X

for infinite sets XX, and

Index( W)W Index(\aleph_W) \cong W

for well-ordered sets WW such that W\aleph_W exists. Set theory books sometimes contain the statement “every infinite set is an aleph”; the first of these isomorphisms is our version of this.

For want of a better word, let’s say that a well-ordered set WW is alephable if W\aleph_W exists. Then the inverse processes IndexIndex and \aleph_\bullet define an equivalence

(Set ,)(alephable well-ordered sets,). (\mathbf{Set}_\infty, \leq) \simeq (\text{alephable well-ordered sets}, \preceq).

ZFC-based set theory puts the emphasis on the right-to-left assignment, W WW \mapsto \aleph_W. In ZFC, every well-ordered set is alephable, so that’s a reasonable thing to do. But in ETCS, where that’s not guaranteed, it makes more sense to emphasize the left-to-right direction, XIndex(X)X \mapsto Index(X). That’s why I started there.

I chose the word “index” as an abbreviation for “aleph-index”: the index of XX is the well-ordered set WW such that WX\aleph_W \cong X. Maybe set theorists have no name for “index” because they’d just say “the ordinal α\alpha such that X= αX = \aleph_\alpha”.

Incidentally, the reason why I switched from K(X)K(X) to Index(X)Index(X) near the start of the last post was exactly so that we’d get an inverse to \aleph_\bullet. I’d have been happy to stick with K(X)K(X) (thus, also including the finite sets <X\lt X) if there was a standard name for the inverse to KK. That inverse would be a ladder of sets like the alephs, but starting at \emptyset rather than \mathbb{N}. But as far as I know, it doesn’t have a name (and in particular, it’s not quite the same as the von Neumann hierarchy).

Which well-ordered sets WW are alephable? This is the same as the question “which well-ordered sets are the index of some set?”, which we already answered last time. Translating into the language of alephs, we know:

  • 00 is alephable (i.e. 0\aleph_0 \cong \mathbb{N} exists);

  • if WW is alephable then so is W +W^+, and W +( W) +\aleph_{W^+} \cong (\aleph_W)^+;

  • if WW is alephable then so is VV for all VWV \prec W.

The first two properties guarantee that n\aleph_n exists for all natural numbers nn. But W\aleph_W need not exist for all well-ordered sets WW. In particular:

It is consistent with ETCS that ω\aleph_\omega does not exist.

This is just a restatement of a fact we met last time: it is consistent with ETCS that there is no set with index ω\omega. What it tells us that if there are any models of ETCS at all, there is one in which the only sets are

0,1,2,, 0, 1, 2,. 0, 1, 2, \ldots, \aleph_0, \aleph_1, \aleph_2, \ldots.

That’s it. No more!

There’s a crucial characterization of the alephs that doesn’t mention index:

If W\aleph_W exists, then so does V\aleph_V for every VWV \prec W, and W\aleph_W is the smallest set > V\gt \aleph_V for every VWV \prec W.

For example, if ω\aleph_\omega exists then it is the smallest set with the property that ω> n\aleph_\omega \gt \aleph_n for every nn \in \mathbb{N}.

To see why this characterization holds, think about the order-equivalence

(Set ,)(alephable well-ordered sets,). (\mathbf{Set}_\infty, \leq) \simeq (\text{alephable well-ordered sets}, \preceq).

We know that among all well-ordered sets, the alephable ones are downwards closed. Now, it’s a triviality that any well-ordered set WW is the least well-ordered set V\succ V for every VWV \prec W. Transporting this trivial fact across the equivalence, from right to left, gives the characterization of W\aleph_W.

When people choose to denote a set by W\aleph_W rather than just XX or whatever, it’s usually because they want to see it as part of the succession of alephs

0, 1,, ω, ω+1,. \aleph_0, \aleph_1, \ldots, \aleph_\omega, \aleph_{\omega + 1}, \ldots.

The beginning part of that succession of alephs is displayed in what I called the “tautological bundle”. Last time I drew this picture for a set XX, where the fibre over an isomorphism class [A][A] is AA itself:

Tautological bundle of a set X

If instead we start with an alephable well-ordered set WW and put X= WX = \aleph_W, the picture becomes this:

Tautological bundle of a well-ordered set W

Here I’ve used the notation

w={vW:v<w} &#x21A1; w = \{ v \in W : v \lt w \}

when wWw \in W. It’s standard to write w\downarrow w for the set of elements less than or equal to ww; this is a variation on that notation. (If you want to use the double downwards arrow in the comments, I’m afraid the only way I know of getting it here is to use unicode: type “&#x21A1;” without the quotation marks.)

Every downwards closed proper subset of WW is of the form w&#x21A1; w for a unique wWw \in W. Equivalently, every well-ordered set W\prec W is isomorphic to w&#x21A1; w for a unique wWw \in W. So the fibres of p:EWp: E \to W are the alephs V\aleph_V for VWV \prec W.

The alephs that appear as the fibres here stop one short of W\aleph_W itself. If we want to get W\aleph_W as a fibre, we can do it by replacing WW by W +W^+. Then the picture is:

Tautological bundle of W-plus

Here I’ve lazily reused the letters EE and pp, which I shouldn’t really have done: they’re different from the EE and pp for WW. Anyway, the point is that the top fibre here is W\aleph_W.

All this gives another characterization of the alephs. Let WW be a well-ordered set. Then W\aleph_W exists if and only if there exist a set EE and function p:EW +p: E \to W^+ with the following property:

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

In that case, p:EW +p: E \to W^+ is determined uniquely up to isomorphism of sets over W +W^+, and the fibre over the top element of W +W^+ is W\aleph_W.

Summarizing what we’ve just seen and what we saw at the end of the last post, the following conditions on a model of ETCS are equivalent:

  • all alephs exist;

  • every well-ordered set is the index of some set;

  • the “Cantorian axiom”: for every well-ordered set WW, there exists a function p:EWp: E \to W into WW such that for all wWw \in W, the fibre p 1(w)p^{-1}(w) is the smallest infinite set >p 1(v)\gt p^{-1}(v) for all v<wv \lt w;

  • for every set II, there exists a function into II whose fibres are pairwise non-isomorphic.

I’ll finish by relating the condition “all alephs exist” to the existence of limits (which we met in Part 2). First:

All alephs exist implies unboundedly many weak limits.

“Unboundedly many” means that for every set XX, there is some weak limit at least as big as XX.

Why is this true, assuming all alephs exist?

Let XX be an infinite set. We can take an initial well-ordered set WW with underlying set XX. I claim that W\aleph_W does the job: that it’s a weak limit X\geq X.

First, W\aleph_W is a weak limit. “Initial” means that WW is the least well-ordered set of its cardinality, so WW can’t be a successor. Hence WW is a limit (as a well-ordered set). Now we saw last time that a set is a weak limit if and only if its index is a limit. Put another way, V\aleph_V is a weak limit if and only if VV is a limit, for well-ordered sets VV. So W\aleph_W is a weak limit.

All we have left to do is to show that WX\aleph_W \geq X. By construction, the underlying set U(W)U(W) of WW is XX, so our task is to show that

WU(W). \aleph_W \geq U(W).

This looks like this should be true by miles: after all, 0=\aleph_0 = \mathbb{N} is much bigger than \emptyset, and 1\aleph_1 is vastly bigger than 11, and ω\aleph_\omega is dramatically bigger than U(ω)=U(\omega) = \mathbb{N}, etc. In a couple of posts’ time, we’ll look in detail at the question of W\aleph_W versus U(W)U(W). In any case, the inequality we have to prove follows from the inequality KIK \preceq I mentioned near the start of the last post. I’m running out of steam now so I won’t explain how, but it only takes a couple of lines.

So, if all alephs exist then there are unboundedly many weak limits. What about the converse? It’s false:

It is consistent with ETCS + (there are unboundedly many weak limits) that not all alephs exist.

In other words, “all alephs exist” is strictly stronger than “there are unboundedly many weak limits”.

For the proof, I’ll want to talk not only about weak limits and alephs, but also strong limits and beths. So that’s going to have to wait until next time.

Next time

There are two standard ways to make a set XX bigger: take its successor X +X^+ or its power set 2 X2^X. The alephs are what you get by starting with \mathbb{N} and repeatedly taking successors. The beths are what you get by starting with \mathbb{N} and repeatedly taking power sets. We’ll meet the beths next time.

Posted at June 20, 2021 1:07 PM UTC

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

7 Comments & 1 Trackback

Re: Large Sets 5

I like this very much! But one thing that you did not mention (at least explicitly): for the case of ω\aleph_\omega, this will be the fibre over the top element of ω+1\omega+1. But ω\aleph_\omega is also the total space of the bundle over ω\omega. So I guess for limit ordinals α\alpha there should be a similar phenomenon. This seems to be another way to state that W\aleph_W exists.

Also, it’s trivial, but worth pointing out that in your last dot point in the list of things equivalent to the existence of all alephs (“function into II”), there’s an “off-by-ω\omega” effect. When quantifying over all II it’s invisible. But if one wants to get a specific W\aleph_W then II needs to either be bigger than WW by an initial copy of ω\omega, or one must specify the fibres of the function to II should be infinite.

(I’m being super picky, I know! But thinking of the pedagogical effect of these posts for people less used to axiomatic set theory)

Posted by: David Roberts on June 21, 2021 1:00 AM | Permalink | Reply to this

Re: Large Sets 5

Thanks, David. I agree with all that and appreciate you writing it. When deciding what to put in a post, there’s a constant tension between — on the one hand — explaining enough, being gentle, and saying all the things in my head, and — on the other — not explaining too much, not wittering on forever, and actually finishing writing the thing before my energy runs out. Fortunately, people make insightful comments that more than make up for shortcomings in the posts :-)

Posted by: Tom Leinster on June 21, 2021 10:34 AM | Permalink | Reply to this

Re: Large Sets 5

Thanks for this series, to which I have just caught up (on the main body of the exposition, not the comments).

I think that there is a typo. (I tried putting the sentence I’m about to quote in a blockquote environment, but then the parser complained about cdata in column 0. Who knows?) But, anyway, there’s a sentence “Transporting this trivial fact across the equivalence, from right to left, via gives the characterization of W\aleph_W.” Maybe ‘via’ does not belong?

Posted by: L Spice on June 22, 2021 9:34 PM | Permalink | Reply to this

Re: Large Sets 5

Indeed it doesn’t! Thank you.

Don’t know what’s up with the blockquoting. I tried it myself in a comment just now, using syntax like this:

Non-quoted text.

> Blockquoted text.

More non-quoted text.

…and it worked fine (in the preview at least). But sometimes these errors happen for reasons I don’t understand.

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

Re: Large Sets 5

That syntax may be the key.

Transporting this trivial fact across the equivalence, from right to left, via gives the characterization of W\aleph_W.

Indeed, that must be it. I had been trying to use <blockquote>.

Posted by: L Spice on June 22, 2021 11:55 PM | Permalink | Reply to this

Re: Large Sets 5

Hi, I’m an undergraduate student. I’m not very educated in math, but this series is so well-written that it is really easy to follow. But it inspires me many questions. I apologize in advance if my questions are trivial or don’t make much sense. I’d like to do not waste anyone’s time, so feel free to ignore this it’s too farfetched.

On of the reasons I like more this series is that I came at defining something like K(X)K(X) while asking myself if it was possible to define cardinality and statistic concepts more generally, but I was betrayed by my lack of formal education on category theory.

Q1. For example, why can’t we define cardinality more generally, but “internally” to “any” given category? The idea is that every category should be able to bring on the table its own intrinsic concept of number system, i.e., its cardinal arithmetic. For XCX\in C, for good categories (With internal hom and subobject classifier?) would be nice to have an object kXC\text{k}X\in C such that XYX\leq Y implies kXkY\text{k}X \leq \text{k} Y and a map # X:[X,Ω]kX\#_ X:[X,\Omega]\to \text{k} X

Let me try to convey my reasoning and motivation. Instead of naively starting by something like a function || C:CK(C)|-|_{C}:C\to K(C) where I take K(C)K(C) to be the isomorphism classes of objects of a category - I don’t think we can naturally extend this to a functor in general, e.g. for finite dim. vec. spaces we would need to chose a basis for every vec. space) - I tried to take k(X)={iso classes of subobjects of X}\text{k}(X)=\{\text{iso classes of subobjects of }X\} each object. This is like the definition in “part 4” but with non-strict inequality k(X)=K(X +)\text{k}(X)=K(X^+). In this case, we have for P(X)P(X) the power functor CSetC\to\boldsymbol{Set} a cardinality map (I think I proved it’s “natural” when C=SetC=\boldsymbol{Set}) # X:P(X)k(X)\#_X:P(X)\to \text{k}(X)

Q2. To what extent is it possible to define morphism X\oplus_X s.t. # X(pq) X# X(pq)=# X(p) X# X(q)\#_X(p\cup q)\oplus_X\#_X(p\cap q)=\#_X(p)\oplus_X\#_X(q)

Q3.Assume we can achieve this in general for a class of categories: what stops us from developing a kind of rudimental “theory of frequencies/statistic” in every category?

For example: given any CC-morphisms f:EBf:E\to B we would like to define its “first frequency” f #:BkEf^{\#}:B\to\text{k} E and its second frequency f #2=f ##:kEkBf^{\#2}=f^{\#\#}:\text{k} E\to \text{k} B. Given b:1Bb:1\to B and fixed f:EBf:E\to B take f 1b:=1× b,fEf^{-1}b:=1\times_{b,f}E regarded as an element of [E,Ω][E,\Omega] define f #=# Ef 1f^\#=\#_E\circ f^{-1} This was inspired heavily by learning how bundles were depicted as polynomials in the recent video “David Spivak: “Poly: a category of remarkable abundance.”” In fact the end game/question is to recover something like

# E(E)= b:1Bf #bkE\#_E(E)=\bigoplus_{b:1\to B}f^{\#}b \in \text{k}E

I need more structure to be defined but if it’s possible to define a multiplication map :kB×kEkE\cdot:\text{k}B\times \text{k}E\to \text{k}E and defined the degree of a bundle as δ(f:EB):=max b:1Bf #(b)kE\delta(f:E\to B):=\max_{b:1\to B} f^{\#}(b)\in \text{k}E then, let j,0 EkEj,0_E\in \text{k}E, I hope to achieve # E(E)= j=0 E δ(f)f #2(j)j\#_E(E)=\bigoplus_{j=0_E}^{\delta(f)}f^{\#2}(j)\cdot j

To complete the circle: assume we can define fractions in kB\text{k}B. If I see f:EBf:E\to B as a map yielding outcomes, a subobject i:IBi:I\to B as an “event” then I would define P f(i)= biP f(b)P f(id B)=# E(f 1i)# E(E)\mathsf{P}_f(i)=\frac{\displaystyle \bigoplus_{b\in i}\mathsf{P}_f(b) }{\mathsf{P}_f({id_B})}=\frac{\#_E (f^{-1}i)}{\#_E(E)}

Where P f(b)=f #(b)\mathsf{P}_f(b)=f^\#(b).

Best regards. V.

ps: I apologize for my bad english.

Posted by: V on June 23, 2021 12:49 PM | Permalink | Reply to this

Re: Large Sets 5

Excuse me, I messed up in the last lines. I had probelms with typesetting. The last formula is intended to be

P f(i)= bif #(b)f #(id B)=# E(f 1i)# E(E)\mathsf{P}_f(i)=\frac{\displaystyle \bigoplus_{b\in i}f^\#(b) }{f^\#({id_B})}=\frac{\#_E (f^{-1}i)}{\#_E(E)}

Posted by: V on June 23, 2021 1:02 PM | Permalink | Reply to this
Read the post Large Sets 6
Weblog: The n-Category Café
Excerpt: Introducing the beths.
Tracked: June 24, 2021 4:09 PM

Post a New Comment