Hyperoperation

This article is about the arithmetic concept. For the group theory hyperoperation concept, see Hyperstructure.

In mathematics, the hyperoperation sequence is an infinite sequence of arithmetic operations (called hyperoperations) that starts with the unary operation of successor (n = 0), then continues with the binary operations of addition (n = 1), multiplication (n = 2), and exponentiation (n = 3), after which the sequence proceeds with further binary operations extending beyond exponentiation, using right-associativity. For the operations beyond exponentiation, the nth member of this sequence is named by Reuben Goodstein after the Greek prefix of n suffixed with -ation (such as tetration (n = 4), pentation (n = 5), hexation (n = 6), etc.) and can be written as using n − 2 arrows in Knuth's up-arrow notation. Each hyperoperation may be understood recursively in terms of the previous one by:

$\begin{matrix} a \uparrow^m b & = & \underbrace{a \uparrow^{m-1} (a \uparrow^{m-1} (a \uparrow^{m-1} (...(a \uparrow^{m-1} (a \uparrow^{m-1} a))...)))} \\ & & b\mbox{ copies of }a \end{matrix}$ (m ≥ 0)

It may also be defined according to the recursion rule part of the definition, as in Knuth's up-arrow version of the Ackermann function:

$a \uparrow^m b = a \uparrow^{m-1} (a \uparrow^m (b-1))$ (m ≥ -1)

This can be used to easily show numbers much larger than those which scientific notation can, such as Skewes' number and googolplexplex, but there are some numbers which even they cannot easily show, such as Graham's number and TREE(3).

This recursion rule is common to many variants of hyperoperations (see below).

Definition

The hyperoperation sequence $H_n(a,b) \,:\, (\mathbb{N}_0)^3 \rightarrow \mathbb{N}_0\,\!$ is the sequence of binary operations $H_n \,:\, (\mathbb{N}_0)^2 \rightarrow \mathbb{N}_0\,\!$, defined recursively as follows:

$H_n(a,b) = \begin{cases} b + 1 & \text{if } n = 0 \\ a &\text{if } n = 1 \text{ and } b = 0 \\ 0 &\text{if } n = 2 \text{ and } b = 0 \\ 1 &\text{if } n \ge 3 \text{ and } b = 0 \\ H_{n-1}(a,H_n(a,b-1)) & \text{otherwise} \end{cases}\,\!$

(Note that for n = 0, the binary operation essentially reduces to a unary operation (successor function) by ignoring the first argument.)

For n = 0, 1, 2, 3, this definition reproduces the basic arithmetic operations of successor (which is a unary operation), addition, multiplication, and exponentiation, respectively, as

$H_0(a,b) = b + 1\,\!,$

$H_1(a,b) = a + b\,\!,$

$H_2(a,b) = a \cdot b\,\!,$

$H_3(a,b) = a^{b}\,\!,$

So what will be the next operation after exponentiation? We defined multiplication so that $H_2(a,3) = a * 3 = a + a + a,$, and defined exponentiation so that $H_3(a,3) = a ^ 3 = a \cdot a\cdot a,$ so it seems logical to define the next operation, tetration, so that $H_4(a,3) = tetration(a, 3) = a^{a^{a}},$ with a tower of three 'a'. Analogously, the pentation of (a,3) will be tetration(a,tetration(a,a))), with three 'a' in it. The H operations for n ≥ 3 can be written in Knuth's up-arrow notation as

$H_4(a,b) = a\uparrow\uparrow{b}\,\!,$

$H_5(a,b) = a\uparrow\uparrow\uparrow{b}\,\!,$

...

$H_n(a,b) = a\uparrow^{n-2}b \text{ for } n \ge 3\,\!,$

...

Knuth's notation could be extended to negative indices ≥ -2 in such a way as to agree with the entire hyperoperation sequence, except for the lag in the indexing:

$H_n(a,b) = a \uparrow^{n-2}b\text{ for } n \ge 0.\,\!$

The hyperoperations can thus be seen as an answer to the question "what's next" in the sequence: successor, addition, multiplication, exponentiation, and so on. Noting that

