Mayoración

Una funció f (d'orde 1) major a una g (d'orde n) si i solament si:

$f(max(x_1,x_2,\mathrm{..},x_n))\ge g(x_1,x_2,\mathrm{..},x_n)$

Notació: $f^{(1)}\to g^{(n)}$

Teoremes referides a la mayoración

• Tota funció recursiva primitiva està mayorada per la funció de Ackermann.
  • Recordem les propietats de la funció de Ackermann:
    • $Seak\in \mathbb{N},f_k\in FRP$ (1)
    • $Seaa>b,f_k(a)>f_k(b)$ (2)
    • $Seax,k\in \mathbb{N},f_k(x)>x$ (3)
    • $Seak\in \mathbb{N},f_{k+1}(x)>f_k(x)$ (4)

Lemes

Lema (A)

Les funcions recursivas base està mayoradas per $f_0$ Siga $X=x_1,x_2,\mathrm{..},x_n$

Demostració:

• $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_j^{(n)}(X)$

Lema (B)

Si $f_k\to I^{(n)}y{f}_k\to h_i^{(m)}coni=\mathrm{1..}m(2)$ llavors $f_{k+1}\to \varphi (I^{(n)},h_1^{(m)},h_2^{(m)},\mathrm{...},h_m^{(m)})$

Demostració:

Si $f_k\to h_i^{(m)}coni=\mathrm{1..}m$ llavors $Max(h_1(X),h_2(X),\mathrm{..},h_n(X))\le f_k(Max(X))$

Llavors, $\varphi (I,h_1,h_2,\mathrm{...},h_m)(X)=I(h_1(X),h_2(X),\mathrm{...},h_m(X))$

Usant l'hipòtesis i $f^k$ és creixent (2).

$f_k(Max(h_1(X),h_2(X),\mathrm{..},h_n(X)))\le f_k(f_k(Max(X)))$

Per definició de funció potencia:

$f_k(f_k(Max(X)))=f_k^2(Max(X))$

Aplicant (4) vàries voltes ...

$f_k^2(Max(X))\le f_k^{(2+1)}(Max(X))\le \mathrm{..}\le f_k^{(2+Max(X))}(Max(X))$

Per definició:

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

Per lo tant, $f_{k+1}\to \varphi (I^{(n)},h_1^{(m)},h_2^{(m)},\mathrm{...},h_m^{(m)})$