## June 29, 2021

### Large Sets 7

#### Posted by Tom Leinster

Previously: Part 6. Next: Part 8

Given a well-ordered set $W$, there are at least two ways of manufacturing a plain, unadorned set. You can, of course, take the underlying set $U(W)$. But you can also take the beth $\beth_W$. How do they compare in size?

Let’s look at some of the first few cases, recalling that when $n$ is a natural number, $\beth_n$ means $\beth_W$ for the unique well-ordered set $W$ with $n$ elements.

• $\beth_0$ is $\mathbb{N}$, the smallest infinite set, whereas $0$ is the empty set.

• $\beth_1$ is the uncountable set $2^\mathbb{N}$, whereas $1$ is the well-ordered set with only one element.

• $\beth_4 = 2^{2^{2^{2^{\mathbb{N}}}}}$ is probably bigger than any specific set used by 95% of mathematicians in a lifetime, whereas $4$ has, well, just four elements.

So comparing $\beth_W$ with $U(W)$ seems like racing an intercontinental ballistic missile against a snail — or more traditionally, a hare against a tortoise.

Unlike in the fable, our tortoise never overtakes the hare. But it’s conceivable that it does keep catching up, only to fall behind again an instant later. Moments when the tortoise catches the hare are called “beth fixed points”, and they’re our topic for today.

We can begin to understand how the race looks by going through an inductive proof that the tortoise never overtakes the hare:

$\beth_W \geq U(W)$

for all well-ordered sets $W$. (Apparently our hare is called Beth.) To avoid distracting complications, I’ll assume in the proof that all beths exist.

This inductive proof splits into three cases, according to the three kinds of well-ordered set:

• Suppose that $W$ is empty. Then $\beth_W \cong \mathbb{N}$ and $U(W) \cong \emptyset$. Obviously $\mathbb{N} \geq \emptyset$: the hare begins with a head start.

• Suppose that $W$ is a successor, say $W = V^+$. Then $\beth_W = 2^{\beth_V} \gt \beth_V$. What about $U(W)$? If $W$ is finite then $U(W) \cong U(V) + 1$, but the increase by $1$ doesn’t make a difference: the tortoise $U(W)$ hasn’t even reached the starting point $\mathbb{N}$ of the hare. And if $W$ is infinite then $U(W) \cong U(V)$, so the tortoise stands still while the hare leaps ahead. Whether $W$ is finite or infinite, the hare’s lead over the tortoise gets bigger.

• Finally, suppose that $W$ is a limit. Then $\beth_W$ is the smallest set such that $\beth_W \geq 2^{\beth_V}$ for all $V \prec W$. Now turning to the underlying sets, it can happen that $U(W)$ is strictly larger than $\sup_{V \prec W} U(V)$ — for example, if $W$ is the smallest uncountable well-ordered set. But because there are well-ordered sets of every cardinality, $U(W)$ can’t be any larger than the successor of that supremum. I leave the remaining details of the induction to you, but the point is that when $W$ is a limit, $U(W)$ is sometimes slightly bigger than $U(V)$ for all previous well-ordered sets $V$: the tortoise may, if it feels like it, take a small step forward.

A well-ordered set $W$ such that $\beth_W$ exists and is $\cong U(W)$ is called a beth fixed point, and what I’ve said so far may make it seem unlikely that there are any beth fixed points at all.

But there’s another way to look at things that makes the existence of beth fixed points much more plausible. To explain it, I’ll need to do a quick recap of some stuff on well-ordered sets that I wrote about at leisure in Part 3.

