### Large Sets 2

#### Posted by Tom Leinster

*Previously: Part 1. Next: Part 3*

The world of large cardinals is inhabited by objects with names like
*inaccessible*, *ineffable* and *indescribable*, evoking the vision of sets
so large that they cannot be reached or attained by any means we
have available. In this post, I’ll talk about the smallest sets that cannot
be reached using the axiom of ETCS: limits.

Most of the ETCS axioms assert the existence of certain sets, either outright or constructed from other sets and functions between them. Informally, those axioms say:

We have sets $0$, $1$, $2$ and $\mathbb{N}$.

For any sets $A$ and $B$, we have their product $A \times B$.

For any sets $A$ and $B$, function $f: A \to B$, and $b \in B$, we have the fibre $f^{-1}(b)$.

For any sets $A$ and $B$, we have the set $B^A$ of functions from $A$ to $B$.

(That accounts for seven of the ten ETCS axioms, in the form I listed them last time. The other three axioms are that sets and functions form a category, a function is determined by its effect on elements, and the axiom of choice.)

We can use the axioms of ETCS to build new sets, such as $\mathbb{N}^{2^{\mathbb{N}}}$. But we can also contemplate sets that are too big to be constructed in this way — that “cannot be reached from below”.

Here “big” refers to the relation $\leq$ on sets, defined by $X \leq Y$ if and only if there exists an injection $X \to Y$. Strict inequality $X \lt Y$ means that $X \leq Y$ and $X$ is not isomorphic to $Y$. The Cantor–Bernstein theorem tells us that $X \leq Y \leq X$ if and only if $X \cong Y$, so another way to say $X \lt Y$ is “$X \leq Y$ but not $Y \leq X$”.

A set $X$ that “cannot be reached from below” using ETCS is one with the following properties:

$0 \lt X$, $1 \lt X$, $2 \lt X$ and $\mathbb{N} \lt X$.

For any sets $A \lt X$ and $B \lt X$, we have $A \times B \lt X$.

For any sets $A \lt X$ and $B \lt X$, function $f: A \to B$, and $b \in B$, we have $f^{-1}(b) \lt X$.

For any sets $A \lt X$ and $B \lt X$, we have $B^A \lt X$.

There’s loads of redundancy in this list — for example, $A \times B \cong max(A, B)$ when $A$ and $B$ are infinite, so the item about products can be skipped. It’s easy to see that $X$ satisfies all these conditions if and only if it satisfies just these two:

$\mathbb{N} \lt X$;

for any sets $A \lt X$ and $B \lt X$, we have $B^A \lt X$.

A set $X$ satisfying the first condition is, of course, said to be
uncountable. An infinite set $X$ satisfying the second condition is said to
be a **strong limit**.

(I’ll come back to that word “strong” later.)

This definition of strong limit is still a bit redundant. Since $B^A \leq max(2^A, 2^B)$ for infinite sets $A$ and $B$, it’s equivalent to define an infinite set $X$ to be a strong limit if and only if:

- for any set $A \lt X$, we have $2^A \lt X$.

And in fact, that’s how the definition of strong limit is usually phrased.

For example, $\mathbb{N}$ is a strong limit. But no power set $2^A$ is a strong limit, since $A \lt 2^A$ and $2^A \nless 2^A$. So none of $2^{\mathbb{N}}$, $2^{2^{\mathbb{N}}}$, … is a strong limit.

Are there any strong limits apart from $\mathbb{N}$? That is, are there any uncountable strong limits?

Well, it’s almost in the definition that the existence of uncountable strong limits can’t be proved in ETCS, unless ETCS is inconsistent. Here’s why.

Take a model of ETCS, that is, a category satisfying the ETCS axioms. Let’s temporarily say that a set (in this model) is “small” if it is strictly smaller than every uncountable strong limit. Then the small sets are also a model of ETCS. For example, if $A$ and $B$ are small then for every uncountable strong limit $X$, we have $A \lt X$ and $B \lt X$, therefore $B^A \lt X$; hence $B^A$ is small. So we’ve shown:

