Is it possible to define higher cardinal arithmetics

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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