• $a + b = (a + (b - 1)) + 1$
• $a \cdot b = a + (a \cdot (b - 1))$
• $a ^ b = a \cdot (a ^ {(b - 1)})$
• $a\uparrow\uparrow b= a ^{a \uparrow\uparrow {(b - 1)}}$

the relationship between basic arithmetic operations is illustrated, allowing the higher operations to be defined naturally as above. The parameters of the hyperoperation hierarchy are sometimes referred to by their analogous exponentiation term; so a is the base, b is the exponent (or hyperexponent), and n is the rank (or grade).

In common terms, the hyperoperations are ways of compounding numbers that increase in growth based on the iteration of the previous hyperoperation. The concepts of successor, addition, multiplication and exponentiation are all hyperoperations; the successor operation (producing x+1 from x) is the most primitive, the addition operator specifies the number of times 1 is to be added to itself to produce a final value, multiplication specifies the number of times a number is to be added to itself, and exponentiation refers to the number of times a number is to be multiplied by itself.

Examples

This is a list of the first seven (0th to 6th) hyperoperations. (Notice that in this article, we define 0⁰ as 1.)

n	Operation (Hn(a, b))	Definition	Names	Domain
0	$1 + b$	${ 1 + {\underbrace{1 + 1 + 1 + \cdots + 1} \atop{b \mbox{ copies of 1}}} }$	hyper0, increment, successor, zeration	arbitrary
1	$a + b$	${ a + {\underbrace{1 + 1 + 1 + \cdots + 1} \atop{b \mbox{ copies of 1}}} }$	hyper1, addition	arbitrary
2	$a\cdot b$	${ {\underbrace{a + a + a + \cdots + a}} \atop{b \mbox{ copies of } a} }$	hyper2, multiplication	arbitrary
3	$a^b$ or $a \uparrow b$	${ {\underbrace{a \cdot a \cdot a \cdot a \cdot \ldots \cdot a}} \atop{b \mbox{ copies of } a} }$	hyper3, exponentiation	b real, with some multivalued extensions to complex numbers
4	$^{b}a$ or $a \uparrow\uparrow b$	${ {\underbrace{a \uparrow (a \uparrow (a \uparrow (a \uparrow \cdots \uparrow a))...)}} \atop{b \mbox{ copies of } a} }$	hyper4, tetration	a ≥ 0 or an integer, b an integer ≥ −1 (with some proposed extensions)
5	$a \uparrow\uparrow\uparrow b$ or $a \uparrow^3 b$	${ {\underbrace{a \uparrow\uparrow (a \uparrow\uparrow (a \uparrow\uparrow (a \uparrow\uparrow \cdots \uparrow\uparrow a))...)}} \atop{b \mbox{ copies of } a} }$	hyper5, pentation	a, b integers ≥ −1
6	$a \uparrow\uparrow\uparrow\uparrow b$ or $a \uparrow^4 b$	${ {\underbrace{a \uparrow^3 (a \uparrow^3 (a \uparrow^3 (a \uparrow^3 \cdots \uparrow^3 a))...)}} \atop{b \mbox{ copies of } a} }$	hyper6, hexation	a, b integers ≥ −1

Special cases

H_n(0, b) =

0, when n = 2, or n = 3, b ≥ 1, or n ≥ 4, b odd (≥ −1)

1, when n = 3, b = 0, or n ≥ 4, b even (≥ 0)

b, when n = 1

b + 1, when n = 0

H_n(a, 0) =

0, when n = 2

1, when n = 0, or n ≥ 3

a, when n = 1

H_n(a, −1) =

0, when n = 0, or n ≥ 4

a − 1, when n = 1

−a, when n = 2

1/a , when n = 3

History

One of the earliest discussions of hyperoperations was that of Albert Bennett in 1914, who developed some of the theory of commutative hyperoperations (see below). About 12 years later, Wilhelm Ackermann defined the function $\phi(a, b, n)\,\!$ which somewhat resembles the hyperoperation sequence.

In his 1947 paper, R. L. Goodstein introduced the specific sequence of operations that are now called hyperoperations, and also suggested the Greek names tetration, pentation, etc., for the extended operations beyond exponentiation (because they correspond to the indices 4, 5, etc.). As a three-argument function, e.g., $G(n,a,b) =H_n(a,b)$, the hyperoperation sequence as a whole is seen to be a version of the original Ackermann function $\phi(a,b,n)\,\!$ — recursive but not primitive recursive — as modified by Goodstein to incorporate the primitive successor function together with the other three basic operations of arithmetic (addition, multiplication, exponentiation), and to make a more seamless extension of these beyond exponentiation.

