Hiérarchie de Grzegorczyk

Tout d'abord on introduit un ensemble infini de fonctions notées ${\displaystyle E_{i}}$ pour tout entier naturel ${\displaystyle i}$.

On pose ${\displaystyle E_{0}:(x,y)\mapsto x+y}$ et ${\displaystyle E_{1}:x\mapsto x^{2}+2}$. En d'autre terme, ${\displaystyle E_{0}}$ est la fonction d'addition et ${\displaystyle E_{1}}$ est une fonction unaire qui élève au carré son argument et ajoute ${\displaystyle 2}$.

Ensuite, pour tout entier ${\displaystyle n\geqslant 2}$, on définit

${\displaystyle E_{n}:x\mapsto {\begin{cases}2&{\text{si }}x=0\\E_{n-1}(E_{n}(x-1))&{\text{sinon}}\end{cases}}}$

On peut alors définir la hiérarchie de Grzegorczyk. ${\displaystyle {\mathcal {E}}^{n}}$, la n-ième classe (ou niveau) de la hiérarchie de Grzegorczyk est le plus petit ensemble qui contient

1. ${\displaystyle E_{k}}$ pour ${\displaystyle k<n}$,
2. la fonction nulle,
3. la fonction successeur (${\displaystyle S(x)=x+1}$),
4. les projections (${\displaystyle p_{i}^{m}(t_{1},t_{2},\ldots ,t_{m})=t_{i}}$),

et stable par

1. composition de fonction (si ${\displaystyle f}$, ${\displaystyle g_{1}}$, ${\displaystyle g_{2}}$,... ,${\displaystyle g_{m}}$ sont des fonctions de ${\displaystyle {\mathcal {E}}^{n}}$, alors ${\displaystyle f({\bar {u}})=h(g_{1}({\bar {u}}),g_{2}({\bar {u}}),\dots ,g_{m}({\bar {u}}))}$ l'est aussi),
2. récursion bornée, (si ${\displaystyle g}$, ${\displaystyle h}$ et ${\displaystyle j}$ sont des fonctions de ${\displaystyle {\mathcal {E}}^{n}}$ et que ${\displaystyle f}$ est telle que ${\displaystyle \forall t,\forall {\bar {u}},f(t,{\bar {u}})\leqslant j(t,{\bar {u}})}$, ${\displaystyle f(0,{\bar {u}})=g({\bar {u}})}$ et ${\displaystyle f(t+1,{\bar {u}})=h(t,{\bar {u}},f(t,{\bar {u}}))}$, alors ${\displaystyle f}$ est aussi une fonction de ${\displaystyle {\mathcal {E}}^{n}}$).

On a

${\displaystyle {\mathcal {E}}^{0}\subseteq {\mathcal {E}}^{1}\subseteq {\mathcal {E}}^{2}\subseteq \cdots }$

puisque ${\displaystyle \{E_{k}\mid k<0\}\subseteq \{E_{k}\mid k<1\}\subseteq \{E_{k}\mid k<2\}\subseteq \cdots }$.

En fait, l'inclusion est stricte (Rose 1984; Gakwaya 1997)

${\displaystyle {\mathcal {E}}^{0}\subsetneq {\mathcal {E}}^{1}\subsetneq {\mathcal {E}}^{2}\subsetneq \cdots }$

parce que l'hyperopération ${\displaystyle H_{n}}$ appartient à ${\displaystyle {\mathcal {E}}^{n}}$ mais pas à ${\displaystyle {\mathcal {E}}^{n-1}}$.

• ${\displaystyle {\mathcal {E}}^{0}}$ contient des fonctions comme ${\displaystyle x\mapsto x}$, ${\displaystyle x\mapsto x+1}$, ${\displaystyle x\mapsto x+2}$,
• ${\displaystyle {\mathcal {E}}^{1}}$ contient toutes les fonctions d'addition telles que ${\displaystyle x\mapsto 4x}$, ${\displaystyle (x,y)\mapsto x+y}$,
• ${\displaystyle {\mathcal {E}}^{2}}$ contient les fonctions de multiplication, telles que ${\displaystyle (x,y)\mapsto xy}$, ${\displaystyle x\mapsto x^{4}}$ ,
• ${\displaystyle {\mathcal {E}}^{3}}$ contient les fonctions exponentiation, comme ${\displaystyle (x,y)\mapsto x^{y}}$, ${\displaystyle x\mapsto 2^{2^{2^{x}}}}$. Cet ensemble est égal à celui des fonctions élémentaires,
• ${\displaystyle {\mathcal {E}}^{4}}$ contient la tétration.