Una función f (de orden 1) mayor a una g (de orden n) si y solo si:
Notación:
Teoremas referidos a la mayoración[editar]
- Toda función recursiva primitiva está mayorada por la función de Ackermann.
- Recordemos las propiedades de la función de Ackermann:
(1)
(2)
(3)
(4)
Las funciones recursivas base está mayoradas por
Sea
Demostración:
![{\displaystyle f_{0}(x)=s(x)\geq s(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6a8702d369f88370ec9d426a28f1aef5f13a6d3c)
![{\displaystyle f_{0}(x)=s(x)\geq 0=z(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/db488336d35fc54acbe3b8b4232212e83fdde9f4)
![{\displaystyle f_{0}(Max(X))=s(Max(X))\geq x_{j}=p_{j}^{(n)}(X)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/50db96c9af8fd171dbbc404613edc4bb9c457eb7)
Si
entonces
Demostración:
Si
entonces
Entonces,
Usando la hipótesis y
es creciente (2).
Por definición de función potencia:
Aplicando (4) varias veces ...
Por definición:
Por lo tanto,