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:
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,