Grzegorczyk hierarchy

Definition

First we introduce an infinite set of functions, denoted E_i for some natural number i. We define E 0 ( x , y ) = x + y and E 1 ( x ) = x 2 + 2 . 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 E n ( x ) = E n − 1 x ( 2 ) , i.e. the x-th iterate of E n − 1 evaluated at 2.

From these functions we define the Grzegorczyk hierarchy. E n , 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 ( p i m ( t 1 , t 2 , … , t m ) = t i );
5. the (generalized) compositions of functions in the set (if h, g₁, g₂, ... and g_m are in E n , then f ( u ¯ ) = h ( g 1 ( u ¯ ) , g 2 ( u ¯ ) , … , g m ( u ¯ ) ) is as well); and
6. the results of limited (primitive) recursion applied to functions in the set, (if g, h and j are in E n and f ( t , u ¯ ) ≤ j ( t , u ¯ ) for all t and u ¯ , and further f ( 0 , u ¯ ) = g ( u ¯ ) and f ( t + 1 , u ¯ ) = h ( t , u ¯ , f ( t , u ¯ ) ) , then f is in E n as well)

In other words, E n is the closure of set B n = { Z , S , ( p i m ) i ≤ m , E k : k < n } with respect to function composition and limited recursion (as defined above).

Properties

These sets clearly form the hierarchy

because they are closures over the B n 's and B 0 ⊆ B 1 ⊆ B 2 ⊆ ⋯ .

They are strict subsets (Rose 1984; Gakwaya 1997). In other words

because the hyper operation H n is in E n but not in E n − 1 .

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

Relation to primitive recursive functions

The definition of E n is the same as that of the primitive recursive functions, PR, except that recursion is limited ( f ( t , u ¯ ) ≤ j ( t , u ¯ ) for some j in E n ) and the functions ( E k ) k < n are explicitly included in 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. E n ⊆ P R ) and thus:

It can also be shown that all primitive recursive functions are in some level of the hierarchy (Rose 1984; Gakwaya 1997), thus

and the sets E 0 , E 1 − E 0 , E 2 − E 1 , … , E n − E n − 1 , … partition the set of primitive recursive functions, PR.

Extensions

The Grzegorczyk hierarchy can be extended to transfinite ordinals. Such extensions define a fast-growing hierarchy. To do this, the generating functions E α must be recursively defined for limit ordinals (note they have already been recursively defined for successor ordinals by the relation E α + 1 ( n ) = E α n ( 2 ) ). If there is a standard way of defining a fundamental sequence λ m , whose limit ordinal is λ , then the generating functions can be defined E λ ( n ) = E λ 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 (1970) and is sometimes called the Löb–Wainer hierarchy.