22
$\begingroup$

(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)?

$\endgroup$
21
  • 14
    $\begingroup$ 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. $\endgroup$ Commented Mar 20, 2023 at 17:47
  • 4
    $\begingroup$ 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. $\endgroup$ Commented Mar 20, 2023 at 22:00
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Mar 22, 2023 at 3:09
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Mar 22, 2023 at 11:06
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Mar 22, 2023 at 12:43

1 Answer 1

26
$\begingroup$

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.

$\endgroup$
32
  • 1
    $\begingroup$ 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? $\endgroup$ Commented Mar 21, 2023 at 6:06
  • 4
    $\begingroup$ @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? $\endgroup$ Commented Mar 21, 2023 at 13:46
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Mar 21, 2023 at 14:11
  • 2
    $\begingroup$ @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." $\endgroup$ Commented Mar 21, 2023 at 14:11
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Mar 21, 2023 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.