User:Sligocki/up-arrow properties

This article is now available on my blog: https://www.sligocki.com/2009/10/07/up-arrow-properties.html

Some useful definitions and properties for Knuth's up-arrow notation

Definition

$a\uparrow ^{n}b$ is defined for a, b and n are integers $n\geq 1$ and $b\geq 0$.

1. $a\uparrow ^{1}b=a^{b}$
2. $a\uparrow ^{n}0=1$
3. $a\uparrow ^{n}b=a\uparrow ^{n-1}(a\uparrow ^{n}(b-1))$

Therefore $a\uparrow ^{n}b=a\uparrow ^{n-1}a\uparrow ^{n-1}\cdots \uparrow ^{n-1}a$ (with b copies of a, where $\uparrow$ is right associative) and so it is seen as an extension of the series of operations $+,\times ,\uparrow ,\uparrow ^{2},\dots$ where $\uparrow$ is basic exponentiation

Basic Properties

1. $a\uparrow ^{n}1=a$
2. $2\uparrow ^{n}2=2^{2}=2\times 2=2+2=4$

Extension

We can extend the uparrows to include multiplication and addition as the hyper operator.

This system may be consistently expanded to include multiplication, addition and incrementing:

1. $a\uparrow ^{-2}b=b+1$
2. $a\uparrow ^{-1}b=a+b$
3. $a\uparrow ^{0}b=ab$
4. $a\uparrow ^{1}b=a^{b}$
5. $a\uparrow ^{n}0=1$ (for $n\geq 1$)
6. $a\uparrow ^{n}b=a\uparrow ^{n-1}(a\uparrow ^{n}(b-1))$

Proof of consistency by induction.

We will show that Rules 3, 5 and 6 imply rule 4 Assume that $a\uparrow ^{1}\beta =a^{\beta }$ for any $\beta <b$, then

$a\uparrow ^{1}b=a\uparrow ^{0}(a\uparrow ^{1}(b-1))=a\cdot a^{b-1}=a^{b}$ by rule 6, rule 3 and assumption

Furthermore, $a\uparrow ^{1}0=1=a^{0}$ by rule 5

Thus the assumption is true for all $\beta \geq 0$

Likewise we can show that Rules 2, 5, 6 imply Rule 3 and that Rules 1, 5, 6 imply Rule 2. Therefore, Rules 1, 5, 6 imply Rules 4, 5, 6 and so consistently extend the system.

QED

Clearly some of the properties do not extend.

Changing Bases

Todo: How do you change bases.

Example:

• $3\uparrow ^{k}n\approx 10\uparrow ^{k}n^{\prime }$ what is n'?

For k = 1:

$a\uparrow n=a^{n}=b^{n\log _{b}(a)}=b\uparrow (\log _{b}(a)n)$

For k = 2. For all $a<b$ there is a unique $\delta$ such that

$b\uparrow \uparrow (n-\delta -1)<a\uparrow \uparrow n<b\uparrow \uparrow (n-\delta )$ for all sufficiently large n

Examples:

• $10\uparrow \uparrow (n-1)<3\uparrow \uparrow n<10\uparrow \uparrow n$ for all $n\geq 3$
• $10\uparrow \uparrow (n-3)<2\uparrow \uparrow n<10\uparrow \uparrow (n-2)$ for all $n\geq 4$

Thus the base of a tetration is not very important, they all grow at approximately the same rate eventually.

In fact these numbers $\delta$ grow very slowly.

Claim:

$a\uparrow \uparrow (n+k-1)<(a\uparrow \uparrow k)\uparrow \uparrow n<a\uparrow \uparrow (n+k)\,$

Note, the left inequality is easy to prove:

$(a\uparrow \uparrow k)\uparrow \uparrow n=((a\uparrow \uparrow k)\uparrow )^{n-1}(a\uparrow \uparrow k)>(a\uparrow )^{n-1}(a\uparrow \uparrow k)=a\uparrow \uparrow (n+k-1)\,$

Claim:

$n\uparrow ^{n}n<(3\uparrow ^{n}3)\uparrow ^{n}(3\uparrow ^{n}3-3)<3\uparrow ^{n}(3\uparrow ^{n}3)=3\uparrow ^{n+1}3\,$