The original three-argument Ackermann function $\phi\,\!$ uses the same recursion rule as does Goodstein's version of it (i.e., the hyperoperation sequence), but differs from it in two ways. First, $\phi(a,b,n)\,\!$ defines a sequence of operations starting from addition (n = 0) rather than the successor function, then multiplication (n = 1), exponentiation (n = 2), etc. Secondly, the initial conditions for $\phi\,\!$ result in $\phi(a, b, 3) = a \uparrow\uparrow (b + 1)\,\!$, thus differing from the hyperoperations beyond exponentiation. The significance of the b + 1 in the previous expression is that $\phi(a,b,3)\,\!$ = $a^{a^{\cdot^{\cdot^{\cdot^a}}}}\,\!$, where b counts the number of operators (exponentiations), rather than counting the number of operands ("a"s) as does the b in $a \uparrow\uparrow b\,\!$, and so on for the higher-level operations. (See the Ackermann function article for details.)

Notations

This is a list of notations that have been used for hyperoperations.

Name	Notation equivalent to $H_n(a,b)$	Comment
Knuth's up-arrow notation	$a \uparrow^{n-2} b\,\!$	Used by Knuth (for n ≥ 3), and found in several reference books.
Goodstein's notation	$G(n, a, b)\,\!$	Used by Reuben Goodstein.
Original Ackermann function	$\begin{matrix} \phi(a, b, n-1) \ \text{ for } 1 \le n \le 3 \\ \phi(a, b-1, n-1) \ \text{ for } n \ge 4 \end{matrix}\,\!$	Used by Wilhelm Ackermann (for n ≥ 1)
Ackermann–Péter function	$A(n, b - 3) + 3 \ \text{for } a = 2\,\!$	This corresponds to hyperoperations for base 2 (a = 2)
Nambiar's notation	$a \otimes^{n-1} b\,\!$	Used by Nambiar (for n ≥ 1)
Box notation	$a {\,\begin{array}{|c|}\hline{\!n\!}\\\hline\end{array}\,} b\,\!$	Used by Rubtsov and Romerio.
Superscript notation	$a {}^{(n)} b\,\!$	Used by Robert Munafo.
Subscript notation (for lower hyperoperations)	$a {}_{(n)} b\,\!$	Used for lower hyperoperations by Robert Munafo.
Operator notation (for "extended operations")	$a O_{n-1} b\,\!$	Used for lower hyperoperations by John Donner and Alfred Tarski (for n ≥ 1).
Square bracket notation	$a[n]b\,\!$	Used in many online forums; convenient for ASCII.
Conway chained arrow notation	$a \to b \to (n-2)$	Used by John Horton Conway (for n ≥ 3)
Bowers' Exploding Array Function	$\{a,b,n,1\}$	Used by Jonathan Bowers (for n ≥ 1)

Variant starting from a

Main article: Ackermann function

In 1928, Wilhelm Ackermann defined a 3-argument function $\phi(a, b, n)$ which gradually evolved into a 2-argument function known as the Ackermann function. The original Ackermann function $\phi$ was less similar to modern hyperoperations, because his initial conditions start with $\phi(a, 0, n) = a$ for all n > 2. Also he assigned addition to n = 0, multiplication to n = 1 and exponentiation to n = 2, so the initial conditions produce very different operations for tetration and beyond.

n	Operation	Comment
0	$F_0(a, b) = a + b$
1	$F_1(a, b) = a\cdot b$
2	$F_2(a, b) = a^b$
3	$F_3(a, b) = a \uparrow\uparrow (b + 1)$	An offset form of tetration. The iteration of this operation is different than the iteration of tetration.
4	$F_4(a, b) = (x \mapsto a \uparrow\uparrow (x + 1))^b(a)$	Not to be confused with pentation.

Another initial condition that has been used is $A(0, b) = 2 b + 1$ (where the base is constant $a=2$), due to Rózsa Péter, which does not form a hyperoperation hierarchy.

