3
$\begingroup$

I came around a nice article talking about large countable ordinals with examples such as: Let's have a book with $\omega$ pages (each 1/2 the thickness of previous so we can fit them in a book of finite dimensions), and let's have an encyclopedia with $\omega$ volumes of such books (each with $\omega$ pages).

With the above example, we have the total number of pages in the encyclopedia is $\omega\cdot \omega$. How is it right to use ordinal arithmetic which will lead to the $\omega\cdot \omega$ still being countable? Why we don´t have uncountably many pages in said example?

And how can we with similar examples "reach" uncountably many pages?

EDIT: Yeah, my mistake with $\aleph_0\cdot \aleph_0 = \aleph_0$. In that example it didn't stop with $\omega$ volumes, there also was $\omega$ encyclopedias in a room, $\omega$ rooms in building, etc., giving the number of pages as $\omega^\omega$. Now in this example, $\omega^\omega$ was ordinal exponentiation which gives still a countable ordinal. I don´t understand how can there be a bijection between the natural numbers and the number of pages in said example. Shouldn't this $\omega^\omega$ be cardinal exponentiation and therefore the number of pages be uncountable?

$\endgroup$
9
  • $\begingroup$ Why would we have uncountably many pages? (Also, $\aleph_0\cdot\aleph_0=\aleph_0$ in cardinal arithmetic, so I don’t know why you are singling our ordinal arithmetic.) $\endgroup$ Aug 9, 2019 at 14:03
  • $\begingroup$ Well, have you seen this? $\endgroup$ Aug 9, 2019 at 14:10
  • 1
    $\begingroup$ Also, when you say “the number” of something that implies cardinality, whereas we do have a natural ordering of all the pages, by volume and then by page within volume which has type $\omega\cdot\omega.$ $\endgroup$ Aug 9, 2019 at 14:11
  • 2
    $\begingroup$ math.stackexchange.com/questions/599022/… and math.stackexchange.com/questions/627291/… and math.stackexchange.com/questions/988559/… and probably a handful of other related questions have been asked before. $\endgroup$
    – Asaf Karagila
    Aug 9, 2019 at 14:27
  • 1
    $\begingroup$ Please give a reference to the "nice article" so we can read the presentation of the example for ourselves. When you refer to something you've read in a question, you should always give a reference. $\endgroup$ Aug 10, 2019 at 17:53

1 Answer 1

3
$\begingroup$

I think you are right. Depending on how you look at it, this story "pages within books within encyclopedia within..." may actually be a better analogy with cardinals than with ordinals, although the two have a natural correspondence for exponentiations of $\omega$ / $\aleph_0$ to finite powers.

Ordinals are about enumerating things one after another, and it is perfectly fine to imagine first taking $\omega$ pages and assembling them into book $0,$ then taking another $\omega$ pages and assembling them into book $1,$ whose pages have numbers $\omega + n$ for $n\in \omega,$ and then taking the next $\omega$ pages and putting them into book $2$ which has page numbers $\omega\cdot 2 + n$ for $n\in \omega,$ and so on. Then when we're done assembling the encyclopedia with $\omega$ books, the $n$-th page in book $k$ has number $\omega\cdot k+n.$ Then we can start a new encyclopedia, whose $0$-th book has $0$-th page $\omega^2,$ first page $\omega^2+1$ and so on.

The thing to realize is that what we're doing here is enumerating off pages. The books and encyclopedias and so on were just conceptual devices to organize the layers. Something we'd call an ordinal notation more formally, and I've included the more standard version of the ordinal notation side by side. Something we should take note of on the long haul up to $\omega^\omega$ is that at no point are we more than finitely many layers deep in our categorization. Even if we're at the googolplex-th hyperlibrary or whatever we want to call it, it is a finite iteration of the original concept of the book. We just had to invent it at a certain point to continue our story once we had enumerated so many pages that they filled a whole $\omega$-sequence of googolplex-minus-one-th hyperlibraries.

As such, our pages before the $\omega^\omega$-th have numbers of the form $$\omega^n\cdot a_n+\omega^{n-1}\cdot a_{n-1}+\ldots +\omega\cdot a_1 + a_0$$ where the $a_i$ are natural numbers, so they each correspond to a finite sequence of natural numbers. It's a common exercise in introductions to cardinality to show that the set of all finite sequences of natural numbers has cardinality $\aleph_0.$

However, I think most people who would be told an abbreviated version of the story you lay out would have a much different picture of what the end state after $\omega$ iterations of "books within encyclopedias within..." would look like. One might imagine a whole completed infinite hierarchy, in which case it would make sense to ask simultaneously "which $n$-hyperlibrary is the page in" for all $n$ and there would be no reason to expect that all but a finite number of answers would be $0$.

