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}))\geq 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:
    • $Sea\;k\in \mathbb {N} ,\;f_{k}\in FRP$ (1)
    • $Sea\;a>b,\;f_{k}(a)>f_{k}(b)$ (2)
    • $Sea\;x,k\in \mathbb {N} ,\;f_{k}(x)>x$ (3)
    • $Sea\;k\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)\geq s(x)$
• $f_{0}(x)=s(x)\geq 0=z(x)$
• $f_{0}(Max(X))=s(Max(X))\geq x_{j}=p_{j}^{(n)}(X)$

Lema (B)

Si $f_{k}\to I^{(n)}\;y\;f_{k}\to h_{i}^{(m)}\;con\;i\;=\;1..m(2)$ entonces $f_{k+1}\to \phi \ (I^{(n)},h_{1}^{(m)},h_{2}^{(m)},...,h_{m}^{(m)})$

Demostración:

Si $f_{k}\to h_{i}^{(m)}\;con\;i\;=1..m$ entonces $Max(h_{1}(X),h_{2}(X),..,h_{n}(X))\leq f_{k}(Max(X))$

Entonces, $\phi \ (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)))\leq 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))\leq f_{k}^{(2+1)}(Max(X))\leq ..\leq 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 \phi \ (I^{(n)},h_{1}^{(m)},h_{2}^{(m)},...,h_{m}^{(m)})$

• Datos: Q6007705