Mayoración

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

${\displaystyle f(max(x_{1},x_{2},..,x_{n}))\geq g(x_{1},x_{2},..,x_{n})}$

Notación: ${\displaystyle 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:
    • ${\displaystyle Sea\;k\in \mathbb {N} ,\;f_{k}\in FRP}$ (1)
    • ${\displaystyle Sea\;a>b,\;f_{k}(a)>f_{k}(b)}$ (2)
    • ${\displaystyle Sea\;x,k\in \mathbb {N} ,\;f_{k}(x)>x}$ (3)
    • ${\displaystyle Sea\;k\in \mathbb {N} ,\;f_{k+1}(x)>f_{k}(x)}$ (4)

Lemas

Lema (A)

Las funciones recursivas base está mayoradas por ${\displaystyle f_{0}}$ Sea ${\displaystyle X=x_{1},x_{2},..,x_{n}}$

Demostración:

• ${\displaystyle f_{0}(x)=s(x)\geq s(x)}$
• ${\displaystyle f_{0}(x)=s(x)\geq 0=z(x)}$
• ${\displaystyle f_{0}(Max(X))=s(Max(X))\geq x_{j}=p_{j}^{(n)}(X)}$

Lema (B)

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

Demostración:

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

Entonces, ${\displaystyle \phi \ (I,h_{1},h_{2},...,h_{m})(X)=I(h_{1}(X),h_{2}(X),...,h_{m}(X))}$

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

${\displaystyle 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:

${\displaystyle f_{k}(f_{k}(Max(X)))=f_{k}^{2}(Max(X))}$

Aplicando (4) varias veces ...

${\displaystyle f_{k}^{2}(Max(X))\leq f_{k}^{(2+1)}(Max(X))\leq ..\leq f_{k}^{(2+Max(X))}(Max(X))}$

Por definición:

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

Por lo tanto, ${\displaystyle f_{k+1}\to \phi \ (I^{(n)},h_{1}^{(m)},h_{2}^{(m)},...,h_{m}^{(m)})}$

• Datos: Q6007705