Mayoración

Una función f (de orden 1) mayor a una g (de orden n) si y solo si:

$f(max(x_1,x_2,..,x_n))\ge g(x_1,x_2,..,x_n)$

Notación: $f^{(1)}\to g^{(n)}$

Teoremas referidos a la mayoración

• Toda función recursiva primitiva está mayorada por la función de Ackermann.
  • Recordemos las propiedades de la función de Ackermann:
    • $Seak\in \mathbb{N},f_k\in FRP$ (1)
    • $Seaa>b,f_k(a)>f_k(b)$ (2)
    • $Seax,k\in \mathbb{N},f_k(x)>x$ (3)
    • $Seak\in \mathbb{N},f_{k+1}(x)>f_k(x)$ (4)

Lemas

Lema (A)

Las funciones recursivas base está mayoradas por $f_0$ Sea $X=x_1,x_2,..,x_n$

Demostración:

• $f_0(x)=s(x)\ge s(x)$
• $f_0(x)=s(x)\ge 0=z(x)$
• $f_0(Max(X))=s(Max(X))\ge x_j=p_j^{(n)}(X)$

Lema (B)

Si $f_k\to I^{(n)}y{f}_k\to h_i^{(m)}coni=1..m(2)$ entonces $f_{k+1}\to \varphi (I^{(n)},h_1^{(m)},h_2^{(m)},...,h_m^{(m)})$

Demostración:

Si $f_k\to h_i^{(m)}coni=1..m$ entonces $Max(h_1(X),h_2(X),..,h_n(X))\le f_k(Max(X))$

Entonces, $\varphi (I,h_1,h_2,...,h_m)(X)=I(h_1(X),h_2(X),...,h_m(X))$

Usando la hipótesis y $f^k$ es creciente (2).

$f_k(Max(h_1(X),h_2(X),..,h_n(X)))\le f_k(f_k(Max(X)))$

Por definición de función potencia:

$f_k(f_k(Max(X)))=f_k^2(Max(X))$

Aplicando (4) varias veces ...

$f_k^2(Max(X))\le f_k^{(2+1)}(Max(X))\le ..\le f_k^{(2+Max(X))}(Max(X))$

Por definición:

$f_k^{(2+Max(X))}(Max(X))=f_{k+1}(Max(X))$

Por lo tanto, $f_{k+1}\to \varphi (I^{(n)},h_1^{(m)},h_2^{(m)},...,h_m^{(m)})$

Plantilla:Control de autoridades