Jump to content

User:Sligocki/up-arrow properties

From Wikipedia, the free encyclopedia
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 .

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]

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:

  1. (for )


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:


For k = 2. For all there is a unique such that

for all sufficiently large n

Examples:

  • for all
  • for all

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:

Note, the left inequality is easy to prove:


Claim:

Notes

[edit]
  1. ^ Note, for any a,b, d is uniquely defined, let's call it . Making a small table we get:
    a\b 2 3 4 5 6 ... 10 100 1000 10000
    2 2 2 2 3 ... 3 3 3 4
    3 1 1 1 ... 1 2 2 2

    As you can see, these values rise very slowly, in fact, (I believe that) if , then . The following table shows the smallest number b such that

    d\a 2 3 4 5 6 7 8 ... 10 100
    1 4 5 6 7 8 9 ... 11 101
    2 3 12 81 759 9164 135608 2376342 ...
    3 6 ...
    4 5298 ...