グジェゴルチク階層

まず自然数 i で添字付けられた関数族 E_i を導入する。まず次のように定義する：

${\displaystyle E_{0}(x,y)=x+y}$

${\displaystyle E_{1}(x)=x^{2}+2}$

${\displaystyle E_{n}(x)=E_{n-1}^{x}(2)}$ （ただし n > 1）

これらの関数からグジェゴルチク階層を定義する。${\displaystyle {\mathcal {E}}^{n}}$ は n番目の階層であり、次の関数からなる：

1. E_k （ただし k < n）
2. ゼロ関数 (Z(x) = 0);
3. 後者関数 (S(x) = x + 1);
4. 射影関数 (${\displaystyle p_{i}^{m}(t_{1},t_{2},\dots ,t_{m})=t_{i}}$);
5. （一般）合成関数 （もし h, g₁, g₂, ... と g_m が${\displaystyle {\mathcal {E}}^{n}}$ に属すならば ${\displaystyle f({\bar {u}})=h(g_{1}({\bar {u}}),g_{2}({\bar {u}}),\dots ,g_{m}({\bar {u}}))}$ も同様）^{[note 1]}; および
6. 限定（原始）再帰 （もし g, h と j が ${\displaystyle {\mathcal {E}}^{n}}$ に属し ${\displaystyle f(t,{\bar {u}})\leq j(t,{\bar {u}})}$, ${\displaystyle f(0,{\bar {u}})=g({\bar {u}})}$, ${\displaystyle f(t+1,{\bar {u}})=h(t,{\bar {u}},f(t,{\bar {u}}))}$ ならば、 f もまた ${\displaystyle {\mathcal {E}}^{n}}$ に属す)^{[note 1]}

換言すれば ${\displaystyle {\mathcal {E}}^{n}}$ は ${\displaystyle B_{n}=\{Z,S,(p_{i}^{m})_{i\leq m},E_{k}:k<n\}}$ を含み関数合成と限定原始再帰で閉じた最小の集合（閉包）である。

これらの集合は明らかに階層を成す。

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

実際これらは ${\displaystyle B_{n}}$ の閉包であって ${\displaystyle B_{0}\subseteq B_{1}\subseteq B_{2}\subseteq \cdots }$ となっているからである。

これらは強い意味での包含関係が成り立つ（Rose 1984; Gakwaya 1997）。換言すれば

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

というのも、ハイパー演算子 ${\displaystyle H_{n}}$ は ${\displaystyle {\mathcal {E}}^{n}}$ に属すが ${\displaystyle {\mathcal {E}}^{n-1}}$ には属さないからである。

• ${\displaystyle {\mathcal {E}}^{0}}$ は次を含む： x+1, x+2, ...
• ${\displaystyle {\mathcal {E}}^{1}}$ は全ての加法関数を備える： x+y, 4x, ...
• ${\displaystyle {\mathcal {E}}^{2}}$ は全ての乗法関数を備える： xy, x⁴, ...
• ${\displaystyle {\mathcal {E}}^{3}}$ は全ての指数関数を備える： x^y, 2^22x さらにこの階層は初等帰納的関数のクラスや反復指数時間で計算可能な関数のクラスなどと一致する
• ${\displaystyle {\mathcal {E}}^{4}}$ は全てのテトレーション関数を備える。

${\displaystyle {\mathcal {E}}^{n}}$ の定義は再帰が限定 （ある j ${\displaystyle \in {\mathcal {E}}^{n}}$ に対して ${\displaystyle f(t,{\bar {u}})\leq j(t,{\bar {u}})}$）されていることと、${\displaystyle (E_{k})_{k<n}}$ が明示的に導入されることを除けば 原始帰納的関数のクラス PR の定義に似ている。グジェゴルチク階層は原始再帰の強さを制限しているものと見ることができる。

この事実からグジェゴルチク階層に属す全ての関数は原始帰納的関数であること（すなわち ${\displaystyle {\mathcal {E}}^{n}\subseteq PR}$）が示される。したがって

${\displaystyle \bigcup _{n}{{\mathcal {E}}^{n}}\subseteq PR}$

さらに全ての原始帰納的関数が何れかの階層に属すことも示される（Rose 1984; Gakwaya 1997）。つまり

${\displaystyle \bigcup _{n}{{\mathcal {E}}^{n}}=PR}$

また ${\displaystyle {\mathcal {E}}^{0},{\mathcal {E}}^{1}-{\mathcal {E}}^{0},{\mathcal {E}}^{2}-{\mathcal {E}}^{1},\dots ,{\mathcal {E}}^{n}-{\mathcal {E}}^{n-1},\dots }$ は原始帰納的関数のクラス PR の分割となっている。さらに各々の領域は潰れていない。

グジェゴルチク階層は超限順序数に一般化できる。そのような拡張として急成長階層が定義される。それには、極限順序数に対する生成関数 ${\displaystyle E_{\alpha }}$ を帰納的に定義しなければならない（後続型順序数に対しては ${\displaystyle E_{\alpha +1}(n)=E_{\alpha }^{n}(2)}$ とすればよい。) もし極限順序数 ${\displaystyle \lambda }$ の基本列 ${\displaystyle \lambda _{m}}$ を作る一般的な方法があれば、 生成関数は ${\displaystyle E_{\lambda }(n)=E_{\lambda _{n}}(n)}$ と定義できる。ところがこの定義は基本列を作る方法に依存する。Rose（1984）は任意の順序数 α < ε₀ に対する基本列の一般的な構成法を提案した。

独自の拡張としては Martin Löb と Stan S. Wainer（1970）による Löb–Wainer 階層がある。