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 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) Lemas Lema (A) Las funciones recursivas base está mayoradas por Sea
Demostración:
Lema (B) 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,
Categoría:Funciones