Hyperoperation: Information from Answers.com

This article is about hyperoperations in arithmetic. For the group theory term with the same name, see hyperoperation (group theory).

It has been suggested that pentation be merged into this article or section. (Discuss)

In mathematics, the hyperoperation sequence^{[nb 1]} is a sequence of binary operations that starts with addition, multiplication and exponentiation, called hyperoperations^[1]^[12]^[14] in general. The nth member of this sequence is named by Reuben Goodstein after the Greek prefix of n suffixed with -ation (such as tetration, pentation)^[6] and can be written using $(n - 2)$ arrows in Knuth's up-arrow notation. Each hyperoperation is defined recursively in terms of the previous one, as is the case with arrow notation. The part of the definition that does this is the recursion rule of the Ackermann function:

$a \uparrow^n b = a \uparrow^{n-1} \left(a \uparrow^n (b-1)\right)$

which is common to many variants of hyperoperations (see below).

1 Definition
2 Examples
3 History
4 Notations
5 Generalization
6 See also
7 Notes
8 References

Definition

Main article: Knuth's up-arrow notation

The hyperoperation sequence is a sequence $H n$ of binary operations on $\mathbb{N}$ , indexed by $\mathbb{N}$ , which starts with addition (n = 1), multiplication (n = 2) and exponentiation $(n = 3)$ . The parameters of the hyperoperation hierarchy are referred to by their analogous exponentiation term^[15]; so a is the base, b is the exponent (or hyperexponent^[13]), and n is the rank (or grade^[7]).

Using arrow notation we can define hyperoperations as

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

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

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

this produces a natural relationship between the hyperoperations, and allows higher operations to be defined, which produce very large numbers from small inputs, as further explained in the separate article on tetration.

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 addition, multiplication and exponentiation are all hyperoperations; 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 six hyperoperations.

n	Operation	Definition	Names	Domain
0	$b + 1$	${ 1 + {\underbrace{1 + 1 + 1 + \cdots + 1}_{b}} }$	hyper0, increment, successor	b arbitrary
1	$a + b$	${ a + {\underbrace{1 + 1 + 1 + \cdots + 1}_{b}} }$	hyper1, addition	arbitrary
2	$a b$	${ {\underbrace{a + a + a + \cdots + a}} \atop{b} }$	hyper2, multiplication	arbitrary
3	$a \uparrow b = a^b$	${ {\underbrace{a \cdot a \cdot a \cdot a \cdot \ldots \cdot a}} \atop{b} }$	hyper3, exponentiation	a > 0, b real, or a non-zero, b an integer, with some multivalued extensions to complex numbers
4	$a \uparrow\uparrow b$	${ {\underbrace{a \uparrow a \uparrow a \uparrow \cdots \uparrow a}} \atop{b} }$	hyper4, tetration	a > 0, 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 \cdots \uparrow\uparrow a}} \atop{b} }$	hyper5, pentation	a and b integers, a > 0, b ≥ 0
6	$a \uparrow^4 b$	${ {\underbrace{a \uparrow^3 a \uparrow^3 \cdots \uparrow^3 a}} \atop{b} }$	hyper6, hexation	a and b integers, a > 0, b ≥ 0

History

One of the earliest discussions of hyperoperations was that of Albert Bennett^[7] in 1914, who developed some of the theory of commutative hyperoperations (see below). About 12 years later, Wilhelm Ackermann defined the function $φ(a, b, n)$ ^[16] which somewhat resembles the hyperoperation sequence. The original Ackermann function with three arguments used the same recursion rule, but it differs from modern hyperoperations in at least two ways. First, it assigned addition to $n = 0$ , multiplication to $n = 1$ and exponentiation to $n = 2$ . Secondly, the initial conditions of $φ$ indicate that $\phi(a, b, 3) = a \uparrow\uparrow (b + 1)$ , which produces very different values than hyperoperations above exponentiation.^[8]^[17]^[18]

In 1947, Reuben Goodstein^[6] defined the hyperoperation sequence as it is used today,^{[dubious – discuss]} where he used the notation $G (n, a, b)$ for what would be written as $a \uparrow^{n-2}b$ in arrow notation. In the 1947 paper, Goodstein introduced the names "tetration", "pentation", "hexation", etc., for the successive operators beyond exponentiation.

Notations

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

