- 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[edit]
is defined for a, b and n are integers
and
.
![{\displaystyle a\uparrow ^{1}b=a^{b}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1db933c640e883c9ad0859068e16e1f3c481ffb2)
![{\displaystyle a\uparrow ^{n}0=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bbb5fff09142a656b9964ffaae70b04a8c5a5199)
![{\displaystyle a\uparrow ^{n}b=a\uparrow ^{n-1}(a\uparrow ^{n}(b-1))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1d943eade0e5fbd2951880141b926553a6982b3a)
Therefore
(with b copies of a, where
is right associative) and so it is seen as an extension of the series of operations
where
is basic exponentiation
Basic Properties[edit]
![{\displaystyle a\uparrow ^{n}1=a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c012501ba27ba279960a31f349d113be5cd7ed88)
![{\displaystyle 2\uparrow ^{n}2=2^{2}=2\times 2=2+2=4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9f7f889ce3537c74d9d8ecc39997f8dcfd01b7c9)
Extension[edit]
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:
![{\displaystyle a\uparrow ^{-2}b=b+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a9e328b819e5de3ab76bedb635ca37a98ec26d5)
![{\displaystyle a\uparrow ^{-1}b=a+b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9dc8e6f6f0aacd00c8107b8a95ba821d21b00b7d)
![{\displaystyle a\uparrow ^{0}b=ab}](https://wikimedia.org/api/rest_v1/media/math/render/svg/877376981cb48e588590469dc10f95f2ef7366c7)
![{\displaystyle a\uparrow ^{1}b=a^{b}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1db933c640e883c9ad0859068e16e1f3c481ffb2)
(for
)
![{\displaystyle a\uparrow ^{n}b=a\uparrow ^{n-1}(a\uparrow ^{n}(b-1))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1d943eade0e5fbd2951880141b926553a6982b3a)
- Proof of consistency by induction.
We will show that Rules 3, 5 and 6 imply rule 4
Assume that
for any
, then
by rule 6, rule 3 and assumption
Furthermore,
by rule 5
Thus the assumption is true for all
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[edit]
Todo: How do you change bases.
Example:
what is n'?
For k = 1:
![{\displaystyle a\uparrow n=a^{n}=b^{n\log _{b}(a)}=b\uparrow (\log _{b}(a)n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d42de9a1b77820947a879a36496b68aa0732c8c0)
For k = 2. For all
there is a unique
such that
for all sufficiently large n
Examples:
for all ![{\displaystyle n\geq 3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/73136e4a27fe39c123d16a7808e76d3162ce42bb)
for all ![{\displaystyle n\geq 4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/25010fec4b0f68f1b46f49d14917d962acca0b16)
Thus the base of a tetration is not very important, they all grow at approximately the same rate eventually.[note 1]
In fact these numbers
grow very slowly.
Claim:
![{\displaystyle a\uparrow \uparrow (n+k-1)<(a\uparrow \uparrow k)\uparrow \uparrow n<a\uparrow \uparrow (n+k)\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/239f0ff94336d57f2d03572b0a70ae3d91d84653)
Note, the left inequality is easy to prove:
![{\displaystyle (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)\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b002d95a1985e69ac3266d9e5f7830e5a8bc8070)
Claim:
![{\displaystyle 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\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3ef77895e6226e072413f4a58f52f430f48c3ead)