Why do we need "canonical" well orders?

Question

(I asked this question on Math.SE earlier but received no response and am therefore moving it here, please note that I realise this question is probably incredibly naïve for the experienced set-theorist, but for an outsider it seems like an important question to ask, and am therefore asking it. )

Von-Neumann ordinals can be thought of as "canonical" well-orders, indeed every well-order $(W,<)$ has a unique ordinal that is its "order type".

This raises the question of why a canonical order is needed, it seems to me that every application of ordinals can be done by using a "large enough" well-ordered set instead that is guaranteed by Hartogs' lemma$^{*}$, for example, instead of performing a transfinite process on an ordinal, we perform it on the "large enough" well ordered set $(X, <)$ whose existence is guaranteed by Hartogs' lemma. Using this method we can prove the first basic applications of ordinals such as Zorn's Lemma$^{\dagger}$ (see for example Asaf Karagila's answer to Zermelo set theory and Zorn's lemma).

$^{*}$ For the purposes of this question let Hartogs' Lemma state: For every set $S$, there exists a well-ordered set $(X, <)$, such that there is no injection from $X\to S$.

$^{\dagger}$ Interestingly popular set-theory books give the exact same argument using ordinals, which are totally superfluous (and need not exist without replacement)!

Remarks/Notes:

The above observations seem to imply, that the "working mathematician" can totally ignore ordinals, but I am more interested in why they are so important to the working set-theorist/logician (given that they literally are a set-theorist's "bread and butter").
This is not an entirely useless question that does not "affect things" in any way, since ordinals $\ge \omega+\omega$ need not exist in $\mathsf{ZFC}-\mathsf{Replacement}$, and indeed the above method gives a proof of Zorn's lemma in $\mathsf{ZFC}-\mathsf{Replacement}$. Given that many find replacement dubious, this seems like a strong argument for not using ordinals. (OK, without replacement sets of size larger than $\aleph_{\omega}$ need not exist, but assuming replacement the above method can easily construct such large sets without the need for ordinals.)
I suppose one can ask a similar question about cardinal numbers: Why do we need cardinal numbers, when we can reason about cardinalities using simply injections and bijections on sets?
Ordinals seem to give us a "uniform definability" but is that actually useful?

One answer that I have received is "convenience", but if convenience is the answer why do we need a formal notion that takes hours to develop when an informal notion seems to suffice (formally)?

I do not understand why I got downvoted so fast, is my question bad? If it is bad can someone explain? I really did try my best, and so being welcomed onto this site with an anonymous downvote, is not very motivating. — Vivaan Daga, Mar 20 '23 at 17:47
Hartogs' Lemma, not Hartog's Lemma, because the guy's name was Friedrich Hartogs. The paper was Über das Problem der Wohlordnung. Mathematische Annalen, 76:590–5, 1915. — Paul Taylor, Mar 20 '23 at 22:00
@Shinrin-Yoku I don't really understand your comment about convenience. Isn't this how most of mathematics works? If you're a casual user then informal notions may suffice. If you're a heavy user then it's worth putting some effort into being more formal, in order to make things easier in the long run. Why bother to invent category theory when an informal notion of "natural transformation" would probably have been fine? Why give a formal definition of a differentiable manifold when people got by without it for decades? If you're looking for a coercive reason, it's not going to exist. — Timothy Chow, Mar 22 '23 at 00:21
@TimothyChow I just meant you define ordinals to be equivalence classes of well orders. This seems “formal” enough, and doesn’t not need VN ordinals. Why do we want it to be a set? I honestly can’t see a good reason until you get to absoluteness… — Vivaan Daga, Mar 22 '23 at 02:03
@Shinrin-Yoku I suppose it ultimately comes down to a matter of taste, but I don't understand what advantages you think your suggestion has. Isn't it "wasteful" to define ordinals (even finite ordinals) to be proper classes rather than sets? Certainly ZF is based on the philosophy that "everything is a set," so it seems odd to forgo defining 1 as ${\varnothing}$ in favor of defining it to be the class of all well-ordered sets of length 1. — Timothy Chow, Mar 22 '23 at 03:03
Also, it seems to me that you're exaggerating how complicated von Neumann ordinals are. An ordinal is just a transitive set that is well-ordered by $\in$. That doesn't take hours to define. — Timothy Chow, Mar 22 '23 at 03:09
@TimothyChow I was trying to go to far lengths to avoid replacement. The replacement axiom is seen as quite dubious by many logicians. Also about “complicated” I agree that they are quite simple, but if you look at a book like Jech, he spends 2-3 pages defining ordinals and proving things about them and then proves Zorn’s lemma using ordinals, which makes the unsuspecting reader think there is something special about ordinals in the proof… — Vivaan Daga, Mar 22 '23 at 04:35
Do you also worry why we should define the ranks $V_\alpha$? — Monroe Eskew, Mar 22 '23 at 10:44
@MonroeEskew If you can come up with an example that does not refer to definability and displays the utility of having just any canonical well order, I would happily concede. For your question I see no problem defining $V_X$ for a well-order $X$… — Vivaan Daga, Mar 22 '23 at 10:49
I don't know what $V_X$ would mean. The $V_\alpha$'s are defined by iterating the powerset operation. Would you repeat it ordertype(X)-many times? It just so happens that when we do this, the Von Neumann ordinals come out, with $\alpha$ first appearing as an element of the (ordertype-of-$\alpha+1)^{th}$ stage. — Monroe Eskew, Mar 22 '23 at 10:54
@MonroeEskew Yes, I would recurse on the well orders. Would you say that it is the definablity of ordinals that are important rather than the canonicity? As a set theorist are you family with examples where canonicty is crucial? — Vivaan Daga, Mar 22 '23 at 11:02
As explained by Kameryn, the absoluteness of the ordinals plays an important role in set theory. My point here is just that it seems natural to try to iterate an operation like powerset (or constructibility operations) along a well-order, but actually that gives you back the Von Neumann ordinals in a canonical way. — Monroe Eskew, Mar 22 '23 at 11:06
@Shinrin-Yoku I'm a little surprised to hear you say that "the replacement axiom is seen as quite dubious by many logicians." To be sure, some people reject infinite set theory entirely. But are you claiming that there are "many logicians" who are happy with Zermelo set theory but not the replacement axiom? Can you give any examples of such people? I can't think of any offhand. Banning replacement leads to various technical nuisances; there's a reason ZF is "standard" while Zermelo set theory is not. — Timothy Chow, Mar 22 '23 at 12:26
Also, I don't think one should read too much into Jech's expository choices. Anyone writing a textbook on set theory will introduce ordinals at some point. No matter where that material is inserted, a critic could object, "Why put it there? Why not introduce it earlier, or postpone it until later, or split it into two sections?" There are various topics in set theory that many students balk at, but ordinals are not usually one of them, so I'm sure Jech just put that material where he thought was logical, without worrying about what philosophical implications his choice might seem to convey. — Timothy Chow, Mar 22 '23 at 12:43
@TimothyChow Honestly I am not an expert, but AFAIK categorical foundations don’t have replacement. See also the paper the answer linked. Also you can look at Tom Leinster’s “large sets”, which I learnt of by an MSE commentator. About Jech I wasn’t critiquing him, just pointing out an interesting thing. — Vivaan Daga, Mar 22 '23 at 12:46
@TimothyChow Mac Lane, for example, was skeptical of Replacement (and much more!). — Kameryn Williams, Mar 22 '23 at 13:00
It's true that ETCS doesn't have replacement, but I didn't think that was because of any skepticism about the replacement axiom. I thought it was that replacement was perceived as unnecessary (a perception that may not have been accurate). See this MO question for some discussion of this point. Note also, by the way, that the type-theoretic foundations assumed by various proof assistants end up being equiconsistent with ZFC + infinitely many inaccessibles. — Timothy Chow, Mar 22 '23 at 13:47
@KamerynWilliams Not sure how your answer got unaccepted I clicked the check again. — Vivaan Daga, Mar 22 '23 at 14:02
@TimothyChow Also note that hardly any working mathematicians know about ordinals, yet Zorn’s lemma is integral to them. — Vivaan Daga, Mar 25 '23 at 17:50
@Shinrin-Yoku Well, I certainly don't think of Zorn's lemma as being a reason to introduce ordinals. We seem to be going all over the map, from convenience to ordinals-as-sets to replacement to Jech's expository choices to Zorn's lemma. You might get a more focused answer if you asked a more focused question rather than half a dozen questions jumbled into one. — Timothy Chow, Mar 25 '23 at 18:47

score 26 · Accepted Answer · answered Mar 20 '23 at 20:38

26

This isn't about just any choice for a 'canonical' well-order, but the von Neumann ordinals in particular have nice properties that you don't get just from well-orders. They admit a logically simple definition which enables certain arguments about complexity of definitions to go through.

A relation $R$ being well-founded is a $\Pi_1$ property—it can be expressed with a single unbounded universal quantifier. (Namely, when saying that every nonempty subset of the domain has an $R$-minimal element, that "every" is an unbounded quantifier.) This implies that being well-founded is downward absolute: if you thin down your universe to have fewer sets then $R$ will still be well-founded in the thinner universe. After all, if every nonempty subset of the domain has an $R$-minimal element, that's still true if you throw out some of those subsets.

Is being well-founded upward absolute? If $R$ is well-founded, does it stay well-founded even if we expand our universe by adding new sets? For this, we would like a $\Sigma_1$ way of characterizing well-foundedness—expressed using a single unbounded existential quantifier. Then, if the witnessing object exists it continue to exists in a larger universe, so $R$ stays well-founded.

One attempt at this is: $R$ is well-founded if and only if there's a ranking function $\rho$ from the domain of $R$ to an ordinal. (That is, $x \mathbin{R} y$ iff $\rho(x) < \rho(y)$.) We'd like $\rho$ to still be a ranking function in the larger universe. But the problem is, if being an ordinal is only $\Pi_1$, then how do we know the codomain of $\rho$ is still an ordinal in the larger universe?

This is where von Neumann ordinals have an advantage over just well-orders. You can express that $\alpha$ is a von Neumann ordinal just by quantifying over the elements of $\alpha$. This means that $\alpha$ is still a von Neumann ordinal if you add new sets. So this gives a $\Sigma_1$ way to characterize well-foundedness, whence it is upward absolute. Being also downward absolute, we simply say it's absolute.

[Technical caveat here: I'm only talking about so-called transitive extensions/submodels, where both universes are transitive sets or classes. One can talk about other, nonstandard models, where you can add new elements to old sets, but let me set those aside.]

Why care about absoluteness? If you're a set theorist this is clear. A lot of the daily work of the set theorist involves moving up and down between universes, and you want to know what properties carry up or down. But even if you're not a set theorist this can be relevant. A question mathematicians sometimes want to know is whether the axiom of choice was necessary for such and such theorem. For example, maybe you know of the Galvin–Glazer proof of Hindman's theorem using idempotent ultrafilters and you want to know whether you really need choiceful objects like ultrafilters to prove it. An instance of Shoenfield's absoluteness theorem says that Hindman's theorem is actually provable in ZF, so you didn't need AC all along. While a non-logician may be happy to treat the theorem as a blackbox, if one digs into why it works one'll see that the absoluteness of well-foundedness is key in the proof.

Finally, are von Neumann ordinals (or some other nice canonical choice for well-orders) really necessary for this sort of absoluteness result? If you look at some contexts where von Neumann ordinals aren't available then you don't have that well-foundedness is upward absolute. For instance, this mathoverflow answer addresses the case with ZFC - Replacement.

answered Mar 20 '23 at 20:38

Kameryn Williams

2,077

1

This is very nice, thank you. Is there a reason for just having canonical well orders?(may not be Von Neumann or nicely definable) In other words does “canonicity” help set theorists in any way? – Vivaan Daga Mar 21 '23 at 06:06
4

@Shinrin-Yoku There's certainly some convenience to canonicity; e.g., suppose we want to define Goedel's constructible universe $\mathbf{L}$. The standard definition proceeds by defining $L_\alpha$ for every ordinal $\alpha$. How would you propose to define $\mathbf{L}$ without ordinals? I can imagine some ways of proceeding, but they all seem a little awkward. For comparison, we can ask why there is even a need for finite ordinals and cardinals. Can't we dispense with finite cardinals in combinatorics and deal with just injections and bijections? Maybe, but why would we want to? – Timothy Chow Mar 21 '23 at 13:46
@TimothyChow The problem is that infinite things require replacement, so it would be nice to have a deeper reason for canonical well orders. Perhaps there is a utility of “canonicity”… – Vivaan Daga Mar 21 '23 at 13:58
1

To add on to @TimothyChow's point, Adrian Mathias has a paper where he does construct $L$ in a system where he doesn't have access to von Neumann ordinals, in order to show that that system is bi-interpretable with a system that does have enough Replacement. His comments in the envoi, especially 10.10, are exactly about your question. – Kameryn Williams Mar 21 '23 at 14:11
2

@Shinrin-Yoku See this quote from Mathias (p. 84 of that paper):
"But if, sated with geometry, one wants to do transfinite recursion theory, why make life hard by avoiding von Neumann ordinals? Compare the mammoth struggle in section 4 to present the concept of constructibility without using Mostowski’s principle with the easy ride you get if you adopt it. And the two systems are equiconsistent, so one is not demanding a stronger system; one is merely presenting Mac Lane’s sytem in a style that is more efficient for transfinite recursion theory."
– Kameryn Williams Mar 21 '23 at 14:11
This probably a trivial question but why can’t one construct $L$ by recursing on well orders? – Vivaan Daga Mar 21 '23 at 15:45
2

You can—that's what Mathias does in that article. (And the same can be done in other contexts where you don't have access to von Neumann ordinals.) But his point is, not having a canonical choice for well-orders makes the process much more difficult. The process is much easier when you do have that canonical choice, and for the systems Mathias is working with, it doesn't increase their logical strength to use a system that does allow that canonical choice. – Kameryn Williams Mar 21 '23 at 16:15
From my very naïve point of view the $L$ example seems to boil down to the absoluteness of VN ordinals, so would you say that it is really VN ordinals that matter, rather than any other canonical well order we could have chosen? Are there no places where ordinals are genuinely useful not because of their absoluteness but because of the fact that they form a class, $C$, consisting of sets, such that every well ordered set is isomorphic to exactly one element in $C$? – Vivaan Daga Mar 21 '23 at 16:40
1

I'm not aware off-hand of anywhere that it's particularly helpful just to have some choice of isomorphism-type in a class $C$, whether ordinals/well-orders or elsewhere. After all, you can always just work with the equivalence classes of $C$. – Kameryn Williams Mar 21 '23 at 16:58
1

@Shinrin-Yoku Note that Kameryn is talking not just about canonical representatives, but about these things being very absolute between universes of set theory, having to do with the definitions having very low complexity. This is where the utility really lies. – Monroe Eskew Mar 22 '23 at 11:34
@KamerynWilliams About working with equivalence classes, I think the problem is that they don’t form sets, which can be a bit problematic; at least from my naive point of view… – Vivaan Daga Mar 22 '23 at 13:13
For example I have doubts that the Zorn’s lemma example can be proved using classes… – Vivaan Daga Mar 22 '23 at 13:39
So it would nice to have a quantifiable measure when @MonroeEskew says ‘really lies’… – Vivaan Daga Mar 22 '23 at 14:03
@Shinrin-Yoku I would say the measure here is the complexity in the Levy hierarchy. – Monroe Eskew Mar 22 '23 at 14:49
@MonroeEskew I did not mean measure in that way, I meant to say is there a way to show that the real (apart from convenience) use of ordinals comes from definability rather than the canonicity they provide? In other words if I used global choice to create a totally random set like class of ordinals, will you run into problems before you get to definablity? – Vivaan Daga Mar 22 '23 at 14:54
@Shinrin-Yoku You have to get some experience working with different models of set theory. You can creat a random class of “ordinals” in one universe, but what does it tell you about others? I don’t know how you will show the Schoenfield absoluteness theorem without recourse to ordinals, for instance. – Monroe Eskew Mar 22 '23 at 15:16
@MonroeEskew I totally agree, but it would even nicer if there was a use of ordinals before we get to the fact they are nicely definable. – Vivaan Daga Mar 22 '23 at 15:26
@Shinrin-Yoku I don't know what criteria would satisfy that. If you're using ordinals, you must have first defined them, and once you do that, you'll see that the definition is nice. – Monroe Eskew Mar 22 '23 at 16:40
@MonroeEskew Maybe some argument that requires a unique well ordered set for an uncountable amount of sets, with there being no canonical way to assign a set a well ordered set without using ordinals or some global choice function… don’t know if such an argument exists though… I don’t want a rigorous criteria, such a nice argument that shows that canonicity is also important. – Vivaan Daga Mar 22 '23 at 16:58
Or maybe there is a convincing argument that there is no such example… – Vivaan Daga Mar 22 '23 at 18:09
@Shinrin-Yoku The word "canonical" is a notoriously slippery one. See Kevin Buzzard's blog post for example. I think it will be difficult to prove anything rigorous about canonicity. I must say, usually I hear colleagues complain that something is not canonical, and they take it for granted that a canonical version would be better. I can't recall the last time I heard a colleague express dissatisfaction with something that's canonical, and imply that a non-canonical alternative would be preferable. – Timothy Chow Mar 22 '23 at 21:48
@TimothyChow I didn’t say it would be preferable, such an argument would just reinforce the importance of canonicity maybe Kameryn can clarify what they meant when they said that such an argument won’t exist. – Vivaan Daga Mar 23 '23 at 07:04
@TimothyChow That was just a remark for avoiding Zorn’s lemma, my question from the get go was: ignoring definablity, does the existence of a set like class $C$, such that each well ordered set is isomorphic to exactly one element in $C$, benefit us in any way other than convenience? Sadly I don’t anyone knows the answer to that question… Probably because it requires a “X ray” study of set theory, which maybe impossible for most humans… – Vivaan Daga Mar 25 '23 at 18:54
@Shinrin-Yoku It might help if you could give an example, not necessarily from set theory but from any branch of mathematics at all, where you think that canonicity (of anything you choose) "benefits us in some way other than convenience." That way, we'd have a better idea of what you're looking for. – Timothy Chow Mar 25 '23 at 21:38
@TimothyChow Ok example: The proof that each set occurs in $V_{\alpha}$ for some ordinal $\alpha$, the usual proof involves taking unions of ordinals, the same proof would not work without some canonical orders if we wanted to prove that each set occurs in $V_{X}$ for some well ordered $X$ (Where $V_X$ is defined by recursion). – Vivaan Daga Mar 26 '23 at 06:37
@Shinrin-Yoku The proof would use the axiom of foundation and be structurally identical to the usual one. You could definitely the class of all sets in some $V_X$ for a well-ordered $X$, and you could prove using foundation and a minimality argument that every set occurs in one of these. – Monroe Eskew Mar 26 '23 at 15:14
@MonroeEskew No, if you follow the steps of the usual proof you will see that we have to “pick” well ordered sets and patch them up to get a contradiction. Problem is without ordinals, there is no way to create such a choice function. – Vivaan Daga Mar 26 '23 at 15:17
@Shinrin-Yoku but for every two well-orders, one is embeddable into the other as an initial segment. – Monroe Eskew Mar 26 '23 at 15:20
@MonroeEskew Here is how the usual proof goes: Suppose the class of all sets that did not belong to any $V_X$ was non-empty, by regularity there exists a set $a$ such that all $b\in a$ belong to some $V_X$, for each $b$ we can pick an $X$ by using global choice or canonical well orders and then patch them up to construct a well ordered set $W$ such that $a\in V_W$ a contradiction. – Vivaan Daga Mar 26 '23 at 15:25
@Shinrin-Yoku Since the $V_X$ construction is canonical, each $b\in a$ is in an $\in$-minimal $V_X$. Use replacement at the end for the contradiction. – Monroe Eskew Mar 26 '23 at 15:31
@MonroeEskew But the entire point is that we don’t have ordinals and so the $V_{X}$ construction is not canonical. BTW the strongest argument I have seen so far in favour of ordinals is the proof that $\aleph_{\omega}$ exists it is true that using Hartogs one can give a ordinal free proof but the point is that the set we end up constructing is just a really messy canonical order type. – Vivaan Daga Mar 26 '23 at 15:34
Let us continue this discussion in chat. – Monroe Eskew Mar 26 '23 at 15:35

Why do we need "canonical" well orders?

1 Answers1