Name	Notation	Comment
standard arrow notation	$a \uparrow^{n-2} b = H_n(a, b)$	Used by Knuth,^[19] and found in several reference books.^[20]^[21]
Goodstein's notation	$G (n, a, b)$	Used by Reuben Goodstein.^[6]
original Ackermann function	$A (a, b, n - 1) = H n (a, b)$	This is not quite the same as hyperoperations.
modern Ackermann function	$A (n, b - 3) + 3 = H n (2, b)$	This the same as hyperoperations for base 2.
Nambiar's notation	$a \otimes^n b$	Used by Nambiar^[22]
Box notation	$a {\,\begin{array}{\|c\|}\hline{\!n\!}\\\hline\end{array}\,} b$	Used by Rubtsov and Romerio.^[14]^[15]
Superscript notation	$a (n) b$	Used by Robert Munafo.^[11]
Subscript notation	$a (n) b$	Used for lower hyperoperations by Robert Munafo.^[11]
Square bracket notation	`a[n]b`	Used in many online forums; convenient for ASCII.

Generalization

For different initial conditions or different recursion rules, very different operations can occur. Some mathematicians refer to all variants as examples of hyperoperations.

In the general sense, a hyperoperation hierarchy $(S,\,I,\,F)$ is a family $(F_n)_{n \in I}$ of binary operations on $S$ , indexed by a set $I$ , such that there exists $i, j, k \in I$ where

$F i (a, b) = a + b$ (addition),
$F j (a, b) = a b$ (multiplication), and
$F k (a, b) = a b$ (exponentiation).

Also, if the last condition is relaxed (i.e. there is no exponentiation), then we may also include the commutative hyperoperations, described below. Although one could list each hyperoperation explicitly, this is generally not the case. Most variants only include the successor function (or addition) in their definition, and redefine multiplication (and beyond) based on a single recursion rule that applies to all ranks. Since this is part of the definition of the hierarchy, and not a property of the hierarchy itself, it is difficult to define formally.

There are many possibilities for hyperoperations that are different from Goodstein's version. By using different initial conditions for $F n (a,0)$ or $F n (a,1)$ , the iterations of these conditions may produce different hyperoperations above exponentiation, while still corresponding to addition and multiplication. The modern definition of hyperoperations includes $F n (a,0) = 1$ for all $n \ge 3$ , whereas the variants below include $F n (a,0) = a$ , and $F n (a,0) = 0$ .

An open problem in hyperoperation research is whether the hyperoperation hierarchy $(\mathbb{N}, \mathbb{N}, F)$ can be generalized to $(\mathbb{C}, \mathbb{C}, F)$ , and whether $(\mathbb{C}, F_n)$ forms a quasigroup (with restricted domains).

Variant starting from $a$

Main article: Ackermann function

