title: Mayoración
text: # Mayoración
  
  Una función f (de orden 1) mayor a una g (de orden n) si y solo si:
  
  $f(max(x_{1},x_{2},..,x_{n}))\geq 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_{0}$ Sea $X=x_{1},x_{2},..,x_{n}$
  
  Demostración:
  
  * $f_{0}(x)=s(x)\geq s(x)$
  * $f_{0}(x)=s(x)\geq 0=z(x)$
  * $f_{0}(Max(X))=s(Max(X))\geq x_{j}=p_{j}^{(n)}(X)$
  
  **Lema (B)**
  
  Si $f_{k}\to I^{(n)}\;y\;f_{k}\to h_{i}^{(m)}\;con\;i\;=\;1..m(2)$ entonces $f_{k+1}\to \phi \ (I^{(n)},h_{1}^{(m)},h_{2}^{(m)},...,h_{m}^{(m)})$
  
  Demostración:
  
  Si $f_{k}\to h_{i}^{(m)}\;con\;i\;=1..m$ entonces $Max(h_{1}(X),h_{2}(X),..,h_{n}(X))\leq 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)))\leq f_{k}(f_{k}(Max(X)))$
  
  Por definición de función potencia:
  
  $f_{k}(f_{k}(Max(X)))=f_{k}^{2}(Max(X))$
  
  Aplicando (4) varias veces ...
  
  $f_{k}^{2}(Max(X))\leq f_{k}^{(2+1)}(Max(X))\leq ..\leq f_{k}^{(2+Max(X))}(Max(X))$
  
  Por definición:
  
  $f_{k}^{(2+Max(X))}(Max(X))=f_{k+1}(Max(X))$
  
  Por lo tanto, $f_{k+1}\to \phi \ (I^{(n)},h_{1}^{(m)},h_{2}^{(m)},...,h_{m}^{(m)})$
  
  * Datos: Q6007705
  