Variant starting from 0

In 1984, C. W. Clenshaw and F. W. J. Olver began the discussion of using hyperoperations to prevent computer floating-point overflows. Since then, many other authors have renewed interest in the application of hyperoperations to floating-point representation. (Since H_n(a, b) are all defined for b = -1) While discussing tetration, Clenshaw et al. assumed the initial condition $F_n(a, 0) = 0$, which makes yet another hyperoperation hierarchy. Just like in the previous variant, the fourth operation is very similar to tetration, but offset by one.

n	Operation	Comment
0	$F_0(a, b) = b + 1$
1	$F_1(a, b) = a + b$
2	$F_2(a, b) = a\cdot b = e^{\ln(a) + \ln(b)}$
3	$F_3(a, b) = a^b$
4	$F_4(a, b) = a \uparrow\uparrow (b - 1)$	An offset form of tetration. The iteration of this operation is much different than the iteration of tetration.
5	$F_5(a, b) = (x \mapsto a \uparrow\uparrow (x - 1))^b(0)= 0 \text{ if } a>0$	Not to be confused with pentation.

Lower hyperoperations

An alternative for these hyperoperations is obtained by evaluation from left to right. Since

• $a+b = (a+(b-1))+1$
• $a\cdot b = (a\cdot (b-1))+a$
• $a^b = (a^{(b-1)})\cdot a$

define (with ° or subscript)

$a_{(n+1)}b = (a_{(n+1)}(b-1))_{(n)}a$

with

$\begin{array}{lcll} a_{(1)}b & = & a+b \\ a _ {(2)} 0 & = & 0 \\ a _ {(n)} 1 & = & a & \text{for } n>2 \\ \end{array}$

This was extended to ordinal numbers by Donner and Tarski,^{[Definition 1]} by :

$\begin{array}{lcl} \alpha O_0 \beta & = & \alpha + \beta \\ \alpha O_\gamma \beta & = & \sup\limits_{\eta<\beta, \xi<\gamma}(\alpha O_\gamma \eta) O_\xi \alpha \end{array}$

It follows from Definition 1(i), Corollary 2(ii), and Theorem 9, that, for a ≥ 2 and b ≥ 1, that

$a O_n b = a _{(n+1)} b$

But this suffers a kind of collapse, failing to form the "power tower" traditionally expected of hyperoperators:^{[Theorem 3(iii)]}

$\alpha_{(4)}(1+\beta) = \alpha^{(\alpha^\beta)}.$

If α ≥ 2 and γ ≥ 2,^{[Corollary 33(i)]}

$\alpha_{(1+2\gamma+1)}\beta \leq \alpha_{(1+2\gamma)}(1+3\alpha\beta).$

n	Operation	Comment
0	$F_0(a,b) = a + 1$	increment, successor, zeration
1	$F_1(a, b) = a + b$
2	$F_2(a, b) = a\cdot b$
3	$F_3(a, b) = a^b$	This is exponentiation.
4	$F_4(a, b) = a^{(a^{(b-1)})}$	Not to be confused with tetration.
5	$F_5(a, b) = (x \mapsto x^{x^{(a-1)}})^{b-1}(a)$	Not to be confused with pentation. Similar to tetration.

Commutative hyperoperations

Commutative hyperoperations were considered by Albert Bennett as early as 1914, which is possibly the earliest remark about any hyperoperation sequence. Commutative hyperoperations are defined by the recursion rule

$F_{n+1}(a, b) = \exp(F_n(\ln(a), \ln(b)))$

which is symmetric in a and b, meaning all hyperoperations are commutative. This sequence does not contain exponentiation, and so does not form a hyperoperation hierarchy.

n	Operation	Comment
0	$F_0(a, b) = \ln(e^{a} + e^{b})$
1	$F_1(a, b) = a + b$
2	$F_2(a, b) = a\cdot b = e^{\ln(a) + \ln(b)}$	This is due to the properties of the logarithm.
3	$F_3(a, b) = a^{\ln(b)} = e^{\ln(a)\ln(b)}$	A commutative form of exponentiation.
4	$F_4(a, b) = e^{e^{\ln(\ln(a))\ln(\ln(b))}}$	Not to be confused with tetration.

See also

• Large numbers