TITLE: Is it possible to define higher cardinal arithmetics
QUESTION [31 upvotes]: 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.

REPLY [25 votes]: 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):



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

REPLY [2 votes]: 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
{"set_name": "stack_exchange", "score": 31, "question_id": 187917}