Mayoración

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

f ( m a x (

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

Las funciones recursivas base está mayoradas por

c o n

{\displaystyle f_{k}\to I^{(n)}\;y\;f_{k}\to h_{i}^{(m)}\;con\;i\;=\;1..m(2)}

c o n

{\displaystyle f_{k}\to h_{i}^{(m)}\;con\;i\;=1..m}

a x (

{\displaystyle Max(h_{1}(X),h_{2}(X),..,h_{n}(X))\leq f_{k}(Max(X))}

{\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

a x (

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

a x (

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

Aplicando (4) varias veces ...

a x (

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

a x (

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