Mayoración

Una función f (de orden 1) mayora a una g (de orden n) si y sólo si:

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

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

Lemas

Lema (A)

Las funciones recursivas base está mayoradas por f₀ Sea X = x₁,x₂,..,x_n

Demostración:

• $f_{0}(x) = s(x) \ge s(x)$
• $f_{0}(x) = s(x) \ge 0 = z(x)$
• $f_{0}(Max(X)) = s(Max(X)) \ge x_{j} = p^{(n)}_{j}(X)$

Lema (B)

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

Demostración:

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

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

Usando la hipótesis y f^k es creciente (2).

$f_{k}(Max(h_{1}(X),h_{2}(X), .. , h_{n}(X))) \le f_{k}(f_{k}(Max(X)))$

Por definición de función potencia:

$f_{k}(f_{k}(Max(X))) = f^2_{k}(Max(X))$

Aplicando (4) varias veces ...

$f^2_{k}(Max(X)) \le f^{(2+1)}_{k}(Max(X)) \le .. \le f^{(2+Max(X))}_{k}(Max(X))$

Por definición:

$f^{(2+Max(X))}_{k}(Max(X)) = f_{k+1}(Max(X))$

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