In 1928, Wilhelm Ackermann defined a 3-argument function $φ(a, b, n)$ which gradually evolved into a 2-argument function known as the Ackermann function. The original Ackermann function $φ$ was less similar to modern hyperoperations, because his initial conditions start with $φ(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 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 much different than the iteration of tetration.
4	$F_4(a, b) = (x \to 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.^[23] Since then, many other authors^[24]^[25]^[26] have renewed interest in the application of hyperoperations to floating-point representation. While discussion 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
1	$F 1 (a, b) = a + b$
2	$F 2 (a, b) = a 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 \to a \uparrow\uparrow (x - 1))^b(0)$	Not to be confused with pentation.

Commutative hyperoperations

Commutative hyperoperations were considered by Albert Bennett as early as 1914,^[7] 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 b = e ln(a) + ln(b)$	This is due to the properties of the logarithm.
3	$F 3 (a, 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.

Balanced hyperoperations

Balanced hyperoperations, first considered by Clément Frappier in 1991,^[27] are based on the iteration of the function $x x$ , and are thus related to Steinhaus-Moser notation. The recursion rule used in balanced hyperoperations is

$F_{n+1}(a, b) = (x \to F_n(x, x))^{\log_2(b)}(a)$

which requires continuous iteration, even for integer b.

n	Operation	Comment
0		Rank 0 does not exist.^{[nb 2]}
1	$F 1 (a, b) = a + b$
2	$F_2(a, b) = ab = a 2^{\log_2(b)}$
3	$F_3(a, b) = a^b = a^{2^{\log_2(b)}}$	This is exponentiation.
4	$F_4(a, b) = (x \to x^x)^{\log_2(b)}(a)$	Not to be confused with tetration.

Lower hyperoperations

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

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

define (with ° or subscript) $a (n + 1) b = (a (n + 1) (b - 1)) (n) a$ with $a (1) b = a + b$ , $a (2) 0 = 0$ , and $a (n) 0 = 1$ for $n > 2$

But this suffers a kind of collapse, failing to form the "power tower" traditionally expected of hyper4: $a_{(4)}b = a^{(a^{(b-1)})}$

How can $a (n) b$ be so different from $a (n) b$ for n>3? This is because of a symmetry called associativity that's defined into + and × (see field) but which ^ lacks. It is more apt to say the two (n)s were decreed to be the same for n<4. (On the other hand, one can object that the field operations were defined to mimic what had been "observed in nature" and ask why "nature" suddenly objects to that symmetry…)

The other degrees do not collapse in this way, and so this family has some interest of its own as lower (perhaps lesser or inferior) hyperoperations. With hyperfunctions greater than three, it is also lower in the sense that the answers you get are actually often a lot lower than the answers you get when using the standard method.

n	Operation	Comment
0	$b + 1$	increment, successor, zeration
1	$F 1 (a, b) = a + b$
2	$F 2 (a, b) = a 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 \to x^{x^{(a-1)}})^{b-1}(a)$	Not to be confused with pentation.

Notes

^ The hyperoperation sequence has historically been referred to by many names, including: the Ackermann function^[1]^[2] (3-argument), the Ackermann hierarchy^[3], the Grzegorczyk hierarchy^[4]^[5] (which is more general), Goodstein's function^[6], operation of the nth grade^[7], z-fold iterated exponentiation of x with y^[8], arrow operations^[9], reihenalgebra^[10] and hyper-n.^[1]^[10]^[11]^[12]^[13] The most commonly used of any of these terms is the Ackermann function, whose Google search gives almost a million hits, mostly refering to the 2-argument function.
^ If there was a rank 0 balanced hyperoperation $f (a, b)$ , then addition would be $a + b = (x \to f(x, x))^{\log_2(b)}(a)$ . Substituting $b = 1$ in this equation gives $a + 1 = (x \to f(x, x))^{0}(a) = a$ which is a contradiction.

References

^ ^a ^b ^c Daniel Geisler (2003). "What lies beyond exponentiation?". http://tetration.org/. Retrieved 2009-04-17.
^ Stephen Wolfram (2002). A New Kind of Science (NKS). Wolfram Media. pp. 897?. ISBN 1579550088.
^ Harvey M. Friedman (Jul. 2001). "Long Finite Sequences". Journal of Combinatorial Theory, Series A 95 (1): 102–144. http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WHS-45RFJ9C-5&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_version=1&_urlVersion=0&_userid=10&md5=8097ac57c9dbe05b99fef6a95309f1df. Retrieved 2009-04-17.
^ Manuel Lameiras Campagnola and Cristopher Moore and José Félix Costa (Dec. 2002). "Transfinite Ordinals in Recursive Number Theory". Journal of Complexity 18 (4): 977–1000. http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WHX-482XFM6-4&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=f4e3ffc2a28e8abd16cde236197fd487. Retrieved 2009-04-17.
^ Marc Wirz (1999). "Characterizing the Grzegorczyk hierarchy by safe recursion". CiteSeer. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.3374. Retrieved 2009-04-21.
^ ^a ^b ^c ^d R. L. Goodstein (Dec. 1947). "Transfinite Ordinals in Recursive Number Theory". Journal of Symbolic Logic 12 (4): 123–129. http://www.jstor.org/stable/2266486. Retrieved 2009-04-17.
^ ^a ^b ^c ^d Albert A. Bennett (Dec. 1915). "Note on an Operation of the Third Grade". Annals of Mathematics, Second Series 17 (2): 74–75. http://www.jstor.org/stable/2007124. Retrieved 2009-04-17.
^ ^a ^b Paul E. Black (2009-03-16). "Ackermann's function". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology (NIST). http://www.itl.nist.gov/div897/sqg/dads/HTML/ackermann.html. Retrieved 2009-04-17.
^ J. E. Littlewood (Jul. 1948). "Large Numbers". Mathematical Gazette 32 (300): 163–171. http://www.jstor.org/stable/3609933. Retrieved 2009-04-17.
^ ^a ^b Markus Müller (1993). "Reihenalgebra". http://www.math.tu-berlin.de/~mueller/reihenalgebra.pdf. Retrieved 2009-04-17.
^ ^a ^b ^c Robert Munafo (1999-11). "Inventing New Operators and Functions". Large Numbers at MROB. http://www.mrob.com/pub/math/largenum-3.html. Retrieved 2009-04-17.
^ ^a ^b A. J. Robbins (2005-11). "Home of Tetration". http://tetration.itgo.com/index.html. Retrieved 2009-04-17. ^{[dead link]}
^ ^a ^b I. N. Galidakis (2003). "Mathematics". http://ioannis.virtualcomposer2000.com/math/index.html. Retrieved 2009-04-17.
^ ^a ^b C. A. Rubtsov and G. F. Romerio (2005-12). "Ackermann's Function and New Arithmetical Operation". http://forum.wolframscience.com/showthread.php?s=&threadid=956. Retrieved 2009-04-17.
^ ^a ^b G. F. Romerio (2008-01-21). "Hyperoperations Terminology". Tetration Forum. http://math.eretrandre.org/tetrationforum/attachment.php?aid=208. Retrieved 2009-04-21.
^ Wilhelm Ackermann (1928). "Zum Hilbertschen Aufbau der reellen Zahlen". Mathematische Annalen 99: 118–133. doi:10.1007/BF01459088.
^ Robert Munafo (1999-11-03). "Versions of Ackermann's Function". Large Numbers at MROB. http://www.mrob.com/pub/math/ln-2deep.html. Retrieved 2009-04-17.
^ J. Cowles and T. Bailey (1988-09-30). "Several Versions of Ackermann's Function". Dept. of Computer Science, University of Wyoming, Laramie, WY. http://www.cs.utexas.edu/users/boyer/ftp/nqthm/nqthm-1992/examples/basic/peter.events. Retrieved 2009-04-17.
^ Donald E. Knuth (Dec. 1976). "Mathematics and Computer Science: Coping with Finiteness". Science 194 (4271): 1235–1242. http://www.sciencemag.org/cgi/content/abstract/194/4271/1235. Retrieved 2009-04-21.
^ Daniel Zwillinger (2002). CRC standard mathematical tables and formulae, 31st Edition. CRC Press. pp. 4. ISBN 1584882913.
^ Eric W. Weisstein (2003). CRC concise encyclopedia of mathematics, 2nd Edition. CRC Press. pp. 127–128. ISBN 1584883472.
^ K. K. Nambiar (1995). "Ackermann Functions and Transfinite Ordinals". Applied Mathematics Letters 8 (6): 51–53. http://www.sciencemag.org/cgi/content/abstract/194/4271/1235. Retrieved 2009-04-21.
^ C.W. Clenshaw and F.W.J. Olver (Apr. 1984). "Beyond floating point". Journal of the ACM 31 (2): 319–328. http://portal.acm.org/citation.cfm?id=62.322429. Retrieved 2009-04-21.
^ W. N. Holmes (Mar. 1997). "Composite Arithmetic: Proposal for a New Standard". Computer 30 (3): 65–73. http://portal.acm.org/citation.cfm?id=620661. Retrieved 2009-04-21.
^ R. Zimmermann (1997). "Computer Arithmetic: Principles, Architectures, and VLSI Design". Lecture notes, Integrated Systems Laboratory, ETH Zürich. http://www.iis.ee.ethz.ch/~zimmi/publications/comp_arith_notes.pdf. Retrieved 2009-04-17.
^ T. Pinkiewicz and N. Holmes and T. Jamil (2000). "Design of a composite arithmetic unit for rational numbers". Proceedings of the IEEE. pp. 245–252. http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=845571. Retrieved 2009-04-17.
^ C. Frappier (1991). "Iterations of a kind of exponentials". Fibonacci Quarterly 29 (4): 351–361.

v • d • e Hyperoperations

Basic	Addition · Multiplication · Exponentiation · Tetration · Pentation

Inverse, group 1	Subtraction · Division · nth root · Super-root

Inverse, group 2	Subtraction · Division · Logarithm · Super-logarithm

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

Hyperoperation

Contents