For any model of ETCS, the sets smaller than every uncountable strong limit are also a model of ETCS.

This immediately implies a simple independence result:

It is consistent with ETCS that there are no uncountable strong limits.

For if ETCS is consistent then we can take a model of it and cut down to the model consisting of just the “small” sets. And by construction, that cut-down model of ETCS contains no uncountable strong limit.

Let me digress for a moment on the “strong” terminology. In set theory,
there are two standard ways of making a set $A$ slightly bigger. One is to
take its power set, $2^A$. The other is to take the smallest set strictly
bigger than $A$, denoted by $A^+$ (the **successor** of $A$). A priori,
there is no reason to expect that $A^+$ and $2^A$ should be the same, and
we’ve known since Cohen that, in fact, they needn’t be. So whenever we see
something interesting involving power sets, we can ask what would happen if
we replaced them by successors, and vice versa.

In particular, we can make this replacement in the definition of strong
limit. Thus, an infinite set $X$ is said to be a **weak limit** if:

- for any set $A \lt X$, we have $A^+ \lt X$.

It should be clear that every strong limit is a weak limit. It’s also
nearly immediate that an infinite set is a weak limit if and only if it is
*not* the successor of anything. That is, every infinite set is a weak
limit or a successor, but not both.

If there are any models of ETCS at all, there’s one in which the generalized continuum hypothesis holds, i.e. $A^+ = 2^A$ for all infinite sets $A$. In such a model, weak limit $=$ strong limit, so by the result above:

It is consistent with ETCS that there are no uncountable weak limits.

That’s the end of the digression on weak limits. However, I want to point
out that when I defined $A^+$, I implicitly assumed the fact that any
family $(A_i)_{i \in I}$ of sets, indexed over some nonempty set $I$, has a
smallest member. (For without this fact, how would we know that there’s a
*smallest* set strictly bigger than $A$?) This can be proved using Zorn’s
lemma, or by arbitrarily well-ordering each member.

The fact that every nonempty family of sets has a smallest element is extremely important, and I’ll use it over and over again throughout these posts.

For example, it tells us that if (in a given model of ETCS) there are any uncountable strong limits at all, there is a smallest one. So earlier, when I wrote this —

Let’s temporarily say that a set (in this model) is “small” if it is strictly smaller than every uncountable strong limit

— it can be understood as follows. If there are no uncountable strong limits, then every set is small. If there is an uncountable strong limit, then there is a least one, $X$, and a set $A$ is small if and only if $A \lt X$.

In fact, it’s easy to describe the smallest uncountable strong limit, assuming there are any uncountable strong limits at all. We know that every uncountable strong limit is bigger than all of

$\mathbb{N}, 2^{\mathbb{N}}, 2^{2^{\mathbb{N}}}, \ldots.$

Since this sequence of sets has an upper bound, it has a *least* upper
bound or supremum. Call it $X$. You should be able to convince yourself
that $X$ is an uncountable strong limit. So, $X$ is the *smallest*
uncountable strong limit. The standard name for $X$ is $\beth_\omega$, and
I’ll say much more about it in future posts.

One last general point. At the risk of sounding slow — a risk that
any mathematical blogger constantly exposes themselves to — it
took me a while to really appreciate that despite the extreme
structurelessness of sets, *infinite sets can have different qualities*. They may just be bags of featureless dots, but even bags of featureless dots can have distinctive features.

Here I’m contrasting “quality” with “quantity”. Of course, there are
basic properties of sets such as uncountability that refer to being
bigger or smaller than some threshold. But my point is that there are
natural, important properties of sets that *appear and disappear as you
climb the ladder*. Being a strong limit is one such property:
$\mathbb{N}$ is, $2^{\mathbb{N}}$ isn’t, $2^{2^{\mathbb{N}}}$ isn’t, etc.,
until you reach the supremum $\beth_\omega$, which is again. Later posts
will introduce several more such properties.

#### Next time

However you like to approach set theory, well-ordered sets arise inevitably, and they’re my topic for next time.

## Re: Large Sets 2

How much choice do you need for the statement that every family of sets has a smallest member? How far can you get with, say, only DC?