Grzegorczyk hierarchy

Properties

These sets clearly form the hierarchy

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

because they are closures over the ${\displaystyle B_n}$'s and ${\displaystyle B_0\subseteq B_1\subseteq B_2\subseteq \cdots }$.

They are strict subsets. In other words

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

because the hyperoperation ${\displaystyle H_n}$ is in ${\displaystyle {\mathcal{E}}^n}$ but not in ${\displaystyle {\mathcal{E}}^{n-1}}$.

• ${\displaystyle {\mathcal{E}}^0}$ includes functions such as x+1, x+2, ...
  • Every unary function f(x) in ${\displaystyle {\mathcal{E}}^0}$ is upper bounded by some x+n. However, ${\displaystyle {\mathcal{E}}^0}$ also includes more complicated functions like x∸1, x∸y (where ∸ is the monus sign defined as x∸y = max(x-y, 0)), x mod y, etc.
• ${\displaystyle {\mathcal{E}}^1}$ provides all addition functions, such as x+y, 4x, ...
• ${\displaystyle {\mathcal{E}}^2}$ provides all multiplication functions, such as xy, x⁴
• ${\displaystyle {\mathcal{E}}^3}$ provides all exponentiation functions, such as x^y, 2^22x, and is exactly the elementary recursive functions.
• ${\displaystyle {\mathcal{E}}^4}$ provides all tetration functions, and so on.

Notably, both the function ${\displaystyle U}$ and the characteristic function of the predicate ${\displaystyle T}$ from the Kleene normal form theorem are definable in a way such that they lie at level ${\displaystyle {\mathcal{E}}^0}$ of the Grzegorczyk hierarchy. This implies in particular that every recursively enumerable set is enumerable by some ${\displaystyle {\mathcal{E}}^0}$-function.

Relation to primitive recursive functions

The definition of ${\displaystyle {\mathcal{E}}^n}$ is the same as that of the primitive recursive functions, PR, except that recursion is limited (${\displaystyle f(t,\overline{u})\le j(t,\overline{u})}$ for some j in ${\displaystyle {\mathcal{E}}^n}$) and the functions ${\displaystyle (E_k{)}_{k<n}}$ are explicitly included in ${\displaystyle {\mathcal{E}}^n}$. Thus the Grzegorczyk hierarchy can be seen as a way to limit the power of primitive recursion to different levels.

It is clear from this fact that all functions in any level of the Grzegorczyk hierarchy are primitive recursive functions (i.e. ${\displaystyle {\mathcal{E}}^n\subseteq \mathsf{P}\mathsf{R}}$) and thus:

${\displaystyle \bigcup _n{\mathcal{E}}^n\subseteq \mathsf{P}\mathsf{R}}$

It can also be shown that all primitive recursive functions are in some level of the hierarchy, thus

${\displaystyle \bigcup _n{\mathcal{E}}^n=\mathsf{P}\mathsf{R}}$

and the sets ${\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 }$ partition the set of primitive recursive functions, PR.

Meyer and Ritchie introduced another hierarchy subdividing the primitive recursive functions, based on the nesting depth of loops needed to write a LOOP program that computes the function. For a natural number ${\displaystyle i}$, let ${\displaystyle {\mathcal{L}}_i}$ denote the set of functions computable by a LOOP program with LOOP and END commands nested no deeper than ${\displaystyle i}$ levels. Fachini and Maggiolo-Schettini showed that ${\displaystyle {\mathcal{L}}_i}$ coincides with ${\displaystyle {\mathcal{E}}_{i+1}}$ for all integers ${\displaystyle i>1}$.^p.63

Extensions

The Grzegorczyk hierarchy can be extended to transfinite ordinals. Such extensions define a fast-growing hierarchy. To do this, the generating functions ${\displaystyle E_{\alpha }}$ must be recursively defined for limit ordinals (note they have already been recursively defined for successor ordinals by the relation ${\displaystyle E_{\alpha +1}(n)=E_{\alpha }^n(2)}$). If there is a standard way of defining a fundamental sequence ${\displaystyle {\lambda }_m}$, whose limit ordinal is ${\displaystyle \lambda }$, then the generating functions can be defined ${\displaystyle E_{\lambda }(n)=E_{{\lambda }_n}(n)}$. However, this definition depends upon a standard way of defining the fundamental sequence. Rose (1984) suggests a standard way for all ordinals α < ε₀.

The original extension was due to Martin Löb and Stan S. Wainer and is sometimes called the Löb–Wainer hierarchy.