The pages aren't enumerated up from the bottom, rather they come into existence all at once in this structure. So a page is characterized by an $\omega$-sequence of natural number coordinates, where the 0-th coordinate tells you the page within the book, the 1-st tells you the book within the encyclopedia, the googolplex-th tells you the googolplex-minus-one-th hyperlibrary within the googolplex-th hyperlibrary etc. And it's an equally standard exercise to show that the cardinality of the set of all $\omega$-sequences of naturals, i.e. $\aleph_0^{\aleph_0}$, comes out to $2^{\aleph_0}$ which is uncountable.

Note that in this picture, there is no way to order the pages bottom up like we did in the ordinal picture. The most obvious way to order them would be kind of the opposite: we look for the lowest level of the hierarchy (i.e. the smallest number coordinate) on which they differ and order them according to that. (So if one has a smaller page number within their book, it is smaller, even if the book it's in has a larger number.) This is not a well-ordering and thus doesn't really correspond to enumeration.

Also note that as I mentioned at the top, this irreconcilable divergence between the two pictures only happens when we get to infinite powers. The ordinals less than $\omega^3$ can be written $\omega^2\cdot l+ \omega\cdot m + n$ which is three natural number coordinates. The definition of $\aleph_0^3$ is the cardinality of the cartesian product $\omega\times\omega\times \omega,$ which is the set of all ordered triples $(l,m,n).$ Both are described by three natural number coordinates. While it's important to keep the concepts separate, since they do eventually diverge, this shows why whoever told you this story might have overlooked the potential confusion as to what story we're telling when we get to $\omega^\omega$ or $\aleph_0^{\aleph_0}.$


As to how to "reach" uncountably many pages, it was explained briefly in a comment and link by Don Thousand, and has probably been explained more thoroughly elsewhere on this site but I'll try to elaborate. As we enumerate, the organizational story we tell ourselves inevitably runs out. We can go substantially higher than $\omega^\omega$ just by continuing to iterate after that, but words and symbols are only countably infinite in number and they eventually must fail us.

In the absence of a full story for how we count to an uncountable number, we fall back on some more abstract arguments. The ordinals that we can enumerate up to explicitly in a fashion like we were doing above correspond to computable well-orderings of $\mathbb N$ (these are called recursive ordinals). However, there are many more well-orderings of $\mathbb N$ than that. We know this since when we arrange the recursive well-orderings in order of how high they go, they form a countable well-ordered set (there are countably many recursive relations after all) so they correspond to a well-ordering of $\mathbb N,$ which by its definition goes higher than any recursive ordinal. We call arbitrary well orderings of $\mathbb N$ countable ordinals.

Now we can repeat the same argument with all of the well-orderings of $\mathbb N,$ not just the recursive ones. Arrange them in order of how high they go and the result is a well-ordered set which by its definition goes higher than any countable ordinal. This is the first uncountable ordinal.

So while we can enumerate an uncountable number of pages in a sense (and I'll note that obviously this can be made much more rigorous than I'm probably making it sound, using axioms of set theory and all of that), it is not nearly as constructive a process as for small countable ordinals like $\omega^\omega$ or even much larger recursive ordinals, and it's not visualizable in any useful way I'm familiar with. (But a point in favor of its 'constructiveness': the argument does not use the axiom of choice.)

$\endgroup$
8
  • $\begingroup$ I consider both the pages of a book and the volumes of an encyclopedia as inherently ordered. If you exchange two pages or two volumes, you'll definitely notice that something is wrong as soon as you get to that point. Note that pages have page numbers, which increase by one each page. I also disagree that ordinals are about counting; as the name already says, ordinals are about ordering. $\endgroup$
    – celtschk
    Aug 10, 2019 at 7:00
  • $\begingroup$ @celtschk They are about well ordering which is a lot more specific than ordering. Sure, the pages in an individual book are ordered and the books in a given encyclopedia are ordered, but we can’t extrapolate from that that all the pages in their entirety are well ordered. $\endgroup$ Aug 10, 2019 at 7:20
  • $\begingroup$ I disagree. The very essence of counting is that the order does not matter, you get the same result no matter where you start and end. Which is the very opposite of ordering (and yes, ordinals are about well-ordering, which are special orderings). And of course a well-ordered set of well-ordered sets induces a well-order on the union. $\endgroup$
    – celtschk
    Aug 10, 2019 at 7:26
  • $\begingroup$ @celtschk also, when you say “when you get to that point” you are clearly already assuming the first sense. My point is only that there is a second reasonable way to interpret. Does the distinction between the manifestly well ordered $\omega^\omega$ and the infinite product that can’t be well ordered absent choice not make sense? $\endgroup$ Aug 10, 2019 at 7:34
  • $\begingroup$ I can well get to that point by randomly opening the encyclopedia, and by chance finding the wrongly ordered pages. Indeed, it is very uncommon that someone reads an encyclopedia front to back. $\endgroup$
    – celtschk
    Aug 10, 2019 at 7:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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