MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was wondering what the cardinality of $\omega\uparrow^\omega\omega$ is, with $\uparrow$ being Knuth's up-arrow notation. I ask this purely out of curiosity; after finding out about set theory I feel like a child with a new toy. I'm not on the same level as everyone else on this site, and everything I've learned about set theory I've learned on Wikipedia. The answer to my question might very well be there, but after much searching and attempts to understand the language there, I'm still not sure. Is this an appropriate question for this site? Thank you.


share|cite|improve this question
up vote 10 down vote accepted

The Knuth arrow notation is most often defined only on the natural numbers, but it seems that the central idea of it can be naturally extended to the ordinals, as follows:

$$\alpha\uparrow^0\beta=1$$ $$\alpha\uparrow^1\beta=\alpha^\beta$$ $$\alpha\uparrow^\eta\beta=\sup_{\eta'\lt\eta}[\alpha\uparrow^{\eta'}\sup_{\beta'\lt\beta}(\alpha\uparrow^\eta\beta')].$$

This definition simply replaces the use of $n-1$ and $b-1$ in the usual natural number definition of the Knuth arrow with a supremum over all smaller values, which allows the definition to work with limit ordinals, which have no immediate predecessor. On finite and successor values, this definition agrees with the standard formula. (I'm not sure if others have proposed a different transfinite extension of the concept....I can imagine alternative definitions that treat the limit cases differently, but this won't affect the main conclusion.)

Using this definition, one can show by transfinite induction that if $\alpha, \beta$ and $\eta$ are countable ordinals, then $\alpha\uparrow^\eta\beta$ is also countable, because by the induction hypothesis, this will be a countable supremum of countable ordinals.

In particular, $\omega\uparrow^\omega\omega$ is a very large countable ordinal, and the anwer to your question is that it has cardinality $\aleph_0$.

share|cite|improve this answer
Thank you! I appreciate it. – Benjamin Hansel Nov 11 '12 at 19:06
Kenneth Harris's slides (…) contain a nice, accessible account of $\alpha\uparrow\uparrow\beta$, that is, the case $\eta=2$. – Joel David Hamkins Nov 11 '12 at 19:47
That's a great resource! I was wondering about this whole thing because $\epsilon_0=\omega\uparrow\uparrow\omega$ or $\omega\uparrow\uparrow\uparrow2$. – Benjamin Hansel Nov 11 '12 at 20:13
Joel's answer is the right one in light of the OP's description of his background, but for set-theorists, let me point out a quick overkill argument. This inductive definition (and indeed any definition remotely resembling it) is $\Delta_1^{ZF}$, so by Lévy's cardinal boundedness theorem, the output of the function it defines can't have (hereditary) cardinality greater than its inputs and $\aleph_0$. The parentheses around the word "hereditary" are because it can be omitted when dealing with ordinals (or any transitive sets). – Andreas Blass Nov 12 '12 at 2:22

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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