So: writing $\preceq$ for the usual preorder on well-ordered sets, a well-ordered set $W$ is initial if it’s $\preceq$-least of its cardinality (that is, $W \preceq W'$ for any well-ordered set $W'$ such that $U(W) \cong U(W')$). For every set $X$, there is an initial well-ordered set $I(X)$ with underlying set $X$, and it’s unique up to isomorphism. This defines a left adjoint $I$ to the underlying set functor $U$:

$I: (\mathbf{Set}, \leq) \rightleftarrows (\mathbf{WOSet}, \preceq): U.$

Both categories appearing in this adjunction are large preorders. In particular, $\mathbf{Set}$ isn’t the ordinary category of sets! Its objects are sets, there’s one map $X \to Y$ if $X \leq Y$, and there are no maps $X \to Y$ otherwise.

The adjunction $I \dashv U$ restricts to an equivalence

$I: (\mathbf{Set}, \leq) \rightleftarrows (\text{initial well-ordered sets}, \preceq): U.$

So, sets and initial well-ordered sets are interchangeable, as long as the only aspect of sets we’re interested in is cardinal inequality.

Now let $W$ be a beth fixed point:

$\beth_W \cong U(W).$

Then $W$ must be an initial well-order: for if $V$ is another well-ordered set with $V \prec W$ and $U(V) \cong U(W)$, then

$\beth_V \lt \beth_W \cong U(W) \cong U(V) \leq \beth_V,$

So the beth fixed points are certain initial well-ordered sets. And since initial well-ordered sets are in canonical one-to-one correspondence with sets, we might as well work with sets instead. In other words, define a set $X$ to be a beth fixed point if $\beth_{I(X)}$ exists and

$\beth_{I(X)} \cong X.$

We’ve defined the property of being a “beth fixed point” for both sets and well-ordered sets. The two definitions hang together nicely. That is, a set $X$ is a beth fixed point if and only if the well-ordered set $I(X)$ is a beth fixed point. Equivalently, a well-ordered set $W$ is a beth fixed point if and only if it is initial and the set $U(W)$ is a beth fixed point.

One advantage of this reformulation is that it lets us use our pre-existing intuition about fixed points. Rather than looking for points of equality of the two operations

$\beth_\bullet, U: (\text{well-ordered sets}) \to (sets),$

we can look for fixed points of the single operation

$\beth_{I(-)}: (sets) \to (sets).$

And now our intuition kicks in! In a geometric context, given an operation $f: S \to S$ on some kind of space $S$, how might we look for fixed points of $f$? The simplest way is to choose a point $s_0$ and iterate:

$s_0, f(s_0), f(f(s_0)), \ldots.$

If we’re lucky, this sequence has a limit, $s$. If we’re doubly lucky, $f$ is continuous enough that it preserves this limit. Then $s$ is a fixed point of $f$.

Let’s see if we can construct a beth fixed point by this strategy. Again, to keep things simple, I’ll assume that all beths exist in our model. Choose your favourite set $X$, and consider the sequence $(B_n)_{n \in \mathbb{N}}$ of sets given by

$B_0 = X, \quad B_{n + 1} = \beth_{I(B_n)}.$

If this sequence has a supremum — call it $B$ — then it is in fact preserved by $\beth_{I(-)}$, by a little argument that I’ll skip. So, $B$ is then a beth fixed point!

For example, if we start at $X = \emptyset$, then

$B_0 = \emptyset, \quad B_1 = \beth_0 = \mathbb{N}, \quad B_2 = \beth_{I(\mathbb{N})} = \beth_\omega, \quad B_3 = \beth_{I(\beth_\omega)}, \ldots.$

And if the $B_n$s have a supremum, $B$, then it must actually be the smallest beth fixed point.

We seem to have shown not only that a beth fixed point exists, but that there’s an abundance of them, unboundedly many of them: given any set $X$, we constructed a beth fixed point $B$ at least as big as $X$. However, the argument only goes through if the sequence has a supremum (which in ETCS is the same as saying that the sequence is defined). And this isn’t guaranteed, as we’ll see.

But before that, let’s pause to ask:

What’s the point of all this?

Is there any reason to compare $\beth_W$ with $U(W)$, or to ask whether they’re ever the same, other than general curiosity?

I claim that there is, that we’re more or less forced to consider beth fixed points as soon as we’ve accepted the idea of iterating the power set construction.

What this comes down to is a general point about axiomatic set theory. Suppose, for instance, that we’re interested in ETCS plus certain other axioms. Then it’s natural to ask which sets are too large to be constructed or accessed using our axioms. More exactly, call a set $X$ “unreachable” if the sets $\lt X$ are a model of ETCS plus our other axioms. Then the question becomes, which sets are unreachable? Can we characterize them directly?

For example, if we’re considering ETCS alone with no further axioms, we saw in Part 2 that the “unreachable” sets are the strong limits. That is, a set $X$ is a strong limit if and only if the sets $\lt X$ are a model of ETCS.

Now, what about ETCS plus the axiom “all beths exist”? Which sets are unreachable with respect to this axiomatic system? The answer is the beth fixed points. In other words:

A set $X$ is a beth fixed point if and only if the sets $\lt X$ are a model of ETCS + (all beths exist).

This provides a different motivation for the concept of beth fixed point, quite separate from hares and tortoises.

Here’s a proof of the “only if” direction. (I leave “if” to you.) Let $X$ be a beth fixed point. We have to show that the sets $\lt X$ are a model of ETCS + (all beths exist).

The first observation is this:

Every beth fixed point is an uncountable strong limit.

Indeed, the well-ordered set $I(X)$ is a limit, from which it follows that $\beth_{I(X)}$ is a strong limit. But $X \cong \beth_{I(X)}$, so $X$ is a strong limit; and uncountability is easy. Hence the sets $\lt X$ are a model of ETCS.

Now we have to show that in this model, all beths exist. In other words, given a well-ordered set $W$ such that $U(W) \lt X$, our task is to show that $\beth_W$ exists and is $\lt X$.

By adjointness, $U(W) \lt X$ implies that $W \prec I(X)$. Now $\beth_{I(X)}$ exists (that was part of the definition of $X$ being a beth fixed point), so $\beth_W$ exists, and it follows from the definition of the beths that $\beth_W \lt \beth_{I(X)}$. But $\beth_{I(X)} \cong X$, so $\beth_W \lt X$, as required.

From this result, we get a little independence theorem:

It is consistent with ETCS + (all beths exist) that there are no beth fixed points.

The proof follows a pattern that we’ve already seen a few times before. Take a model of ETCS + (all beths exist). Call a set in this model “small” if it is $\lt$ every beth fixed point. It follows from the result above that the small sets are a model of ETCS + (all beths exist), and by construction, this model contains no beth fixed points. QED!

One can also consider aleph fixed points, defined in the obvious way. Since

$U(W) \leq \aleph_W \leq \beth_W,$

any beth fixed point is an aleph fixed point. Much of what I’ve written here about beth fixed points can be repeated for aleph fixed points. But I don’t have anything special to say about the aleph case, so I’ll stop here.

#### Next time

Some of cardinal arithmetic is “trivial”, in the sense that

$X + Y \cong X \times Y \cong \max(X, Y)$

for infinite sets $X$ and $Y$. Next time, I’ll talk about the part that isn’t. We’ll look at exponentiation, infinite sums and products, cofinality, and the division of sets into regular and singular. And I’ll mention a completely wrong intuition about cardinal arithmetic that I carried around with me for years.

Posted at June 29, 2021 3:47 PM UTC

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

### Re: Large Sets 7

One could probably get even larger cardinsls by postulating the existence of limit sets from iterating the beth fixed point endofunctor $X \mapsto \beth_{I(X)}$ in the same way that one did by iterating exponentiation by the booleans $X \mapsto 2^X$. And then one could postulate an endofunctor $X \mapsto F(X)$ that takes sets to a limit set of iterating $\beth_{I(X)}$, and the existence of fixed points of $F(X)$.

One could then postulate a family of endofunctors $G:\mathbb{N}\rightarrow (Set \rightarrow Set)$ where $G(0)(X) = 2^X$, $G(1)(X) = \beth_I(X)$, $G(2)(X) = F(X)$, and so forth, iteratively defined by repeating the procedure above for $G(n)(X)$ to get $G(n+1)(X)$.

### Re: Large Sets 7

Something that I find myself musing upon when reading the posts up to this point is the reliance upon the fact that $X \lt 2^{X}$. Suppose that we instead work constructively. One can make sense of Cantor’s diagonalisation argument to some extent constructively, but I don’t think one can conclude that $X \lt 2^{X}$ (one does for elementary reasons have that $X \leq 2^{X}$).

What if we imposed in a constructive setting (sufficiently weak that one cannot obviously get a contradiction by the usual argumentation) that there is a bijection between $\mathbb{N}$ and $2^{\mathbb{N}}$? This would obviously completely change the situation discussed in the blog posts; one would never really get off the ground.

Is there some obvious way in which taking the existence of such a bijection as an axiom is nonsensical?

If not, it would sort of make the infinite set hierarchy (up to the level of universes at least) feel philosophically a little like sophistry…

Posted by: Richard Williamson on July 2, 2021 3:34 PM | Permalink | Reply to this

### Re: Large Sets 7

Or, maybe better, rather than imposing a bijection between $\mathbb{N}$ and $2^{\mathbb{N}}$ (which maybe one can in fact use constructive versions of diagonalisation to get a contradiction from, at least a sufficiently strong version of constructivity), impose that $2^{\mathbb{N}} \lt \mathbb{N}$.

Posted by: Richard Williamson on July 2, 2021 3:41 PM | Permalink | Reply to this

### Re: Large Sets 7

One can make sense of Cantor’s diagonalisation argument to some extent constructively, but I don’t think one can conclude that $X \lt 2^{X}$.

Can’t you? I guess we’d have to agree on how to define $\lt$ in a constructive setting, but if $X \lt Y$ means there exists an injection from $X$ to $Y$ but there does not exist an injection from $Y$ to $X$, then I think you can prove this constructively using Lawvere’s fixed point theorem.

Posted by: Todd Trimble on July 2, 2021 9:45 PM | Permalink | Reply to this

### Re: Large Sets 7

Yes, the diagonalization argument works fine constructively for that. I can’t think offhand of another way to constructively define $\lt$. (Of course, it won’t have all the properties of the classical version.)

Posted by: Mike Shulman on July 3, 2021 5:17 AM | Permalink | Reply to this

### Re: Large Sets 7

It is definitely the case that what we take to be constructive is very relevant here. I’ll try to outline the kind of thing I had in mind in a few different ways.

The most ‘mainstream’ way to think about it is probably with regard to predicativity. There are different flavours of predicativity; some will reject the axiomatic construction of function sets, for instance, which will prevent even Lawvere’s fixed point theorem being used. Indeed, Lawvere’s fixed point theorem (in, for instance, the form: if there is a surjection $\mathbb{N} \rightarrow 2^{\mathbb{N}}$, then every map $\mathbb{N} \rightarrow \mathbb{N}$ has a fixed point) relies rather fundamentally on exactly the kind of argumentation which a predicativist who rejects the axiomatic assumption of the existence of function sets would reject, because it assumes some unknown surjection amongst a set of functions which is also ‘unknowable’ in its totality.

But even if one admits function sets and admits Lawvere’s fixed point theorem, there are, for instance, issues around what we wish $2^{\mathbb{N}}$ to mean. Is it the function set where $2$ is a two element set? Or the function set where $2$ is really meant to be the set of truth values? Or the power set (set of all subsets) of $\mathbb{N}$? These things are not necessarily the same (not only to a predicativist, but to many types of constructivist; that the first two are not the same would be common to almost any type of constructivist).

If we work with power sets, our predicativist will have all kinds of objections; these are rejected in more or less all flavours of predicativism.

But with either of the other two options, the proof of Theorem 3.3 at the nLab page Cantor’s theorem completely breaks down; it is really using the fact that a power set is a set of subsets.

Moreover, there definitely is an injection $\mathbb{N}^{\mathbb{N}} \rightarrow \mathbb{N}$ in certain forms of constructive mathematics (there is paper of Bauer on exactly this, working in a realisability topos). So there is at the very least something very special constructively about the set $T$ of truth values if we claim that there is a proof that there is no injection $T^{\mathbb{N}} \rightarrow \mathbb{N}$, and I think one can see this specialness as unconvincing: the set of truth values is (constructively) something more complicated and difficult to pin down than $\mathbb{N}$. It is not clear from a predicative-like standpoint that it makes sense to work with it as a totality, or to take that negation has no fixed point as a provable fact. But even if one is not a predicativist, I think one should be very careful.

In a less mainstream way, I think there are a number of other issues. One is around the definition of $\lt$. To a philosophical constructivist concerned with meaning (over and above trying to make a definition in a formal system), $X \lt 2^{X}$ should mean that there is an injection from $X$ to $2^{X}$ with the property that there is provably (where the proof here is constructively meaningful, e.g. some kind of algorithm is involved) an element of $2^{X}$ which is not in the image of this injection. There is no semantically valid justification that I see (i.e. no argument rooted in the philosophical/pre-formal understanding of proofs as constructively meaningful) that this is equivalent to saying that there is no injection $2^{X} \rightarrow X$. And thus if a formal system does prove this, it cannot be constructive according to our philosophical/pre-formal standard. I think the above nLab page, which was mainly written by Toby Bartels, is trying to make something like this point; it is to me a little difficult to follow, but I think it is suggesting that even if one does accept that there is no injection $2^{\mathbb{N}} \rightarrow \mathbb{N}$, this does not necessarily justify concluding that $\mathbb{N} \lt 2^{\mathbb{N}}$.

I think I’ll stop here as this comment is already long; hopefully something of this gives some idea as to why I think skepticism towards $\mathbb{N} \lt 2^{\mathbb{N}}$ might not be completely unjustifiable. To get back to my original comment, suppose for example that one is a predicativist and rejects power sets, and that one imposes as an axiom that $2^{\mathbb{N}} \lt \mathbb{N}$. Can one prove that anything goes wrong?

Or even if you are a classical mathematician, suppose that we adopt some kind of ‘paraconsistent’ position, and that I say to you that you are not allowed to use the fact that both $2^{\mathbb{N}} \lt \mathbb{N}$ and $\mathbb{N} \lt 2^{\mathbb{N}}$ is a contradiction, or any fact which admits a proof involving Lawvere’s fixed point theorem (where you intepret this honourably, and thus do not just chuck it in as a redundant hypothesis, etc). Can you find some other contradiction if you assume that $2^{\mathbb{N}} \lt \mathbb{N}$?

Posted by: Richard Williamson on July 3, 2021 10:37 PM | Permalink | Reply to this

### Re: Large Sets 7

If predicativism was a principal concern, then why didn’t you say so at the outset? :-)

So much of categorical reasoning seems impredicative by its very nature, and I’ve never really understood what makes predicativism a compelling consideration. But this is not an argument, just a plea of ignorance. I.e., I’ll bow out. I do recall that Mike and Toby had a series of conversations at the nForum in which Mike wound up saying something like at least he now better appreciated the predicativist attitude (sorry Mike for putting words in your mouth, and for my bad memory!). I wasn’t trying to follow their conversation closely.

Posted by: Todd Trimble on July 3, 2021 11:41 PM | Permalink | Reply to this

### Re: Large Sets 7

Predicativism is actually not a principal concern for me personally, but people often do not like/understand/engage with the more philosophical argument I outlined in the second half of my second comment (about having consistent meaning), so I gave one example of a way in which objections can be raised in an ordinary formal framework.

Several aspects of my second comment, excluding the more philosophical part, are independent of predicitavism, as I tried to point out. And as I wrote at the very end, one can also arrive at the kind of question I wished to raise in my original comment even in completely classical mathematics; I wouldn’t be surprised if this ‘paraconsistent’ formulation needs some tightening before one really gets to the heart of what I’m asking, but the dialogue in doing so might be interesting.

Posted by: Richard Williamson on July 4, 2021 6:33 AM | Permalink | Reply to this

### Re: Large Sets 7

I confess that I don’t know what predicativism means (that isn’t a request), but I understood the final paragraph of this comment

Or even if you are a classical mathematician…

— to be a challenge aimed at those like me who are ignorant of all that stuff. However, I don’t understand the rules of the game.

The challenge is to derive a contradiction from $2^\mathbb{N} \lt \mathbb{N}$ without using certain kinds of argument. Normally I’d take as part of the definition of $X \lt Y$ that there is no injection $Y \to X$; but since there certainly is an injection $\mathbb{N} \to 2^\mathbb{N}$, that can’t be the definition you have in mind. Earlier in the comment, you write:

To a philosophical constructivist concerned with meaning […], $X \lt 2^X$ should mean that there is an injection from $X$ to $2^X$ with the property that there is provably […] an element of $2^X$ which is not in the image.

Suppose we take that as a definition of $\lt$, generalizing from $X$ and $2^X$ to an arbitrary pair of sets $X$ and $Y$. Then $\mathbb{N} \lt \mathbb{N}$, since the successor function is an injection whose image provably doesn’t contain $0$. And “$\mathbb{N} \lt \mathbb{N}$” simply conflicts with the accepted definition of $\lt$.

So I don’t understand what definition of $\lt$ I’m meant to be using in that final paragraph.

Or should it be a $\leq$? I can see that it’s a challenge to derive a contradiction from $2^\mathbb{N} \leq \mathbb{N}$ “directly”, in the sense of working with a hypothetical injection $2^\mathbb{N} \to \mathbb{N}$ rather than a hypothetical surjection $\mathbb{N} \to 2^\mathbb{N}$. (I seem to remember trying that before and not getting an answer I liked much.) Is that essentially the question here?

Posted by: Tom Leinster on July 4, 2021 11:27 AM | Permalink | Reply to this

### Re: Large Sets 7

Thanks for thinking about the challenge!

Normally I’d take as part of the definition of $X \lt Y$ that there is no injection $Y \lt X$; but since there certainly is an injection $\mathbb{N} \rightarrow 2^{\mathbb{N}}$, that can’t be the definition you have in mind.

Actually this is fine. The rules of the game as I stated them are that you are not allowed to use the fact that both $\mathbb{N} \lt 2^{\mathbb{N}}$ and $2^{\mathbb{N}} \lt \mathbb{N}$ hold is a contradiction, i.e. you are not allowed to use ex falso quodlibet (falsity implies everything) in the case of this proof of falsity; and you are not allowed to appeal to Lawvere’s fixed point theorem anywhere. The contradiction that you mentioned, if not strictly encompassed by these rules, is in the spirit of them, and you can perfectly well use the usual definition of $2^{\mathbb{N}} \lt \mathbb{N}$; you are just not allowed to use ex falso quodlibet in the case of having and not having an injection $\mathbb{N} \rightarrow 2^{\mathbb{N}}$. Similarly with any other such ‘immediate’ contradictions if I’m overlooking any more.

Concerning…

Then $\mathbb{N} \lt \mathbb{N}$, since the successor function is an injection whose image provably doesn’t contain 0.

…the definition I made was only intended to be used in a constructive setting, and does, as you observe, behave differently to the classical one. One can perfectly well have both $X \lt Y$ and $Y \lt X$ for example, as well as $X \lt X$. This is just a different kind of mathematics. It does indeed not make much sense to use it for the challenge I posed.

Regarding…

Is that essentially the question here?

…yes, unless I’m overlooking something, that sounds like what I’m getting at :-).

