请输入您要查询的字词:

 

单词 PropertiesOfSuperexponentiation
释义

properties of superexponentiation


In this entry, we list some basic properties of the superexponetial functionMathworldPlanetmath f:2, defined recursively by

f(m,0)=m,f(m,n+1)=mf(m,n).

Furthermore, we set f(0,n):=0 for all n.

Given m, the values of f are

m,mm,mmm,,m.m,,

where the evaluation of these values start from the top, for example: 333=381.

Proposition 1.

Suppose x,y,zN (including 0), and for all except the first assertion, x>1.

  1. 1.

    xf(x,y).

  2. 2.

    f(x,y) is increasing in both arguments.

  3. 3.

    2f(x,y)f(x,y+1).

  4. 4.

    f(x,y)2f(x,y+1).

  5. 5.

    f(x,y)f(x,y)f(x,y+2)

  6. 6.

    f(x,y)+f(x,z)f(x,1+max{y,z}).

  7. 7.

    f(x,y)f(x,z)f(x,1+max{y,z}).

  8. 8.

    f(x,y)f(x,z)f(x,2+max{y,z}).

  9. 9.

    f(f(x,y),z)f(x,y+2z).

  10. 10.

    y<f(x,y).

Proof.

Most of the proofs are done by inductionMathworldPlanetmath.

  1. 1.

    The case when x=0 is obvious. Assume now that x0. Induct on y. The case y=0 is clear. Suppose xf(x,y). Then xxxxf(x,y)=f(x,y+1).

  2. 2.

    To see f(x,y)<f(x,y+1) for x>1, induct on y. First, f(x,0)=x<xx=f(x,1). Next, assume f(x,y)<f(x,y+1). Then f(x,y+1)=xf(x,y)<xf(x,y+1)=f(x,y+1).

    To see f(x,y)<f(x+1,y) for x>1, again induct on y. First, f(x,0)=x<x+1=f(x+1,y). Next, assume f(x,y)<f(x+1,y). Then f(x,y+1)=xf(x,y)<(x+1)f(x,y)<(x+1)f(x+1,y)=f(x+1,y+1).

  3. 3.

    Induct on y: if y=0, then 2f(x,0)=2xx2xx=f(x,1). Next, assume 2f(x,y)f(x,y+1). Then 2f(x,y+1)=xf(x,y)x2f(x,y)xf(x,y+1)=f(x,y+2).

  4. 4.

    If y=0, then f(x,0)2=x2xx=xf(x,0)=f(x,1). Otherwise, y=z+1. Then f(x,y)2=f(x,z+1)2=x2f(x,z)xf(x,z+1)=xf(x,y)=f(x,y+1). The inequality 2f(x,z)f(x,z+1) is derived previously.

  5. 5.

    If y=0, then f(x,0)f(x,0)=xx=f(x,1)f(x,2). Otherwise, y=z+1. Then f(x,y)f(x,y)=f(x,z+1)f(x,z+1)=xf(x,z)f(x,z+1)xf(x,z+1)2=xf(x,z+2)=f(x,z+3)=f(x,y+2).

From the last three statements, the next three proofs can be easily settled, fisrt, let t=max{y,z}. Then

  1. 6.

    f(x,y)+f(x,z)2f(x,t)f(x,t+1).

  2. 7.

    f(x,y)f(x,z)=f(x,t)2f(x,t+1).

  3. 8.

    f(x,y)f(x,z)f(x,t)f(x,t)f(x,t+2).

  4. 9.

    Induct on z. If z=0, then f(f(x,y),0)=f(x,y). Next, assume f(f(x,y),z)f(x,y+2z). Then f(f(x,y),z+1)=f(x,y)f(f(x,y),z)=f(x,y)f(x,y+2z)f(x,y+1)f(x,y+2z)xf(x,y)f(x,y+2z)xf(x,y+2z+1)=f(x,y+2z+2).

  5. 10.

    Induct on y. The case when y=0 is obvious. Next, if y<f(x,y), then y+1<f(x,y)+1<f(x,y)+f(x,0)f(x,y+1).

Concerning the recursiveness of f, here is another basic property of f:

Proposition 2.

f is primitive recursive.

Proof.

Since f(m,0)=m=p11(m) and f(m,n+1)=exp(m,f(m,n))=g(m,n,f(m,n)), where g(x,y,z)=exp(p13(x,y,z),p33(x,y,z)), are defined by primitive recursion via functions p11 and g, and since the projection functions pij, the exponential functionDlmfDlmfMathworld exp, and consequently g, are primitive recursive (g obtained by composition), we see that f is primitive recursive.∎

Remark. Another recursive property of f is that f is not elementary recursive. The proof uses the properties listed above. It is a bit lengthy, and is done in the link below.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 15:22:20