Knuth's Up Arrow Operator (a.k.a. compounded arithmetic operator)

[Michael Orion]

Knuth's up arrow operator is the generalization of the arithmetic
operators in the series: addition, multiplication, exponentiation, ...
These operators are also known as compounded arithmetic operators,
a less well known term but one I like better because it is more
descriptive.

Here is my question: Are there a well defined inverses of the
compounded arithmetic operators? If so were can I learn more
about them?

FYI, the k-th compounded arithmetic operator, <k>, is defined
as follows: Let a, b, and k be positive integers. Then

a <1> b = a + b
a <k> 1 = a for k > 1
a <k> b = a <k-1> (a <k> (b-1))

E.g.
a <1> b = a + b
a <2> b = a x b
a <3> b = a ^ b
a <4> b = a ^ (a ^ (a ^ (...))) (a appears b times)

Thanks for any insight you can offer.

- MO

[Ioannis]

Michael Orion wrote:
[snip]

> Here is my question: Are there a well defined inverses of the
> compounded arithmetic operators? If so were can I learn more
> about them?

[snip]

> Thanks for any insight you can offer.

For general info, look at:

http://www.tetration.org

for the answer to your question, specifically:
http://users.forthnet.gr/ath/jgal/math/exponents3.html

> - MO
--
I. N. G. --- http://users.forthnet.gr/ath/jgal/

[Michael Orion]

On 23 Jan 2005, Ioannis wrote:
>Michael Orion wrote:
>[snip]
>> Here is my question: Are there a well defined inverses of the
>> compounded arithmetic operators? If so were can I learn more
>> about them?
>[snip]
>> Thanks for any insight you can offer.
>
>For general info, look at:
>

><a href="http://www.tetration.org">http://www.tetration.org</a>

>
>for the answer to your question, specifically:

><a href="http://users.forthnet.gr/ath/jgal/math/exponents3.html">http://users.forthnet.gr/ath/jgal/math/exponents3.html</a>
>
>> - MO
>--
>I. N. G. --- <a href="http://users.forthnet.gr/ath/jgal/">http://users.forthnet.gr/ath/jgal/</a>

Thanks! The second paper address many of the questions I had
regarding cao (compounded arithmetic operation). In particular
I was looking for answers to

1) Let a and b be naturals (positive integers). We can solve for c in
1a) a + c = b with c in the integers;
1b) a x c = b with c in the rationals;
1c) a ^ c = b with c in the reals.
Can we prove that a <k> c = b can be solved for c with c in the
reals for any k >= 3?

2) log_a(b) is the solution to a ^ c = b. We can show that
log_a(b) = log_x(b)/log_x(a). Let lk_a(b) be the solution to
a <k> c = b. Is there a formula for a change in base for the lk
funtion as there is for the log function? (b.t.w. log = l3). I.e.
can we write something like lk_a(b) = lk_x(b) * lk_x(a), for some
function *?

One final thought. I love the term "tetration" but I am not too keen
on the pre-superscript notation. It would seem that a notation
like Knuth's or the <k> notation I am using in this thread would be
preferred as it generalizes immediately to any value of k.

- MO

[Ioannis]

Michael Orion wrote:

[snip]

> Thanks! The second paper address many of the questions I had
> regarding cao (compounded arithmetic operation). In particular
> I was looking for answers to
>
> 1) Let a and b be naturals (positive integers). We can solve for c in
> 1a) a + c = b with c in the integers;
> 1b) a x c = b with c in the rationals;
> 1c) a ^ c = b with c in the reals.
> Can we prove that a <k> c = b can be solved for c with c in the
> reals for any k >= 3?
>
> 2) log_a(b) is the solution to a ^ c = b. We can show that
> log_a(b) = log_x(b)/log_x(a). Let lk_a(b) be the solution to
> a <k> c = b. Is there a formula for a change in base for the lk
> funtion as there is for the log function? (b.t.w. log = l3). I.e.
> can we write something like lk_a(b) = lk_x(b) * lk_x(a), for some
> function *?

For a start, look at:
http://en.wikipedia.org/wiki/Tetration

in particular the inverse function "slog" (or superlogarithm)

> One final thought. I love the term "tetration" but I am not too keen
> on the pre-superscript notation. It would seem that a notation
> like Knuth's or the <k> notation I am using in this thread would be
> preferred as it generalizes immediately to any value of k.

Some authors choose the pre-superscript notation merely on aesthetic
grounds. It was first proposed by Maurer. On this forum, people usually
write a^^b to mean tetration: a^a^a^...^a (b-times).

> - MO
--
I. N. G. --- http://users.forthnet.gr/ath/jgal/

[A N Niel]

> Can we prove that a <k> c = b can be solved for c with c in the
> reals for any k >= 3?

Before asking this, you will have to DEFINE a <k> c with c in the reals.

Note that (a ^^ b) ^^ c CANNOT in general be written as a ^^ d,
where d is a formula involving only b and c, not involving a.
So defining a ^^ (1/2) = x as solution x of x ^^ 2 = a is
not sensible.

[r.e.s.]

> Michael Orion wrote:

>>> a <1> b = a + b
>>> a <k> 1 = a for k > 1
>>> a <k> b = a <k-1> (a <k> (b-1))

>> I love the term "tetration" but I am not too keen

>> on the pre-superscript notation. It would seem that a
>> notation like Knuth's or the <k> notation I am using in
>> this thread would be preferred as it generalizes
>> immediately to any value of k.

I agree, and have personally used variants like [k] for years.
It's nice to index the entire hierarchy, using Ackermann's
indexing, from which tetration gets its name:
[0]=' (successor), [1]=+, [2]=*, [3]=^, [4]=^^,...
Starting with successor, the definition is as follows,
for integers b >= 0, k >= 0, n >= 0:
b[0]n = n'
b[1]0 = b
b[2]0 = 0
b[k+3]0 = 1
b[k+1](n+1) = b[k](b[k+1]n).

For a case in which this greatly clarifies (IMO) an
otherwise messy hard-to-read presentation, see my posting
of a separate thread on "Level-k Goodstein Sequences".

Also note that b plays the role of a "base", which often
is fixed, so the operator can be interpreted as unary (i.e.,
b[k]a is the unary operator b[k] applied to a) and in that
context we can write simply [k+1](n+1) = [k]([k+1]n) (i.e.,
[k]n denotes operator b[k] with argument n).

--r.e.s.

[Michael Orion]

Dear R.E.S.,

I was not able to find your posting, "Level-k Goldstein Sequences".
Could you post a link? Also, I like very much the "foundations"
you give (i.e. b[0]n = n', b[1]0 = b, etc.). Is there a good textbook
on the subject. For that matter is there a good name for the subject.
I use the term "compounded arithmetic operation". A term like,
"Knuth's up-arrow" leaves me cold because it names but does not
describe. Anyway, any papers or texts you can suggest would be
apprecieated.

- MO

[Amadeus Train-Owwell Zirconium]

does Knuth deal with the nonassociativety
of powering?... (2^2)^h + 1 doesn't
equal 2^(2^h) + 1 e.g., in general.

Michael Orion wrote:

> >Starting with successor, the definition is as follows,
> >for integers b >= 0, k >= 0, n >= 0:
> >b[0]n = n'
> >b[1]0 = b
> >b[2]0 = 0
> >b[k+3]0 = 1
> >b[k+1](n+1) = b[k](b[k+1]n).

> I use the term "compounded arithmetic operation". A term like,

> "Knuth's up-arrow" leaves me cold because it names but does not

.
--Pinochet's Programme for Social Security!
http://larouchepub.com