On a completely different note, iust in case somebody missed it, I’d just like to emphasise again something that I mentioned in my long second comment, namely that there is provably (in completely classical mathematics!) an injection $\mathbb{N}^{\mathbb{N}} \rightarrow \mathbb{N}$ in the internal logic of a realisability topos (roughly speaking: a flavour of constructivity formalising a strong notion of computation). Consider this in the light of some of the observations in Tom’s Large Sets 8. It is clear that at the very least some of the classical theory of cardinality must be ‘sophistry’, i.e. infinite sets do not have to behave exactly as in ‘classical’/’ordinary’ mathematics, for one cannot have that injection $\mathbb{N}^{\mathbb{N}} \rightarrow \mathbb{N}$ and have all aspects of the classical theory of cardinality; at least something has to give.

Posted by: Richard Williamson on July 5, 2021 12:08 AM | Permalink | Reply to this

### Re: Large Sets 7

Richard,

you seem to be wanting to do this not in predicative mathematics, but with a foundation based in relevance logic, which rejects EFQ.

Lawvere’s diagonal argument is purely algebraic. It doesn’t even need the existence of hom-sets, and concludes that given a fixed-point-free endomorphism $\sigma$ of $Y$, for every function $F\colon X\times X \to Y$ there is an explicit function $X\to Y$ (finitarily!) constructed from $\sigma$ and $F$ that is not equal to any of the functions $F(x,-)$, for $x\in X$. The proof works in great generality (indeed more than I stated, I’ve got a short note in preparation that goes into this). One can take $X=Y=\mathbb{N}$, for instance.

