In number theory there are several operators like ‎addition, ‎multiplication and ‎exponentiation defined from ‎$‎‎‎\omega‎‎\times‎‎\omega‎$ ‎to ‎‎$‎‎‎\omega‎$. Each ‎of ‎them ‎is defined as an ‎iteration of ‎‎‎the other. ‎The sequence of building such iterated operators can go further to define faster and faster hyperoperators‎. The first of them is tetration which is defined as iterated exponentiation. Let ‎$‎‎m\uparrow n$ ‎denote the tetration of ‎$‎‎m$ and ‎$‎n‎$‎ ‎that ‎is‎ ‎‎$‎‎\underbrace{m^{m^{m^{.^{.^{.}}}}}}_{n - times}$. This operator appears in several interesting occasions in logic, computations and combiantorics, for example see these Wikipedia articles on Graham's number, Ackermann's function, busy Beaver function and Chaitin's incompleteness theorem.

Now consider the infinitary case. ‎In set theory ‎addition, ‎multiplication ‎and ‎exponentiation are defined for ‎cardinal ‎numbers. ‎

Question 1. What ‎about ‎‎$‎‎‎\kappa‎‎\uparrow‎‎\lambda‎$? ‎How should we define this? ‎ ‎

Intuitively, we expect to define ‎$‎‎\aleph_0‎\uparrow‎\aleph_0$ ‎to be ‎‎$‎\aleph_0^{‎‎\aleph_0^{‎‎\aleph_0^{.^{.^{.}}}}}.$

But this intuitive definition of tetration has some counter-intuitive properties, as then ‎we ‎expect ‎to ‎have ‎‎$‎‎‎‎\aleph_0^{(‎‎\aleph_0‎\uparrow‎\aleph_0)}=‎‎\aleph_0‎\uparrow‎\aleph_0$ which is ‎impossible ‎by ‎Cantor's ‎theorem which says ‎$‎‎‎\forall ‎‎\kappa‎\geq\aleph_0\;\;\;\aleph_0^{‎\kappa‎}>‎\kappa‎$.

Note that for the cases of addition, multiplication and exponentiation, we have quite natural operations $f_+, f_\times$ and $f_e$ such that given cardinals $\kappa, \lambda$, we have $f_+(\kappa,\lambda)=\kappa+\lambda, f_\times(\kappa, \lambda)=\kappa\times \lambda$ and $f_e(\kappa,\lambda)=\kappa^\lambda.$

Question 2. Is there a natural operation $f_t$ defined so that for all natural numbers $m,n$ we have $f_t(m,n)= ‎‎‎m\uparrow n$, and so that its definition is so natural that it also works for infinite cardinal numbers?

The next question is taken from Noah's answer, where an answer to it may help in defining the tetration for higher infinite.

Question 3. What is $m\uparrow n$ counting?

See also What combinatorial quantity the tetration of two natural numbers represents?. But note that the answers given in the above question are so that they are not suitable for treating infinite cardinals.

  • 5
    "Hyperoperations" on ordinal numbers have been treated e.g. by Doner & Tarski, but of course you are aware of that. – bof Nov 24 '14 at 5:54
  • 5
    The problem with cardinal arithmetic is that it generally insists on being discontinuous. – Asaf Karagila Nov 24 '14 at 9:40
  • 7
    Isn't standard notation for tetration $\uparrow\uparrow$? Other than that, we don't even have any combinatorial sort of definition for tetration, unlike exponentiation, say, so I find it quite unlikely for such satisfactory definition to exist. – Wojowu Nov 24 '14 at 16:57
  • 3
    @GHfromMO: Generally, the logic tag is appropriate for anything that would be appropriate on the logic section of arXiv. This includes this question. – Asaf Karagila Nov 24 '14 at 17:05
  • 3
    @GHfromMO, set theory is part of logic . . . – Noah Schweber Nov 24 '14 at 18:03

Let me begin with an observation:

