Grzegorczyk hierarchy

From Wikipedia, the free encyclopedia
Jump to: navigation, search

The Grzegorczyk hierarchy (pronounced: [ɡʐɛˈɡɔrt͡ʂɨk]), named after the Polish logician Andrzej Grzegorczyk, is a hierarchy of functions used in computability theory (Wagner and Wechsung 1986:43). Every function in the Grzegorczyk hierarchy is a primitive recursive function, and every primitive recursive function appears in the hierarchy at some level. The hierarchy deals with the rate at which the values of the functions grow; intuitively, functions in lower level of the hierarchy grow slower than functions in the higher levels.

Definition[edit]

First we introduce an infinite set of functions, denoted Ei for some natural number i. We define E_0(x,y)=x+y and E_1(x)=x^2+2. I.e., E0 is the addition function, and E1 is a unary function which squares its argument and adds two. Then, for each n greater than 1, we define E_n(x)=E^{x}_{n-1}(2).

From these functions we define the Grzegorczyk hierarchy. \mathcal{E}^n, the n-th set in the hierarchy, contains the following functions:

  1. Ek 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, \dots, t_m) = t_i );
  5. the (generalized) compositions of functions in the set (if h, g1, g2, ... and gm are in \mathcal{E}^n, then  f(\bar{u}) = h(g_1(\bar{u}), g_2(\bar{u}), \dots, g_m(\bar{u})) is as well)[note 1]; and
  6. the results of limited (primitive) recursion applied to functions in the set, (if g, h and j are in \mathcal{E}^n and f(t, \bar{u}) \leq j(t, \bar{u}) for all t and \bar{u}, and further f(0, \bar{u}) = g(\bar{u}) and f(t+1, \bar{u}) = h(t,\bar{u},f(t,\bar{u})), then f is in \mathcal{E}^n as well)[note 1]

In other words, \mathcal{E}^n is the closure of set B_n = \{Z, S, (p_i^m)_{i \le m}, E_k : k < n\} with respect to function composition and limited recursion (as defined above).

Properties[edit]

These sets clearly form the hierarchy

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

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

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

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

because the hyper operation H_n is in \mathcal{E}^n but not in \mathcal{E}^{n-1}.

  • \mathcal{E}^0 includes functions such as x+1, x+2, ...
  • \mathcal{E}^1 provides all addition functions, such as x+y, 4x, ...
  • \mathcal{E}^2 provides all multiplication functions, such as xy, x4
  • \mathcal{E}^3 provides all exponentiation functions, such as xy, 222x, and is exactly the elementary recursive functions.
  • \mathcal{E}^4 provides all tetration functions, and so on.

Relation to primitive recursive functions[edit]

The definition of \mathcal{E}^n is the same as that of the primitive recursive functions, RP, except that recursion is limited (f(t, \bar{u}) \leq j(t, \bar{u}) for some j in \mathcal{E}^n) and the functions (E_k)_{k<n} are explicitly included in \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.  \mathcal{E}^n \subseteq RP ) and thus:

 \bigcup_n{\mathcal{E}^n} \subseteq RP

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

 \bigcup_n{\mathcal{E}^n} = RP

and the sets  \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, RP.

Extensions[edit]

The Grzegorczyk hierarchy can be extended to transfinite ordinals. Such extensions define a fast-growing hierarchy. To do this, the generating functions E_\alpha must be recursively defined for limit ordinals (note they have already been recursively defined for successor ordinals by the relation  E_{\alpha+1}(n) = E_\alpha^n(2) ). If there is a standard way of defining a fundamental sequence \lambda_m, whose limit ordinal is \lambda, then the generating functions can be defined  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 α < ε0.

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

Notes[edit]

  1. ^ a b Note: here \bar{u} represents a tuple of inputs to f. The notation f(\bar{u}) means that f takes some arbitrary number of arguments and if \bar{u} = (x, y, z), then f(\bar{u}) = f(x, y, z). In the notation f(t, \bar{u}), the first argument, t, is specified explicitly and the rest as the arbitrary tuple \bar{u}. Thus, if \bar{u} = (x, y, z), then f(t, \bar{u}) = f(t, x, y, z). This notation allows composition and limited recursion to be defined for functions, f, of any number of arguments.

References[edit]