If one allows $Y^X$, then one can construct from every function $X\to Y^X$ an element of $Y^X$ that is not in the image of that function. Again, this works for an arbitrary cartesian closed category, for example any well-pointed $\Pi W$-pretopos, which is a weakly impredicative setup for set theory (weakly in that it’s cartesian closed, but with no subobject classifier).

The first version works for a general well-pointed $W$-pretopos, which corresponds to a strongly predicative system.

What goes wrong in having injections both ways is that the CSB theorem breaks down, at least in the example from Bauer, since that’s not a boolean topos, and booleanness is required for CSB.

Also, no one seems to have mentioned that in a constructive setting, a more fruitful comparison of size $X \leq Y$ is when $X$ is a subquotient of $Y$. This includes both the “exists an injection” definition (the standard $\leq$, and the “exists a surjection” defintion (set theorists $\leq^*$, which is sometimes used in the absence of Choice, and then no longer the same as $\leq$), but which works without excluded middle. It’s like “subfinitely indexed”.

Going back to

Lawvere’s fixed point theorem (in, for instance, the form: if there is a surjection $\mathbb{N} \rightarrow 2^{\mathbb{N}}$, then every map $\mathbb{N} \rightarrow \mathbb{N}$ has a fixed point) relies rather fundamentally on exactly the kind of argumentation which a predicativist who rejects the axiomatic assumption of the existence of function sets would reject, because it assumes some unknown surjection amongst a set of functions which is also ‘unknowable’ in its totality.

The proof, again, works in a well-pointed $\Pi W$-pretopos, hence assuming function sets. But if function sets are too much for this hypothetical strong predicativist, then this version works in any well-pointed $(W)$-pretopos, and indeed in any well-pointed cartesian category: Suppose there is a function $F\colon X\times X\to Y$ such that for the endomorphism $\sigma\colon Y\to Y$, the function $X\stackrel{\Delta}X\times X\stackrel{F}{\to} Y\stackrel{\sigma}{\to} Y$ is equal to some $F(x_\sigma,-)$, for some $x_\sigma\in X$. Then $\sigma$ has a fixed point. The only thing here that is mildly objectionable is the existential quantifier on the $x_\sigma\in X$. If that is instantiated in a constructive way, namely there is an algorithm to find it, then the fixed point of $\sigma$ is entirely constructive.

I should point out that I keep saying well-pointed, since Lawvere’s theorem is really about the well-pointed quotient of a cartesian category. If one wants to work in the internal logic of a non-well-pointed topos, say, then global points should be interpreted as being taken in the filterquotient construction instead. Or more generally, by Mike’s work on stack semantics, every reasonable category that could correspond to sets (probably any pretopos) is internally well-pointed, so take these arguments as living in there.

Posted by: David Roberts on July 5, 2021 2:46 AM | Permalink | Reply to this

### Re: Large Sets 7

Arg a typo: it should be “$\stackrel{\Delta}{\to}X\times X\stackrel{F}{\to} Y\stackrel{\sigma}{\to} Y$ is equal to some $F(x_\sigma,-)$,…”

Posted by: David Roberts on July 5, 2021 2:56 AM | Permalink | Reply to this

### Re: Large Sets 7

I’ve just realized that there’s something nice I could have said in this post and didn’t.

One way to characterize infinite sets is this: they’re the sets $X$ such that there exists a non-injective surjection $X \to X$. “Non-injective surjection” means that each fibre has at least one element, and at least one fibre has at least two elements.

A set $X$ is an aleph fixed point iff it satisfies a similar but massively stronger condition. There has to exist a function $X \to X$ that is surjective and really spectacularly non-injective: the fibres are not only infinite, but all have different cardinalities. So the larger $X$ is, the bigger some of the fibres are going to have to be, hence the further from injective our function is.

Beth fixed points can be characterized similarly, strengthening the “different cardinalities” condition on the fibres to “$2^{X_i} \leq X_j$ or $2^{X_j} \leq X_i$ for all $i \neq j$”, where $X_i$ is the $i$th fibre.

Posted by: Tom Leinster on July 5, 2021 9:40 PM | Permalink | Reply to this
Read the post Large Sets 9.5
Weblog: The n-Category Café
Excerpt: On hyper-inaccessible and Mahlo sets
Tracked: July 8, 2021 4:54 AM
Read the post Large Sets 12
Weblog: The n-Category Café
Excerpt: Replacement is a natural supplement to ETCS.
Tracked: July 18, 2021 8:13 PM
Read the post Borel Determinacy Does Not Require Replacement
Weblog: The n-Category Café
Excerpt: Despite what they say.
Tracked: July 24, 2021 1:44 AM

Post a New Comment