$2 \!\uparrow\uparrow\! n$ is equal to the number of sets of rank at most $n$.

[If you followed the combinatorics tag here and have forgotten what the rank of a set is, see this article for a refresher. Roughly, the rank of a set is the "depth" of the nesting of braces when it's written out in long form. For example, we have one set of rank $0$ (namely $\emptyset = \{\}$). There are two sets of rank $0$ or $1$ (namely $\{\}$ and $\{\{\}\}$), there are $4$ sets of rank at most $2$ (namely $\{\}$, $\{\{\}\}$, $\{\{\{\}\}\}$, and $\{\{\},\{\{\}\}\}$), there are $16$ of rank at most $3$, $65536$ of rank $\leq 4$, etc.]

This observation is easily proved by induction, and it gives us a natural answer to your Question 3 when we restrict ourselves to tetration with base 2.

What about the unrestricted version of Question 3?

For this, we want to stop viewing set membership as a binary relation (membership value of $0$ or $1$). Instead, let's allow $k$ possible membership values: a set can be a member of another with value $0$ (not a member), $k-1$ (fully a member), or anything in between.

For example, this view still gives us one set of rank $0$, namely the empty set $\{\}$, but now we have $k$ sets of rank $0$ or $1$, namely the sets containing only $\{\}$, with value between $0$ and $k-1$ (of course, the set containing $\{\}$ with value $0$ is identified with $\{\}$, so that we only get $k-1$ new sets of rank $1$, for a total of $k$ with rank $0$ or $1$). It is easy to check that we get $k^k$ "sets" of rank at most $2$, $k^{k^k}$ of rank at most $3$, and $k \!\uparrow\uparrow\! n$ sets of rank at most $n$.

So a plausible answer to your Question 3 is:

$k \!\uparrow\uparrow\! n$ is equal to the number of sets of rank at most $n$ when we adopt a $k$-valued notion of set membership.

One of the nice things about this answer is that it generalizes easily to higher cardinals.

As you know, the notion of $B$-valued set membership, where $B$ is some set (usually a Boolean algebra or a partial order) is a common one in set theory. Sets with a $B$-valued notion of membership are often called $B$-names, and they are naturally equipped with a notion of rank. In light of the foregoing discussion on finite tetration, I propose the following as a fairly natural definition for transfinite tetration:

$\kappa \!\uparrow\uparrow\! \nu$ is equal to the number of $B$-names of rank at most $\nu$, where $B$ is a set of size $\kappa$.

Notice that this definition coincides with the inductive definition in Noah's answer. One drawback to this definition (noticed already by Noah) is that the value of $\kappa \!\uparrow\uparrow\!\nu$ is determined by treating $\kappa$ as a cardinal while treating $\nu$ as an ordinal.

Right now, I can see two approaches to "fixing" this drawback: either live with it (it's not a bug, it's a feature!), or modify the definition to (something like) one of the following three possibilities (the third being my personal preference):

  1. $\kappa \!\uparrow\uparrow\! \nu$ is the number of $B$-names hereditarily smaller than $\nu^+$, where $B$ is a set of size $\kappa$.

  2. $\kappa \!\uparrow\uparrow\! \nu$ is the number of $B$-names of rank at most $\nu$, where $B$ is a set of size $\kappa$.

  3. $\kappa \!\uparrow\uparrow\! \nu$ is the number of $B$-names of rank less than $\nu^+$, where $B$ is a set of size $\kappa$.

  • +1. I like this a lot! – Noah Schweber Aug 18 '16 at 16:40
  • Your definition of "cardinal $ \uparrow\uparrow $ ordinal" is great, but "$ \kappa\uparrow\uparrow\nu $ is the number of $ B $-names hereditarily smaller than $ \nu $, where $ B $ is a set of size $ \kappa $" does not have the desired values for finite $ \kappa $ and $ \nu $. – Alex Mennen Aug 19 '16 at 3:41
  • @AlexMennen: You're right, and this is certainly a bug! I may try to think some more on this, and try to find a bug-free way of defining the cardinals version. – Will Brian Aug 19 '16 at 16:13
  • @WillBrian So you simply say $2 \uparrow\uparrow n$ is the size of $V_{n+1}.$ But then based on your suggestion, we must have $2 \uparrow\uparrow \aleph_0$ has size $|V_\omega|=\aleph_0$ which is not suitable. – Mohammad Golshani Aug 20 '16 at 3:28
  • @MohammadGolshani: You're right, of course. I think I meant to write $\nu^+$ there, not just $\nu$. I've edited to correct it and to include a few different possibilities for a cardinals-only definition, but I'm not completely convinced that any of them are the obviously correct and/or compellingly natural extension of the finite case. – Will Brian Aug 22 '16 at 21:13

Too long for a comment, not quite an answer:

Of course, no definition of cardinal tetration can satisfy the property $$\lambda\ge\aleph_0\implies\kappa^{(\kappa\uparrow\lambda)}=\kappa\uparrow\lambda.$$ So however we define tetration, as the OP observes, it will have to be weird.

There is a natural inductive definition to make. We define $\kappa\uparrow\alpha$ for $\alpha$ an ordinal:

  • $\kappa\uparrow 0=1$;

  • $\kappa\uparrow(\beta+1)=\kappa^{(\kappa\uparrow\beta)};$

  • $\kappa\uparrow\lambda=\sup \{\kappa\uparrow\beta: \beta<\lambda\}$ for $\lambda$ a limit ordinal.

So, for example, under this definition $\aleph_0\uparrow\omega=\beth_\omega$.

Now, however, we run into an interesting problem: what should $\kappa_0\uparrow\kappa_1$ be, for $\kappa_0, \kappa_1$ cardinals?

  • Approach 1: $\kappa_0\uparrow\kappa_1=\kappa_0\uparrow InOr(\kappa_1)$, where $InOr(\kappa_1)$ is the initial ordinal of $\kappa_1$, that is, the least ordinal of cardinality $\kappa_1$.

This has the drawback of making $\aleph_0\uparrow\aleph_0\not=\aleph_0\uparrow(\aleph_0+1)$. (Of course, this is an abuse of notation, but it's meant to be provocative.)

  • Approach 2: $\kappa_0\uparrow\kappa_1=\sup \{\kappa_0\uparrow \alpha: \vert\alpha\vert=\kappa_1\}$.

This has the drawback of being discontinuous in annoying ways - for example, $\aleph_0\uparrow n=\beth_n$ but $\aleph_0\uparrow\aleph_0$ is much larger than $\beth_\omega$ - as well as hard to calculate.


The "right" approach, in my mind, is to figure out what set $\kappa_0\uparrow\kappa_1$ is the cardinality of. That is, we know how to define $\kappa_0^{\kappa_1}$ since that's just the cardinality of the set of maps from $\kappa_1$ to $\kappa_0$; in the case of tetration, though, it's not clear what set is being counted. There is a purely finitary combinatorial question lurking here:

What is $n\uparrow k$ counting?

to which I don't know the answer.

  • 2
    Cardinal exponentiation is already discontinuous, so why would this be considered a drawback? – Andrés E. Caicedo Nov 24 '14 at 22:15
  • 1
    D'oh - of course you're right. Still, I find this specific example of discontinuity a little disconcerting. (Although right now I do think Approach 2 is the right way to define cardinal tetration.) – Noah Schweber Nov 24 '14 at 23:29
  • @NoahS In the above, you first define tetration for ordinals, and then use it to define tetration for cardinals, as a sup. To see if it natural, we might expect the same works for earlier cardinal operations, say exponentiation. But I don't see if we have$2^{\aleph_0}=\aleph_0^{\aleph_0}=sup\{\aleph_0^{\alpha}: |\alpha|=\aleph_0\},$ where in $sup$, ordinal exponentiation is considered. – Mohammad Golshani Nov 25 '14 at 3:59
  • Also your last question is essentially my question 2. – Mohammad Golshani Nov 25 '14 at 4:00
  • @MohammadGolshani, I think that tetration has a recursive character which exponentiation lacks. Obviously this is informal, but I don't find the fact that exponentiation can't be defined similarly to necessarily be a point against this. (Re: question 2, I don't think they're the same; one can have a natural operation corresponding to tetration - even one with a definition that lifts seamlessly to infinite cardinals - without having a concrete picture of the set being counted.) – Noah Schweber Nov 25 '14 at 4:13

Another answer that isn't really an answer, but too long for a comment: Regarding the confusion over Cantor's theorem showing that $ \aleph_{0}^{\left(\aleph_{0}^{\aleph_{0}^{\aleph_{0}^{...}}}\right)}\neq\aleph_{0}^{\aleph_{0}^{\aleph_{0}^{...}}} $, think about what $ \aleph_{0}^{\aleph_{0}^{\aleph_{0}^{...}}} $ even means. The most natural interpretation is that it is $ \sup_{n<\omega}\aleph_{0}\uparrow n $. Then $ \aleph_{0}^{\left(\aleph_{0}^{\aleph_{0}^{\aleph_{0}^{...}}}\right)} $ means $ \aleph_{0}^{\sup_{n<\omega}\aleph_{0}\uparrow n} $. If exponentiation were continuous, then this would be $ \sup_{n<\omega}\aleph_0^{\aleph_{0}\uparrow n}=\sup_{n<\omega}\aleph_{0}\uparrow (n+1)=\sup_{n<\omega}\aleph_{0}\uparrow n $. Thus Cantor's theorem shows that exponentiation is not continuous.

Also, a nitpick: your use of $ \uparrow $ to denote tetration is nonstandard. Knuth's uparrow notation uses $ \uparrow\uparrow $ for tetration, and $ \uparrow $ as a synonym for exponentiation.

A category-theoretic angle. Accordingly, more questions than answers. But at least I hope it uncovers some subtle issue.

Let us ask how to define transfinite iterates of an endofunctor $F$. That is, what properties should uniquely (up to isomorphism) determine $F^\lambda$ as something like "$\underbrace{\cdots\circ F\circ F\circ\cdots}_{\text{$\lambda$ times}}$".

If this is solved, then $\kappa\uparrow\lambda$ could be defined as the cardinality of $F^\lambda(\text{singleton})$, where $F$ is the functor from sets to sets given by $F(S)=X^S$, with $X$ any (fixed) set of cardinality $\kappa$. (It is true that $F$ is actually contravariant, but there still is no problem iterating it.)

When $\lambda$ is an ordinal, one might try direct limit of the $\lambda$-shaped diagram, with $F$ as transition functors.

In this way one gets something peculiar. Already at $\lambda=\omega$ the limiting category might be not equivalent to the category of sets. Whatever it is, $F^\lambda(\text{singleton})$ will be defined, it will be an isomorphism class of objects of a category defined uniquely up to equivalence.

So it remains to describe this category, at least the class of isomorphism classes of its objects. This will then give a natural candidate for $\kappa\uparrow\lambda$ as one of the members of this class, uniquely determined by the above.

A variant - we could take the (large) groupoid of sets and bijections, we don't actually need non-bijective morphisms. However I don't know whether we would obtain something essentially different at limiting stages.

Still another variant - we might take the $\textit{inverse}$ limit of the backwards diagram; if it does have a terminal object, we might take the value of the limiting functor on it. This then would be a genuine set. Here however I don't know whether the terminal indeed exists in the limiting category.

When $\lambda$ is just a cardinal, I am at a loss. I need some ordering to get started with the above.

After a while I decided to post a separate question about the nature of these limiting categories, Infinite iterates of the contravariant hom endofunctors on sets

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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