Croissance de la fonction d'Ackermann

La seconde ligne du texte fait de $x \mapsto A_x$ une définition par récurrence dans l'ensemble des applications de $\mathbb N$ dans $\mathbb N$, à laquelle s'applique encore le théorème de définition par récurrence.

(i) Par récurrence sur $x$. Pour $x = 0$, $y + 1 > y$. Supposons (i) vrai pour $x$, et montrons $A(x + 1, y) > y$ par récurrence sur $y$. On a $A(x + 1, 0) = A(x, 1) > 1 > 0$. Si $A(x + 1, y) > y$, c'est-à-dire $A(x + 1, y) \geqslant y + 1$, alors $$\begin{aligned} A(x + 1, y + 1) &= A\big(x, A(x + 1, y)\big) \\ &> A(x + 1, y) \geqslant y + 1. \end{aligned}$$

(ii) Pour $x = 0$, c'est clair. Sinon, $A(x + 1, y + 1) = A(x, A(x + 1, y)) > A(x + 1, y)$ par (i).

(iii) Par récurrence sur $y$. Pour $y = 0$, il y a égalité. Si $A(x + 1, y) \geqslant A(x, y + 1)$, alors $A(x + 1, y) > y + 1$ par (i), donc $A(x + 1, y) \geqslant y + 2$, et par (ii) $$\begin{aligned} A(x + 1, y + 1) &= A\big(x, A(x + 1, y)\big) \\ &\geqslant A(x, y + 2). \end{aligned}$$ La seconde inégalité suit : $A(x + 1, y) \geqslant A(x, y + 1) > A(x, y)$.

(iv) $A(1, 0) = A(0, 1) = 2$ et $A(1, y + 1) = A(1, y) + 1$. Puis $A(2, 0) = A(1, 1) = 3$ et $A(2, y + 1) = A(2, y) + 2$. Enfin $A(3, 0) = A(2, 1) = 5 = 2^3 - 3$ et $$A(3, y + 1) = 2A(3, y) + 3 = 2^{y+4} - 3.$$

(v) Par la croissance en chaque variable, (ii) et (iii), puis par (iii) appliqué à $A(k + 1, y)$ et la définition, et enfin par (iii) : $$\begin{aligned} A\big(x, A(x', y)\big) &\leqslant A\big(k, A(k, y)\big) \\ &< A\big(k, A(k + 1, y)\big) \\ &= A(k + 1, y + 1) \\ &\leqslant A(k + 2, y). \end{aligned}$$