7
$\begingroup$

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.

$|\omega\uparrow^\omega\omega|=?$

Improve this question
$\endgroup$

1 Answer 1

Reset to default
14
$\begingroup$

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

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

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.

Please note that there are other natural definitions, depending on how one treats the limit stage. which will not be the same as this one. For example, in the definition above, by $\alpha\beta$ I had intended that one should use the natural product, rather than the common product, because this achieves some nicer properties. But others may want to do things differently, and the resulting functions will differ. Nevertheless, what I say below will apply to all the natural formulations of the arrow.

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$.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Kenneth Harris's slides (google.com/…) contain a nice, accessible account of $\alpha\uparrow\uparrow\beta$, that is, the case $\eta=2$. $\endgroup$
    – Joel David Hamkins
    Commented Nov 11, 2012 at 19:47
  • 1
    $\begingroup$ That's a great resource! I was wondering about this whole thing because $\epsilon_0=\omega\uparrow\uparrow\omega$ or $\omega\uparrow\uparrow\uparrow2$. $\endgroup$
    – B H
    Commented Nov 11, 2012 at 20:13
  • 2
    $\begingroup$ 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). $\endgroup$
    – Andreas Blass
    Commented Nov 12, 2012 at 2:22
  • $\begingroup$ Slight flaw in definition, I believe you meant to have $\alpha\uparrow^\eta0=1$. $\endgroup$
    – Simply Beautiful Art
    Commented Aug 6, 2018 at 19:40
  • 1
    $\begingroup$ No, your calculation is not correct with the natural product, as I indicated, since $\omega\cdot\omega^\omega=\omega^{\omega+1}$ with the natural product (you seem to be using the common product). Meanwhile, your alternative formulation is indeed what I would have used with the common product, and this is the kind of thing to which I was referring. I find it less attractive than using the natural product, however, precisely because it aligns less directly with the usual presentation of the finite case. $\endgroup$
    – Joel David Hamkins
    Commented Aug 6, 2018 at 21:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .