Grzegorczyk Hierarchy - Definition

Definition

First we introduce an infinite set of functions, denoted E_i for some natural number i. We define and . I.e., E₀ is the addition function, and E₁ is a unary function which squares its argument and adds two. Then, for each n greater than 1, we define .

From these functions we define the Grzegorczyk hierarchy., the n-th set in the hierarchy, contains the following functions:

1. E_k for k < n
2. the zero function (Z(x) = 0);
3. the successor function (S(x) = x + 1);
4. the projection functions ;
5. the (generalized) compositions of functions in the set (if h, g₁, g₂, ... and g_m are in, then is as well); and
6. the results of limited (primitive) recursion applied to functions in the set, (if g, h and j are in and for all t and, and further and, then f is in as well)

In other words, is the closure of set with respect to function composition and limited recursion (as defined above).